Satz von Löwenheim-Skolem - Löwenheim–Skolem theorem

In der mathematischen Logik ist der Löwenheim-Skolem-Satz ein Satz über die Existenz und Kardinalität von Modellen , benannt nach Leopold Löwenheim und Thoralf Skolem .

Die genaue Formulierung ist unten angegeben. Es impliziert, dass, wenn eine abzählbare Theorie erster Ordnung ein unendliches Modell hat , sie für jede unendliche Kardinalzahl κ ein Modell der Größe κ hat , und dass keine Theorie erster Ordnung mit einem unendlichen Modell bis auf Isomorphie ein eindeutiges Modell haben kann . Folglich sind Theorien erster Ordnung nicht in der Lage, die Kardinalität ihrer unendlichen Modelle zu kontrollieren.

Der (abwärts gerichtete) Löwenheim-Skolem-Satz ist neben dem Kompaktheitssatz eine der beiden Schlüsseleigenschaften, die im Satz von Lindström verwendet werden , um die Logik erster Ordnung zu charakterisieren . Im Allgemeinen gilt das Löwenheim-Skolem-Theorem nicht in stärkeren Logiken wie der Logik zweiter Ordnung .

Satz

In seiner allgemeinen Form, der Löwenheim-Skolem Satz besagt , dass für jede Signatur σ , jede unendliche σ - Struktur M und jede unendliche Kardinalzahl & kgr; & ge ; | & sgr; | Gibt es eine σ -Struktur N , so dass | N | = κ und so dass

• wenn κ < | M | dann ist N eine elementare Unterstruktur von M ;
• wenn κ > | M | dann ist N eine elementare Erweiterung von M .

Der Satz wird oft in zwei Teile geteilt, die den beiden obigen Fällen entsprechen. Der Teil des Satzes, der behauptet, dass eine Struktur elementare Unterstrukturen aller kleineren unendlichen Kardinalitäten hat, wird als abwärts gerichteter Löwenheim-Skolem-Satz bezeichnet . Der Teil des Satzes, der behauptet, dass eine Struktur elementare Erweiterungen aller größeren Kardinalitäten hat, ist als aufwärts gerichteter Löwenheim-Skolem-Satz bekannt .

Diskussion

Im Folgenden gehen wir auf das allgemeine Konzept von Signaturen und Strukturen ein.

Konzepte

Unterschriften

Eine Signatur besteht aus einem Satz von Funktionssymbolen S _func , einem Satz von Beziehungssymbolen S _rel und einer Funktion, die die Anzahl von Funktions- und Beziehungssymbolen darstellt. (Ein nulläres Funktionssymbol wird als konstantes Symbol bezeichnet.) Im Kontext der Logik erster Ordnung wird eine Signatur manchmal als Sprache bezeichnet. Sie heißt abzählbar, wenn die Menge der darin enthaltenen Funktions- und Beziehungssymbole abzählbar ist, und im Allgemeinen ist die Kardinalität einer Signatur die Kardinalität der Menge aller darin enthaltenen Symbole. ${\displaystyle \operatorname {ar} :S_{\operatorname {func} }\cup S_{\operatorname {rel} }\rightarrow \mathbb {N} _{0}}$

Eine Theorie erster Ordnung besteht aus einer festen Signatur und einer festen Menge von Sätzen (Formeln ohne freie Variablen) in dieser Signatur. Theorien werden oft spezifiziert, indem eine Liste von Axiomen angegeben wird, die die Theorie erzeugen, oder indem eine Struktur angegeben wird und die Theorie aus den von der Struktur erfüllten Sätzen besteht.

Strukturen / Modelle

Bei einer Signatur σ eine σ - Struktur M ist eine konkrete Interpretation der Symbole in σ . Es besteht aus einer zugrunde liegenden Menge (oft auch mit " M " bezeichnet) zusammen mit einer Interpretation der Funktions- und Beziehungssymbole von σ . Eine Interpretation eines konstanten Symbols von σ in M ist einfach ein Element von M . Allgemeiner gesagt ist eine Interpretation eines n- ären Funktionssymbols f eine Funktion von M ⁿ bis M . Ebenso ist eine Interpretation eines Relationssymbols R eine n- äre Relation auf M , dh eine Teilmenge von  M ⁿ .

