Twierdzenie Löwenheima-Skolema - Löwenheim–Skolem theorem

W logice matematycznej The twierdzenie Löwenheim-Skolem jest twierdzenie o istnieniu i liczności z modeli , nazwany Leopold Löwenheim i Thoralf Skolem .

Dokładne sformułowanie podano poniżej. Oznacza to, że jeśli policzalna teoria pierwszego rzędu ma nieskończony model , to dla każdej nieskończonej liczby kardynalnej κ ma model o rozmiarze κ , a żadna teoria pierwszego rzędu z nieskończonym modelem nie może mieć unikalnego modelu aż do izomorfizmu . W konsekwencji teorie pierwszego rzędu nie są w stanie kontrolować kardynalności swoich nieskończonych modeli.

Twierdzenie (w dół) Löwenheima-Skolema jest jedną z dwóch kluczowych właściwości, wraz z twierdzeniem o zwartości , które są używane w twierdzeniu Lindströma do scharakteryzowania logiki pierwszego rzędu . Ogólnie rzecz biorąc, twierdzenie Löwenheima-Skolema nie utrzymuje się w silniejszych logikach, takich jak logika drugiego rzędu .

Twierdzenie

W swojej ogólnej formie, twierdzenie löwenheima-skolema stwierdza, że dla każdego podpisu Ď każdy nieskończony σ - struktura M i każdy nieskończona liczba kardynalna k ≥ | σ | , istnieje σ -struktura N taka, że | N | = κ i takie, że

• jeśli κ < | M | wtedy N jest elementarną podstrukturą M ;
• jeśli κ > | M | wtedy N jest elementarnym rozszerzeniem M .

Twierdzenie często dzieli się na dwie części odpowiadające dwóm powyższym przypadkom. Część twierdzenia twierdząca, że ​​struktura ma elementarne podstruktury wszystkich mniejszych nieskończonych kardynałów jest znana jako twierdzenie Löwenheima-Skolema w dół . Część twierdzenia twierdząca, że ​​struktura ma elementarne rozszerzenia wszystkich większych kardynałów jest znana jako twierdzenie Löwenheima-Skolema w górę .

Dyskusja

Poniżej omówimy ogólną koncepcję podpisów i struktur.

Koncepcje

Podpisy

Podpis składa się z zestawu symboli funkcja S _func , zestaw symboli relacja S _rel i funkcją reprezentującą liczbę operandów funkcji i relacji symboli. (Symbol funkcji null jest nazywany symbolem stałym.) W kontekście logiki pierwszego rzędu podpis jest czasami nazywany językiem. Nazywa się ją policzalną, jeśli zbiór zawartych w nim symboli funkcji i relacji jest policzalny, a ogólnie moc sygnatury jest mocą zbioru wszystkich zawartych w nim symboli. ${\displaystyle \operatorname {ar}:S_{\operatorname {funkcja}}\cup S_{\operatorname {rel}}\rightarrow \mathbb {N} _{0}}$

Teoria pierwszego rzędu składa się z ustalonego podpisu i ustalonego zestawu zdań (formuły bez wolnych zmiennych) w tym podpisie. Teorie są często określane przez podanie listy aksjomatów, które generują teorię, lub przez podanie struktury i przyjęcie teorii jako składającej się ze zdań spełnianych przez strukturę.

Konstrukcje / Modele

Biorąc podpis σ , A σ - struktura M jest interpretacja beton z symboli w Ď . Składa się z podstawowego zbioru (często oznaczanego również przez " M ") wraz z interpretacją funkcji i symboli relacji σ . Interpretacja stałego symbolu σ w M jest po prostu elementem M . Bardziej ogólnie, z interpretacja n -ary symbol funkcji F jest funkcją z M ⁿ z M . Podobnie interpretacja symbolu relacyjnego R jest relacją n- argumentową na M , tj. podzbiorem  M ⁿ .

Podstrukturą σ -structure M uzyskuje się poprzez podzbiór N o M , która jest zamykana pod interpretacji wszystkich symboli funkcyjnych w Ď (stąd zawiera interpretacji wszystkich symboli stałych w Ď ), a następnie ograniczenie interpretacje symbole relacji do N . Elementarny podbudowa jest bardzo szczególny przypadek tego; w szczególności elementarna podstruktura spełnia dokładnie te same zdania pierwszego rzędu, co struktura pierwotna (jej elementarne rozszerzenie).

Konsekwencje

Stwierdzenie podane we wstępie następuje natychmiast po przyjęciu M jako nieskończonego modelu teorii. Dowód odwróconej części twierdzenia pokazuje również, że teoria z dowolnie dużymi modelami skończonymi musi mieć model nieskończony; czasami uważa się to za część twierdzenia.

Teorię nazywa się kategoryczną, jeśli ma tylko jeden model, aż do izomorfizmu. Termin ten został wprowadzony przez Veblena (1904) i przez jakiś czas matematycy mieli nadzieję, że zdołają oprzeć matematykę na solidnych podstawach, opisując kategoryczną teorię pierwszego rzędu pewnej wersji teorii mnogości. Twierdzenie Löwenheima-Skolema zadało pierwszy cios tej nadziei, ponieważ sugeruje, że teoria pierwszego rzędu, która ma nieskończony model, nie może być kategoryczna. Później, w 1931 roku, nadzieja została całkowicie zniszczona przez twierdzenie Gödla o niezupełności .

Wiele konsekwencji twierdzenia Löwenheima-Skolema wydawało się sprzeczne z intuicją logikom na początku XX wieku, ponieważ rozróżnienie między właściwościami pierwszego i nie pierwszego rzędu nie zostało jeszcze zrozumiane. Jedną z takich konsekwencji jest istnienie niepoliczalnych modeli prawdziwej arytmetyki , które spełniają każdy aksjomat indukcyjny pierwszego rzędu, ale mają podzbiory nieindukcyjne.

Niech N oznacza liczby naturalne, a R liczby rzeczywiste. Z twierdzenia wynika, że ​​teoria ( N , +, ×, 0, 1) (teoria prawdziwej arytmetyki pierwszego rzędu) ma nieprzeliczalne modele, a teoria ( R , +, ×, 0, 1) (teoria ciał rzeczywistych domkniętych ) ma model przeliczalny. Są oczywiście aksjomaty charakteryzujące ( N , +, ×, 0, 1) i ( R , +, ×, 0, 1) aż do izomorfizmu. Twierdzenie Löwenheima-Skolema pokazuje, że te aksjomatyzacje nie mogą być pierwszorzędowe. Na przykład w teorii liczb rzeczywistych zupełność rzędu liniowego użytego do scharakteryzowania R jako pełnego ciała uporządkowanego jest własnością nie pierwszego rzędu .

Inną konsekwencją, która została uznana za szczególnie niepokojącą, jest istnienie przeliczalnego modelu teorii mnogości, który jednak musi spełniać zdanie mówiące, że liczby rzeczywiste są niepoliczalne. Twierdzenie Cantora mówi, że niektóre zbiory są niepoliczalne. Ta sprzeczna z intuicją sytuacja stała się znana jako paradoks Skolema ; pokazuje, że pojęcie policzalności nie jest absolutne .

Szkic dowodowy

Część dolna

Dla każdego pierwszego rzędu -formula z aksjomatu wyboru zakłada istnienie funkcji ${\displaystyle \sigma}$${\ Displaystyle \ varphi (y, x_ {1}, \ ldots, x_ {n}) \ ,,}$

${\ Displaystyle f_ {\ varphi}: M ^ {n} \ do M}$

tak, że dla wszystkich , albo ${\ Displaystyle a_ {1}, \ ldots, a_ {n} \ w M}$

${\ Displaystyle M \ modele \ varphi (f_ {\ varphi} (a_ {1}, \ kropki, a_ {n}), a_ {1}, \ kropki, a_ {n})}$

lub

${\ Displaystyle M \ modele \ neg \ istnieje r \, \ varphi (y, a_ {1}, \ kropki, a_ {n}) \,.}$

