Täydellisyyslause

Olkoot $A$ ja $B_{1},B_{2},\dots ,B_{m}$ propositiolauseita, ja olkoon propositiolausejoukko ${\mathcal {J}}=\{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})=\ldots =v(B_{m})=1$; niin propositiolauseella $A$ on luonnollinen päättely propositiolausejoukosta ${\mathcal {J}}$.

Todistus

Todistuksessa käytettäviä lemmoja

Olkoon ${\mathcal {K}}$ 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 ${\mathcal {K}}\vdash D$, niin $D\in {\mathcal {K}}$.

Todistus: Jos ${\mathcal {K}}\vdash D$ ja jos ${\mathcal {K}}\cup \{D\}$ on ristiriitainen, niin ${\mathcal {K}}\cup \{D\}\vdash C\land \lnot C$ jollakin propositiolauseella $C$ ja edelleen ${\mathcal {K}}\vdash \lnot D$. Täten ${\mathcal {K}}$ on ristiriitainen, mikä on ristiriita, joten ${\mathcal {K}}\cup \{D\}$ on ristiriidaton. Koska ${\mathcal {K}}$ on maksimaalisesti ristiriidaton, niin ${\mathcal {K}}={\mathcal {K}}\cup \{D\}$, joten $D\in {\mathcal {K}}$.

Lemma 2

$\lnot D\in {\mathcal {K}}$ jos ja vain jos $D\not \in {\mathcal {K}}$.

Todistus: Jos $\lnot D\in {\mathcal {K}}$ ja jos $D\in {\mathcal {K}}$, niin ${\mathcal {K}}\vdash \lnot D$ ja ${\mathcal {K}}\vdash D$. Koska ${\mathcal {K}}$ on ristiriidaton, niin ollaan saatu ristiriita, joten $D\not \in {\mathcal {K}}$. Jos taas $D\not \in {\mathcal {K}}$ ja jos ${\mathcal {K}}\cup \{\lnot D\}$ on ristiriitainen, niin saadaan ${\mathcal {K}}\cup \{\lnot D\}\vdash C\land \lnot C$ jollakin propositiolauseella $C$ ja edelleen ${\mathcal {K}}\vdash \lnot \lnot D$ ja ${\mathcal {K}}\vdash D$, joten lemman 1 nojalla $D\in {\mathcal {K}}$. Ollaan saatu ristiriita, joten ${\mathcal {K}}\cup \{\lnot D\}$ on ristiriidaton. Koska ${\mathcal {K}}$ on maksimaalisesti ristiriidaton, niin ${\mathcal {K}}={\mathcal {K}}\cup \{\lnot D\}$, joten $\lnot D\in {\mathcal {K}}$.

Lemma 3

$(D\land E)\in {\mathcal {K}}$ jos ja vain jos $D\in {\mathcal {K}}$ ja $E\in {\mathcal {K}}$.

Todistus: Jos $(D\land E)\in {\mathcal {K}}$, niin ${\mathcal {K}}\vdash D\land E$, josta saadaan ${\mathcal {K}}\vdash D$ ja ${\mathcal {K}}\vdash E$. Lemman 1 nojalla $D\in {\mathcal {K}}$ ja $E\in {\mathcal {K}}$. Jos taas $D\in {\mathcal {K}}$ ja $E\in {\mathcal {K}}$, niin ${\mathcal {K}}\vdash D$ ja ${\mathcal {K}}\vdash E$, mistä saadaan ${\mathcal {K}}\vdash D\land E$, joten lemman 1 nojalla $(D\land E)\in {\mathcal {K}}$.

Lemma 4

$(D\lor E)\in {\mathcal {K}}$ jos ja vain jos $D\in {\mathcal {K}}$ tai $E\in {\mathcal {K}}$.

