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 JudahMartin Goldstern, Haim Judah: The Incompleteness Phenomenon. A new course in mathematical logic. A.K. Peters, Wellesley, Massachusetts, 1995, s. 148. .):

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 1915Löwenheim, Leopold: Über Möglichkeiten im Relativkalkül, „Mathematische Annalen”, 76 (1915), s. 447–470.. Górne i dolne twierdzenia Löwenheima-Skolema były wzmocnieniami wcześniejszych wyników udowodnionymi przez Alfreda Tarskiego (zobacz Zofia Adamowicz i Paweł ZbierskiZofia 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. .). Z tego powodu niektórzy autorzy nazywają twierdzenia w wersjach podanych przez nas twierdzeniami Löwenheima-Skolema-Tarskiego (zob. np. Wiktor Marek i Janusz OnyszkiewiczWiktor Marek, Janusz Onyszkiewicz: Elementy logiki i teorii mnogości w zadaniach, Państwowe Wydawnictwo Naukowe, Warszawa 1975, wyd. 2, s. 121.).

Zobacz też teoria modeli

Przypisy

Linki zewnętrzne [dostęp 2023-06-18]. Löwenheim–Skolem theorems and nonstandard models , Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].

Kategoria:Teoria modeli Löwenheima-Skolema