Showing two formulations of completeness theorem equivalent

Assignment Help Mathematics

Reference no: EM132381212

The Completeness Theorem Problems -

Problem 1 - Complete the proof of Proposition: Suppose Γ is complete and consistent. Then:

1. If Γ |- φ, then φ ∈ Γ.

2. φ Λ ψ ∈ Γ iff both φ ∈ Γ and ψ ∈ Γ.

3. φ ∨ ψ ∈ Γ iff either φ ∈ Γ or ψ ∈ Γ.

4. φ → ψ ∈ Γ iff either φ ∉ Γ or ψ ∈ Γ.

Problem 2 - Complete the proof of Lemma: (Truth Lemma). v(Γ*) |= φ iff φ ∈ Γ*.

Problem 3 - Use Corollary 11.7 to prove Theorem 11.6, thus showing that the two formulations of the completeness theorem are equivalent.

Corollary 11.7 - (Completeness Theorem, Second Version). For all Γ and φ sentences: if Γ |= φ then Γ |- φ.

Theorem 11.6 - (Completeness Theorem). Let Γ be a set of sentences. If Γ is consistent, it is satisfiable.

Problem 4 - In order for a derivation system to be complete, its rules must be strong enough to prove every unsatisfiable set inconsistent. Which of the rules of derivation were necessary to prove completeness? Are any of these rules not used anywhere in the proof? In order to answer these questions, make a list or diagram that shows which of the rules of derivation were used in which results that lead up to the proof of Theorem 11.6. Be sure to note any tacit uses of rules in these proofs.

Problem 5 - Prove (1) of Theorem: (Compactness Theorem). The following hold for any sentences Γ and φ:

1. Γ |= φ iff there is a finite Γ₀ ⊆ Γ such that Γ₀ |= φ.

2. Γ is satisfiable if and only if it is finitely satisfiable.

Problem 6 - Prove Proposition. Avoid the use of |-.

Proposition - Suppose Γ is complete and finitely satisfiable. Then:

1. (φ Λ ψ) ∈ Γ iff both φ ∈ Γ and ψ ∈ Γ.

2. (φ ∨ ψ) ∈ Γ iff either φ ∈ Γ or ψ ∈ Γ.

3. (φ → ψ) ∈ Γ iff either φ ∉ Γ or ψ ∈ Γ.

Problem 7 - Prove Lemma. (Hint: the crucial step is to show that if Γ_nis finitely satisfiable, then either Γ_n U {φ_n} or Γ_n U {¬φ_n} is finitely satisfiable.)

Lemma - Every finitely satisfiable set Γ can be extended to a complete and finitely satisfiable set Γ*.

Problem 8 - Write out the complete proof of the Truth Lemma (Lemma 11.5) in the version required for the proof of Theorem 11.12.

Lemma 11.5 (Truth Lemma). v(Γ*) |= φ iff φ ∈ Γ*.

Theorem11.12 (Compactness). Γ is satisfiable if and only if it is finitely satisfiable.

Reference no: EM132381212

Questions Cloud

How many days did tater and will inventory stay on premise : Tater and will reported sales for 2018 of $43 million. Tater and will listed $7.6 million of inventory on its balance sheet. How many days did Tater.

Money to retire and make the withdrawals as planned : Carow Industries has just started to deposit $200 at the end of each month into its employees' retirement fund

ENG215 Research And Writing Assignment problem : ENG215 Research And Writing assignment help and assessment help, Strayer University - Using Hite and Seitz (2016), relevant supplemental resources.

Calculate current ratio and quick ratio and cash : You are evaluating the balance sheet for William corporation. From the balance sheet you will find the following cash and marketable securities.

Showing two formulations of completeness theorem equivalent : Use Corollary 11.7 to prove Theorem 11.6, thus showing that the two formulations of the completeness theorem are equivalent

MCGY2611 Music from the Middle Ages to Baroque Assignment : MCGY2611 Music from the Middle Ages to Baroque Assignment help and solution, The University of Sydney, Assessment help - Write a 2000 word essay.

Calculate basic earning for share and price earnibg ratio : Calculate basic earning for share and price earnibg ratio for each year income available for common shareholder.

What is the navigation bar and describe its function : How many active menu bar selections does Sage 50 have? List the menu bar selections. What is the Navigation Bar? Briefly describe its function.

Distinguish between general and legislative regulate : Define and distinguish between general and legislative regulate.How often is this document published? Name six items that typically are published.

User Account

All Pages