compactness theorem for classical propositional logic

Call a set Δ of wff’s of (classical) propositional logicPlanetmathPlanetmath sound if there is an interpretationMathworldPlanetmathPlanetmath (or valuation) v such that v(A)=1 for every AΔ.

Theorem 1.

(Compactness Theorem) Δ is sound iff every finite subset of it is sound.

One direction is trivial. The converseMathworldPlanetmath is trivial too if Δ is finite. We now prove that if every finite subset of an infinite setMathworldPlanetmath Δ is sound, so is Δ. There are two well-known proofs of this, one assumes that the set V of propositional variables is countableMathworldPlanetmath, and the other does not. The one that does uses Konig’s lemma, and the other one uses TychonoffPlanetmathPlanetmath’s theorem (hence the name compactness theorem).

Proof using Konig’s lemma. Let A1, be an enumeration of all the wff’s in Δ (this assumes that the set V of all propositional variables is countable). Let i1 be positive integers such that p1,,pin are the propositional variables that occur in wff’s A1,,An. Since {A1,,An} is sound, the set Sn:={v2Vv(Aj)=1,j=1,,n} for each n. Furthermore, Sn+1Sn. Let Un:={v(p1)v(pn)vSn}. In other words, each Un is a set of words over {0,1} of length n. Then Un is finite and non-empty (because Sn) for each n. Since Sn+1Sn, there is a word in Un that is a prefix of a word in Un+1 for each n.

Let T be the tree with root r (some arbitrary symbol) such that

  1. 1.

    its vertices other than r are elements of U1,,Un,.

  2. 2.

    the children of r are elements of U1,

  3. 3.

    if Un is a vertex, then its children are elements of Un+1 with prefix

It’s easy to see that T is finitely branching, since each Un is finite. Furthermore, by inductionMathworldPlanetmath, if Un+1, then its prefix of length n, an element of Un, is a vertex of T. So , as a child of , is a vertex T. Since each Un for each n, the T has infinitely many vertices. As a result, we apply Konig’s lemma, so that T has an infinite branch T. It is easy to see that T corresponds to an infinite word α over {0,1}, which in turn corresponds to an interpretation v such that v(pi) is the i’th letter in α. It is now clear that v(Ai)=1 for each AiΔ, hence Δ is sound.

Proof using Tychonoff’s theorem. For any set Δ of wff’s, define S(Δ):={v2Vv(A)=1, for all AΔ}. It is easy to see that

S({ΔiiI})={S(Δi)iI} (1)

for v is in the former set iff v(A)=1 for all A{ΔiiI} iff v(Ai)=1 for all AiΔi, iI, iff v in the later set.

Next, equip 2:={0,1} with the discrete topology, and 2V the product topology. Since 2 is compactPlanetmathPlanetmath, so is 2V by the Tychonoff’s theorem, and therefore the finite intersection property applies. In addition, for any wff A, S({A}) is closed in 2V, since there are only a finite number of propositional variables occurring in A. As a result, by equation (1), S(Δ) is closed for any set Δ of wff’s.

Now, suppose every finite subset of Δ is sound. In particular, every singleton subset of Δ is sound. This means that for each AΔ, S({A}). Let 𝔇:={S({A})AΔ). Then every member of 𝔇 is closed, and, by assumptionPlanetmathPlanetmath and equation (1), the intersectionMathworldPlanetmath of any finite family of members of 𝔇 is non-empty, which means that 𝔇. But 𝔇=S(Δ) by equation (1), the result follows.

Remark. It can be shown that the general version of the compactness theorem is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to the prime ideal theorem in Boolean algebraMathworldPlanetmath.

By the compactness theorem, one can show that soundness and consistency are the semantical and syntactical sides of the same idea.

Lemma 1.

Soundness and consistency are the same on finite setsMathworldPlanetmath.


If A1,,An, then B, where B is A1(A2((An)), or v(B)=1 for all v, or v(A1)=0 or v(A2((An)))=1, or v(A1)=0 or v(A2)=0 or or v(An)=0 for all v, by induction, or v(Ai)=0 for some i, where i=1,,n, which means {A1,,An} is not sound.

Conversely, if {A1,,An} is not sound, then v(Ai)=0 for some i, where i=1,,n for all v. Renumber if necessary, so that the indices 1 and i are switched, and v(A1)=0 for all v. Let B be the formulaMathworldPlanetmathPlanetmath A2((An)) Then v(A1B)=1 for all v. By the completeness theorem, A1B, and therefore A1,,An by the deduction theoremMathworldPlanetmath n times. ∎

Proposition 1.

Soundness and consistency are the same on all sets.


For one direction, see here ( Now, suppose Δ is consistent. Then every finite subset of it is consistent, and therefore sound by the last proposition, hence Δ itself is sound by the compactness theorem. ∎

A set Δ of wff’s is uniquely sound if there is a unique interpretation v such that v(A)=1 for every AΔ.

Corollary 1.

A set is maximally consistent iff it is a uniquely sound theory.


If Δ is maximally consistent, then it is a theory (see here (, and sound by the last corollary. Suppose v1(A)=v2(A)=1 for all AΔ. If v1v2, then there is some wff BΔ such that v1(B)v2(B). So one of them is 1, say v1(B)=1. Then Δ{B} is sound, and therefore consistent by the last corollary, contradicting the maximality of Δ.

We actually proved more: any maximally consistent Δ is {Av(A)=1}, where v is the unique interpretation such that v(A)=1 for all AΔ. One direction is obvious. The other direction comes from the fact that {Av(A)=1} is consistent and Δ is maximal.

Conversely, suppose a theory Δ is uniquely sound. Then Δ=Ded(Δ)={ΓWLΔΓ}, where WL is the set of all maximally consistent sets of the logic L. Suppose {ΓWLΔΓ} has at least two elements, say, Γ1,Γ2. Then by the last paragraph, they are both uniquely sound. Let v1,v2 be the two respective unique interpretations such that vi(A)=1 for every AΓi, i=1,2. Since Γ1Γ2, there is a wff BΓ1-Γ2 such that v1(B)=1 and v2(B)=0. In addition, v1(A)=v2(A)=1 for all AΔ, which forces v1=v2 because Δ is uniquely sound. But this contradicts the inequality v2(B)v2(B). Therefore, {ΓWLΔΓ} has exactly one element, which is Δ. ∎

Remark. It is easy to see that Δv:={Av(A)=1} is maximally consistent for any interpretation v: it is sound, and therefore consistent; it is maximal, for given any wff B, either v(B)=1 or v(B)=0, so that either BΔv or ¬BΔv. Coupled with the corollary above, there is a one-to-one correspondence vΔv between interpretations and maximally consistent sets of a logic.

Title compactness theorem for classical propositional logic
Canonical name CompactnessTheoremForClassicalPropositionalLogic
Date of creation 2013-03-22 19:35:21
Last modified on 2013-03-22 19:35:21
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 14
Author CWoo (3771)
Entry type Theorem
Classification msc 03B05
Defines sound
Defines uniquely sound