Eine Unterstruktur einer σ -Struktur M erhält man, indem man eine Teilmenge N von M nimmt, die unter den Interpretationen aller Funktionssymbole in σ abgeschlossen ist (also die Interpretationen aller konstanten Symbole in σ einschließt ) und dann die Interpretationen der einschränkt Beziehungssymbole zu N . Ein elementarer Unterbau ist dabei ein ganz besonderer Fall; insbesondere erfüllt eine elementare Unterstruktur genau die gleichen Sätze erster Ordnung wie die ursprüngliche Struktur (ihre elementare Erweiterung).

Folgen

Die in der Einleitung gegebene Aussage folgt unmittelbar, indem M als ein unendliches Modell der Theorie angenommen wird. Der Beweis des Aufwärtsteils des Satzes zeigt auch, dass eine Theorie mit beliebig großen endlichen Modellen ein unendliches Modell haben muss; manchmal wird dies als Teil des Theorems angesehen.

Eine Theorie heißt kategorial, wenn sie bis auf Isomorphie nur ein Modell hat. Dieser Begriff wurde von Veblen (1904) eingeführt , und einige Zeit danach hofften Mathematiker, die Mathematik auf eine solide Grundlage stellen zu können, indem sie eine kategoriale Theorie erster Ordnung einer Version der Mengenlehre beschreiben. Der Löwenheim-Skolem-Satz versetzte dieser Hoffnung einen ersten Schlag, da er impliziert, dass eine Theorie erster Ordnung mit einem unendlichen Modell nicht kategorisch sein kann. Später, im Jahr 1931, wurde die Hoffnung durch Gödels Unvollständigkeitssatz völlig zerstört .

Viele Konsequenzen des Löwenheim-Skolem-Theorems schienen den Logikern des frühen 20. Jahrhunderts kontraintuitiv, da die Unterscheidung zwischen Eigenschaften erster und nicht erster Ordnung noch nicht verstanden wurde. Eine solche Konsequenz ist die Existenz von unzähligen Modellen der wahren Arithmetik , die jedes Induktionsaxiom erster Ordnung erfüllen, aber nicht-induktive Teilmengen haben.

Seien N die natürlichen Zahlen und R die reellen Zahlen . Aus dem Satz folgt, dass die Theorie von ( N , +, ×, 0, 1) (die Theorie der wahren Arithmetik erster Ordnung) unzählige Modelle hat, und dass die Theorie von ( R , +, ×, 0, 1) (die Theorie der reellen geschlossenen Körper ) hat ein abzählbares Modell. Es gibt natürlich Axiomatisierungen, die ( N , +, ×, 0, 1) und ( R , +, ×, 0, 1) bis hin zum Isomorphismus charakterisieren . Der Satz von Löwenheim-Skolem zeigt, dass diese Axiomatisierungen nicht erster Ordnung sein können. In der Theorie der reellen Zahlen ist beispielsweise die Vollständigkeit einer linearen Ordnung, die verwendet wird, um R als einen vollständig geordneten Körper zu charakterisieren , eine Eigenschaft , die nicht erster Ordnung ist .

Eine weitere als besonders besorgniserregend angesehene Konsequenz ist die Existenz eines abzählbaren Modells der Mengenlehre, das dennoch den Satz erfüllen muss, dass die reellen Zahlen nicht abzählbar sind. Der Satz von Cantor besagt, dass einige Mengen überabzählbar sind. Diese kontraintuitive Situation wurde als Skolems Paradox bekannt ; es zeigt, dass der Begriff der Abzählbarkeit nicht absolut ist .

Beweisskizze

Abwärtsteil

Für jede erster Ordnung -Formel das Axiom der Wahl impliziert die Existenz einer Funktion ${\displaystyle \sigma}$${\displaystyle\varphi(y,x_{1},\ldots,x_{n})\,,}$

${\displaystyle f_{\varphi}:M^{n}\to M}$

