Twierdzenie o zwartości

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Twierdzenie o zwartości to twierdzenie mówiące, że nieskończony zbiór zdań rachunku predykatów pierwszego rzędu jest spełnialny, jeśli tylko każdy jego podzbiór skończony jest spełnialny. Równoważnie, jeśli taki zbiór jest sprzeczny, to istnieje jego skończony podzbiór, który jest sprzeczny.

Dowody[edytuj | edytuj kod]

Za pomocą twierdzenia o pełności[edytuj | edytuj kod]

Załóżmy, że A\, nie jest spełnialny. Wówczas na mocy twierdzenia o pełności, zbiór ten jest sprzeczny, a co za tym idzie istnieje dowód zdania fałszywego ze zbioru założeń A\,. Z definicji dowodu wynika, że zbiór A_0\, elementów zbioru A\,, których użyto w tym dowodzie jest skończony. Oczywiście jest on podzbiorem zbioru A\, i jednocześnie na mocy twierdzenia o zgodności jest on niespełnialny. Kończy to dowód twierdzenia.

Za pomocą twierdzenia Łosia[edytuj | edytuj kod]

Każdy skończony podzbiór i\subseteq A jest spełnialny, czyli ma model M_i\,. Niech I\, będzie zbiorem wszystkich skończonych podbiorów zbioru A\, i niech F_j  := \{ i\in I:  j\subseteq i \} dla dażdego j\in I. Wówczas F_{j_1} \cap F_{j_2} = F_{j_1\cup j_2}, czyli rodzina  (F_j:j\in I) ma własność skończonych przekrojów.

Wobec tego, na mocy twierdzenia o ultrafiltrze istnieje taki ultrafiltr U\,, że F_j \in U\, dla każdego j\in I\,. Wtedy na mocy twierdzenia Łosia ultraprodukt \prod M_i / U jest modelem zbioru A\,, bo dla każdego \sigma\in A\, zbiór \{i\in I: M_i \models \sigma \} \supseteq \{i\in I : \sigma\in i \} = F_{\{\sigma\}}\, jest elementem ultrafiltru U\,.

Zobacz też[edytuj | edytuj kod]