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

$\mathrm{\exists }{x}_1\mathrm{\exists }{x}_2...\mathrm{\exists }{x}_{k-1}\mathrm{\exists }{x}_k(\mathrm{\neg }(x_1=x_2))\wedge \dots \wedge (\mathrm{\neg }(x_1=x_k))\wedge \dots \wedge (\mathrm{\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 $\phi$ ma model o mocy co najmniej $k$ dla każdego $k.$ Rozważmy następujące zbiory zdań

$A=\{\phi \}\cup \{{\psi }_k:k=2,3,\dots \},$ $A_n=\{\phi ,{\psi }_2,\dots ,{\psi }_n\}.$

W każdym modelu $ℳ$ zdania $\phi$ o mocy co najmniej $n$ wszystkie zdania ze zbioru $A_n$ są spełnione, czyli $ℳ\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 $𝒩.$

Ponieważ $𝒩\models \phi$ i model $𝒩$ ma co najmniej $k$ elementów, dla każdego $k,$ więc $𝒩$ jest modelem nieskończonym zdania $\phi .$

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 $\phi$ (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 $ℒ(\tau )$ oraz niech $ℳ$ będzie modelem nieskończonym dla tego języka, z uniwersum $M.$ Jeśli $\kappa$ jest liczbą kardynalną spełniającą $|M|⩽\kappa$ oraz $|ℒ(\tau )|⩽\kappa ,$ to istnieje model $𝒩$ języka $ℒ(\tau )$ z uniwersum $N$ taki, że

$|N|=\kappa$ oraz $ℳ\prec 𝒩$ (tzn. model $ℳ$ jest elementarnym podmodelem modelu $𝒩$).

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

Wnioski z twierdzenia

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

Innymi słowy, i mniej ściśle: W każdym modelu $ℳ$ można znaleźć elementarny podmodel $𝒩\prec ℳ$ 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 $ℳ$ przeliczalnego języka $ℒ(\tau )$ zawiera przeliczalny elementarny podmodel $𝒩\prec ℳ.$

Wnioski z twierdzenia

• Konsekwencją nawet tego specjalnego przypadku twierdzenia jest paradoks Skolema.
• Jeśli zdanie $\phi$ ma nieskończony model $ℳ,$ to $\phi$ 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 $ℒ(\tau )$ oraz niech $ℳ$ będzie modelem nieskończonym dla tego języka, z uniwersum $M.$ Jeśli $A$ jest zbiorem spełniającym $|M|⩽|A|$ (tzn. istnieje iniekcja $f:M\to A$) oraz $|ℒ(\tau )|⩽|A|,$ to istnieje model $𝒩$ języka $ℒ(\tau )$ z uniwersum $N$ taki, że

$|N|=|A|$ (tzn. istnieje bijekcja $g:N\to A$) oraz $ℳ\prec 𝒩.$

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

$\phi :=(\mathrm{\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 $\phi$ ma model przeliczalny, na przykład zbiór $\mathbb{N};$ z górnego twierdzenia LS wnioskujemy, że $\phi$ 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 $\phi .$ Z dolnego twierdzenia LS wnioskujemy, że $\phi$ 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

• Szablon:MathWorld [dostęp 2023-06-18].
• Szablon:Paywall Löwenheim–Skolem theorems and nonstandard models Szablon:Lang, Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].