Lemat Lindenbauma

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

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

Z konstrukcji i Zatem X zawiera się w Y.

Zupełność Y[edytuj | edytuj kod]

Twierdzimy, że 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 | edytuj kod]

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

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