Twierdzenie o zwartości - Compactness theorem

W logice matematycznej The twierdzenie o zwartości stwierdza, że zestaw z pierwszego rzędu zdań ma modelu , wtedy i tylko wtedy, gdy każdy skończony podzbiór z nim ma model. To twierdzenie jest ważnym narzędziem w teorii modeli , ponieważ zapewnia użyteczną (ale generalnie nieskuteczną) metodę konstruowania modeli dowolnego zestawu zdań, które są całkowicie spójne .

Twierdzenie zwartość dla rachunku zdań jest konsekwencją Twierdzenie Tichonowa (która mówi, że produkt o zwartych jest zwarta) stosowane do zwartych przestrzeni kamienia , stąd nazwa twierdzenia za. Podobnie jest to analogiczne do właściwości skończonego przecięcia charakteryzującej zwartość w przestrzeniach topologicznych : zbiór zamkniętych zbiorów w zwartej przestrzeni ma niepuste przecięcie, jeśli każda skończona podkolekcja ma niepuste przecięcie.

Twierdzenie o zwartości jest jedną z dwóch kluczowych właściwości, wraz z twierdzeniem Löwenheima-Skolema skierowanym w dół , które jest używane w twierdzeniu Lindströma do scharakteryzowania logiki pierwszego rzędu. Chociaż istnieją pewne uogólnienia twierdzenia o zwartości na logiki nie pierwszego rzędu, samo twierdzenie o zwartości w nich nie ma, z wyjątkiem bardzo ograniczonej liczby przykładów.

Historia

Kurt Gödel udowodnił policzalne twierdzenie o zwartości w 1930 r. Anatolij Malcew udowodnił niezliczony przypadek w 1936 r.

Aplikacje

Twierdzenie o zwartości ma wiele zastosowań w teorii modeli; zarysowano tutaj kilka typowych wyników.

Twierdzenie o zwartości implikuje zasadę Robinsona : jeśli zdanie pierwszego rzędu zachodzi w każdym polu o charakterystyce zero, to istnieje stała p taka, że ​​zdanie zachowuje się dla każdego pola o charakterystyce większej niż p . Można to zobaczyć w następujący sposób: załóżmy, że φ jest zdaniem, które zachodzi w każdym polu charakterystycznym zero. Wtedy jego negacja ¬φ wraz z aksjomatami pola i nieskończonym ciągiem zdań 1 + 1 ≠ 0, 1 + 1 + 1 ≠ 0,…, jest nie do spełnienia (bo nie ma pola o charakterystyce 0, w którym ¬φ zachowuje , a nieskończona sekwencja zdań zapewnia, że ​​każdy model będzie polem o charakterystyce 0). Dlatego istnieje skończony podzbiór A tych zdań, którego nie można spełnić. Możemy założyć, że A zawiera ¬φ, aksjomaty pola, a dla niektórych k pierwszych k zdań w postaci 1 + 1 + ... + 1 ≠ 0 (ponieważ dodanie kolejnych zdań nie zmienia niezadowalania). Niech B zawiera wszystkie zdania A z wyjątkiem ¬φ. Wówczas dowolne pole o charakterystyce większej od k jest modelem B , a ¬φ razem z B nie jest zadowalające. Oznacza to, że φ musi zachodzić w każdym modelu B , co oznacza dokładnie, że φ zachodzi w każdym polu o charakterystyce większej niż k .

Drugie zastosowanie twierdzenia o zwartości pokazuje, że każda teoria, która ma dowolnie duże modele skończone lub pojedynczy model nieskończony, ma modele o arbitralnie dużej liczności (jest to twierdzenie w górę Löwenheima – Skolema ). Na przykład istnieją niestandardowe modele arytmetyki Peano z niezliczoną liczbą „liczb naturalnych”. Aby to osiągnąć, niech T będzie początkową teorią i niech κ będzie dowolną liczbą kardynalną . Dodaj do języka T jeden stały symbol dla każdego elementu κ. Następnie dodaj do T zbiór zdań, które mówią, że obiekty oznaczone przez dowolne dwa różne symbole stałe z nowej kolekcji są różne (jest to zbiór zdań κ ² ). Ponieważ każdy skończony podzbiór tej nowej teorii jest spełniony przez wystarczająco duży, skończony model T lub przez dowolny model nieskończony, cała rozszerzona teoria jest zadowalająca. Ale każdy model rozszerzonej teorii ma moc przynajmniej κ

