Lemat Lindenbauma

Z Wikipedii

Lemat Lindenbauma, jedno z twierdzeń metamatematycznych, zwane tradycyjnie "lematem". Sformułowane przez polskiego logika ze szkoły lwowsko-warszawskiej, Adolfa Lindenbauma. Ma ono szerokie zastosowanie w teorii modeli, m.in. w dowodach twierdzenia o pełności tzw. metodą henkinowską.

Lemat Lindenbauma głosi, że dowolny niesprzeczny zbiór formuł można rozszerzyć do niesprzecznego i zupełnego zbioru formuł.

Zapis formalny jest następujący (przez X oznaczamy zbiór formuł a przez Fm zbiór wszystkich formuł nad danym przeliczalnym alfabetem):

$\forall _{X} (\neg \forall _{\varphi \in Fm} [ X \vdash \varphi ] \Rightarrow \exists _{Y} [\{X \subseteq Y\} \wedge \neg \forall _{\varphi \in Fm} \{ Y \vdash \varphi \} \wedge \forall _{\varphi \in Fm} \{Y \vdash \varphi \vee Y \vdash \neg \varphi \}])$

[edytuj] Dowód lematu Lindenbauma

Tw. $\forall _{X} (\neg \forall _{\varphi \in Fm} [ X \vdash \varphi ] \Rightarrow \exists _{Y} [\{X \subseteq Y\} \wedge \neg \forall _{\varphi \in Fm} \{ Y \vdash \varphi \} \wedge \forall _{\varphi \in Fm} \{Y \vdash \varphi \vee Y \vdash \neg \varphi \}])$ .

Dowód:

Niech X będzie zbiorem niesprzecznym. Niech ciąg formul $\alpha _0, \alpha _1, \ldots$ będzie wyliczeniem zbioru formuł Fm. Taki ciąg istnieje, bo formuł jest przeliczalnie wiele. Określmy:

$Y 0 = X$ ,

$Y _{n+1} = \left\{ {Y _n \cup \{ \alpha _n\},\ gdy\ \langle \neg \alpha _n \rangle \not \in Cn(Y _n) \atop Y _n \cup \{\neg \alpha _n\},\ gdy\ \langle \neg \alpha _n \rangle \in Cn(Y _n)}\right.$ ,
$Y = \bigcup _{n \in \mathbb{N}} Y _n$ .

[Oznaczenia $\langle \alpha \rangle$ będziemy używać aby pokazać, że chodzi o użycie metajęzykowe. Zazwyczaj stosuje się w tym celu cudzysłowy quine'owskie (popularnie zwane "rogami"), które ze względu na ograniczenia techniczne Wikipedii nie są dostępne.]

Aby udowodnić lemat Lindenbauma, musimy pokazać trzy rzeczy: (a) zawieranie się X w Y, (b) zupełność Y i (c) niesprzeczność Y.

[edytuj] Zawieranie się

$X \subseteq Y$ . Z konstrukcji $Y = \bigcup _{n \in \mathbb{N}} Y _n$ i $Y 0 = X$ . Zatem X zawiera się w Y.

[edytuj] Zupełność Y

Twierdzimy, że Y jest zupełny, czyli $\forall _{\varphi \in Fm} (Y \vdash \varphi \vee Y \vdash \neg \varphi)$ . Dowód: Ustalmy $\varphi$ . Niech $\varphi = \alpha _n$ . Są dwa przypadki:

Przypadek 1. $\langle \neg \alpha _n \rangle \not \in Cn(Y _n)$ ;
Przypadek 2. $\langle \neg \alpha _n \rangle \in Cn(Y _n)$ .

Ad 1: $\alpha _n \in Y _{n + 1}$ , więc $\alpha _n \in Y$ .

Ad 2: $\langle \neg \alpha _n \rangle \in Y _{n + 1}$ , więc $\neg \alpha _n \in Y$ .

[edytuj] Niesprzeczność Y

Twierdzimy, że Y jest niesprzeczny. Dowodzimy przez indukcję po n, że dla każdego n $Y n$ jest niesprzeczne:

(0) $Y 0$ jest niesprzeczny z założenia. [krok zerowy]

(i) załóżmy, że $Y n$ jest niesprzeczny. [założenie indukcyjne]

(T) $Y n + 1$ jest niesprzeczny. [teza indukcyjna]

Fakt: $\forall _X \forall _\varphi [X \not\vdash \neg\varphi \Rightarrow X \cup \{\varphi\}\ jest\ niesprzeczne]$

Przypadek 1. $Y _{n+1} = Y _n \cup \{ \alpha _n\}$ . Z definicji $Y n$ : $\langle \neg \alpha \rangle \not\in Cn(Y _n)$ . Z Faktu: $Y _n \cup \{\alpha _n\}$ jest niesprzeczny.
Przypadek 2. $Y _{n+1} = Y _n \cup \{ \neg \alpha _n\}$ . Wtedy $\langle \neg\alpha _n \rangle \in Cn(Y _n)$ . $C n (Y n) = C n (Y n + 1)$ . Z (i), $Y n + 1$ jest niesprzeczny.