Lindenbaumin lause

Lindenbaumin lause on propositiologiikassa seuraavanlainen: jos $𝒥$ on ristiriidaton propositiolausejoukko, niin $𝒥$ voidaan laajentaa maksimaalisesti ristiriidattomaksi propositiolausejoukoksi $𝒦$, jolla $𝒥\subset 𝒦$.

Määritelmä: propositiolausejoukko $ℛ$ on ristiriitainen, jos $ℛ⊢B\wedge \mathrm{\neg }B$ jollakin propositiolauseella $B$.

Määritelmä: propositiolausejoukko $𝒰$ on maksimaalisesti ristiriidaton, jos $𝒰$ on ristiriidaton ja jokainen propositiolausejoukko $ℒ$, jolle pätee $𝒰\subset ℒ$ ja $ℒ\setminus 𝒰\ne \mathrm{\varnothing }$, on ristiriitainen.

Todistus

Olkoon $𝒥$ ristiriidaton propositiolausejoukko ja olkoon kaikkien propositiolauseiden joukko $𝒫=\{A_0,A_1,A_2,\dots \}$. Määritellään joukot ${𝒥}_0\subset {𝒥}_1\subset \dots \subset {𝒥}_n\subset \dots$ induktiivisesti, kun $n\in \mathbb{N}\cup \{0\}$: ${𝒥}_0=𝒥$ ja

${𝒥}_{n+1}=\{\begin{array}{cc}{𝒥}_n\cup \{A_n\},& \text{kun}{𝒥}_n\cup \{A_n\}\text{on ristiriidaton}\\ {𝒥}_n,& \text{muussa tapauksessa.}\end{array}$

Induktiolla voidaan osoittaa, että ${𝒥}_n$ on ristiriidaton kaikilla $n$.

Olkoon $𝒦=\bigcup _{n=0}^{\mathrm{\infty }}{𝒥}_n$.

Väite: $𝒦$ ristiriidaton.

Tehdään vastaoletus: $𝒦$ on ristiriitainen, joten $𝒦⊢B\wedge \mathrm{\neg }B$ jollakin propositiolauseella $B$. Nyt on olemassa äärellinen propositiolauseiden joukko $𝒬=\{C_1,C_2,\dots ,C_m\}$ siten, että $𝒬⊢B\wedge \mathrm{\neg }B$ ja $𝒬\subset 𝒦$. Olkoon $C_i\in {𝒥}_{n_i}$ kaikilla $i=1,2,\dots ,m$ ja olkoon $n=\max \{n_1,n_2,\dots ,n_m\}$. Koska $𝒬\subset {𝒥}_n$, niin ${𝒥}_n⊢B\wedge \mathrm{\neg }B$, joten ${𝒥}_n$ on ristiriitainen. Ollaan päädytty ristiriitaan. Täten $𝒦$ on ristiriidaton.

Väite: $𝒦$ on maksimaalisesti ristiriidaton.

Tehdään vastaoletus: Olkoon $ℒ$ on ristiriidaton propositiolausejoukko siten, että $𝒦\subset ℒ$, $ℒ\setminus 𝒦\ne \mathrm{\varnothing }$ ja $ℒ=𝒦\cup \{A_n\}$, missä $A_n\in 𝒫$. Nyt $A_n\in ̸𝒦$, joten ${𝒥}_n\cup \{A_n\}$ on ristiriitainen. Koska ${𝒥}_n\cup \{A_n\}\subset 𝒦\cup \{A_n\}\subset ℒ$, niin $ℒ$ on ristiriitainen. Ollaan päädytty ristiriitaan. Täten $𝒦$ on maksimaalisesti ristiriidaton.

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