Midterm Exam

MATH 557, Mathematical Logic

Pennsylvania State University October 22, 2013

1. Use an unsigned tableau to show that

¬ ∃y (Sy ∧ ∀x (Exy ⇔ (Sx ∧ ¬ Exx)))

is logically valid.

2. Let I be the identity predicate, and let f be a unary operation. Exhibit a normal structure or structures to illustrate the following facts:

(a) ∀z ∃x Izfx is not a logical consequence of ∀x ∀y (Ifxfy ⇒ Ixy).

(b) ∀x P x is not a logical consequence of (the conjunction of) ∀x (P x ⇒ P fx), ∀x ∀y (Ifxfy ⇒ Ixy), ∃z (P z ∧ ¬ ∃x Izfx).

Try to use the simplest possible structures.

3. State König’s Lemma precisely. Define all of the concepts in the lemma in terms of very basic mathematical concepts such as finite sets, infinite sets, functions, binary relations, and the natural number system.

4. Define what is meant by a quasitautology. Letting A be the sentence ((∀x P x) ∧ (∀x Qx)) ⇒ ∃x (P x ∧ Qx), exhibit a companion sequence for A which has A as a quasitautological consequence.

5. In Chapter 3 we studied several proof systems for predicate calculus: LH , LH′, LG, LG^{+}, LG′, LG(atomic), LG(symmetric). Select one of these systems. For the system that you select:

(a) Define what are the objects of the system.

(b) List the axioms and rules of the system.

(c) Explain what is meant by a derivation or proof in the system, and what it means for an object of the system to be derivable or provable.

(d) Explain what it means for an object of the system to be logically valid.

(e) State the soundness and completeness theorems for the system.