Lindenbaumin lause

Lindenbaumin lause on propositiologiikassa seuraavanlainen: jos ${\mathcal {J}}$ on ristiriidaton propositiolausejoukko, niin ${\mathcal {J}}$ voidaan laajentaa maksimaalisesti ristiriidattomaksi propositiolausejoukoksi ${\mathcal {K}}$, jolla ${\mathcal {J}}\subset {\mathcal {K}}$.

Määritelmä: propositiolausejoukko ${\mathcal {R}}$ on ristiriitainen, jos ${\mathcal {R}}\vdash B\land \lnot B$ jollakin propositiolauseella $B$.

Määritelmä: propositiolausejoukko ${\mathcal {U}}$ on maksimaalisesti ristiriidaton, jos ${\mathcal {U}}$ on ristiriidaton ja jokainen propositiolausejoukko ${\mathcal {L}}$, jolle pätee ${\mathcal {U}}\subset {\mathcal {L}}$ ja ${\mathcal {L}}\setminus {\mathcal {U}}\neq \emptyset$, on ristiriitainen.

Todistus

Olkoon ${\mathcal {J}}$ ristiriidaton propositiolausejoukko ja olkoon kaikkien propositiolauseiden joukko ${\mathcal {P}}=\{A_{0},A_{1},A_{2},\dots \}$. Määritellään joukot ${\mathcal {J}}_{0}\subset {\mathcal {J}}_{1}\subset \ldots \subset {\mathcal {J}}_{n}\subset \ldots$ induktiivisesti, kun $n\in \mathbb {N} \cup \{0\}$: ${\mathcal {J}}_{0}={\mathcal {J}}$ ja

${\mathcal {J}}_{n+1}={\begin{cases}{\mathcal {J}}_{n}\cup \{A_{n}\},\quad &{\text{kun}}\ {\mathcal {J}}_{n}\cup \{A_{n}\}\ {\text{on ristiriidaton}}\\{\mathcal {J}}_{n},\quad &{\text{muussa tapauksessa.}}\end{cases}}$

Induktiolla voidaan osoittaa, että ${\mathcal {J}}_{n}$ on ristiriidaton kaikilla $n$.

Olkoon ${\mathcal {K}}=\displaystyle {\bigcup _{n=0}^{\infty }{\mathcal {J}}_{n}}$.

Väite: ${\mathcal {K}}$ ristiriidaton.

Tehdään vastaoletus: ${\mathcal {K}}$ on ristiriitainen, joten ${\mathcal {K}}\vdash B\land \lnot B$ jollakin propositiolauseella $B$. Nyt on olemassa äärellinen propositiolauseiden joukko ${\mathcal {Q}}=\{C_{1},C_{2},\dots ,C_{m}\}$ siten, että ${\mathcal {Q}}\vdash B\land \lnot B$ ja ${\mathcal {Q}}\subset {\mathcal {K}}$. Olkoon $C_{i}\in {\mathcal {J}}_{n_{i}}$ kaikilla $i=1,2,\dots ,m$ ja olkoon $n=\max\{n_{1},n_{2},\dots ,n_{m}\}$. Koska ${\mathcal {Q}}\subset {\mathcal {J}}_{n}$, niin ${\mathcal {J}}_{n}\vdash B\land \lnot B$, joten ${\mathcal {J}}_{n}$ on ristiriitainen. Ollaan päädytty ristiriitaan. Täten ${\mathcal {K}}$ on ristiriidaton.

Väite: ${\mathcal {K}}$ on maksimaalisesti ristiriidaton.

Tehdään vastaoletus: Olkoon ${\mathcal {L}}$ on ristiriidaton propositiolausejoukko siten, että ${\mathcal {K}}\subset {\mathcal {L}}$, ${\mathcal {L}}\setminus {\mathcal {K}}\neq \emptyset$ ja ${\mathcal {L}}={\mathcal {K}}\cup \{A_{n}\}$, missä $A_{n}\in {\mathcal {P}}$. Nyt $A_{n}\not \in {\mathcal {K}}$, joten ${\mathcal {J}}_{n}\cup \{A_{n}\}$ on ristiriitainen. Koska ${\mathcal {J}}_{n}\cup \{A_{n}\}\subset {\mathcal {K}}\cup \{A_{n}\}\subset {\mathcal {L}}$, niin ${\mathcal {L}}$ on ristiriitainen. Ollaan päädytty ristiriitaan. Täten ${\mathcal {K}}$ on maksimaalisesti ristiriidaton.

Siis mielivaltaiselle, ristiriidattomalle propositiolausejoukolle on olemassa laajennus, joka on maksimaalisesti ristiriidaton propositiolausejoukko. $\square$