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 zdanie $\varphi$ ma model nieskończony, to dla każdego $k$ zdanie $\varphi$ 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 $\varphi$ ma model o mocy większej lub równej $k,$ to zdanie $\varphi$ 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 $\psi _{k}$ następującą formułę:

$\exists x_{1}\exists x_{2}...\exists x_{k-1}\exists 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 $\psi _{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 $\varphi$ 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,\dots \},$ $A_{n}=\{\varphi ,\psi _{2},\dots ,\psi _{n}\}.$

W każdym modelu ${\mathcal {M}}$ zdania $\varphi$ 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 otrzymujemy, ż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|\leqslant \kappa$ oraz $|{\mathcal {L}}(\tau )|\leqslant \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 )|\leqslant |A|$ istnieje elementarny podmodel ${\mathcal {N}}$ modelu ${\mathcal {M}}$ z uniwersum $N$ spełniają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 twierdzenia

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 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 (niewspominają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|\leqslant |A|$ (tzn. istnieje iniekcja $f\colon M\to A$) oraz $|{\mathcal {L}}(\tau )|\leqslant |A|,$ to istnieje model ${\mathcal {N}}$ języka ${\mathcal {L}}(\tau )$ z uniwersum $N$ taki, że

$|N|=|A|$ (tzn. istnieje bijekcja $g\colon 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\colon A\times A\to A,$

czyli

Dla każdego nieskończonego zbioru $A$ istnieje model zdania

$\varphi :=(\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 $\varphi$ ma model przeliczalny, na przykład zbiór $\mathbb {N} ;$ z górnego twierdzenia LS wnioskujemy, że $\varphi$ 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 $\varphi .$ Z dolnego twierdzenia LS wnioskujemy, że $\varphi$ ma model o mocy $|A|.$ Więc „dolne LS” ⇒ AC.

Uwagi historyczne

Pierwszy rezultat tego typu, twierdzenie A sformułowane wcześniej, został 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 (zob. np. Wiktor Marek i Janusz Onyszkiewicz).

Zobacz też

• teoria modeli

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Löwenheim-Skolem Theorem, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2023-06-18].
• Löwenheim–Skolem theorems and nonstandard models (ang.), Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].