Lemat Lindenbauma

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 \}])

Dowód lematu Lindenbauma[edytuj | edytuj kod]

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.

Zawieranie się[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.

Niesprzeczność Y[edytuj | edytuj kod]

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). Cn(Y _n) = Cn(Y _{n +1}). Z (i), Y _{n+1} jest niesprzeczny.

\square

Bibliografia[edytuj | edytuj kod]

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