Twierdzenie Löwenheima-Skolema

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Twierdzenie Löwenheima-Skolema – ważne twierdzenie logiki matematycznej dotyczące mocy modeli dla formuł logiki pierwszego rzędu.

Współcześnie, nazwa twierdzenie (czy wręcz twierdzenia) Löwenheima-Skolema jest używana na określenie serii rezultatów gwarantujących istnienie modeli pewnych mocy. Dwa najczęściej stosowane wyniki noszą nazwy górnego twierdzenia Löwenheima-Skolema i dolnego twierdzenia Löwenheima-Skolema.

Istnienie modelu nieskończonego[edytuj | edytuj kod]

Jedną z postaci twierdzenia Löwenheima-Skolema jest poniższe stwierdzenie:

Twierdzenie A

Jeżeli zdanie φ ma model nieskończony to dla każdego k zdanie φ ma model o mocy większej lub równej k.

Można również pokazać silniejszą postać twierdzenia (porównaj Twierdzenie C poniżej):

Twierdzenie B

Jeżeli dla każdego k zdanie φ ma model o mocy większej lub równej k to zdanie φ ma model przeliczalnie nieskończony.

Dowód twierdzenia A[edytuj | edytuj kod]

Poniżej znajduje się dowód prostszej postaci twierdzenia Löwenheima-Skolema. Dowód istnienia przeliczalnie nieskończonego modelu dla zdań spełniających warunek z twierdzenia wynika wprost z konstrukcji z dowodu twierdzenia o zupełności.

Korzystamy z twierdzenia o zwartości:

Jeżeli każdy skończony podzbiór zbioru zdań A jest spełnialny to A również jest spełnialny.

Dla każdego naturalnego k>1 oznaczmy przez ψk następującą formułę:

\exist x_1 \exist x_2 ... \exist x_{k-1} \exist x_k (\neg (x_1=x_2)) \wedge \ldots \wedge (\neg (x_1=x_k)) \wedge \ldots \wedge (\neg (x_{k-1}=x_k))

Intuicyjnie ψk oznacza Istnieje k różnych obiektów. Zdanie takie może być spełnione jedynie w modelach o uniwersum mocy większej lub równej k.

Załóżmy teraz, że φ ma model o mocy co najmniej k dla każdego k. Rozważmy następujące zbiory zdań

A=\{\varphi\} \cup \{\psi_k : k=2,3,...\},  A_n =\{\varphi, \, \psi_2, \ldots, \psi_n\}

W każdym modelu {\mathcal M} zdania φ o mocy co najmniej n wszystkie zdania ze zbioru  A_n są spełnione, czyli {\mathcal M}\models A_n. Zauważmy również, że każdy skończony podzbiór B \subseteq A zawiera się w zbiorze  A_n, dla pewnego n; stąd wnioskujemy że każdy skończony podzbiór zbioru A ma model. Z twierdzenia o zwartości otzrymujemy że cały zbiór A ma model {\mathcal N}.

Ponieważ {\mathcal N}\models\varphi i model {\mathcal N} ma co najmniej k elementów, dla każdego k, więc {\mathcal N} jest modelem nieskończonym zdania \varphi.

Wnioski z twierdzenia[edytuj | edytuj kod]

Ze sformułowanego powyżej twierdzenia Löwenheima-Skolema wynika wiele negatywnych wniosków o niemożności wyrażenia pewnych problemów w logice pierwszego rzędu. Oto przykładowe z nich:

  • problem osiągalności wierzchołka w grafie nie da się opisać przy pomocy formuły logiki pierwszego rzędu
  • ani klasy skończonych modeli, ani klasy skończonych modeli danego zdania \varphi (np. skończonych grup, skończonych ciał, itd) nie można opisać przy pomocy formuły logiki pierwszego rzędu

Górne twierdzenie Löwenheima-Skolema[edytuj | edytuj kod]

Niech \tau będzie alfabetem pewnego języka pierwszego rzędu {\mathcal L}(\tau) oraz niech {\mathcal M} będzie modelem nieskończonym dla tego języka, z uniwersum M. Jeśli \kappa jest liczbą kardynalną spełniającą  |M|\le \kappa oraz |{\mathcal L}(\tau)|\le \kappa, to istnieje model {\mathcal N} języka {\mathcal L}(\tau) z uniwersum N taki, że

|N|=\kappa oraz {\mathcal M}\prec {\mathcal N} (tzn model {\mathcal M} jest elementarnym podmodelem modelu {\mathcal N}).

Innymi słowy, i mniej ściśle: Każdy model \mathcal M można rozszerzyć elementarnie do modelu \mathcal N dowolnej (dużej) mocy (spełniającego  \mathcal M \prec \mathcal N).

Wnioski z twierdzenia[edytuj | edytuj kod]

  • Jeśli zdanie \varphi ma model przeliczalny, to \varphi ma model każdej nieskończonej mocy. Nawet ogólniej: jeśli zbiór \Sigma zdań ma model przeliczalny, to \Sigma ma model każdej nieskończonej mocy.
  • Stąd: w logice pierwszego rzędu nie można rozróżnić modeli przeliczalnych od nieprzeliczalnych.

Dolne twierdzenie Löwenheima-Skolema[edytuj | edytuj kod]

