Twierdzenie Löwenheima-Skolema

Z Wikipedii

Twierdzenie Löwenheima-Skolema to ważne twierdzenie logiki matematycznej dotyczące mocy modeli dla formuł logiki pierwszego rzędu. Zostało ono po raz pierwszy udowodnione przez niemieckiego matematyka Leopolda Löwenheima w roku 1915.

Spis treści 1 Twierdzenie 2 Dowód 2.1 Lemat o zwartości 3 Wnioski z twierdzenia 4 Zobacz również

[edytuj] Twierdzenie

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

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:

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

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.

Udowodnimy najpierw prosty lemat:

[edytuj] Lemat o zwartości

Jeżeli każdy skończony podzbiór zbioru zdań A jest spełnialny to A również jest spełnialny.

Załózmy, że A nie jest spełnialny, lecz każdy jego skończony podzbiór jest. Z twierdzenia o zupełności wynika, że istnieje dowód zdania sprzecznego z A. Dowód ten jednak wykorzystuje skończenie wiele zdań z A. Ten zbiór zdań nie może być spełnialny (bo udaje się z niego udowodnić sprzeczność) i jest skończony. To kończy dowód lematu.

Dla każdego całkowitego k>1 oznaczmy przez ψ_k następującą formułę:

Intuicyjnie ψ_k oznacza Istnieje k róznych 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, ale nie ma modelu nieskończonego. Rozważmy następujący zbiór zdań

Zbiór zdań A nie może mieć modelu. Istotnie, gdyby miał model M to M byłby albo skończony albo nieskończony. Jednakże w każdym z tych przypadków uzyskujemy sprzeczność:

• jeśli M jest skończony to istnieje takie n, że n > card M, ale wtedy M nie może spełniać ψ_n,
• jeśli M jest nieskończony to jest również modelem dla φ co stoi w sprzeczności z założeniem, że φ nie ma modelu nieskończonego.

Stosując teraz powyższy lemat dochodzimy do wniosku, że A zawiera skończony podzbiór formuł B nie mający modelu. Widać, że jeśli B nie zawierałby φ to B miałby skończony model. Zatem B zawiera φ. Załóżmy teraz, że k to największa liczba całkowita taka, że ψ_k należy do B. Z założenia φ ma model mocy większej niż k. Model ten spełnia więc wszystkie zdania z B. To jednak stoi w sprzeczności z wnioskiem z lematu. Uzyskana sprzeczność dowodzi fałszywości założenia jakoby zdanie φ nie miało modelu nieskończonego.

[edytuj] Wnioski z twierdzenia

Z 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
• w logice pierwszego rzędu nie można rozróżnić modeli przeliczalnych od nieprzeliczalnych.

Inną konsekwencją twierdzenia Löwenheima-Skolema jest tzw. paradoks Skolema.

[edytuj] Zobacz również

• Twierdzenie o zupełności dla logiki pierwszego rzędu.