Twierdzenie Löwenheima-Skolema

Z Wikipedii

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.

Spis treści

1 Istnienie modelu nieskończonego
- 1.1 Dowód twierdzenia A
- 1.2 Wnioski z twierdzenia
2 Górne twierdzenie Löwenheima-Skolema
- 2.1 Wnioski z twierdzenia
3 Dolne twierdzenie Löwenheima-Skolema
- 3.1 Specjalny przypadek dolnego twierdenia
- 3.2 Wnioski z twierdzenia
4 Równoważność z aksjomatem wyboru
- 4.1 Dowód
5 Uwagi historyczne
6 Przypisy
7 Zobacz też

[edytuj] Istnienie modelu nieskończonego

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

Twierdzenie A

Jeżeli dla każdego k zdanie φ ma model o mocy większej lub równej k to zdanie φ ma model nieskończony.

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.

[edytuj] 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 oznaczmy przez ψ_k następującą formułę:

$\exist x_1 \exist x_2 ... \exist x_{k-1} \exist 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 oznacza Istnieje k różnych obiektów. Oczywiście 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ń

$A=\{\varphi\} \cup \{\psi_k : k=2,3,...\}$ , $A_n =\{\varphi, \, \psi_2, \ldots, \psi_n\}$

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

Ponieważ ${\mathcal N}\models\varphi$ i model ${\mathcal N}$ ma co najmniej $k$ elementów, dla każdego $k$ , więc ${\mathcal N}$ jest modelem nieskończonym zdania $\varphi$ .

[edytuj] 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 $\varphi$ (np. skończonych grup, skończonych ciał, itd) nie można opisać przy pomocy formuły logiki pierwszego rzędu

[edytuj] Górne twierdzenie Löwenheima-Skolema

Niech $τ$ będzie alfabetem pewnego języka pierwszego rzędu ${\mathcal L}(\tau)$ oraz niech ${\mathcal M}$ będzie modelem nieskończonym dla tego języka, z uniwersum $M$ . Jeśli $κ$ jest liczbą kardynalną spełniającą $|M|\le \kappa$ oraz $|{\mathcal L}(\tau)|\le \kappa$ , to istnieje model ${\mathcal N}$ języka ${\mathcal L}(\tau)$ z uniwersum $N$ taki, że

| N | = κ

oraz ${\mathcal M}\prec {\mathcal N}$ (tzn model ${\mathcal M}$ jest elementarnym podmodelem modelu ${\mathcal N}$ ).

Innymi słowy, i mniej ściśle: Każdy model $\mathcal M$ można rozszerzyć elementarnie do modelu $\mathcal N$ dowolnej (dużej) mocy (spełniającego $\mathcal M \prec \mathcal N$ ).

[edytuj] Wnioski z twierdzenia

Jeśli zdanie $\varphi$ ma model przeliczalny, to $\varphi$ 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.

[edytuj] Dolne twierdzenie Löwenheima-Skolema

Niech $τ$ będzie alfabetem pewnego języka pierwszego rzędu ${\mathcal L}(\tau)$ oraz niech ${\mathcal M}$ będzie nieskończonym modelem dla tego języka. Dla każdego podzbioru $A \subseteq M$ spełniającego $|{\mathcal L}(\tau)|\le |A|$ istnieje elementarny podmodel ${\mathcal N}$ modelu ${\mathcal M}$ z uniwersum $N$ spelniającym $A \subseteq N$ oraz $| A | = | N |$ .

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

[edytuj] Specjalny przypadek dolnego twierdenia

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 ${\mathcal M}$ przeliczalnego języka ${\mathcal L}(\tau)$ zawiera przeliczalny elementarny podmodel ${\mathcal N}\prec {\mathcal M}$ .

[edytuj] Wnioski z twierdzenia

Konsekwencją nawet tego specjalnego przypadku twierdzenia jest tzw. paradoks Skolema.
Jeśli zdanie $\varphi$ ma nieskończony model $\mathcal M$ , to $\varphi$ ma model każdej mocy $κ < | M |$ .

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

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 ${\mathcal L}(\tau)$ oraz niech ${\mathcal M}$ będzie modelem nieskończonym dla tego języka, z uniwersum

M

. Jeśli

A

jest zbiorem spełniającym $|M|\le |A|$ (tzn istnieje iniekcja $f:M\to A$ ) oraz $|{\mathcal L}(\tau)|\le |A|$ , to istnieje model ${\mathcal N}$ języka ${\mathcal L}(\tau)$ z uniwersum

N

taki, że

| N | = | A |

(tzn istnieje bijekcja $g:N\to A$ ) oraz ${\mathcal M}\prec {\mathcal N}$

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

[edytuj] Dowód

Aksjomat wyboru jest równoważne zdaniu

Dla każdego nieskończonego zbioru

A

istnieje iniekcja $f:A\times A \to A$

czyli

Dla każdego nieskończonego zbioru

A

istnieje model zdania

φ := $(\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

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

$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$ o mocy $| B |$ spełniający zdanie φ. Z dolnego twierdzenia LS wnioskujemy że φ ma model o mocy $| A |$ . Więc "dolne LS" ⇒ AC.

[edytuj] Uwagi historyczne

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

Przypisy

↑ 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
↑ Löwenheim, Leopold: Über Möglichkeiten im Relativkalkül, "Mathematische Annalen", 76 (1915), strony 447-470.
↑ 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.
↑ Wiktor Marek; Janusz Onyszkiewicz: Elementy logiki i teorii mnogości w zadaniach, Państwowe Wydawnictwo Naukowe, Warszawa 1975, wydanie 2., strona 121.

[edytuj] Zobacz też

teoria modeli
twierdzenie o zupełności dla logiki pierwszego rzędu

Kategorie: Logika matematyczna • Twierdzenia matematyczne

We provide Linux to the World

Twierdzenie Löwenheima-Skolema

Z Wikipedii

Spis treści

[edytuj] Istnienie modelu nieskończonego

[edytuj] Dowód twierdzenia A

[edytuj] Wnioski z twierdzenia

[edytuj] Górne twierdzenie Löwenheima-Skolema

[edytuj] Wnioski z twierdzenia

[edytuj] Dolne twierdzenie Löwenheima-Skolema

[edytuj] Specjalny przypadek dolnego twierdenia

[edytuj] Wnioski z twierdzenia

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

[edytuj] Dowód

[edytuj] Uwagi historyczne

Przypisy

[edytuj] Zobacz też

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach