Questions: Metalogical Properties and Foundational Theorems

Question 1

Gödel's 1929 Completeness Theorem establishes that for first-order logic, if Γ ⊨ φ then Γ ⊢ φ. What does this mean in plain terms?

• A. Every true statement can be proved from axioms alone, without any premises
• B. Every semantically valid argument has a formal derivation using the inference rules
• C. Any consistent set of axioms produces only true statements
• D. All mathematical truths can be derived from a finite set of axioms

Answer: (B)

Completeness (Γ ⊨ φ → Γ ⊢ φ) says: if φ is true in every model where Γ is true, then there is a formal derivation of φ from Γ using the inference rules. It connects the semantic notion of consequence (⊨) to the syntactic notion of derivability (⊢). Options A and D are much stronger claims, and Gödel's Incompleteness Theorems (a different result) specifically refute D for arithmetic. Option C describes soundness, not completeness.

Question 2

Which of the following correctly distinguishes Gödel's 1929 Completeness Theorem from his 1931 Incompleteness Theorems?

• A. The Completeness Theorem applies to propositional logic; Incompleteness applies to first-order logic
• B. Completeness shows the first-order proof system derives all semantically valid arguments; Incompleteness shows axiomatic theories of arithmetic cannot prove all arithmetic truths
• C. Both concern the same property — Incompleteness refuted what Completeness claimed
• D. Completeness shows arithmetic is provable from axioms; Incompleteness shows those axioms are inconsistent

Answer: (B)

These are entirely different results about different things. The Completeness Theorem (1929) concerns the *first-order proof system itself* — the standard inference rules are sufficient to derive every semantically valid consequence. The Incompleteness Theorems (1931) concern *specific axiomatic theories of arithmetic* — no consistent, sufficiently strong arithmetic axiom system can prove all truths about natural numbers. First-order logic is complete; arithmetic as a theory is incomplete. These facts are compatible.

Question 3

Soundness of a formal proof system guarantees that every provable statement is true in all models of the premises.

• T. True
• F. False

Answer: True

Soundness (Γ ⊢ φ → Γ ⊨ φ) means the proof system never proves something false: if you derive φ from Γ using the inference rules, then φ is true in every model of Γ. Soundness is typically proven by verifying each inference rule preserves truth, then arguing by induction on proof length. It is the minimum requirement for a proof system to be worth using — a system that proves false things is worse than useless.

Question 4

Gödel's First Incompleteness Theorem shows that the first-order logic proof system is incomplete — there are logical consequences it can seldom derive.

• T. True
• F. False

Answer: False

This is the key confusion to avoid. Gödel's First Incompleteness Theorem (1931) concerns *arithmetic as a theory*: any consistent, sufficiently expressive axiom system for arithmetic leaves some arithmetic truths unprovable from those axioms. It says nothing about the first-order *proof system* being incomplete. Gödel's 1929 Completeness Theorem established the opposite: the first-order proof system IS complete — every logical consequence has a formal derivation. These are different theorems about different things.

Question 5

Explain in your own words why the Compactness Theorem is a surprising consequence of completeness, and give an example of what it allows you to conclude.

Model answer: Compactness says: if every finite subset of an infinite set Γ has a model, then Γ itself has a model. It's surprising because infinitely many sentences together might seem to demand more than any finite subset. One consequence: you can build non-standard models of arithmetic by adding infinitely many axioms ('there exists a number greater than 0', '...greater than 1', '...greater than 2', ...). Every finite subset is satisfiable, so by compactness the entire infinite set is satisfiable — yielding a model containing an 'infinite' natural number.

Compactness follows from completeness because a formal proof uses only finitely many premises. If Γ had no model, by completeness there would be a proof of a contradiction from Γ — but that finite proof uses only finitely many sentences from Γ, so some finite subset is unsatisfiable, contradicting the assumption. This finite-witnessing property means first-order logic cannot express properties like 'infinitely many' in a way that pins down infinite cardinalities — any first-order sentence true in an infinite structure is also satisfiable in non-standard models.