Questions: Compactness Theorem for First-Order Logic

Question 1

Let T be the first-order theory of arithmetic. You extend it by adding a new constant c and axioms {c > 0, c > 1, c > 2, ...}. What does the compactness theorem guarantee about this extended theory?

• A. The extended theory is unsatisfiable, because no natural number can satisfy c > n for all n
• B. The extended theory has a model, but only one — the standard natural numbers with c interpreted as infinity
• C. The extended theory has a model containing a non-standard element that is larger than every standard natural number
• D. The extended theory is satisfiable only if you add an axiom explicitly asserting that non-standard elements exist

Answer: (C)

Any finite subset of the extended theory is satisfiable — just interpret c as a natural number larger than the largest n mentioned. By compactness, the entire theory has a model. But that model must contain an element c satisfying c > n for every standard natural number n — which no standard natural number can do. So the model contains a non-standard element. This is the compactness construction: finite satisfiability extends to a model, but the model differs from the intended interpretation by containing 'extra' elements. Option B is wrong because the extended theory has many models; the standard natural numbers are not one of them (no natural number exceeds all others).

Question 2

Which of the following correctly states the compactness theorem for first-order logic?

• A. Any finite first-order theory with arbitrarily large finite models has an infinite model
• B. A set of first-order sentences has a model if and only if every finite subset of it has a model
• C. Every first-order theory can be axiomatized by a finite set of sentences
• D. If a first-order sentence is true in all finite models, it is true in all infinite models

Answer: (B)

The compactness theorem states: an (infinite) set Γ of sentences has a model iff every finite subset of Γ has a model. Option A describes the Upward Löwenheim-Skolem direction — a related but distinct result. Option C is false; many important theories (like arithmetic) require infinitely many axioms. Option D is also false — there are sentences true in all finite models but false in some infinite model (e.g., the assertion that a relation is acyclic). Compactness specifically addresses the relationship between satisfiability of a set and satisfiability of its finite subsets.

Question 3

Second-order logic can characterize the natural numbers up to isomorphism, but this expressibility comes at the cost of losing the compactness property.

• T. True
• F. False

Answer: True

Second-order logic, which can quantify over sets and properties, can write a sentence that pins down ℕ uniquely up to isomorphism (the Dedekind-Peano axioms in second-order form). First-order logic cannot do this — any first-order theory with an infinite model has non-standard models of every infinite cardinality (Löwenheim-Skolem). But second-order logic loses compactness: a set of second-order sentences can be such that every finite subset is satisfiable while the whole set is not. The trade-off — expressivity vs. model-theoretic manageability — is a central theme of logic.

Question 4

Compactness means that most first-order theory can be captured by a finite set of axioms, since satisfiability is finitely determined.

• T. True
• F. False

Answer: False

This confuses two different things. Compactness says that unsatisfiability is finitely witnessed — if Γ is unsatisfiable, some finite subset is already unsatisfiable. It does not say that a satisfiable theory can be axiomatized finitely. Many important first-order theories (Peano arithmetic, the theory of real closed fields) require infinitely many axioms and cannot be finitely axiomatized. Compactness is about when a contradiction forces itself to be detectable in a finite piece of the theory, not about how many axioms are needed to describe a structure.

Question 5

Why does the finiteness of formal proofs imply the compactness theorem for first-order logic?

Model answer: A formal proof is a finite sequence of steps, so any proof uses only finitely many sentences from the axiom set, even if that set is infinite. If a set Γ of sentences were unsatisfiable, completeness guarantees a proof of a contradiction — but that proof uses only finitely many sentences from Γ, meaning some finite subset of Γ is already unsatisfiable. Contrapositively: if every finite subset of Γ is satisfiable (no finite subset proves a contradiction), then Γ itself must be satisfiable. The argument is essentially: completeness + finiteness of proofs = compactness.

This is why compactness is often described as completeness stated contrapositively. The deep connection is that first-order logic has a complete proof system, and complete proof systems produce only finite proofs. Any logical system with a complete finite-proof system automatically satisfies compactness. Second-order logic lacks a complete proof system, which is connected to why it also lacks compactness.