Trzecim zastosowaniem twierdzenia o zwartości jest konstrukcja niestandardowych modeli liczb rzeczywistych, to znaczy spójnych rozszerzeń teorii liczb rzeczywistych zawierających liczby „nieskończenie małe”. Aby to zobaczyć, niech Σ będzie aksjomatyzacją pierwszego rzędu teorii liczb rzeczywistych. Rozważmy teorię uzyskaną przez dodanie do języka nowego symbolu stałego ε i dołączenie go do Σ aksjomatu ε> 0 i aksjomatów ε <1 / n dla wszystkich dodatnich liczb całkowitych n . Jasne jest, że standardowe liczby rzeczywiste R są modelem dla każdego skończonego podzbioru tych aksjomatów, ponieważ liczby rzeczywiste spełniają wszystko w Σ i, poprzez odpowiedni wybór ε, mogą spełniać dowolny skończony podzbiór aksjomatów dotyczących ε. Zgodnie z twierdzeniem o zwartości istnieje model * R, który spełnia Σ, a także zawiera element nieskończenie mały ε. Podobny argument, przylegający do aksjomatów ω> 0, ω> 1 itd., Pokazuje, że istnienia nieskończenie dużych liczb całkowitych nie można wykluczyć żadną aksjomatyzacją Σ liczb rzeczywistych.

Dowody

Twierdzenie o zwartości można udowodnić za pomocą twierdzenia Gödla o zupełności , które ustanawia, że ​​zbiór zdań jest spełniony wtedy i tylko wtedy, gdy nie można z niego dowieść żadnej sprzeczności. Ponieważ dowody są zawsze skończone, a zatem obejmują tylko skończoną liczbę podanych zdań, następuje twierdzenie o zwartości. W rzeczywistości twierdzenie o zwartości jest równoważne twierdzeniu Gödla o zupełności, a oba są równoważne twierdzeniu o ideale głównym Boole'a , słabej formie aksjomatu wyboru .

Gödel pierwotnie udowodnił twierdzenie o zwartości właśnie w ten sposób, ale później znaleziono pewne „czysto semantyczne” dowody twierdzenia o zwartości, tj. Dowody, które odnoszą się do prawdy, ale nie do udowodnienia . Jeden z tych dowodów opiera się na ultraproduktach, których podstawą jest następujący aksjomat:

Dowód: Napraw język L pierwszego rzędu i niech Σ będzie zbiorem zdań L tak, że każda skończona podkolekcja zdań L, i  ⊆ Σ z niego, ma model . Niech też będzie bezpośrednim iloczynem struktur, a ja będę zbiorem skończonych podzbiorów Σ. Dla każdego i w I niech A, _i  = { j ∈ I  : J ⊇ I }. Rodzina wszystkich tych zbiorów A _i generuje odpowiedni filtr , więc istnieje ultrafiltr U zawierający wszystkie zestawy postaci A _i . ${\ displaystyle {\ mathcal {M}} _ {i}}$${\ displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i}}$

Teraz dla dowolnej formuły φ w Σ mamy:

• zbiór A _{φ} jest w U
• ilekroć j  ∈ A _{φ} , to φ ∈  j , stąd φ trzyma się ${\ displaystyle {\ mathcal {M}} _ {j}}$
• zbiór wszystkich j posiadających własność φ jest nadzbiorem A _{φ} , a więc również w U${\ displaystyle {\ mathcal {M}} _ {j}}$

Korzystając z twierdzenia Łosia widzimy, że φ zachodzi w ultraprodukcie . Więc ten ultraprodukt spełnia wszystkie formuły w Σ. ${\ displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i} / U}$

Zobacz też

• Twierdzenie o zwartości prętowej
• Twierdzenie Herbranda
• Lista tematów algebry Boole'a  - artykuł z listy Wikimedia
• Twierdzenie Löwenheima – Skolema  - Twierdzenie matematyczne

Uwagi

Bibliografia

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Obliczalność i logika (wydanie czwarte). Cambridge University Press.
• Chang, CC; Keisler, H. Jerome (1989). Model Theory (wydanie trzecie). Elsevier. ISBN   0-7204-0692-7 .
• Dawson, John W. junior (1993). „Zwartość logiki pierwszego rzędu: od Gödla do Lindströma”. Historia i filozofia logiki . 14 : 15–37. doi : 10.1080 / 01445349308837208 .
• Hodges, Wilfrid (1993). Teoria modeli . Cambridge University Press. ISBN   0-521-30442-3 .
• Marker, David (2002). Teoria modelu: wprowadzenie . Teksty magisterskie z matematyki 217. Springer. ISBN   0-387-98760-6 .
• Truss, John K. (1997). Podstawy analizy matematycznej . Oxford University Press. ISBN   0-19-853375-6 .