Niech \tau będzie alfabetem pewnego języka pierwszego rzędu {\mathcal L}(\tau) oraz niech {\mathcal M} będzie nieskończonym modelem dla tego języka. Dla każdego podzbioru  A \subseteq M spełniającego |{\mathcal L}(\tau)|\le |A| istnieje elementarny podmodel {\mathcal N} modelu {\mathcal M} z uniwersum N spelniającym  A \subseteq N oraz |A|=|N|.

Innymi słowy, i mniej ściśle: W każdym modelu \mathcal M można znaleźć elementarny podmodel  \mathcal N \prec \mathcal M dowolnej (małej) mocy.

Specjalny przypadek dolnego twierdenia[edytuj | edytuj kod]

Wielu autorów używa nazwy twierdzenie Löwenheima-Skolema dla określenia następującej konsekwencji dolnego twierdzenia Löwenheima-Skolema (zobacz np. Martin Goldstern i Haim Judah[1]):

Twierdzenie C

Każdy model {\mathcal M} przeliczalnego języka {\mathcal L}(\tau) zawiera przeliczalny elementarny podmodel {\mathcal N}\prec {\mathcal M}.

Wnioski z twierdzenia[edytuj | edytuj kod]

  • Konsekwencją nawet tego specjalnego przypadku twierdzenia jest tzw. paradoks Skolema.
  • Jeśli zdanie \varphi ma nieskończony model \mathcal M, to \varphi ma model każdej mocy \kappa < |M|.

Równoważność z aksjomatem wyboru[edytuj | edytuj kod]

Przy założeniu ZF (bez aksjomatu wyboru), bardziej naturalną wersją górnego twierdzenia Löwenheima-Skolema (nie wspominającą dobrych uporządkowań) jest następujące twierdzenie:

Niech \tau będzie alfabetem pewnego języka pierwszego rzędu {\mathcal L}(\tau) oraz niech {\mathcal M} będzie modelem nieskończonym dla tego języka, z uniwersum M. Jeśli A jest zbiorem spełniającym  |M|\le |A| (tzn istnieje iniekcja f:M\to A) oraz |{\mathcal L}(\tau)|\le |A|, to istnieje model {\mathcal N} języka {\mathcal L}(\tau) z uniwersum N taki, że
|N|=|A| (tzn istnieje bijekcja g:N\to A) oraz {\mathcal M}\prec {\mathcal N}

Robert Vaught udowodnił że i górne i dolne twierdzenie Löwenheima-Skolema są równoważne aksjomatowi wyboru.

Dowód[edytuj | edytuj kod]

Aksjomat wyboru jest równoważne zdaniu

Dla każdego nieskończonego zbioru A istnieje iniekcja f:A\times A \to A

czyli

Dla każdego nieskończonego zbioru A istnieje model zdania
φ := (\forall x,y,p,q)(\, f(x,y)=f(p,q) \to x=p\wedge y=q\,),
który jest równoliczny ze zbiorem A.

Zdanie φ ma model przeliczalny, na przykład zbiór \mathbb N; z górnego twierdzenia LS wnioskujemy że φ ma model o każdej nieskończonej mocy. Więc "górne LS" ⇒ AC.

Dla każdego zbioru A można znaleźć zbior B o mocy większej niż A spełniający  B \approx B \times B, na przykład zbiór potęgowy zbioru A\times \mathbb N:

 2^{A\times \mathbb N} \times 2^{A\times \mathbb N} 
\approx 2^{(A \times \mathbb N) \, \dot\cup \,(A\times \mathbb N)}
\approx 2 ^{ A \times \mathbb N \times 2} 
\approx 2 ^{ A \times \mathbb N }

Więc istnieje model M o mocy |B| spełniający zdanie φ. Z dolnego twierdzenia LS wnioskujemy że φ ma model o mocy |A|. Więc "dolne LS" ⇒ AC.

Uwagi historyczne[edytuj | edytuj kod]

Pierwszy rezultat tego typu, twierdzenie A sformułowane wcześniej, był udowodniony przez niemieckiego matematyka Leopolda Löwenheima w roku 1915[2]. Górne i dolne twierdzenia Löwenheima-Skolema były wzmocnieniami wcześniejszych wyników udowodnionymi przez Alfreda Tarskiego (zobacz Zofia Adamowicz i Paweł Zbierski[3]). Z tego powodu niektórzy autorzy nazywają twierdzenia w wersjach podanych przez nas twierdzeniami Löwenheima-Skolema-Tarskiego (zobacz np. Wiktor Marek i Janusz Onyszkiewicz[4].

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. Martin Goldstern; Haim Judah: The Incompleteness Phenomenon. A new course in mathematical logic. A K Peters, Wellesley, Massachusetts, 1995. Strona 148. ISBN 1-56881-029-6
  2. Löwenheim, Leopold: Über Möglichkeiten im Relativkalkül, "Mathematische Annalen", 76 (1915), strony 447-470.
  3. Zofia Adamowicz; Paweł Zbierski: Logic of mathematics. A modern course of classical logic. "Pure and Applied Mathematics" (New York). A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. Strona 108. ISBN 0-471-06026-7.
  4. Wiktor Marek; Janusz Onyszkiewicz: Elementy logiki i teorii mnogości w zadaniach, Państwowe Wydawnictwo Naukowe, Warszawa 1975, wydanie 2., strona 121.