so dass für alle entweder ${\displaystyle a_{1},\ldots,a_{n}\in M}$

${\displaystyle M\models \varphi (f_{\varphi}(a_{1},\dots,a_{n}),a_{1},\dots,a_{n})}$

oder

${\displaystyle M\models\neg\exists y\,\varphi (y,a_{1},\dots,a_{n})\,.}$

Durch erneutes Anwenden des Auswahlaxioms erhalten wir eine Funktion aus den Formeln erster Ordnung auf solche Funktionen${\displaystyle\varphi}$${\displaystyle f_{\varphi}\,.}$

Die Familie der Funktionen führt zu einem Vorabschlussoperator auf der Potenzmenge von${\displaystyle f_{\varphi}}$ ${\displaystyle F}$${\displaystyle M}$

${\displaystyle F(A)=\{f_{\varphi}(a_{1},\dots,a_{n})\in M\mid\varphi\in\sigma ;\,a_{1},\dots ,a_{n}\in A\}}$

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

Abzählbar viele Iterationen führen zu einem Abschlussoperator. Nimmt eine beliebige Teilmenge, so dass , und nachdem man definiert hat , kann man sehen, dass auch Then eine elementare Teilstruktur von nach dem Tarski-Vaught-Test ist . ${\displaystyle F}$ ${\displaystyle F^{\omega}\,.}$${\displaystyle A\subseteq M}$${\displaystyle \left\vert A\right\vert =\kappa}$${\displaystyle N=F^{\omega}(A)\,,}$${\displaystyle \left\vert N\right\vert =\kappa\,.}$${\displaystyle N}$${\displaystyle M}$

Der Trick in diesem Beweis ist im Wesentlichen Skolem zu verdanken, der Funktionssymbole für die Skolem-Funktionen in die Sprache eingeführt hat. Man könnte auch die definieren , wie Teilfunktionen , so dass festgelegt wird , wenn und nur wenn der einzige wichtige Punkt ist , dass ein Vorschließen Operator , so daß eine Lösung für jede Formel mit Parametern enthält , in dem eine Lösung in hat , und dass ${\displaystyle f_{\varphi}}$${\displaystyle f_{\varphi}}$${\displaystyle f_{\varphi}}$${\displaystyle M\models \exists y\,\varphi (y,a_{1},\dots,a_{n})\,.}$${\displaystyle F}$${\displaystyle F(A)}$${\displaystyle A}$${\displaystyle M}$

${\displaystyle \left\vert F(A)\right\vert \leq \left\vert A\right\vert +\left\vert \sigma \right\vert +\aleph _{0}\,.}$

Aufwärtsteil

Zuerst erweitert man die Signatur, indem man für jedes Element von M ein neues konstantes Symbol hinzufügt . Die vollständige Theorie von M für die erweiterte Signatur σ' heißt das Elementardiagramm von M . Im nächsten Schritt fügt man der Signatur κ viele neue Konstantensymbole hinzu und fügt dem Elementardiagramm von M die Sätze c ≠ c' für je zwei verschiedene neue Konstantensymbole c und c' hinzu . Unter Verwendung des Kompaktheitssatzes kann man leicht erkennen, dass die resultierende Theorie konsistent ist. Seit seiner Modelle Mächtigkeit mindestens haben muss κ garantiert der nach unten Teil dieses Satzes die Existenz eines Modells N die Kardinalität genau hat κ . Es enthält eine isomorphe Kopie von M als elementare Unterstruktur.

In anderen Logiken

Obwohl der (klassische) Löwenheim-Skolem-Satz sehr eng an die Logik erster Ordnung gebunden ist, gelten Varianten für andere Logiken. Zum Beispiel hat jede konsistente Theorie in der Logik zweiter Ordnung ein Modell, das kleiner ist als der erste superkompakte Kardinal (vorausgesetzt, es existiert). Die minimale Größe, bei der ein (abwärts gerichteter) Satz vom Löwenheim-Skolem-Typ in einer Logik gilt, wird als Löwenheim-Zahl bezeichnet und kann verwendet werden, um die Stärke dieser Logik zu charakterisieren. Darüber hinaus müssen wir, wenn wir über die Logik erster Ordnung hinausgehen, eines von drei Dingen aufgeben: abzählbare Kompaktheit, den abwärts gerichteten Löwenheim-Skolem-Satz oder die Eigenschaften einer abstrakten Logik .

