Täydellisyyslause

Olkoot ${\displaystyle A}$ ja ${\displaystyle B_{1},B_{2},\dots ,B_{m}}$ propositiolauseita, ja olkoon propositiolausejoukko ${\displaystyle {\mathcal {J}}=\{B_{1},B_{2},\dots ,B_{m}\}}$. Propositiologiikan täydellisyyslause kuuluu seuraavasti: jos kaikilla totuusjakaumilla ${\displaystyle v}$ pätee ${\displaystyle v(A)=1}$, kun ${\displaystyle v(B_{1})=v(B_{2})=\ldots =v(B_{m})=1}$; niin propositiolauseella ${\displaystyle A}$ on luonnollinen päättely propositiolausejoukosta ${\displaystyle {\mathcal {J}}}$.

Todistus

Todistuksessa käytettäviä lemmoja

Olkoon ${\displaystyle {\mathcal {K}}}$ maksimaalisesti ristiriidaton propositiolausejoukko, ja olkoot ${\displaystyle D}$ ja ${\displaystyle E}$ propositiolauseita. Lemmojen todistuksissa sovelletaan luonnollisen päättelyn tunnettuja päättelysääntöjä ja tuloksia.

Lemma 1

Jos ${\displaystyle {\mathcal {K}}\vdash D}$, niin ${\displaystyle D\in {\mathcal {K}}}$.

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

Lemma 2

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

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

Lemma 3

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

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

Lemma 4

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

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

Lemma 5

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

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

Lemma 6

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

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

Propositiologiikan täydellisyyslauseen todistus

Olkoot ${\displaystyle A}$ ja ${\displaystyle B_{1},B_{2},\dots ,B_{m}}$ propositiolauseita, ja olkoon propositiolausejoukko ${\displaystyle {\mathcal {J}}=\{B_{1},B_{2},\dots ,B_{m}\}}$. Propositiologiikan täydellisyyslause: jos kaikilla totuusjakaumilla ${\displaystyle v}$ pätee ${\displaystyle v(A)=1}$, kun ${\displaystyle v(B_{1})=v(B_{2})=\ldots =v(B_{m})=1}$; niin ${\displaystyle {\mathcal {J}}\vdash A}$.

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

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

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

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

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

${\displaystyle 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 ${\displaystyle D}$ pätee ${\displaystyle v(D)=1}$ jos ja vain jos ${\displaystyle D\in {\mathcal {K}}}$. Todistetaan väite 2 induktiolla propositiolauseen ${\displaystyle D}$ rakenteen suhteen.

1. ${\displaystyle D=p_{n}}$. Totuusjakauman ${\displaystyle v}$ määritelmän nojalla ${\displaystyle v(D)=v(p_{n})=1}$ jos ja vain jos ${\displaystyle p_{n}=D\in {\mathcal {K}}}$.
2. ${\displaystyle D=\lnot E}$. Induktio-oletus on, että ${\displaystyle v(E)=1}$ jos ja vain jos ${\displaystyle E\in {\mathcal {K}}}$, mikä on loogisesti yhtäpitävää sen kanssa, että ${\displaystyle v(E)=0}$ jos ja vain jos ${\displaystyle E\not \in {\mathcal {K}}}$. ${\displaystyle v(D)=v(\lnot E)=1}$ jos ja vain jos ${\displaystyle v(E)=0}$ jos ja vain jos ${\displaystyle E\not \in {\mathcal {K}}}$. Lemman 2 nojalla ${\displaystyle E\not \in {\mathcal {K}}}$ jos ja vain jos ${\displaystyle \lnot E=D\in {\mathcal {K}}}$.
3. ${\displaystyle D=(E\land F)}$. Induktio-oletus on, että ${\displaystyle v(E)=1}$ jos ja vain jos ${\displaystyle E\in {\mathcal {K}}}$ ja että ${\displaystyle v(F)=1}$ jos ja vain jos ${\displaystyle F\in {\mathcal {K}}}$. ${\displaystyle v(D)=v(E\land F)=1}$ jos ja vain jos ${\displaystyle v(E)=v(F)=1}$. Induktio-oletuksen nojalla ${\displaystyle v(E)=v(F)=1}$ jos ja vain jos ${\displaystyle E\in {\mathcal {K}}}$ ja ${\displaystyle F\in {\mathcal {K}}}$. Lemman 3 nojalla ${\displaystyle E\in {\mathcal {K}}}$ ja ${\displaystyle F\in {\mathcal {K}}}$ jos ja vain jos ${\displaystyle (E\land F)=D\in {\mathcal {K}}}$.
4. ${\displaystyle D=(E\lor F)}$. Induktio-oletus on, että ${\displaystyle v(E)=1}$ jos ja vain jos ${\displaystyle E\in {\mathcal {K}}}$ ja että ${\displaystyle v(F)=1}$ jos ja vain jos ${\displaystyle F\in {\mathcal {K}}}$. ${\displaystyle v(D)=v(E\lor F)=1}$ jos ja vain jos ${\displaystyle v(E)=1}$ tai ${\displaystyle v(F)=1}$ jos ja vain jos ${\displaystyle E\in {\mathcal {K}}}$ tai ${\displaystyle F\in {\mathcal {K}}}$. Lemman 4 nojalla ${\displaystyle E\in {\mathcal {K}}}$ tai ${\displaystyle F\in {\mathcal {K}}}$ jos ja vain jos ${\displaystyle (E\lor F)=D\in {\mathcal {K}}}$.
5. ${\displaystyle D=(E\to F)}$. Induktio-oletus on, että ${\displaystyle v(E)=1}$ jos ja vain jos ${\displaystyle E\in {\mathcal {K}}}$ ja että ${\displaystyle v(F)=1}$ jos ja vain jos ${\displaystyle F\in {\mathcal {K}}}$. ${\displaystyle v(D)=v(E\to F)=1}$ jos ja vain jos ${\displaystyle v(E)=0}$ tai ${\displaystyle v(F)=1}$ jos ja vain jos ${\displaystyle E\not \in {\mathcal {K}}}$ tai ${\displaystyle F\in {\mathcal {K}}}$. Lemman 5 nojalla ${\displaystyle E\not \in {\mathcal {K}}}$ tai ${\displaystyle F\in {\mathcal {K}}}$ jos ja vain jos ${\displaystyle (E\to F)=D\in {\mathcal {K}}}$.
6. ${\displaystyle D=(E\leftrightarrow F)}$. Induktio-oletus on, että ${\displaystyle v(E)=1}$ jos ja vain jos ${\displaystyle E\in {\mathcal {K}}}$ ja että ${\displaystyle v(F)=1}$ jos ja vain jos ${\displaystyle F\in {\mathcal {K}}}$. ${\displaystyle v(D)=v(E\leftrightarrow F)=1}$ jos ja vain jos joko ${\displaystyle v(E)=v(F)=1}$ tai ${\displaystyle v(E)=v(F)=0}$ jos ja vain jos joko ${\displaystyle E\in {\mathcal {K}}}$ ja ${\displaystyle F\in {\mathcal {K}}}$ tai ${\displaystyle E\not \in {\mathcal {K}}}$ ja ${\displaystyle F\not \in {\mathcal {K}}}$. Lemman 6 nojalla joko ${\displaystyle E\in {\mathcal {K}}}$ ja ${\displaystyle F\in {\mathcal {K}}}$ tai ${\displaystyle E\not \in {\mathcal {K}}}$ ja ${\displaystyle F\not \in {\mathcal {K}}}$ jos ja vain jos ${\displaystyle (E\leftrightarrow F)=D\in {\mathcal {K}}}$.

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

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