Intermediate Logic Final Exam

Use the definition of a deduction in FOL^-_C to explain why, if Γ is an infinite set of formulas of FOL^-_C and Φ is a formula of FOL^-_C such that Γ ⊢ Φ, then there is a finite subset ∆ of Γ such that ∆ ⊢ Φ. (Hint: there’s nothing special about the difference between deductions in SL and deductions in FOL^-_C needed to answer this question. This is actually quite an easy question!)

1. A deduction is a finite sequence of formulas

2. If Γ ⊢ Φ, then there exists a finite deduction ending with Φ where each sentence is either a premise in Γ, an axiom, or something derived from previous sentences in Γ.

3. Since the deduction has finite premises, the sentences in Γ that are in the deduction is also finite.

4. Let ∆ be those finite premises that appear in Γ and in the deduction.

5. The same deduction works using only the premises from ∆

6. Therefore ∆ ⊢ Φ and ∆ is finite.

Use clauses (i) - (iv) of our definition of v^s_M to prove that ⊨∀x₀F₀¹x₀ → ~∀x₀~F₀¹x₀

1. Assume v^s_M​(∀xF(x))=T

2. By clause (iii) v^s[x→d]_M(F(x)) = T

3. By clause (ii) v^s[x→d]_M(~F(x)) = F

4. By clause (iii) v^s_M(∀x~F(x)) = F

5. By clause (ii) v^s_M(~∀x~F(x)) = T

6. Since the antecedent is true, then ⊨∀x₀F₀¹x₀ → ~∀x₀~F₀¹x₀

Without using Lemma 4.1, state and prove the following: If Γ ⊢ Φ and Φ ⊨_SL Ψ, then Γ ⊢ Ψ. (Hint: Remember what ‘⊨_SL’ means? What does Φ ⊨_SL Ψ imply about the formula Φ → Ψ? How could Φ → Ψ then be used in a deduction?)

1. Assume Γ ⊢ Φ

2. ⊨_SLΦ → Ψ since Φ ⊨_SL Ψ means that every valuation that makes Φ true also makes Ψ true.

3. ⊢ Φ → Ψ since every sentential tautology is provable

4. Take the finite derivation of Φ from Γ, append Φ → Ψ, and apply MP to infer Ψ

5. Therefore Γ ⊢ Ψ

What are the axioms of FOL^-_C? What are the inference rules? Exhibit a deduction of the formula ~∀x~~Fx from the set Γ = {~∀xFx}. (Hint: The proof requires at least one instance of each axiom, and at least one application of each inference rule. It is easier if you use the derived rule SL in a few places too.)

Axioms:

(P1) A → (B → A)

(P2) (A → (B → C)) → ((A → B) → (A → C))

(P3) (~B → ~A) → (A → B)

(Q1) ∀xΦ(x) → Φ(t)

(Q2) ∀x(Φ → Ψ) → (Φ → ∀xΨ)

Inference Rules:

(MP) Modus Ponens: from A and A → B infer B

(Gen) Generalization from A infer ∀x A (x cannot be free)

1. ~∀xFx Premise from Γ

2. ∀x~~Fx → ~~F(c) From Q1

3. F(c) from double-negation elimination

4. ∀x~~Fx → F(c) from 2 and 3

5. ∀x(∀x~~Fx → F(x)) Gen 4

6. ∀x(∀x~~Fx → F(x)) → (∀x~~Fx → ∀xF(x)) From Q2

7. (∀x~~Fx → ∀xF(x)) MP 5, 6

8. (∀x~~Fx → ∀xF(x)) → (~∀xFx → ~∀x~~F(x)) Contraposition instance of the formulas

9. (~∀xFx → ~∀x~~F(x)) MP 7, 8

10. ~∀x~~F(x) MP 1, 9

Prove Lemma 4.4: For any set Γ of formulas of FOL^-_C, Γ is inconsistent if and only if Γ ⊢ P₀ Ʌ ~P₀.

Left to Right:

1. If Γ is inconsistent, then there is some formula Φ such that Γ ⊢ Φ and Γ ⊢ ~Φ

2. From Φ and ~Φ, we derive a contradiction.

3. From the contradiction, we can derive any formula, so Γ ⊢ P_{0 and} Γ ⊢ ~P₀

4. From those two, Γ ⊢ P₀ Ʌ ~P₀.

Right to Left:

1. From Γ ⊢ P₀ Ʌ ~P₀, we can derive Γ ⊢ P₀ and Γ ⊢ ~P₀

2. That means Γ proves both a formula and its negation.

3. By definition, that means Γ is inconsistent.