Historische Notizen

Diese Darstellung basiert hauptsächlich auf Dawson (1993) . Um die Frühgeschichte der Modelltheorie zu verstehen, muss man zwischen syntaktischer Konsistenz (mit den Deduktionsregeln der Logik erster Ordnung lässt sich kein Widerspruch ableiten) und Erfüllbarkeit (es gibt ein Modell) unterscheiden. Überraschenderweise wurde der Begriff konsistent manchmal in der einen und manchmal in der anderen Bedeutung verwendet , noch bevor das Vollständigkeitstheorem die Unterscheidung überflüssig machte .

Das erste signifikante Ergebnis der späteren Modelltheorie war Löwenheims Satz in Leopold Löwenheims Veröffentlichung "Über Möglichkeiten im Relativkalkül" (1915):

Für jede abzählbare Signatur σ ist jeder erfüllbare σ -Satz in einem abzählbaren Modell erfüllbar.

Löwenheims Aufsatz beschäftigte sich eigentlich mit der allgemeineren Peirce- Schröder- Verwandtschaftsrechnung ( Relationsalgebra mit Quantoren). Dabei verwendete er auch die mittlerweile veralteten Notationen von Ernst Schröder . Für eine Zusammenfassung des Artikels in englischer Sprache und unter Verwendung moderner Notationen siehe Brady (2000 , Kapitel 8).

Löwenheims Beweis war nach gängiger historischer Sicht fehlerhaft, weil er implizit das Lemma von König ohne Beweis verwendete, obwohl das Lemma zu diesem Zeitpunkt noch kein veröffentlichtes Ergebnis war. Badesa (2004) hält Löwenheims Beweis in einer revisionistischen Darstellung für vollständig.

Skolem (1920) lieferte einen (richtigen) Beweis mit Formeln in der späteren Skolem-Normalform und unter Berufung auf das Auswahlaxiom:

Jede abzählbare Theorie, die in einem Modell M erfüllbar ist, ist in einer abzählbaren Unterstruktur von M erfüllbar .

Skolem (1922) bewies auch die folgende schwächere Version ohne das Axiom der Wahl:

Jede abzählbare Theorie, die in einem Modell erfüllbar ist, ist auch in einem abzählbaren Modell erfüllbar.

Skolem (1929) vereinfacht Skolem (1920) . Schließlich bewies Anatoly Ivanovich Maltsev (Анато́лий Ива́нович Ма́льцев, 1936) den Löwenheim-Skolem-Satz in seiner vollen Allgemeinheit ( Maltsev 1936 ). Er zitierte eine Notiz von Skolem, wonach der Satz 1928 von Alfred Tarski in einem Seminar bewiesen worden war . Daher wird der allgemeine Satz manchmal als Löwenheim-Skolem-Tarski-Satz bezeichnet . Aber Tarski erinnerte sich nicht an seinen Beweis, und es bleibt ein Rätsel, wie er es ohne den Kompaktheitssatz schaffen konnte .

Es ist etwas ironisch, dass Skolems Name sowohl mit der Aufwärtsrichtung des Theorems als auch mit der Abwärtsrichtung verbunden ist:

"Ich folge der Gewohnheit, Korollar 6.1.4 den aufwärts gerichteten Löwenheim-Skolem-Satz zu nennen. Aber Skolem glaubte es nicht einmal, weil er nicht an die Existenz unzählbarer Mengen glaubte." – Hodges (1993) .

"Skolem [...] verwarf das Ergebnis als bedeutungslos; Tarski [...] antwortete sehr vernünftig, dass Skolems formalistische Sichtweise den abwärts gerichteten Löwenheim-Skolem-Satz ebenso für bedeutungslos halten sollte wie den aufwärts." – Hodges (1993) .

