Proof 1 (countable language)

Let S be a countable set of sentences in a propositional language with atomic sentences p_{0}, p_{1}, p_{2}, …. 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. V_{n} will be the partial truth assignment after assigning the first n truth values. If W agrees with V_{n} on its domain, then call W an extension of V_{n}.

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

First of all, V_{0} 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 V_{n}. We’ll show that the same holds of V_{n+1}.

Suppose not. Then both of the following must be true:

(1) Some finite subset S_{0} of S is not satisfied by any extension of V_{n} ⋃ {(p_{n}, T)}

(2) Some finite subset S_{1} of S is not satisfied by any extension of V_{n} ⋃ {(p_{n}, F)}

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

Define V = U {V_{n} : 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 V_{n} assigns truth values to all sentence letters in φ. {φ} is a finite subset of S, so some extension of V_{n} satisfies it. Every extension of V_{n} agrees on the assignments to the atomic sentences that appear in φ. So since some extension of V_{n} makes φ true, all extensions of V_{n} 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!