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 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   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 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   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 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   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 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 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 (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 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, 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ż edytuj

Przypisy edytuj

  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 edytuj