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

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

Twierdzenie B

Jeżeli dla każdego zdanie ma model o mocy większej lub równej to zdanie 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 oznaczmy przez następującą formułę:

Intuicyjnie oznacza "Istnieje różnych obiektów". Zdanie takie może być spełnione jedynie w modelach o uniwersum mocy większej lub równej

Załóżmy teraz, że ma model o mocy co najmniej dla każdego 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 otrzymujemy, ż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

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

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

  • 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

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 spełniają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 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 przeliczalnego języka zawiera przeliczalny elementarny podmodel

Wnioski z twierdzenia

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

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 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

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

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.