Täydellisyyslause

Olkoot $A$ ja $B_1,B_2,\dots ,B_m$ propositiolauseita, ja olkoon propositiolausejoukko $𝒥=\{B_1,B_2,\dots ,B_m\}$. Propositiologiikan täydellisyyslause kuuluu seuraavasti: jos kaikilla totuusjakaumilla $v$ pätee $v(A)=1$, kun $v(B_1)=v(B_2)=\dots =v(B_m)=1$; niin propositiolauseella $A$ on luonnollinen päättely propositiolausejoukosta $𝒥$.

Todistus

Todistuksessa käytettäviä lemmoja

Olkoon $𝒦$ maksimaalisesti ristiriidaton propositiolausejoukko, ja olkoot $D$ ja $E$ propositiolauseita. Lemmojen todistuksissa sovelletaan luonnollisen päättelyn tunnettuja päättelysääntöjä ja tuloksia.

Lemma 1

Jos $𝒦⊢D$, niin $D\in 𝒦$.

Todistus: Jos $𝒦⊢D$ ja jos $𝒦\cup \{D\}$ on ristiriitainen, niin $𝒦\cup \{D\}⊢C\wedge \mathrm{\neg }C$ jollakin propositiolauseella $C$ ja edelleen $𝒦⊢\mathrm{\neg }D$. Täten $𝒦$ on ristiriitainen, mikä on ristiriita, joten $𝒦\cup \{D\}$ on ristiriidaton. Koska $𝒦$ on maksimaalisesti ristiriidaton, niin $𝒦=𝒦\cup \{D\}$, joten $D\in 𝒦$.

Lemma 2

$\mathrm{\neg }D\in 𝒦$ jos ja vain jos $D\in ̸𝒦$.

Todistus: Jos $\mathrm{\neg }D\in 𝒦$ ja jos $D\in 𝒦$, niin $𝒦⊢\mathrm{\neg }D$ ja $𝒦⊢D$. Koska $𝒦$ on ristiriidaton, niin ollaan saatu ristiriita, joten $D\in ̸𝒦$. Jos taas $D\in ̸𝒦$ ja jos $𝒦\cup \{\mathrm{\neg }D\}$ on ristiriitainen, niin saadaan $𝒦\cup \{\mathrm{\neg }D\}⊢C\wedge \mathrm{\neg }C$ jollakin propositiolauseella $C$ ja edelleen $𝒦⊢\mathrm{\neg }\mathrm{\neg }D$ ja $𝒦⊢D$, joten lemman 1 nojalla $D\in 𝒦$. Ollaan saatu ristiriita, joten $𝒦\cup \{\mathrm{\neg }D\}$ on ristiriidaton. Koska $𝒦$ on maksimaalisesti ristiriidaton, niin $𝒦=𝒦\cup \{\mathrm{\neg }D\}$, joten $\mathrm{\neg }D\in 𝒦$.

Lemma 3

$(D\wedge E)\in 𝒦$ jos ja vain jos $D\in 𝒦$ ja $E\in 𝒦$.

Todistus: Jos $(D\wedge E)\in 𝒦$, niin $𝒦⊢D\wedge E$, josta saadaan $𝒦⊢D$ ja $𝒦⊢E$. Lemman 1 nojalla $D\in 𝒦$ ja $E\in 𝒦$. Jos taas $D\in 𝒦$ ja $E\in 𝒦$, niin $𝒦⊢D$ ja $𝒦⊢E$, mistä saadaan $𝒦⊢D\wedge E$, joten lemman 1 nojalla $(D\wedge E)\in 𝒦$.

Lemma 4

$(D\vee E)\in 𝒦$ jos ja vain jos $D\in 𝒦$ tai $E\in 𝒦$.

Todistus: Jos $(D\vee E)\in 𝒦$ ja jos $D\in ̸𝒦$ ja $E\in ̸𝒦$, niin lemman 2 nojalla $\mathrm{\neg }D\in 𝒦$ ja $\mathrm{\neg }E\in 𝒦$, mistä saadaan $𝒦⊢(\mathrm{\neg }D\wedge \mathrm{\neg }E)$. Propositiolauseesta $\mathrm{\neg }D\wedge \mathrm{\neg }E$ voidaan tunnetusti päätellä propositiolause $\mathrm{\neg }(D\vee E)$. Täten $𝒦⊢D\vee E$ ja $𝒦⊢\mathrm{\neg }(D\vee E)$, mikä on ristiriita, joten $D\in 𝒦$ tai $E\in 𝒦$. Jos taas $D\in 𝒦$ tai $E\in 𝒦$, niin $𝒦⊢D$ tai $𝒦⊢E$. Saadaan joka tapauksessa $𝒦⊢D\vee E$, joten lemman 1 nojalla $(D\vee E)\in 𝒦$.

