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\}. 
*[[Propositiologiikka|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. 

# 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}. 
# 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}. 
# 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}. 
# 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}. 
# 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}. 
# 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