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 set is consistent (vacuously).

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:

First Proof. Suppose $\Delta$ is consistent. Let $P$ be the partially ordered set of all consistent supersets of $\Delta$, ordered by inclusion $\subseteq$. If $\mathcal{C}$ is a chain of elements in $P$, then $\bigcup\mathcal{C}$ is consistent by the lemma above, so $\bigcup\mathcal{C}\in P$ as each element of $\mathcal{C}$ is a superset of $\Delta$. By Zorn’s lemma, $P$ has a maximal element, call it $\Gamma$. To see that $\Gamma$ is maximally consistent, suppose $\Gamma$ is not maximal. Then there is a wff $A$ such that $\Gamma\not\vdash A$ and $\Gamma\not\vdash\neg A$, the first of which implies that $A\notin\Gamma$, and the second of which implies that $\Gamma\cup\{A\}$ is consistent, and therefore in $P$. The two imply that $\Gamma\cup\{A\}$ is a consistent proper superset of $\Gamma$, contradicting the maximality of $\Gamma$ in $P$. Therefore, $\Gamma$ is maximally consistent. $\square$

Second Proof. Let $A_{1},\ldots,A_{n},\ldots$ 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 $\Delta$ be a consistent set of wff’s. Define sets $\Gamma_{1},\Gamma_{2},\ldots,\Gamma$ of wff’s inductively as follows:

First, notice that each $\Gamma_{i}$ is consistent. This is done by induction on $i$. By assumption, the case is true when $i=1$. Now, suppose $\Gamma_{n}$ is consistent. Then its deductive closure Ded$(\Gamma_{n})$ is also consistent. If $\Gamma_{n}\vdash A_{n}$, then clearly $\Gamma_{n}\cup\{A_{n}\}$ is consistent since it is a subset of Ded$(\Gamma)$. Otherwise, $\Gamma_{n}\not\vdash A_{n}$, or $\Gamma_{n}\not\vdash\neg\neg A_{n}$ by the substitution theorem, and therefore $\Gamma_{n}\cup\{\neg A_{n}\}$ by one of the properties of consistency (see here). In either case, $\Gamma_{{n+1}}$ is consistent.

Next, $\Gamma$ is maximally consistent. $\Gamma$ is consistent because, by the lemma above, it is the union of a chain of consistent sets. To see that $\Gamma$ is maximal, pick any wff $A$. Then $A$ is some $A_{n}$ in the enumerated list of all wff’s. Therefore, either $A\in\Gamma_{{n+1}}$ or $\neg A\in\Gamma_{{n+1}}$. Since $\Gamma_{{n+1}}\subseteq\Gamma$, we have $A\in\Gamma$ or $\neg A\in\Gamma$, which implies that $\Gamma$ is maximal (see here). $\square$.

Given a logic $L$, let $W_{L}$ be the set of all maximally $L$-consistent sets. By Lindebaum’s lemma, $W_{L}\neq\varnothing$. We record two useful corollaries:

• For any consistent set $\Delta$, Ded$(\Delta)=\bigcap\{\Gamma\in W_{L}\mid\Delta\subseteq\Gamma\}$.

• $L=\bigcap W_{L}$.