Two more short and sweet proofs of propositional compactness

Proof 1 (countable language)

Let S be a countable set of sentences in a propositional language with atomic sentences p0, p1, p2, ….  Assume that S is finitely satisfiable. We want to build a truth assignment V that satisfies S.

We’ll assign truth values to the atomic sentences one at a time. Vn will be the partial truth assignment after assigning the first n truth values. If W agrees with Vn on its domain, then call W an extension of Vn.

We’ll now prove by induction that for each n, every finite subset of S is satisfied by some extension of Vn.

First of all, V0 is just the empty set, and every function is an extension of the empty set. So the hypothesis follows trivially from the finite satisfiability of S. 

Now, assume that every finite subset of S is satisfied by some extension of Vn. We’ll show that the same holds of Vn+1.

Suppose not. Then both of the following must be true:
(1) Some finite subset S0 of S is not satisfied by any extension of Vn ⋃ {(pn, T)}
(2) Some finite subset S1 of S is not satisfied by any extension of Vn ⋃ {(pn, F)}

S0 ⋃ S1 is not satisfied by any extension of Vn ⋃ {(pn, T)}, or any extension of Vn ⋃ {(pn, F)}. So it’s not satisfied by any extension of Vn, contradicting the inductive hypothesis since S0 ⋃ S1 is a finite set. This proves that every finite subset of S is satisfied by some extension of Vn, for each n.

Define V = U {Vn : n ∈ ω}. We now show that V satisfies S. Consider any sentence φ ∈ S. φ contains a finite number of atomic sentences, so there’s some n large enough that Vn assigns truth values to all sentence letters in φ.  {φ} is a finite subset of S, so some extension of Vn satisfies it. Every extension of Vn agrees on the assignments to the atomic sentences that appear in φ.  So since some extension of Vn makes φ true, all extensions of Vn must make φ true.  In particular, V makes φ true.

Proof 2 (any language)

Suppose S is a finitely satisfiable set of sentences, and let L be the set of atomic sentences.

A partial function g: L → {T, F} is called good if each finite subset of S is satisfied by some extension of g.

The good partial functions are a poset under ⊆, and since S is finitely satisfiable, ∅ is good. Furthermore, the union of any chain of good functions is a good function. Thus every chain has an upper bound, namely its union.

By Zorn’s lemma, there’s a maximal good function g. Since g is maximal, the domain of g is all of L.

We now show that g satisfies every element of S.
… Suppose φ ∈ S.
… Since g is good, it has an extension satisfying φ.
… But g already has all of L as its domain, so g satisfies φ.

So S is satisfiable!

Leave a Reply