Questions: Compactness Theorem for Propositional Logic

Question 1

Suppose you want to prove that an infinite planar graph G can be 4-colored. You know that every finite subgraph of G is 4-colorable (by the finite 4-color theorem). Which argument correctly applies the compactness theorem?

• A. Since every finite subgraph is 4-colorable and G is a union of finite subgraphs, G must be 4-colorable — no compactness needed
• B. Introduce a propositional variable for each node-color assignment, write finitely many formulas encoding valid 4-coloring for each finite subgraph, note every finite subset of these formulas is satisfiable, conclude by compactness that the full formula set is satisfiable
• C. Apply compactness directly to the graph: since every finite sub-graph is finite, the infinite graph is just a large finite graph
• D. Compactness cannot be applied here because graph coloring requires first-order logic

Answer: (B)

The correct approach encodes the coloring problem as a propositional formula set: variables p_{v,c} meaning 'vertex v gets color c', with formulas asserting each vertex gets exactly one color and adjacent vertices get different colors. Every finite subgraph induces a finite subset of these formulas, which is satisfiable by the finite 4-color theorem. By compactness, the infinite formula set is satisfiable, meaning a valid 4-coloring of the entire infinite graph exists. Option A fails because a union of 4-colorable subgraphs need not have a globally consistent coloring — the colorings of different subgraphs might be incompatible.

Question 2

The compactness theorem says: an infinite set Σ is satisfiable if and only if every finite subset is satisfiable. Which direction is the non-trivial and logically surprising one?

• A. If Σ is satisfiable, then every finite subset is satisfiable
• B. If every finite subset of Σ is satisfiable, then Σ itself is satisfiable
• C. Both directions are equally surprising
• D. Neither direction is surprising — they follow immediately from definitions

Answer: (B)

The forward direction (satisfiable Σ ⇒ every finite subset satisfiable) is trivial: a truth assignment making all of Σ true obviously makes every subset true. The surprising direction is the converse: merely knowing that no finite 'window' into Σ produces a contradiction is enough to conclude a global satisfying assignment exists. This is non-obvious because there are infinitely many formulas to satisfy simultaneously — the theorem says finite local consistency implies global consistency, which is the genuinely powerful and non-trivial claim.

Question 3

The proof of compactness from completeness relies on the fact that formal proofs are finite objects.

• T. True
• F. False

Answer: True

This is the key observation. A proof of a contradiction from Σ can only cite finitely many formulas from Σ (proofs are finite sequences of steps). So if every finite subset of Σ is satisfiable (and hence consistent — no finite subset proves a contradiction), then Σ itself cannot prove a contradiction. By completeness, if Σ does not prove a contradiction, it is consistent; by completeness again, consistency implies satisfiability. The finiteness of proofs is what makes the entire chain work.

Question 4

The compactness theorem implies that propositional logic can express the property 'this structure is finite.'

• T. True
• F. False

Answer: False

Compactness implies the opposite: propositional logic CANNOT express finiteness. If a set of formulas is satisfied by arbitrarily large finite structures, compactness guarantees it is also satisfied by an infinite structure (by adding formulas asserting 'at least n elements exist' for every n — any finite subset of these formulas is satisfiable, so the whole set is). This means no propositional theory can have only finite models without having no models at all. Finiteness is precisely what propositional (and first-order) logic cannot pin down.

Question 5

Why do proofs being finite objects imply that compactness follows from completeness?

Model answer: A derivation of contradiction ⊥ from a set Σ is a finite proof — it cites a finite list of formulas from Σ as premises. So any contradiction derivable from Σ is already derivable from some finite subset Σ₀ ⊆ Σ. Contrapositive: if every finite subset of Σ is satisfiable (hence consistent — no finite subset derives ⊥), then no finite subset derives ⊥, so Σ itself derives no contradiction. By completeness, Σ is consistent, and by completeness again (in its completeness direction), consistent means satisfiable. The finite-proof observation is what lets us move from 'no finite part contradicts' to 'the whole is consistent.'

Without this finiteness fact, the argument would break: an infinitely long proof might somehow cite all of Σ and derive a contradiction even when no finite portion can. But proof systems are defined to have finite proof objects, so this scenario is impossible. The compactness theorem is in a precise sense a theorem about the finitary nature of formal proof rather than about propositional logic's semantics directly.