Foundations of Mathematics (Mathematical Logic)

Graduate Course Department of Mathematics, University of Patras

June 20, 2006

Write 10 out of the following 12 points.

Answer one of the following two questions (4 points)

1. State the completeness theorem for predicate logic and sketch a proof by describing a necessary interpretation in detail (which are the underlying set and the interpretations of the symbols of the language). Explain in detail the conjunction and negation step in the inductive argument needed.

2. State and prove the lemma of Rasiowa - Sikorski on ultrafilters and explain how it is used in the proof of the completeness theorem for predicate logic.

Answer one of the following two questions (2 points)

3. Show that if F is a maximal proper filter of a Boolean algebra B, then for every element x in the algebra we have that either x ∈ F or ¬x ∈ F.

4. State and prove the completeness theorem for propositional logic.

Answer two out of the following three questions (6 points)

5. (a). In a language that contains only one binary predicate ≤ (which we think with its usual meaning) express the following properties: (i) there is no element (strictly) between x and y. (ii) x is the immediate successor of y. (iii) every pair of elements has an infimum.

(b) Explain why the following formula is a tautology

∀x(φ(x) → ψ) → (∃xφ(x) → ψ),

when the variable x does not occur freely in ψ. Give a counterexample for the case when the variable x occurs freely in ψ.

6. Consider a language L of predicate logic that contains a binary relation symbol P. Is it possible that a structure for L with finite underlying set satisfies simultaneously

σ_{1} = ∀x¬P (x, x),

σ_{2} = ∀x∀y∀z((P (x, y) ∧ P (y, z)) → P (x, z)),

σ_{3} = ∀x∃yP (x, y) ?

Show that the theory that consists of σ_{1}, σ_{2}, σ_{3} and the following

τ = ∀x_{1}...∀x_{n}∀x_{n+1}(x_{n+1} = x_{1} ∨ ... ∨ x_{n+1} = x_{n})

(n fixed) proves formally some contradiction φ ∧ ¬φ.

7. Let L be a language for predicate logic that has relation symbols and among them a unary one P, no function symbols and no constants symbols. Define the relativization σ^{P} of a formula σ with respect to P, inductively, as

σ^{P} = σ, when σ is atomic formula.

(σ♢τ)^{P} = σ^{P} ♢τ^{P}, when ♢ = ∧, ∨, →, ↔.

(¬σ)^{P} = ¬σ^{P}.

(∀xσ)^{P} = ∀x(P (x) → σ^{P}).

(∃xσ)^{P} = ∃x(P (x) ∧ σ^{P})

Consider a structure A for L. Consider also the structure B with universe P^{A} = {x ∈ |A| | A ⊧ P (x)} and having as relations the restrictions of the relations of A to P^{A}. Show that, for any sentence σ, A ⊧ σ if and only if B ⊧ σ.

Good Luck!