Lemat Lindenbauma

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Dowód lematu Lindenbauma[edytuj]

Tw. .

Dowód:

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

  • ,
  • ,
  • .

[Oznaczenia 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ę[edytuj]

. Z konstrukcji i . Zatem X zawiera się w Y.

Zupełność Y[edytuj]

Twierdzimy, że Y jest zupełny, czyli . Dowód: Ustalmy . Niech . Są dwa przypadki:

  • Przypadek 1. ;
  • Przypadek 2. .

Ad 1: , więc .

Ad 2: , więc .

Niesprzeczność Y[edytuj]

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

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

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

(T) jest niesprzeczny. [teza indukcyjna]

Fakt:

  • Przypadek 1. . Z definicji : . Z Faktu: jest niesprzeczny.
  • Przypadek 2. . Wtedy . . Z (i), jest niesprzeczny.

Bibliografia[edytuj]

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