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 ${\displaystyle \varphi }$ ma model nieskończony, to dla każdego ${\displaystyle k}$ zdanie ${\displaystyle \varphi }$ ma model o mocy większej lub równej ${\displaystyle k.}$

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

Twierdzenie B

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

${\displaystyle \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 ${\displaystyle \psi _{k}}$ oznacza "Istnieje ${\displaystyle k}$ różnych obiektów". Zdanie takie może być spełnione jedynie w modelach o uniwersum mocy większej lub równej ${\displaystyle k.}$

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

${\displaystyle A=\{\varphi \}\cup \{\psi _{k}:k=2,3,\dots \},}$ ${\displaystyle A_{n}=\{\varphi ,\psi _{2},\dots ,\psi _{n}\}.}$

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

Ponieważ ${\displaystyle {\mathcal {N}}\models \varphi }$ i model ${\displaystyle {\mathcal {N}}}$ ma co najmniej ${\displaystyle k}$ elementów, dla każdego ${\displaystyle k,}$ więc ${\displaystyle {\mathcal {N}}}$ jest modelem nieskończonym zdania ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \tau }$ będzie alfabetem pewnego języka pierwszego rzędu ${\displaystyle {\mathcal {L}}(\tau )}$ oraz niech ${\displaystyle {\mathcal {M}}}$ będzie modelem nieskończonym dla tego języka, z uniwersum ${\displaystyle M.}$ Jeśli ${\displaystyle \kappa }$ jest liczbą kardynalną spełniającą ${\displaystyle |M|\leqslant \kappa }$ oraz ${\displaystyle |{\mathcal {L}}(\tau )|\leqslant \kappa ,}$ to istnieje model ${\displaystyle {\mathcal {N}}}$ języka ${\displaystyle {\mathcal {L}}(\tau )}$ z uniwersum ${\displaystyle N}$ taki, że

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

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

Wnioski z twierdzenia

• Jeśli zdanie ${\displaystyle \varphi }$ ma model przeliczalny, to ${\displaystyle \varphi }$ ma model każdej nieskończonej mocy. Nawet ogólniej: jeśli zbiór ${\displaystyle \Sigma }$ zdań ma model przeliczalny, to ${\displaystyle \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 ${\displaystyle \tau }$ będzie alfabetem pewnego języka pierwszego rzędu ${\displaystyle {\mathcal {L}}(\tau )}$ oraz niech ${\displaystyle {\mathcal {M}}}$ będzie nieskończonym modelem dla tego języka. Dla każdego podzbioru ${\displaystyle A\subseteq M}$ spełniającego ${\displaystyle |{\mathcal {L}}(\tau )|\leqslant |A|}$ istnieje elementarny podmodel ${\displaystyle {\mathcal {N}}}$ modelu ${\displaystyle {\mathcal {M}}}$ z uniwersum ${\displaystyle N}$ spełniającym ${\displaystyle A\subseteq N}$ oraz ${\displaystyle |A|=|N|.}$

Innymi słowy, i mniej ściśle: W każdym modelu ${\displaystyle {\mathcal {M}}}$ można znaleźć elementarny podmodel ${\displaystyle {\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^[1]):

Twierdzenie C

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

Wnioski z twierdzenia

• Konsekwencją nawet tego specjalnego przypadku twierdzenia jest paradoks Skolema.
• Jeśli zdanie ${\displaystyle \varphi }$ ma nieskończony model ${\displaystyle {\mathcal {M}},}$ to ${\displaystyle \varphi }$ ma model każdej mocy ${\displaystyle \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 ${\displaystyle \tau }$ będzie alfabetem pewnego języka pierwszego rzędu ${\displaystyle {\mathcal {L}}(\tau )}$ oraz niech ${\displaystyle {\mathcal {M}}}$ będzie modelem nieskończonym dla tego języka, z uniwersum ${\displaystyle M.}$ Jeśli ${\displaystyle A}$ jest zbiorem spełniającym ${\displaystyle |M|\leqslant |A|}$ (tzn. istnieje iniekcja ${\displaystyle f\colon M\to A}$) oraz ${\displaystyle |{\mathcal {L}}(\tau )|\leqslant |A|,}$ to istnieje model ${\displaystyle {\mathcal {N}}}$ języka ${\displaystyle {\mathcal {L}}(\tau )}$ z uniwersum ${\displaystyle N}$ taki, że

${\displaystyle |N|=|A|}$ (tzn. istnieje bijekcja ${\displaystyle g\colon N\to A}$) oraz ${\displaystyle {\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 ${\displaystyle A}$ istnieje iniekcja ${\displaystyle f\colon A\times A\to A,}$

czyli

Dla każdego nieskończonego zbioru ${\displaystyle A}$ istnieje model zdania

${\displaystyle \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 ${\displaystyle A.}$

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

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

${\displaystyle 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 ${\displaystyle M}$ o mocy ${\displaystyle |B|}$ spełniający zdanie ${\displaystyle \varphi .}$ Z dolnego twierdzenia LS wnioskujemy że ${\displaystyle \varphi }$ ma model o mocy ${\displaystyle |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^[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 (zob. np. Wiktor Marek i Janusz Onyszkiewicz^[4]).

Zobacz też

• teoria modeli

Przypisy