Twierdzenie Löwenheima-Skolema

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj]

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

Twierdzenie A

Jeżeli zdanie φ ma model nieskończony to dla każdego k zdanie φ 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 φ ma model o mocy większej lub równej k to zdanie φ ma model przeliczalnie nieskończony.

Dowód twierdzenia A[edytuj]

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łę:

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ń

,

W każdym modelu zdania φ o mocy co najmniej wszystkie zdania ze zbioru są spełnione, czyli . Zauważmy również, że każdy skończony podzbiór zawiera się w zbiorze , dla pewnego ; stąd wnioskujemy że każdy skończony podzbiór zbioru ma model. Z twierdzenia o zwartości otzrymujemy że cały zbiór ma model .

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

Wnioski z twierdzenia[edytuj]

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 (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[edytuj]

Niech będzie alfabetem pewnego języka pierwszego rzędu oraz niech będzie modelem nieskończonym dla tego języka, z uniwersum . Jeśli jest liczbą kardynalną spełniającą oraz , to istnieje model języka z uniwersum taki, że

oraz (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 ).

Wnioski z twierdzenia[edytuj]

  • Jeśli zdanie ma model przeliczalny, to ma model każdej nieskończonej mocy. Nawet ogólniej: jeśli zbiór zdań ma model przeliczalny, to 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[edytuj]

Niech będzie alfabetem pewnego języka pierwszego rzędu oraz niech będzie nieskończonym modelem dla tego języka. Dla każdego podzbioru spełniającego istnieje elementarny podmodel modelu z uniwersum spelniającym oraz .

Innymi słowy, i mniej ściśle: W każdym modelu można znaleźć elementarny podmodel dowolnej (małej) mocy.

Specjalny przypadek dolnego twierdenia[edytuj]

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 przeliczalnego języka zawiera przeliczalny elementarny podmodel .

Wnioski z twierdzenia[edytuj]

  • Konsekwencją nawet tego specjalnego przypadku twierdzenia jest tzw. paradoks Skolema.
  • Jeśli zdanie ma nieskończony model , to ma model każdej mocy .

Równoważność z aksjomatem wyboru[edytuj]

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 będzie alfabetem pewnego języka pierwszego rzędu oraz niech będzie modelem nieskończonym dla tego języka, z uniwersum . Jeśli jest zbiorem spełniającym (tzn istnieje iniekcja ) oraz , to istnieje model języka z uniwersum taki, że
(tzn istnieje bijekcja ) oraz

Robert Vaught udowodnił że i górne i dolne twierdzenie Löwenheima-Skolema są równoważne aksjomatowi wyboru.

Dowód[edytuj]

Aksjomat wyboru jest równoważne zdaniu

Dla każdego nieskończonego zbioru istnieje iniekcja

czyli

Dla każdego nieskończonego zbioru istnieje model zdania
φ := ,
który jest równoliczny ze zbiorem .

Zdanie φ ma model przeliczalny, na przykład zbiór ; 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 można znaleźć zbior o mocy większej niż spełniający , na przykład zbiór potęgowy zbioru :

Więc istnieje model o mocy spełniający zdanie φ. Z dolnego twierdzenia LS wnioskujemy że φ ma model o mocy . Więc "dolne LS" ⇒ AC.

Uwagi historyczne[edytuj]

Pierwszy rezultat tego typu, twierdzenie A sformułowane wcześniej, był 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 (zobacz np. Wiktor Marek i Janusz Onyszkiewicz[4].

Zobacz też[edytuj]

Przypisy

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