Stosując ponownie aksjomat wyboru otrzymujemy funkcję z formuł pierwszego rzędu do takich funkcji${\displaystyle \varphi}$${\displaystyle f_{\varphi}\,.}$

Rodzina funkcji powoduje powstanie operatora preclosure na zestaw zasilania z${\displaystyle f_{\varphi}}$ ${\ Displaystyle F}$${\ Displaystyle M}$

${\ Displaystyle F (A) = \ {f_ {\ varphi} (a_ {1}, \ kropki, a_ {n}) \ w M \ mid \ varphi \ w \ sigma; \, a_ {1}, \ kropki ,a_{n}\w A\}}$

dla ${\displaystyle A\subseteq M\,.}$

Iteracji przeliczalnie wiele razy wyniki w operatora zamknięcia Biorąc dowolny podzbiór taki sposób, i że określone można zauważyć, że również wtedy jest elementarnym podstruktury przez badanie Tarski-Vaught . ${\ Displaystyle F}$ ${\ Displaystyle F ^ {\ omega} \,.}$${\displaystyle A\subseteq M}$${\ Displaystyle \ lewo \ vert A \ prawy \ vert = \ kappa}$${\ Displaystyle N = F ^ {\ omega} (A) \ ,,}$${\ Displaystyle \ lewo \ vert N \ prawy \ vert = \ kappa \,.}$${\ Displaystyle N}$${\ Displaystyle M}$

Sztuczka zastosowana w tym dowodzie jest zasadniczo spowodowana przez Skolema, który wprowadził do języka symbole funkcyjne dla funkcji Skolema . Można również określić jako funkcja częściowa taki sposób, że określa się wtedy i tylko wtedy, gdy tylko ważne jest to, że jest operatorem preclosure taki sposób, że znajduje się rozwiązanie dla każdego z parametrów wzoru w którym ma rozwiązanie, w i ${\displaystyle f_{\varphi}}$${\displaystyle f_{\varphi}}$${\displaystyle f_{\varphi}}$${\ Displaystyle M \ modele \ istnieje r \ \ varphi (y a_ {1} \ kropki a_ {n}) \ .}$${\ Displaystyle F}$${\ Displaystyle F (A)}$${\ Displaystyle A}$${\ Displaystyle M}$

${\ Displaystyle \ lewo \ vert F (A) \ prawo \ vert \ leq \ lewo \ vert A \ prawo \ vert + \ lewy \ vert \ sigma \ prawy \ vert + \ aleph _ {0} \,.}$

Część górna

Po pierwsze, rozszerza się podpis, dodając nowy symbol stałej dla każdego elementu M . Pełna teoria M dla rozszerzonego podpis Ď” nazywany jest elementarny schemat z M . W następnym kroku dodaje się κ wiele nowych stałych symboli do sygnatury i dodaje do diagramu elementarnego M zdania c ≠ c' dla dowolnych dwóch odrębnych nowych symboli stałych c i c' . Korzystając z twierdzenia o zwartości , łatwo zauważyć, że uzyskana teoria jest spójna. Ponieważ jego modele muszą mieć kardynalność co najmniej κ , dolna część tego twierdzenia gwarantuje istnienie modelu N, który ma kardynalność dokładnie κ . Zawiera izomorficzną kopię M jako elementarną podstrukturę.

W innych logikach

Chociaż (klasyczne) twierdzenie Löwenheima-Skolema jest bardzo ściśle związane z logiką pierwszego rzędu, warianty obowiązują dla innych logik. Na przykład każda spójna teoria w logice drugiego rzędu ma model mniejszy niż pierwszy superkompaktowy kardynał (zakładając, że taki istnieje). Minimalny rozmiar, przy którym twierdzenie Löwenheima-Skolema ma zastosowanie w logice, jest znany jako liczba Löwenheima i może być użyty do scharakteryzowania siły tej logiki. Co więcej, jeśli wychodzimy poza logikę pierwszego rzędu, musimy zrezygnować z jednej z trzech rzeczy: przeliczalnej zwartości, w dół twierdzenia Löwenheima-Skolema lub własności abstrakcyjnej logiki .