Lemma 5

$(D\to E)\in 𝒦$ jos ja vain jos $D\in ̸𝒦$ tai $E\in 𝒦$.

Todistus: Jos $(D\to E)\in 𝒦$, niin $𝒦⊢D\to E$. Tunnetusti $\{D\to E\}⊢\mathrm{\neg }D\vee E$, joten $𝒦⊢\mathrm{\neg }D\vee E$. Lemman 1 nojalla $(\mathrm{\neg }D\vee E)\in 𝒦$, joten lemman 4 ja lemman 2 nojalla $D\in ̸𝒦$ tai $E\in 𝒦$. Jos taas $D\in ̸𝒦$ tai $E\in 𝒦$, niin lemman 2 ja lemman 4 nojalla $𝒦⊢\mathrm{\neg }D\vee E$. Tunnetusti $\{\mathrm{\neg }D\vee E\}⊢D\to E$, joten $𝒦⊢D\to E$. Lemman 1 nojalla $(D\to E)\in 𝒦$.

Lemma 6

$(D\leftrightarrow E)\in 𝒦$ jos ja vain jos joko $\{D,E\}\subset 𝒦$ tai $\{\mathrm{\neg }D,\mathrm{\neg }E\}\subset 𝒦$.

Todistus: Jos $(D\leftrightarrow E)\in 𝒦$, niin $𝒦⊢D\leftrightarrow E$. Tunnetusti $\{D\leftrightarrow E\}⊢(D\wedge E)\vee (\mathrm{\neg }D\wedge \mathrm{\neg }E)$, joten $𝒦⊢(D\wedge E)\vee (\mathrm{\neg }D\wedge \mathrm{\neg }E)$. Lemman 1 nojalla $(D\wedge E)\vee (\mathrm{\neg }D\wedge \mathrm{\neg }E)\in 𝒦$, joten lemman 4 nojalla $(D\wedge E)\in 𝒦$ tai $(\mathrm{\neg }D\wedge \mathrm{\neg }E)\in 𝒦$. Lemman 3 nojalla $\{D,E\}\subset 𝒦$ tai $\{\mathrm{\neg }D,\mathrm{\neg }E\}\subset 𝒦$. Jos taas $\{D,E\}\subset 𝒦$ tai $\{\mathrm{\neg }D,\mathrm{\neg }E\}\subset 𝒦$, niin lemman 3 nojalla $(D\wedge E)\in 𝒦$ tai $(\mathrm{\neg }D\wedge \mathrm{\neg }E)\in 𝒦$. Lemman 4 nojalla $(D\wedge E)\vee (\mathrm{\neg }D\wedge \mathrm{\neg }E)\in 𝒦$, joten $𝒦⊢(D\wedge E)\vee (\mathrm{\neg }D\wedge \mathrm{\neg }E)$. Tunnetusti $(D\wedge E)\vee (\mathrm{\neg }D\wedge \mathrm{\neg }E)⊢D\leftrightarrow E$, joten $𝒦⊢D\leftrightarrow E$. Lemman 1 nojalla $(D\leftrightarrow E)\in 𝒦$.

Propositiologiikan täydellisyyslauseen todistus

Olkoot $A$ ja $B_1,B_2,\dots ,B_m$ propositiolauseita, ja olkoon propositiolausejoukko $𝒥=\{B_1,B_2,\dots ,B_m\}$. Propositiologiikan täydellisyyslause: jos kaikilla totuusjakaumilla $v$ pätee $v(A)=1$, kun $v(B_1)=v(B_2)=\dots =v(B_m)=1$; niin $𝒥⊢A$.

Tehdään vastaoletus: kaikilla totuusjakaumilla $v$ pätee $v(A)=1$, kun $v(B_1)=v(B_2)=\dots =v(B_m)=1$; ja toisaalta $𝒥⊬A$.

Väite 1: $𝒥\cup \{\mathrm{\neg }A\}$ on ristiriidaton lausejoukko.

Tehdään väitteen 1 vastaoletus: $𝒥\cup \{\mathrm{\neg }A\}$ on ristiriitainen. Tällöin jollakin propositiolauseella $C$ pätee $𝒥\cup \{\mathrm{\neg }A\}⊢C\wedge \mathrm{\neg }C$. Propositiologiikan tunnettuja päättelysääntöjä soveltamalla saadaan $𝒥\cup \{\mathrm{\neg }A\}⊢\mathrm{\neg }\mathrm{\neg }A$ ja edelleen $𝒥⊢A$. Ollaan päädytty ristiriitaan. Täten väite 1 pätee.

