Lindenbaum's Theorem

Lindenbaum’s Theorem

Suppose $\Sigma$ is a consistent set of sentences in the language $\mathcal{L}$. Then $\Sigma$ can be extended to a maximal consistent set ${\Sigma }^{\ast }$ in the same language $\mathcal{L}$.

Proof Let ${\phi }_1,{\phi }_2,{\phi }_3,\dots$ be an enumeration of all sentences from $\mathcal{L}$. Define \begin{align} \Sigma_1 &= \Sigma, \notag \\ \Sigma_{n+1} &= \begin{cases} \Sigma_n \cup \{\varphi_n\} & \text{if } \Sigma_n \cup \{\varphi_n\} \text{ is consistent}, \\ \Sigma_n & \text{otherwise}, \end{cases} \\ \Sigma^* &= \bigcup_{n \geq 1} \Sigma_n. \notag \end{align} Each ${\Sigma }_n$ is consistent by construction. Hence ${\Sigma }^{\ast }$ is consistent since derivations are finite in length. To see that ${\Sigma }^{\ast }$ is maximal consistent, suppose ${\Sigma }^{\ast }\cup \{\phi \}$ is consistent. We want to show $\phi \in {\Sigma }^{\ast }$ . But $\phi ={\phi }_n$ for some $n$, and because ${\Sigma }_n\cup \{{\phi }_n\}$ must also be consistent since ${\Sigma }_n\subset {\Sigma }^{\ast }$ , it follows by construction that ${\phi }_n\in {\Sigma }_{n+1}$. Hence ${\phi }_n\in {\Sigma }^{\ast }$ and so ${\Sigma }^{\ast }$ is maximal consistent.

Remark

This proof contains an assumption as all sentences from $\mathcal{L}$ is countable.