Todistus: Jos $(D\lor E)\in {\mathcal {K}}$ ja jos $D\not \in {\mathcal {K}}$ ja $E\not \in {\mathcal {K}}$, niin lemman 2 nojalla $\lnot D\in {\mathcal {K}}$ ja $\lnot E\in {\mathcal {K}}$, mistä saadaan ${\mathcal {K}}\vdash (\lnot D\land \lnot E)$. Propositiolauseesta $\lnot D\land \lnot E$ voidaan tunnetusti päätellä propositiolause $\lnot (D\lor E)$. Täten ${\mathcal {K}}\vdash D\lor E$ ja ${\mathcal {K}}\vdash \lnot (D\lor E)$, mikä on ristiriita, joten $D\in {\mathcal {K}}$ tai $E\in {\mathcal {K}}$. Jos taas $D\in {\mathcal {K}}$ tai $E\in {\mathcal {K}}$, niin ${\mathcal {K}}\vdash D$ tai ${\mathcal {K}}\vdash E$. Saadaan joka tapauksessa ${\mathcal {K}}\vdash D\lor E$, joten lemman 1 nojalla $(D\lor E)\in {\mathcal {K}}$.

Lemma 5

$(D\to E)\in {\mathcal {K}}$ jos ja vain jos $D\not \in {\mathcal {K}}$ tai $E\in {\mathcal {K}}$.

Todistus: Jos $(D\to E)\in {\mathcal {K}}$, niin ${\mathcal {K}}\vdash D\to E$. Tunnetusti $\{D\to E\}\vdash \lnot D\lor E$, joten ${\mathcal {K}}\vdash \lnot D\lor E$. Lemman 1 nojalla $(\lnot D\lor E)\in {\mathcal {K}}$, joten lemman 4 ja lemman 2 nojalla $D\not \in {\mathcal {K}}$ tai $E\in {\mathcal {K}}$. Jos taas $D\not \in {\mathcal {K}}$ tai $E\in {\mathcal {K}}$, niin lemman 2 ja lemman 4 nojalla ${\mathcal {K}}\vdash \lnot D\lor E$. Tunnetusti $\{\lnot D\lor E\}\vdash D\to E$, joten ${\mathcal {K}}\vdash D\to E$. Lemman 1 nojalla $(D\to E)\in {\mathcal {K}}$.

Lemma 6

$(D\leftrightarrow E)\in {\mathcal {K}}$ jos ja vain jos joko $\{D,E\}\subset {\mathcal {K}}$ tai $\{\lnot D,\lnot E\}\subset {\mathcal {K}}$.

Todistus: Jos $(D\leftrightarrow E)\in {\mathcal {K}}$, niin ${\mathcal {K}}\vdash D\leftrightarrow E$. Tunnetusti $\{D\leftrightarrow E\}\vdash (D\land E)\lor (\lnot D\land \lnot E)$, joten ${\mathcal {K}}\vdash (D\land E)\lor (\lnot D\land \lnot E)$. Lemman 1 nojalla $(D\land E)\lor (\lnot D\land \lnot E)\in {\mathcal {K}}$, joten lemman 4 nojalla $(D\land E)\in {\mathcal {K}}$ tai $(\lnot D\land \lnot E)\in {\mathcal {K}}$. Lemman 3 nojalla $\{D,E\}\subset {\mathcal {K}}$ tai $\{\lnot D,\lnot E\}\subset {\mathcal {K}}$. Jos taas $\{D,E\}\subset {\mathcal {K}}$ tai $\{\lnot D,\lnot E\}\subset {\mathcal {K}}$, niin lemman 3 nojalla $(D\land E)\in {\mathcal {K}}$ tai $(\lnot D\land \lnot E)\in {\mathcal {K}}$. Lemman 4 nojalla $(D\land E)\lor (\lnot D\land \lnot E)\in {\mathcal {K}}$, joten ${\mathcal {K}}\vdash (D\land E)\lor (\lnot D\land \lnot E)$. Tunnetusti $(D\land E)\lor (\lnot D\land \lnot E)\vdash D\leftrightarrow E$, joten ${\mathcal {K}}\vdash D\leftrightarrow E$. Lemman 1 nojalla $(D\leftrightarrow E)\in {\mathcal {K}}$.

Propositiologiikan täydellisyyslauseen todistus

Olkoot $A$ ja $B_{1},B_{2},\dots ,B_{m}$ propositiolauseita, ja olkoon propositiolausejoukko ${\mathcal {J}}=\{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})=\ldots =v(B_{m})=1$; niin ${\mathcal {J}}\vdash A$.

Tehdään vastaoletus: kaikilla totuusjakaumilla $v$ pätee $v(A)=1$, kun $v(B_{1})=v(B_{2})=\ldots =v(B_{m})=1$; ja toisaalta ${\mathcal {J}}\nvdash A$.

