Lemat Lindenbauma

Lemat Lindenbauma – twierdzenie metamatematyczne, 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 \}]).$

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},\dots$ będzie wyliczeniem zbioru formuł Fm. Taki ciąg istnieje, bo formuł jest przeliczalnie wiele. Określmy:

• $Y_{0}=X,$

• $Y_{n+1}={\begin{cases}Y_{n}\cup \{\alpha _{n}\},&{\text{gdy }}\ \ulcorner \neg \alpha _{n}\urcorner \notin Cn(Y_{n})\\[2pt]Y_{n}\cup \{\neg \alpha _{n}\},&{\text{gdy }}\ \ulcorner \neg \alpha _{n}\urcorner \in Cn(Y_{n})\end{cases}},$
• $Y=\bigcup _{n\in \mathbb {N} }Y_{n}.$

(Oznaczenia $\ulcorner \alpha \urcorner$ będziemy używać aby pokazać, że chodzi o użycie metajęzykowe).

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

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.

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. $\ulcorner \neg \alpha _{n}\urcorner \notin Cn(Y_{n});$
• Przypadek 2. $\ulcorner \neg \alpha _{n}\urcorner \in Cn(Y_{n}).$

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

Ad 2: $\ulcorner \neg \alpha _{n}\urcorner \in Y_{n+1},$ więc $\neg \alpha _{n}\in Y.$

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}{:}$ $\ulcorner \neg \alpha \urcorner \notin Cn(Y_{n}).$ Z Faktu: $Y_{n}\cup \{\alpha _{n}\}$ jest niesprzeczny.
• Przypadek 2. $Y_{n+1}=Y_{n}\cup \{\neg \alpha _{n}\}.$ Wtedy $\ulcorner \neg \alpha _{n}\urcorner \in Cn(Y_{n}).$ $Cn(Y_{n})=Cn(Y_{n+1}).$ Z (i), $Y_{n+1}$ jest niesprzeczny.

Bibliografia

• Woleński Jan, Filozoficzna szkoła lwowsko-warszawska, PWN, Warszawa 1985.