様相論理のLindenbaum補題
主張
任意の$ \Lambda無矛盾な集合$ \Gammaに対して，ある極大$ \Lambda無矛盾$ \Gamma^+が存在し，$ \Gamma \sube \Gamma^+．
証明
$ \Gamma^+を次のように構成する．
1. 論理式の加算無限個の列挙$ \{\varphi_n\}_{n \in \omega}
2. 論理式の集合の加算無限個の列挙$ \{\Gamma_n\}_{n \in \omega}
$ \Gamma_0 \coloneqq \Gamma
$ \Gamma_{n+1} \coloneqq \begin{cases} \Gamma_{n} \cup \{\varphi_n\} & \text{($\Gamma_{n} \cup \{\varphi_n\}$ is $\Lambda$-consistent)} \\ \Gamma_{n} \cup \{\lnot \varphi_n\} & \text{($\Gamma_{n} \cup \{\varphi_n\}$ is $\Lambda$-inconsistent)} \end{cases}
ただし任意の$ 0 \leq i \leq n-1で$ \Gamma_{i} \sube \Gamma_{i+1}とする．
このとき，明らかに$ \Gamma_0 \sube \Gamma_1 \sube \cdots \Gamma_{n-1} \sube \Gamma_{n} \sube \Gamma_{n+1}．
3. 任意の$ n \in \omegaで$ \Gamma_nは$ \Lambda無矛盾である．
$ \Gamma_n \cup \{ \varphi_n \}が$ \Lambda無矛盾なら，$ \Gamma_{n+1} \coloneqq \Gamma_n \cup \{ \lnot \varphi_n \}は自明に$ \Lambda無矛盾である．
$ \Gamma_n \cup \{ \varphi_n \}が$ \Lambda矛盾なら，$ \Gamma_{n+1} \coloneqq \Gamma_n \cup \{ \lnot \varphi_n \}は$ \Lambda無矛盾である．
1. 帰納法の前提として，$ \Gamma_nは$ \Lambda無矛盾とする．
2. $ \vdash_\Lambda \left( \varphi_n \land \bigwedge \Delta \right) \to \botとなる，ある$ \Delta \sube \Gamma_nが存在する．（$ \Lambda矛盾の定義より．）
正確には，ある$ \Delta' \sube \Gamma_{n} \cup \{\varphi_n\}で$ \vdash_\Lambda \bigwedge \Delta' \to \botだが，$ \Gamma_nの任意部分集合だけでは$ \botが導出されないことは$ \Lambda無矛盾性よりわかっているため，必ず$ \varphi_nが必要となる．
3. 背理法より，$ \Gamma_n \cup \{ \lnot \varphi_n \}が$ \Lambda矛盾と仮定する．
4. $ \vdash_\Lambda \left( \lnot \varphi_n \land \bigwedge \Sigma \right) \to \botとなる，ある$ \Sigma \sube \Gamma_nが存在する．（$ \Gamma_nが$ \Lambda無矛盾，$ \Lambda矛盾の定義より．）
2と同様．
5. 命題論理の推論より，$ \vdash_\Lambda \land \bigwedge \Sigma \to \varphi_n．
6. 2と5より，$ \vdash \left( \bigwedge \Sigma \land \bigwedge \Delta \right) \to \bot．整理すれば$ \vdash \left( \bigwedge (\Sigma \cap \Delta) \right) \to \bot
7. $ \Sigma \cup \Delta \sube \Gamma_nである．
8. 6と7より，$ \Gamma_nが$ \Lambda矛盾する．しかし前提1より破綻する．したがって3がおかしくて，$ \Gamma_n \cup \{\lnot \varphi \}は$ \Lambda無矛盾である．
$ \Gamma_0 \coloneqq \Gammaは前提より無矛盾である．
よって再帰的に$ \Gamma_nが$ \Lambda無矛盾．
4. $ \Gamma^+ \coloneqq \bigcup_{n \in \omega} \Gamma_{n}とする．
明らかに，$ \Gamma^+は極大$ \Lambda無矛盾．
$ \Gamma^+は$ \Lambda無矛盾．
仮に$ \Lambda矛盾とすると，ある$ \Delta \sube \Gamma^+で$ \bigwedge \Delta \to \bot \in \Gamma^+，ところが明らかに$ \Delta \sube \Gamma_nであるので$ \Gamma_nが$ \Lambda矛盾していることになり，前提に反する．
任意の論理式$ \varphi_nについて$ \varphi_n \in \Gamma^+または$ \lnot\varphi_n \in \Gamma^+
明らかに$ \Gamma \sube \Gamma^+．（$ \Gamma \eqqcolon \Gamma_0 \sube \Gamma_0 \cup \Gamma_1 \cup \cdots \coloneqq \Gamma^+）