Täydellisyyslause

Olkoot formula_1 ja formula_2 propositiolauseita, ja olkoon propositiolausejoukko formula_3. 
"Propositiologiikan täydellisyyslause" kuuluu seuraavasti: jos kaikilla totuusjakaumilla formula_4 pätee formula_5, kun formula_6; niin propositiolauseella formula_1 on luonnollinen päättely propositiolausejoukosta formula_8. 
Todistus.
Todistuksessa käytettäviä lemmoja.
Olkoon formula_9 maksimaalisesti ristiriidaton propositiolausejoukko, ja olkoot formula_10 ja formula_11 propositiolauseita. Lemmojen todistuksissa sovelletaan luonnollisen päättelyn tunnettuja päättelysääntöjä ja tuloksia. 
Lemma 1.
Jos formula_12, niin formula_13. 
Todistus: Jos formula_12 ja jos formula_15 on ristiriitainen, niin formula_16 jollakin propositiolauseella formula_17 ja edelleen formula_18. Täten formula_9 on ristiriitainen, mikä on ristiriita, joten formula_15 on ristiriidaton. Koska formula_9 on maksimaalisesti ristiriidaton, niin formula_22, joten formula_13. 
Lemma 2.
formula_24 jos ja vain jos formula_25. 
Todistus: Jos formula_24 ja jos formula_13, niin formula_18 ja formula_12. Koska formula_9 on ristiriidaton, niin ollaan saatu ristiriita, joten formula_25. 
Jos taas formula_25 ja jos formula_33 on ristiriitainen, niin saadaan formula_34 jollakin propositiolauseella formula_17 ja edelleen formula_36 ja formula_12, joten lemman 1 nojalla formula_13. Ollaan saatu ristiriita, joten formula_33 on ristiriidaton. Koska formula_9 on maksimaalisesti ristiriidaton, niin formula_41, joten formula_24. 
Lemma 3.
formula_43 jos ja vain jos formula_13 ja formula_45. 
Todistus: Jos formula_43, niin formula_47, josta saadaan formula_12 ja formula_49. Lemman 1 nojalla formula_13 ja formula_45. 
Jos taas formula_13 ja formula_45, niin formula_12 ja formula_49, mistä saadaan formula_47, joten lemman 1 nojalla formula_43. 
Lemma 4.
formula_58 jos ja vain jos formula_13 tai formula_45. 
Todistus: Jos formula_58 ja jos formula_25 ja formula_63, niin lemman 2 nojalla formula_24 ja formula_65, mistä saadaan formula_66. Propositiolauseesta formula_67 voidaan tunnetusti päätellä propositiolause formula_68. Täten formula_69 ja formula_70, mikä on ristiriita, joten formula_13 tai formula_45. 
Jos taas formula_13 tai formula_45, niin formula_12 tai formula_49. Saadaan joka tapauksessa formula_69, joten lemman 1 nojalla formula_58. 
Lemma 5.
formula_79 jos ja vain jos formula_25 tai formula_45.
Todistus: Jos formula_79, niin formula_83. Tunnetusti formula_84, joten formula_85. Lemman 1 nojalla formula_86, joten lemman 4 ja lemman 2 nojalla formula_25 tai formula_45. 
Jos taas formula_25 tai formula_45, niin lemman 2 ja lemman 4 nojalla formula_85. Tunnetusti formula_92, joten formula_83. Lemman 1 nojalla formula_79. 
Lemma 6.
formula_95 jos ja vain jos joko formula_96 tai formula_97. 
Todistus: Jos formula_95, niin formula_99. Tunnetusti formula_100, joten formula_101. Lemman 1 nojalla formula_102, joten lemman 4 nojalla formula_43 tai formula_104. Lemman 3 nojalla formula_96 tai formula_97. 
Jos taas formula_96 tai formula_97, niin lemman 3 nojalla formula_43 tai formula_104. Lemman 4 nojalla formula_102, joten formula_101. Tunnetusti formula_113, joten formula_99. Lemman 1 nojalla formula_95. 
Propositiologiikan täydellisyyslauseen todistus.
Olkoot formula_1 ja formula_2 propositiolauseita, ja olkoon propositiolausejoukko 
formula_3. "Propositiologiikan täydellisyyslause": jos kaikilla totuusjakaumilla formula_4 pätee formula_5, kun formula_6; niin formula_122. 
Tehdään vastaoletus: kaikilla totuusjakaumilla formula_4 pätee formula_5, kun formula_6; ja toisaalta formula_126. 
Väite 1: formula_127 on ristiriidaton lausejoukko. 
Tehdään väitteen 1 vastaoletus: formula_127 on ristiriitainen. Tällöin jollakin propositiolauseella formula_17 pätee formula_130. Propositiologiikan tunnettuja päättelysääntöjä soveltamalla saadaan formula_131 ja edelleen formula_122. Ollaan päädytty ristiriitaan. Täten väite 1 pätee. 
Koska formula_127 on ristiriidaton, niin sillä on Lindenbaumin lauseen nojalla maksimaalisesti ristiriidaton laajennus formula_9, jolla formula_135. 
Olkoon formula_4 totuusjakauma siten, että kaikille atomilauseille formula_137 pätee
formula_138
Väite 2: propositiolauseella formula_10 pätee formula_140 jos ja vain jos formula_13. Todistetaan väite 2 induktiolla propositiolauseen formula_10 rakenteen suhteen. 
Täten väite 2 todistettiin päteväksi. 
Koska formula_213 ja koska formula_214, niin väitteen 2 nojalla totuusjakaumalla formula_4 pätee formula_216 ja siis formula_217. Ollaan saatu ristiriita. Siis alkuperäinen väite eli propositiologiikan täydellisyyslause pätee. formula_218