Questions: Compactness Theorem for Propositional Logic

Question 1

An infinite set Γ of propositional formulas has the property that every finite subset is satisfiable, but you suspect the entire set might be unsatisfiable due to 'accumulating constraints.' What does the compactness theorem tell you?

• A. You need to check all infinite subsets to determine satisfiability
• B. The entire set Γ is satisfiable — finite satisfiability of all subsets implies satisfiability of the whole
• C. The set is satisfiable only if the formulas are arranged in a well-ordering
• D. The compactness theorem applies only to sets with finitely many propositional variables

Answer: (B)

This is precisely what the compactness theorem guarantees. The worry about 'accumulating constraints' is the intuition the theorem refutes — propositional logic lacks the expressive power to create constraints that are only violated at infinity. Any contradiction must be derivable from a finite set of premises (since proofs are finite syntactic objects), so if no finite subset is unsatisfiable, no contradiction is provable, and the whole set is satisfiable.

Question 2

A logician wants to prove an infinite graph G is 3-colorable using compactness. What must the logician establish?

• A. That G contains no odd cycles (sufficient for 2-colorability, not 3-colorability)
• B. That every finite subgraph of G is 3-colorable, then apply compactness to conclude G is 3-colorable
• C. That G is countably infinite, since compactness only applies to countable structures
• D. That G has a Hamiltonian path, allowing a sequential coloring argument

Answer: (B)

Create propositional variables c(v,i) meaning 'vertex v gets color i' for i ∈ {1,2,3}. Add axioms encoding: each vertex gets exactly one color, and adjacent vertices get different colors. Every finite subgraph of G is 3-colorable by assumption, so every finite subset of these axioms is satisfiable. By compactness, the entire (infinite) set of axioms is satisfiable — meaning G itself has a 3-coloring. Countability (option C) is not required for propositional compactness.

Question 3

The compactness theorem implies that if φ is a logical consequence of an infinite set Γ, then φ is a logical consequence of some finite subset of Γ.

• T. True
• F. False

Answer: True

Correct. Logical consequence means Γ ∪ {¬φ} is unsatisfiable. By compactness, if this set is unsatisfiable, then some finite subset Δ ∪ {¬φ} (where Δ ⊆ Γ is finite) is already unsatisfiable — meaning Δ ⊨ φ. So whenever Γ ⊨ φ, some finite Δ ⊆ Γ witnesses it. Logical consequence in propositional logic is always finitely witnessed.

Question 4

Compactness of propositional logic means that most infinite sets of formulas can generally be satisfied simultaneously.

• T. True
• F. False

Answer: False

This misreads the theorem. Compactness does not say all infinite sets are satisfiable — it says that if an infinite set is finitely satisfiable (every finite subset is satisfiable), then it is satisfiable. An infinite set can certainly be unsatisfiable: {p, ¬p, q, ...} is unsatisfiable because the finite subset {p, ¬p} is already unsatisfiable. Compactness constrains how unsatisfiability arises (always from a finite culprit), not whether it can arise.

Question 5

Explain informally why the compactness theorem implies that propositional logic cannot express the constraint 'there are infinitely many true variables.'

Model answer: Suppose Γ consists of formulas asserting 'at least one of p₁,...,pₙ is true' for every n. Any finite subset of Γ is satisfiable by making finitely many variables true. By compactness, Γ itself is satisfiable — but a satisfying assignment can set all but finitely many variables to false and still satisfy every finite disjunction. So Γ doesn't actually force infinitely many variables to be true. Propositional logic cannot distinguish 'finitely many' from 'infinitely many.'

This is the core limitation: propositional formulas encode finite Boolean constraints. Any inconsistency is witnessed by a finite derivation, so propositional logic cannot pin down 'size' in a way that rules out finite solutions. First-order logic has the same property (by Löwenheim-Skolem combined with first-order compactness), which is why non-standard models of arithmetic exist: you can add a constant c with axioms c > 0, c > 1, c > 2, ... — every finite subset is satisfiable, so by compactness the whole theory has a model containing an element greater than every standard natural number.