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 k {\displaystyle k} zdanie φ {\displaystyle \varphi } ma model o mocy większej lub równej k . {\displaystyle k.}

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

Twierdzenie B

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

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

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

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

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

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

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

Innymi słowy, i mniej ściśle: Każdy model M {\displaystyle {\mathcal {M}}} można rozszerzyć elementarnie do modelu N {\displaystyle {\mathcal {N}}} dowolnej (dużej) mocy (spełniającego M N {\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 L ( τ ) {\displaystyle {\mathcal {L}}(\tau )} oraz niech M {\displaystyle {\mathcal {M}}} będzie nieskończonym modelem dla tego języka. Dla każdego podzbioru A M {\displaystyle A\subseteq M} spełniającego | L ( τ ) | | A | {\displaystyle |{\mathcal {L}}(\tau )|\leqslant |A|} istnieje elementarny podmodel N {\displaystyle {\mathcal {N}}} modelu M {\displaystyle {\mathcal {M}}} z uniwersum N {\displaystyle N} spełniającym A N {\displaystyle A\subseteq N} oraz | A | = | N | . {\displaystyle |A|=|N|.}

Innymi słowy, i mniej ściśle: W każdym modelu M {\displaystyle {\mathcal {M}}} można znaleźć elementarny podmodel N M {\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 M {\displaystyle {\mathcal {M}}} przeliczalnego języka L ( τ ) {\displaystyle {\mathcal {L}}(\tau )} zawiera przeliczalny elementarny podmodel N M . {\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 M , {\displaystyle {\mathcal {M}},} to φ {\displaystyle \varphi } ma model każdej mocy κ < | M | . {\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 L ( τ ) {\displaystyle {\mathcal {L}}(\tau )} oraz niech M {\displaystyle {\mathcal {M}}} będzie modelem nieskończonym dla tego języka, z uniwersum M . {\displaystyle M.} Jeśli A {\displaystyle A} jest zbiorem spełniającym | M | | A | {\displaystyle |M|\leqslant |A|} (tzn. istnieje iniekcja f : M A {\displaystyle f\colon M\to A} ) oraz | L ( τ ) | | A | , {\displaystyle |{\mathcal {L}}(\tau )|\leqslant |A|,} to istnieje model N {\displaystyle {\mathcal {N}}} języka L ( τ ) {\displaystyle {\mathcal {L}}(\tau )} z uniwersum N {\displaystyle N} taki, że
| N | = | A | {\displaystyle |N|=|A|} (tzn. istnieje bijekcja g : N A {\displaystyle g\colon N\to A} ) oraz M N . {\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 A {\displaystyle A} istnieje iniekcja f : A × A A , {\displaystyle f\colon A\times A\to A,}

czyli

Dla każdego nieskończonego zbioru A {\displaystyle A} istnieje model zdania
φ := ( x , y , p , q ) ( f ( x , y ) = f ( p , q ) x = p y = q ) , {\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 A . {\displaystyle A.}

Zdanie φ {\displaystyle \varphi } ma model przeliczalny, na przykład zbiór N ; {\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 A {\displaystyle A} można znaleźć zbior B {\displaystyle B} o mocy większej niż A {\displaystyle A} spełniający B B × B , {\displaystyle B\approx B\times B,} na przykład zbiór potęgowy zbioru A × N : {\displaystyle A\times \mathbb {N} {:}}

2 A × N × 2 A × N 2 ( A × N ) ˙ ( A × N ) 2 A × N × 2 2 A × 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 M {\displaystyle M} o mocy | B | {\displaystyle |B|} spełniający zdanie φ . {\displaystyle \varphi .} Z dolnego twierdzenia LS wnioskujemy, że φ {\displaystyle \varphi } ma model o mocy | A | . {\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ż

Przypisy

  1. Martin Goldstern, Haim Judah: The Incompleteness Phenomenon. A new course in mathematical logic. A.K. Peters, Wellesley, Massachusetts, 1995, s. 148. ISBN 1-56881-029-6.
  2. Löwenheim, Leopold: Über Möglichkeiten im Relativkalkül, „Mathematische Annalen”, 76 (1915), s. 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, s. 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, wyd. 2, s. 121.

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].
  • Publikacja w zamkniętym dostępie – wymagana rejestracja, też płatna, lub wykupienie subskrypcji Löwenheim–Skolem theorems and nonstandard models (ang.), Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].
  • Britannica: topic/Lowenheim-Skolem-theorem
  • DSDE: Skolem-Löwenheims_sætning