Notatki historyczne

Relacja ta oparta jest głównie na Dawsonie (1993) . Aby zrozumieć wczesną historię teorii modeli, należy odróżnić spójność syntaktyczną (nie można wyprowadzić sprzeczności za pomocą reguł dedukcji logiki pierwszego rzędu) od spełnialności (istnieje model). Nieco zaskakujące, jeszcze zanim twierdzenie o zupełności uczyniło to rozróżnienie niepotrzebnym, termin spójny był używany czasami w jednym znaczeniu, a czasami w innym.

Pierwszym znaczącym rezultatem tego, co później stało się teorią modeli, było twierdzenie Löwenheima w publikacji Leopolda Löwenheima „Über Möglichkeiten im Relativkalkül” (1915):

Dla każdej przeliczalnej sygnatury σ każde σ -zdanie, które jest spełnialne, jest spełnialne w modelu przeliczalnym.

Artykuł Löwenheima dotyczył bardziej ogólnego rachunku krewnych Peirce'a- Schrödera ( algebry relacji z kwantyfikatorami). Posługiwał się także przestarzałymi już zapisami Ernsta Schrödera . Streszczenie artykułu w języku angielskim i przy użyciu nowoczesnych notacji patrz Brady (2000 , rozdział 8).

Zgodnie z otrzymanym poglądem historycznym, dowód Löwenheima był błędny, ponieważ domyślnie wykorzystywał lemat Kőniga bez udowodnienia tego, chociaż lemat ten nie był wówczas jeszcze opublikowanym wynikiem. W rewizjonistycznej relacji Badesa (2004) uważa, że ​​dowód Löwenheima był kompletny.

Skolem (1920) dał (poprawny) dowód, używając formuł w formie, którą później nazwano by Skolem normalną postacią i opierając się na aksjomie wyboru:

Każda przeliczalna teoria, która jest spełnialna w modelu M , jest spełnialna w przeliczalnej podstrukturze M .

Skolem (1922) wykazał również następującą słabszą wersję bez aksjomatu wyboru:

Każda teoria przeliczalna, która jest spełnialna w modelu, jest również spełnialna w modelu przeliczalnym.

Skolem (1929) uprościł Skolem (1920) . Wreszcie Anatolij Iwanowicz Malcew (Анато́лий Ива́нович Ма́льцев, 1936) udowodnił twierdzenie Löwenheima-Skolema w całej jego ogólności ( Maltsev 1936 ). Zacytował notatkę Skolema, zgodnie z którą twierdzenie to zostało udowodnione przez Alfreda Tarskiego na seminarium w 1928 r. Dlatego też ogólne twierdzenie jest czasami nazywane twierdzeniem Löwenheima–Skolema–Tarskiego . Ale Tarski nie pamiętał swojego dowodu i pozostaje tajemnicą, jak mógł to zrobić bez twierdzenia o zwartości .

Trochę ironiczne jest to, że nazwisko Skolema łączy się zarówno z kierunkiem twierdzenia w górę, jak i w dół:

„Podążam za zwyczajem nazywając wniosek 6.1.4 rosnącym twierdzeniem Löwenheima-Skolema. Ale w rzeczywistości Skolem nawet w to nie wierzył, ponieważ nie wierzył w istnienie niepoliczalnych zbiorów”. – Hodges (1993) .

„Skolem [...] odrzucił wynik jako bezsensowny; Tarski [...] bardzo rozsądnie odpowiedział, że formalistyczny punkt widzenia Skolema powinien uznać dolne twierdzenie Löwenheima-Skolema za bezsensowne, tak samo jak wznoszące się twierdzenie”. – Hodges (1993) .

„Legenda głosi, że Thoralf Skolem do końca życia był zgorszony skojarzeniem jego nazwiska z rezultatem tego typu, który uważał za absurd, a niewyliczalne zestawy są dla niego fikcją nieistniejącą”. – Poizat (2000) .

Bibliografia

Źródła

Twierdzenie Löwenheima-Skolema jest traktowane we wszystkich tekstach wprowadzających do teorii modeli lub logiki matematycznej .

