Lindenbaum’s lemma

In this entry, we prove the following assertion known as Lindenbaum’s lemma: every consistent set is a subset of a maximally consistent set. From this, we automatically conclude the existence of a maximally consistent set based on the fact that the empty setMathworldPlanetmath is consistent (vacuously).

Proposition 1.

(Lindenbaum’s lemma) Every consistent set can be extended to a maximally consistent set.

We give two proofs of this, one uses Zorn’s lemma, and the other does not, and is based on the countability of the set of wff’s in the logic. Both proofs require the following:

Lemma 1.

The union of a chain of consistent sets, ordered by , is consistent.


Let 𝒞:={ΓiiI} be a chain of consistent sets ordered by and indexed by some set I. We want to show that Γ:=𝒞 is also consistent. Suppose not. Then Γ. Let A1,,An be a deductionMathworldPlanetmathPlanetmath of (which is An) from Γ. Then for each j=1,,n-1, there is some Γi(j)𝒞 such that Γi(j)Ai. Since 𝒞 is a chain, take the largest of the Γi(j)’s, say Γk, so that ΓkAi for all i=1,,n-1. This implies that ΓkAn, or Γk, contradicting the assumption that Γk is consistent. As a result, Γ is consistent. ∎

First Proof. Suppose Δ is consistent. Let P be the partially ordered setMathworldPlanetmath of all consistent supersetsMathworldPlanetmath of Δ, ordered by inclusion . If 𝒞 is a chain of elements in P, then 𝒞 is consistent by the lemma above, so 𝒞P as each element of 𝒞 is a superset of Δ. By Zorn’s lemma, P has a maximal elementMathworldPlanetmath, call it Γ. To see that Γ is maximally consistent, suppose Γ is not maximal. Then there is a wff A such that Γ⊬A and Γ⊬¬A, the first of which implies that AΓ, and the second of which implies that Γ{A} is consistent, and therefore in P. The two imply that Γ{A} is a consistent proper superset of Γ, contradicting the maximality of Γ in P. Therefore, Γ is maximally consistent.

Second Proof. Let A1,,An, be an enumeration of all wff’s of the logic in question (this can be achieved if the set of propositional variables can be enumerated). Let Δ be a consistent set of wff’s. Define sets Γ1,Γ2,,Γ of wff’s inductively as follows:

Γ1 := Δ
Γn+1 := {Γn{An}if ΓnAnΓn{¬An}otherwise
Γ := i=1Γi.

First, notice that each Γi is consistent. This is done by inductionMathworldPlanetmath on i. By assumption, the case is true when i=1. Now, suppose Γn is consistent. Then its deductive closure Ded(Γn) is also consistent. If ΓnAn, then clearly Γn{An} is consistent since it is a subset of Ded(Γ). Otherwise, Γn⊬An, or Γn⊬¬¬An by the substitution theorem, and therefore Γn{¬An} by one of the properties of consistency (see here ( In either case, Γn+1 is consistent.

Next, Γ is maximally consistent. Γ is consistent because, by the lemma above, it is the union of a chain of consistent sets. To see that Γ is maximal, pick any wff A. Then A is some An in the enumerated list of all wff’s. Therefore, either AΓn+1 or ¬AΓn+1. Since Γn+1Γ, we have AΓ or ¬AΓ, which implies that Γ is maximal (see here ( .

Given a logic L, let WL be the set of all maximally L-consistent sets. By Lindebaum’s lemma, WL. We record two useful corollaries:

  • For any consistent set Δ, Ded(Δ)={ΓWLΔΓ}.

  • L=WL.


The second statement is a corollary of the first, for L=Ded(). To see the first, let 𝒟:={ΓWLΔΓ}. Then 𝒟 by Lindebaum’s lemma. Also, for any Γ𝒟, Ded(Δ)Γ since Γ is deductively closed. On the other hand if ADed(Δ), then Δ⊬A, so Δ{¬A} is consistent, and therefore is contained in a maximally consistent set Γ𝒟 by Lindenbaum’s lemma. Since ¬AΓ, AΓ, so that A𝒟. ∎

Title Lindenbaum’s lemma
Canonical name LindenbaumsLemma
Date of creation 2013-03-22 19:35:16
Last modified on 2013-03-22 19:35:16
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Theorem
Classification msc 03B45
Classification msc 03B10
Classification msc 03B05
Classification msc 03B99
Related topic EveryFilterIsContainedInAnUltrafilter