Questions: Soundness and Completeness of First-Order Logic

Question 1

Gödel proved in 1931 that some true sentences of arithmetic are unprovable. A student concludes that this shows the FOL proof system is incomplete. What is wrong with this reasoning?

• A. Nothing — Gödel's 1931 result directly refutes the Completeness Theorem
• B. The Completeness Theorem only applies to propositional logic, not FOL
• C. Gödel's Incompleteness Theorems concern specific theories like arithmetic, while Completeness concerns logical validity — sentences true in every structure
• D. The Completeness Theorem was disproved; Gödel's result replaced it

Answer: (C)

These are different theorems at different levels. Completeness (1930) says: if a sentence φ is true in every possible FOL structure (logically valid), then φ is provable. Incompleteness (1931) says: in theories like Peano arithmetic, there are sentences that are true in ℕ but not provable from the axioms. These sentences are not logically valid — they are true in the natural numbers but false in other structures. There is no contradiction: the proof system captures all logical validities (completeness) but no fixed theory can capture all arithmetical truths (incompleteness).

Question 2

What does the Henkin construction accomplish in the proof of the Completeness Theorem?

• A. It proves that all FOL axioms are valid by semantic inspection
• B. It shows that any inconsistent theory has a contradiction derivable in finitely many steps
• C. It builds a model for a consistent theory by treating terms of the language as the elements of the domain
• D. It reduces completeness of FOL to the already-known completeness of propositional logic

Answer: (C)

The Henkin construction is a way of using syntax to construct semantics. Given a consistent theory T, you extend it to a maximal consistent theory with witnesses — a new constant for every existential claim. The model is then built directly: the elements of the domain are equivalence classes of closed terms, and relations are interpreted by what the theory proves about them. The key insight is that the model's objects are not external mathematical entities but the very terms of the language, organized by provable equality.

Question 3

If ⊨ φ (φ is true in every FOL structure), then ⊢ φ (φ is provable in the standard proof system).

• T. True
• F. False

Answer: True

This is exactly what the Completeness Theorem states: the proof system is complete, meaning it can derive every logically valid sentence. The direction ⊢ φ implies ⊨ φ is soundness (easy direction). The direction ⊨ φ implies ⊢ φ is completeness (deep direction, proved by Gödel in 1930). Together they say the proof system captures exactly the logically valid sentences — no more (soundness) and no less (completeness).

Question 4

Gödel's Completeness Theorem implies that most sentence that is true about the natural numbers is provable from the axioms of first-order arithmetic.

• T. True
• F. False

Answer: False

This is precisely the confusion the topic warns against. Completeness says every logically valid sentence — one true in ALL structures — is provable. A sentence like 'this Gödel sentence G is true in ℕ' is not logically valid; it is true in ℕ but false in non-standard models. Completeness guarantees nothing about sentences that are only true in some structures. Gödel's Incompleteness Theorems show that no consistent recursive axiomatization of arithmetic can prove all arithmetical truths.

Question 5

Explain why Gödel's Completeness Theorem and his Incompleteness Theorems do not contradict each other.

Model answer: The theorems operate at different levels. The Completeness Theorem says: the FOL proof system derives exactly the sentences that are true in every model — the logically valid sentences. The Incompleteness Theorems say: for theories like arithmetic, there are sentences true in the intended model (ℕ) but not in every model, and these cannot be proved from the axioms. These 'incomplete' sentences are not logically valid — they fail in non-standard models. So completeness still holds: every sentence true in all models is provable. Incompleteness is about theory-specific truth, not logical validity.

The key distinction is between logical validity (true in all structures) and truth-in-a-specific-model (true in ℕ). The Completeness Theorem covers the former; Incompleteness concerns the latter. Gödel's 1930 result and 1931 result are both correct, and they address entirely different questions about entirely different things.