Prove Lemma 4.5: for every set Γ of sentences of FOL^-_C and for every formula Φ of FOL^-_C, if Γ is consistent, then either Γ U {Φ} or Γ U {~Φ} is consistent. (Hint: Look at the proof of Lemma 2.4 for inspiration. Note, however, that if you use Lemma 4.1 and 4.4, the proof of Lemma 4.5 is actually shorter and easier than the proof of Lemma 2.4 was!)

Proof by contradiction:

1. Suppose Γ is consistent but both Γ U {Φ} or Γ U {~Φ} are inconsistent.

2. By Lemma 4.4, Γ U {Φ} ⊢ P₀ Ʌ ~P₀ and Γ U {~Φ} ⊢ P₀ Ʌ ~P₀

3. By the Deduction Theorem Γ ⊢ Φ → (P₀ Ʌ ~P₀) and Γ ⊢ ~Φ → (P₀ Ʌ ~P₀)

4. If a sentence and its negation syntactically entail the same thing, then that antecedent is provable, so (P₀ Ʌ ~P₀) is provable.

5. But by Lemma 4.4, Γ ⊢ P₀ Ʌ ~P₀ implies Γ is inconsistent, so there is a contradiction

6. Therefore it cannot be that both Γ U {Φ} and Γ U {~Φ} are inconsistent. So at least one of them must be consistent.

What does it mean to say that a set of sentences of FOL^-_C is “maximal” (see property (3) or Lemma 4.6)? What does it mean to say that a set Γ of sentences of FOL^-_C is consistent (see property (3) of Lemma 4.6)? What does it mean to say that a set of FOL^-_C is Henkin? Suppose Γ is a consistent set of sentences of FOL^-_C. Explain the technique used in the proof of Lemma 4.6 to construct a maximal consistent Henkin set Γ* that contains Γ as a subset.

A set of sentences Γ is maximal if

• Γ is consistent

• You cannot add any new sentence without making it inconsistent

A set of sentences Γ is consistent if it does not prove a contradiction.

A set Γ of sentences if Henkin if:

• For every formula ∃xΦ(x) in the language Γ contains a corresponding witness constant “c” s.t. ∃xΦ(x) → Φ(c) is in Γ.

Construction:

• Add witnesses for all existential formulas

• Add it to every sentence as long as it doesn’t break consistsency

• This produces a maximal, consistent, Henkin set containing the original Γ

Prove that if Γ is a set of sentences of FOL^-_C such that Γ ⊨ F¹₀x₀, then Γ ⊨ ∀x₀F¹₀x₀. (Hint: the fact that Γ is a set of sentences is actually quite important! Hint #2: this is essentially a simpler version of Lemma 4.9; look at the proof of that lemma for guidance.)

1. Let M be a model in which all sentences in Γ are true.

2. Because Γ consists only of sentences, their truth does not depend on the assignment of variables. So for every assignment s, (M, s) satisfies Γ.

3. Since Γ ⊨ F(x₀), for every assignment s, if (M, s) satisfies Γ, then (M, s) satisfies F(x₀).

4. ∀x₀F(x₀) is true in M iff F(x₀) is true under every assignment

5. Therefore ∀x₀F(x₀) is true in M

6. Γ ⊨ ∀x₀F(x₀) is true in M since M was arbitrary

State (but don’t prove) Lemma 4.1, Lemma 4.4, Theorem 4.8, and Lemma 4.9. Then state and prove Theorem 4.10, the Completeness Theorem for FOL^-.

Lemma 4.1 (Deduction Theorem):

• if Γ U {Φ} ⊢ Ψ, then Γ ⊢ Φ → Ψ.

Lemma 4.4:

• Γ is inconsistent iff Γ ⊢ P₀ ∧ ~P₀

Lemma 4.8:

• If Γ is a consistent set of formulas of FOL^-_C, then Γ can be extended to a maximally consistent set Γ* of sentences with Γ ⊆ Γ*.

Lemma 4.9:

• If Γ is a maximally consistent, witnessed set of sentences, then Γ has a model (the Henkin term model).

Theorem 4.10:

• If Γ ⊨ Φ, then Γ ⊢ Φ.

Proof by contrapositive:

1. Assume Γ not ⊢ Φ

2. Γ U {¬Φ} is consistent

3. Extend Γ U {¬Φ} to a maximally consistent Henkin set Γ* with Γ U {¬Φ} ⊆ Γ*

4. By Lemma 4.9, there is a canonical Henkin model M with M ⊨ Γ* and since Γ ⊆ Γ* we have M ⊨ Γ. Also ~Φ ∈ Γ*, so M ⊨ ~Φ.

5. Thus there exists a model M that satisfies every sentence of Γ but does not satisfy Φ. So Γ not ⊨ Φ

6. Since Γ not ⊢ Φ led to Γ not ⊨ Φ, then it’s true that if Γ ⊨ Φ, then Γ ⊢ Φ.