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):
![{\displaystyle \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 \}]).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0107efe63578e68210d7031403388e6132e2f79)
Dowód lematu Lindenbauma
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:
![{\displaystyle 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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39d28aab429e84c77d97e301b88bf71a902ec5ac)
(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ę
Z konstrukcji i Zatem X zawiera się w Y.
Zupełność Y
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
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:
![{\displaystyle \forall _{X}\forall _{\varphi }[X\not \vdash \neg \varphi \Rightarrow X\cup \{\varphi \}\ jest\ niesprzeczne]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84ae21c43d5bdbde5f919776c50839d115d40a16)
- Przypadek 1. Z definicji Z Faktu: jest niesprzeczny.
- Przypadek 2. Wtedy Z (i), jest niesprzeczny.
Bibliografia
- Jan Woleński: Filozoficzna szkoła lwowsko-warszawska. Warszawa: Państwowe Wydawnictwo Naukowe, 1985. ISBN 83-01-05334-8.