Koska $𝒥\cup \{\mathrm{\neg }A\}$ on ristiriidaton, niin sillä on Lindenbaumin lauseen nojalla maksimaalisesti ristiriidaton laajennus $𝒦$, jolla $𝒥\cup \{\mathrm{\neg }A\}\subset 𝒦$.

Olkoon $v$ totuusjakauma siten, että kaikille atomilauseille $p_0,p_1,\dots$ pätee

$v(p_n)=\{\begin{array}{cc}1,& \text{jos}{p}_n\in 𝒦\\ 0,& \text{jos}{p}_n\in ̸𝒦.\end{array}$

Väite 2: propositiolauseella $D$ pätee $v(D)=1$ jos ja vain jos $D\in 𝒦$. Todistetaan väite 2 induktiolla propositiolauseen $D$ rakenteen suhteen.

1. $D=p_n$. Totuusjakauman $v$ määritelmän nojalla $v(D)=v(p_n)=1$ jos ja vain jos $p_n=D\in 𝒦$.
2. $D=\mathrm{\neg }E$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in 𝒦$, mikä on loogisesti yhtäpitävää sen kanssa, että $v(E)=0$ jos ja vain jos $E\in ̸𝒦$. $v(D)=v(\mathrm{\neg }E)=1$ jos ja vain jos $v(E)=0$ jos ja vain jos $E\in ̸𝒦$. Lemman 2 nojalla $E\in ̸𝒦$ jos ja vain jos $\mathrm{\neg }E=D\in 𝒦$.
3. $D=(E\wedge F)$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in 𝒦$ ja että $v(F)=1$ jos ja vain jos $F\in 𝒦$. $v(D)=v(E\wedge F)=1$ jos ja vain jos $v(E)=v(F)=1$. Induktio-oletuksen nojalla $v(E)=v(F)=1$ jos ja vain jos $E\in 𝒦$ ja $F\in 𝒦$. Lemman 3 nojalla $E\in 𝒦$ ja $F\in 𝒦$ jos ja vain jos $(E\wedge F)=D\in 𝒦$.
4. $D=(E\vee F)$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in 𝒦$ ja että $v(F)=1$ jos ja vain jos $F\in 𝒦$. $v(D)=v(E\vee F)=1$ jos ja vain jos $v(E)=1$ tai $v(F)=1$ jos ja vain jos $E\in 𝒦$ tai $F\in 𝒦$. Lemman 4 nojalla $E\in 𝒦$ tai $F\in 𝒦$ jos ja vain jos $(E\vee F)=D\in 𝒦$.
5. $D=(E\to F)$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in 𝒦$ ja että $v(F)=1$ jos ja vain jos $F\in 𝒦$. $v(D)=v(E\to F)=1$ jos ja vain jos $v(E)=0$ tai $v(F)=1$ jos ja vain jos $E\in ̸𝒦$ tai $F\in 𝒦$. Lemman 5 nojalla $E\in ̸𝒦$ tai $F\in 𝒦$ jos ja vain jos $(E\to F)=D\in 𝒦$.
6. $D=(E\leftrightarrow F)$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in 𝒦$ ja että $v(F)=1$ jos ja vain jos $F\in 𝒦$. $v(D)=v(E\leftrightarrow F)=1$ jos ja vain jos joko $v(E)=v(F)=1$ tai $v(E)=v(F)=0$ jos ja vain jos joko $E\in 𝒦$ ja $F\in 𝒦$ tai $E\in ̸𝒦$ ja $F\in ̸𝒦$. Lemman 6 nojalla joko $E\in 𝒦$ ja $F\in 𝒦$ tai $E\in ̸𝒦$ ja $F\in ̸𝒦$ jos ja vain jos $(E\leftrightarrow F)=D\in 𝒦$.

Täten väite 2 todistettiin päteväksi.

Koska $\mathrm{\neg }A\in 𝒦$ ja koska $\{B_1,B_2,\dots ,B_m\}\subset 𝒦$, niin väitteen 2 nojalla totuusjakaumalla $v$ pätee $v(\mathrm{\neg }A)=v(B_1)=v(B_2)=\dots =v(B_m)=1$ ja siis $v(A)=0$. Ollaan saatu ristiriita. Siis alkuperäinen väite eli propositiologiikan täydellisyyslause pätee. $◻$