Publikacje historyczne

• Löwenheim, Leopold (1915), „Über Möglichkeiten im Relativkalkül” (PDF) , Mathematische Annalen , 76 (4): 447-470, doi : 10.1007/BF01458217 , ISSN  0025-5831 , S2CID  116581304
  • Löwenheim, Leopold (1977), „O możliwościach w rachunku krewnych”, Od Frege do Gödel: Książka źródłowa w logice matematycznej, 1879-1931 (3rd ed.), Cambridge, Massachusetts: Harvard University Press, s. 228- 251, ISBN 0-674-32449-8( kopia online , s. 228, w Google Books )
• Malcew, Anatolij Iwanowicz (1936), „Untersuchungen aus dem Gebiete der mathematischen Logik” , Matematicheskii Sbornik , Nowaja Serija, 1(43) (3): 323-336
• Skolem, Thoralf (1920), "logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen" Videnskapsselskapet Skrifter I. Matematisk-naturvidenskabelig Klasse , 4 : 1-36
  • Skolem, Thoralf (1977), „Logico-combinatorical research in satisfiability or provability of the matematyczne twierdzenia: uproszczony dowód twierdzenia L. Löwenheima i uogólnienia twierdzenia”, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.), Cambridge, Massachusetts: Harvard University Press, s. 252-263, ISBN 0-674-32449-8( kopia online , s. 252, w Google Books )
• Skolem, Thoralf (1922), "Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre", Mathematikerkongressen I Helsingfors den 4-7 lipca 1922, den Femte Skandinaviska Matematikerkongressen, Redogörelse : 217-232
  • Skolem, Thoralf (1977), „Kilka uwag na temat aksjomatyzowanej teorii mnogości”, Od Frege do Gödel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.), Cambridge, Massachusetts: Harvard University Press, s. 290-301 , ISBN 0-674-32449-8( kopia online , s. 290, w Google Books )
• Skolem, Thoralf (1929), „ Uber einige Grundlagenfragen der Mathematik”, Skrifter Utgitt av Det Norske Videnskaps-Akademi I Oslo, I. Matematyka-klasa przyrody , 7 : 1-49
• Veblen, Oswald (1904), "System aksjomatów geometrii", Transakcje Amerykańskiego Towarzystwa Matematycznego , 5 (3): 343-384, doi : 10.2307/1986462 , ISSN  0002-9947 , JSTOR  1986462

Źródła drugorzędne

• Badesa, Calixto (2004), Narodziny teorii modelu: twierdzenie Löwenheima w ramach teorii krewnych , Princeton, NJ: Princeton University Press, ISBN 978-0-691-05853-5; Bardziej zwięzła relacja pojawia się w rozdziale 9 Leila Haaparanta , wyd. (2009), Rozwój logiki nowoczesnej , Oxford University Press, ISBN 978-0-19-513731-6
• Brady, Geraldine (2000), Od Peirce do Skolema: zaniedbany rozdział w historii logiki , Elsevier, ISBN 978-0-444-50334-3
• Crossley, JN ; Ash, CJ; Brickhill, CJ; Stillwell, JC; Williams, NH (1972), Czym jest logika matematyczna? , Londyn / Oxford / Nowy Jork: Oxford University Press , s. 59-60, ISBN 0-19-888087-1, Zbl  0251.02001
• Dawson, John W., Jr. (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: Cambridge Univ. Pr., ISBN 978-0-521-30442-9
• Poizat, Bruno (2000), Kurs teorii modeli: Wprowadzenie do współczesnej logiki matematycznej , Berlin, New York: Springer, ISBN 978-0-387-98655-5

Zewnętrzne linki

• Sacharow, A. ; Weisstein, EW "Twierdzenie Löwenheima-Skolema" . MatematykaŚwiat .
• Burris, Stanley N., Składki logików, część II, Od Richarda Dedekinda do Gerharda Gentzena
• Burris, Stanley N., w dół twierdzenie Löwenheima-Skolema
• Simpson, Stephen G. (1998), Teoria modeli