Väite 1: ${\mathcal {J}}\cup \{\lnot A\}$ on ristiriidaton lausejoukko.

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

Koska ${\mathcal {J}}\cup \{\lnot A\}$ on ristiriidaton, niin sillä on Lindenbaumin lauseen nojalla maksimaalisesti ristiriidaton laajennus ${\mathcal {K}}$, jolla ${\mathcal {J}}\cup \{\lnot A\}\subset {\mathcal {K}}$.

Olkoon $v$ totuusjakauma siten, että kaikille atomilauseille $p_{0},p_{1},\dots$ pätee

$v(p_{n})={\begin{cases}1,\quad &{\text{jos}}\ p_{n}\in {\mathcal {K}}\\0,&{\text{jos}}\ p_{n}\not \in {\mathcal {K}}.\end{cases}}$

Väite 2: propositiolauseella $D$ pätee $v(D)=1$ jos ja vain jos $D\in {\mathcal {K}}$. 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 {\mathcal {K}}$.
2. $D=\lnot E$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in {\mathcal {K}}$, mikä on loogisesti yhtäpitävää sen kanssa, että $v(E)=0$ jos ja vain jos $E\not \in {\mathcal {K}}$. $v(D)=v(\lnot E)=1$ jos ja vain jos $v(E)=0$ jos ja vain jos $E\not \in {\mathcal {K}}$. Lemman 2 nojalla $E\not \in {\mathcal {K}}$ jos ja vain jos $\lnot E=D\in {\mathcal {K}}$.
3. $D=(E\land F)$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in {\mathcal {K}}$ ja että $v(F)=1$ jos ja vain jos $F\in {\mathcal {K}}$. $v(D)=v(E\land 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 {\mathcal {K}}$ ja $F\in {\mathcal {K}}$. Lemman 3 nojalla $E\in {\mathcal {K}}$ ja $F\in {\mathcal {K}}$ jos ja vain jos $(E\land F)=D\in {\mathcal {K}}$.
4. $D=(E\lor F)$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in {\mathcal {K}}$ ja että $v(F)=1$ jos ja vain jos $F\in {\mathcal {K}}$. $v(D)=v(E\lor F)=1$ jos ja vain jos $v(E)=1$ tai $v(F)=1$ jos ja vain jos $E\in {\mathcal {K}}$ tai $F\in {\mathcal {K}}$. Lemman 4 nojalla $E\in {\mathcal {K}}$ tai $F\in {\mathcal {K}}$ jos ja vain jos $(E\lor F)=D\in {\mathcal {K}}$.
5. $D=(E\to F)$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in {\mathcal {K}}$ ja että $v(F)=1$ jos ja vain jos $F\in {\mathcal {K}}$. $v(D)=v(E\to F)=1$ jos ja vain jos $v(E)=0$ tai $v(F)=1$ jos ja vain jos $E\not \in {\mathcal {K}}$ tai $F\in {\mathcal {K}}$. Lemman 5 nojalla $E\not \in {\mathcal {K}}$ tai $F\in {\mathcal {K}}$ jos ja vain jos $(E\to F)=D\in {\mathcal {K}}$.
6. $D=(E\leftrightarrow F)$. Induktio-oletus on, että $v(E)=1$ jos ja vain jos $E\in {\mathcal {K}}$ ja että $v(F)=1$ jos ja vain jos $F\in {\mathcal {K}}$. $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 {\mathcal {K}}$ ja $F\in {\mathcal {K}}$ tai $E\not \in {\mathcal {K}}$ ja $F\not \in {\mathcal {K}}$. Lemman 6 nojalla joko $E\in {\mathcal {K}}$ ja $F\in {\mathcal {K}}$ tai $E\not \in {\mathcal {K}}$ ja $F\not \in {\mathcal {K}}$ jos ja vain jos $(E\leftrightarrow F)=D\in {\mathcal {K}}$.

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

Koska $\lnot A\in {\mathcal {K}}$ ja koska $\{B_{1},B_{2},\dots ,B_{m}\}\subset {\mathcal {K}}$, niin väitteen 2 nojalla totuusjakaumalla $v$ pätee $v(\lnot A)=v(B_{1})=v(B_{2})=\ldots =v(B_{m})=1$ ja siis $v(A)=0$. Ollaan saatu ristiriita. Siis alkuperäinen väite eli propositiologiikan täydellisyyslause pätee. $\square$