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):

${\mathrm{\forall }}_X(\mathrm{\neg }{\mathrm{\forall }}_{\phi \in Fm}[X⊢\phi ]\Rightarrow {\mathrm{\exists }}_Y[\{X\subseteq Y\}\wedge \mathrm{\neg }{\mathrm{\forall }}_{\phi \in Fm}\{Y⊢\phi \}\wedge {\mathrm{\forall }}_{\phi \in Fm}\{Y⊢\phi \vee Y⊢\mathrm{\neg }\phi \}]).$

Dowód lematu Lindenbauma

Tw. ${\mathrm{\forall }}_X(\mathrm{\neg }{\mathrm{\forall }}_{\phi \in Fm}[X⊢\phi ]\Rightarrow {\mathrm{\exists }}_Y[\{X\subseteq Y\}\wedge \mathrm{\neg }{\mathrm{\forall }}_{\phi \in Fm}\{Y⊢\phi \}\wedge {\mathrm{\forall }}_{\phi \in Fm}\{Y⊢\phi \vee Y⊢\mathrm{\neg }\phi \}]).$

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{array}{cc}{Y}_n\cup \{{\alpha }_n\},& \text{gdy }⌜\mathrm{\neg }{\alpha }_n⌝\notin Cn(Y_n)\\ Y_n\cup \{\mathrm{\neg }{\alpha }_n\},& \text{gdy }⌜\mathrm{\neg }{\alpha }_n⌝\in Cn(Y_n)\end{array},$
• $Y=\bigcup _{n\in \mathbb{N}}{Y}_n.$

(Oznaczenia $⌜\alpha ⌝$ 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 ${\mathrm{\forall }}_{\phi \in Fm}(Y⊢\phi \vee Y⊢\mathrm{\neg }\phi ).$ Dowód: Ustalmy $\phi .$ Niech $\phi ={\alpha }_n.$ Są dwa przypadki:

• Przypadek 1. $⌜\mathrm{\neg }{\alpha }_n⌝\notin Cn(Y_n);$
• Przypadek 2. $⌜\mathrm{\neg }{\alpha }_n⌝\in Cn(Y_n).$

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

Ad 2: $⌜\mathrm{\neg }{\alpha }_n⌝\in Y_{n+1},$ więc $\mathrm{\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: ${\mathrm{\forall }}_X{\mathrm{\forall }}_{\phi }[X⊬\mathrm{\neg }\phi \Rightarrow X\cup \{\phi \}jestniesprzeczne]$

• Przypadek 1. $Y_{n+1}=Y_n\cup \{{\alpha }_n\}.$ Z definicji $Y_n:$ $⌜\mathrm{\neg }\alpha ⌝\notin Cn(Y_n).$ Z Faktu: $Y_n\cup \{{\alpha }_n\}$ jest niesprzeczny.
• Przypadek 2. $Y_{n+1}=Y_n\cup \{\mathrm{\neg }{\alpha }_n\}.$ Wtedy $⌜\mathrm{\neg }{\alpha }_n⌝\in Cn(Y_n).$ $Cn(Y_n)=Cn(Y_{n+1}).$ Z (i), $Y_{n+1}$ jest niesprzeczny.

Bibliografia

• Szablon:Cytuj książkę