"Die Legende besagt, dass Thoralf Skolem bis zu seinem Lebensende über die Assoziation seines Namens mit einem Ergebnis dieser Art empört war, das er für eine Absurdität hielt, und unzählbare Sets seien für ihn Fiktionen ohne reale Existenz." – Poizat (2000) .

Verweise

Quellen

Das Löwenheim-Skolem-Theorem wird in allen einführenden Texten zur Modelltheorie oder zur mathematischen Logik behandelt .

Historische Veröffentlichungen

• 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), "Über Möglichkeiten in der Verwandtschaftsrechnung", From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3. Aufl.), Cambridge, Massachusetts: Harvard University Press, S. 228– 251, ISBN 0-674-32449-8( Online-Kopie , S. 228, bei Google Books )
• Maltsev, Anatoly Ivanovich (1936), "Untersuchungen aus dem Gebiete der mathematischen Logik" , Matematicheskii Sbornik , Novaya Seriya, 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), "Logiko-kombinatorische Untersuchungen zur Erfüllbarkeit oder Beweisbarkeit mathematischer Aussagen: Ein vereinfachter Beweis eines Satzes von L. Löwenheim und Verallgemeinerungen des Satzes", Von Frege bis Gödel: A Source Book in Mathematical Logic, 1879-1931 (3. Aufl.), Cambridge, Massachusetts: Harvard University Press, S. 252–263, ISBN 0-674-32449-8( Online-Kopie , S. 252, bei Google Books )
• Skolem, Thoralf (1922), "Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre", Mathematikerkongressen I Helsingfors den 4–7 Juli 1922, den Femte Skandinaviska Matematikerkongressen, Redogörelse : 217–232
  • Skolem, Thoralf (1977), „Einige Bemerkungen zur axiomatisierten Mengenlehre“, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3. Aufl.), Cambridge, Massachusetts: Harvard University Press, S. 290–301 , ISBN 0-674-32449-8( Online-Kopie , S. 290, bei Google Books )
• Skolem, Thoralf (1929), "Über einige Grundlagenfragen der Mathematik", Skrifter Utgitt av Det Norske Videnskaps-Akademi I Oslo, I. Matematisk-naturvidenskabelig Klasse , 7 : 1–49
• Veblen, Oswald (1904), "A System of Axioms for Geometry", Transactions of the American Mathematical Society , 5 (3): 343–384, doi : 10.2307/1986462 , ISSN  0002-9947 , JSTOR  1986462

Sekundäre Quellen

• Badesa, Calixto (2004), Die Geburt der Modelltheorie: Löwenheims Theorem im Rahmen der Relativitätstheorie , Princeton, NJ: Princeton University Press, ISBN 978-0-691-05853-5; Eine prägnantere Darstellung erscheint in Kapitel 9 von Leila Haaparanta , ed. (2009), Die Entwicklung moderner Logik , Oxford University Press, ISBN 978-0-19-513731-6
• Brady, Geraldine (2000), From Peirce to Skolem: A Neglected Chapter in the History of Logic , Elsevier, ISBN 978-0-444-50334-3
• Crossley, JN ; Ash, CJ; Brickhill, CJ; Stillwell, JC; Williams, NH (1972), Was ist mathematische Logik? , London/Oxford/New York: Oxford University Press , S. 59–60, ISBN 0-19-888087-1, Zbl  0251.02001
• Dawson, John W., Jr. (1993), "The compactness of First-Order Logic: From Gödel to Lindström", History and Philosophy of Logic , 14 : 15–37, doi : 10.1080/01445349308837208
• Hodges, Wilfrid (1993), Modelltheorie , Cambridge: Cambridge Univ. Pr., ISBN 978-0-521-30442-9
• Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic , Berlin, New York: Springer, ISBN 978-0-387-98655-5

Externe Links

• Sacharow, A. ; Weisstein, EW "Theorem von Löwenheim-Skolem" . MathWorld .
• Burris, Stanley N., Beiträge der Logiker, Teil II, Von Richard Dedekind bis Gerhard Gentzen
• Burris, Stanley N., Abwärts gerichteter Löwenheim-Skolem-Satz
• Simpson, Stephen G. (1998), Modelltheorie