Twierdzenie Löwenheima-Skolema

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

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

Twierdzenie A

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

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

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

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

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

• 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

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

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

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

• 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

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

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

Pierwszy rezultat tego typu, twierdzenie A sformułowane wcześniej, był udowodniony przez niemieckiego matematyka Leopolda Löwenheima w roku 1915. 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). 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.

Zobacz też

• teoria modeli
• twierdzenie o zupełności dla logiki pierwszego rzędu