Satz von Löwenheim-Skolem

Der Satz von Löwenheim-Skolem besagt, dass eine abzählbare Menge von Aussagen der Prädikatenlogik erster Stufe, die in einem Modell mit einem überabzählbar unendlich großen Universum erfüllt ist, immer auch in einem Modell mit einer abzählbar unendlich großen Domäne erfüllt ist.

Einige wichtige Begriffe des Satzes seien kurz erläutert: Ein Modell repräsentiert (in einer mathematisch beschreibbaren Form) bestimmte Umstände, die bestehen, wenn bestimmte Aussagen wahr sind. Man sagt dann, dass das Modell die Aussagen erfüllt. Die Domäne (auch Individuenbereich oder Träger genannt) enthält diejenigen Individuen, deren Existenz in dem Modell vorausgesetzt ist. Eine Menge heißt abzählbar unendlich, wenn sie so groß ist wie die Menge der natürlichen Zahlen. Eine überabzählbar unendliche Menge ist größer als die Menge der natürlichen Zahlen. Dabei ist eine Menge ${\displaystyle A}$ mindestens so groß wie eine Menge ${\displaystyle B}$, wenn es eine injektive Funktion von ${\displaystyle B}$ nach ${\displaystyle A}$ gibt.

Ein im Vergleich zu dem Satz von Löwenheim und Skolem leicht zu beweisendes Resultat der Modelltheorie besagt: Wenn eine Menge von Aussagen durch ein bestimmtes unendliches Modell erfüllt ist, so ist sie immer auch durch ein Modell mit einer größeren Domäne erfüllt. Zusammen mit dem Satz von Löwenheim-Skolem ergibt sich, dass eine abzählbare Aussagenmenge, die überhaupt ein unendliches Modell hat, immer auch ein Modell mit einer abzählbar unendlich großen Domäne hat. Aus dem Satz folgt u. a., dass mittels Prädikatenlogik erster Stufe keine unendlichen Strukturen (insbesondere die natürlichen Zahlen) in bis auf Isomorphie eindeutiger Weise beschrieben werden können.

Die Beschränkung auf die Prädikatenlogik erster Stufe ist wesentlich, der Satz lässt sich nicht auf die Prädikatenlogik zweiter Stufe übertragen.

Ist ${\displaystyle \kappa }$ eine Kardinalzahl, die nicht kleiner als die Mächtigkeit der betrachteten konsistenten Menge von Aussagen ist, so hat diese stets ein Modell der Mächtigkeit ${\displaystyle \kappa }$.^[1] Insbesondere gibt es Modelle beliebig großer Mächtigkeit. Auch diese Aussage wird oft als Satz von Löwenheim-Skolem bezeichnet, manchmal als Satz von Löwenheim-Skolem-Tarski.

Der Satz wurde zuerst von Leopold Löwenheim im Jahr 1915 bewiesen. Historisch gesehen handelt es sich um das erste nichttriviale Resultat der Modelltheorie.

1920 verallgemeinerte Albert Thoralf Skolem Löwenheims Resultat. Zum einen zeigte er, dass die Menge von Aussagen selbst abzählbar unendlich groß sein darf (während Löwenheim sein Theorem nur für einzelne Aussagen bewiesen hatte), zum anderen bewies er, dass eine überabzählbare Domäne sich immer unter Bewahrung der Erfüllungsrelation auf eine abzählbare Subdomäne einschränken lässt (für Letzteres muss jedoch das Auswahlaxiom vorausgesetzt werden). Skolem macht bei seinem Beweis Gebrauch von der berühmten Skolemform.

Der Satz wird in modernen Darstellungen der Logik^[2] meist als Korollar aus dem Beweis des Vollständigkeitssatzes der Prädikatenlogik präsentiert. Zu Zeiten Löwenheims und Skolems war die Vollständigkeit noch nicht bewiesen, sodass sie auf diesem Resultat nicht aufbauen konnten. Umgekehrt gilt, dass zumindest Skolems Beweis leicht in einen Vollständigkeitsbeweis hätte umgeformt werden können.

Nimmt man an, dass die Zermelo-Fraenkel-Mengenlehre widerspruchsfrei ist, so hat jedes endliche axiomatische System aus der Zermelo-Fraenkel-Mengenlehre ein abzählbares Modell. Dies folgt aus dem Löwenheim-Skolem-Theorem und wurde weiter oben schon erläutert. Jedoch kann in der Zermelo-Fraenkel-Mengenlehre ein endliches axiomatisches System ${\displaystyle \Psi }$ angegeben werden, sodass die Existenz einer überabzählbaren Menge folgt.

Der Widerspruch löst sich jedoch dann auf, wenn man sich klarmacht, was Abzählbarkeit auf ein Modell bezogen bedeutet.^[3] Sei ${\displaystyle M}$ ein System von ${\displaystyle \Psi }$. Ist weiter ${\displaystyle A\in M}$ eine Menge, die im Modell von ${\displaystyle M}$ überabzählbar ist, so bedeutet dies, dass es in diesem Modell keine Surjektion ${\displaystyle f\colon {\mathcal {N}}\rightarrow A}$ gibt. Die Menge ${\displaystyle {\mathcal {N}}}$ bezeichnet dabei die zu dem Modell ${\displaystyle M}$ relativierte Menge der natürlichen Zahlen. Jedoch bedeutet dies nicht, dass die Menge ${\displaystyle M}$ selbst aus Sicht der Metasprache überabzählbar ist.

Skolem selbst hat das Resultat als paradox betrachtet, daher rührt der Ausdruck Skolemsches Paradoxon.

Das Löwenheim-Skolem-Theorem wurde von dem Philosophen und Logiker Hilary Putnam in der Philosophie auf repräsentationale Systeme angewandt, um folgende These zu begründen: Die Wahrheitsbelegung in allen möglichen Welten fixiert die Referenz sprachlicher Ausdrücke nicht.^[4][5]

• Timothy Bays: Skolem’s Paradox. In: Edward N. Zalta (Hrsg.): Stanford Encyclopedia of Philosophy.
• Richard Zach, Paolo Mancosu, Calixto Badesa: The Development of Mathematical Logic from Russell to Tarski: 1900-1935. In: Leila Haaparanta (Hrsg.): The History of Modern Logic. Oxford University Press, New York und Oxford 2009. S. 178 ff., ucalgary.ca (englisch).

1. ↑ Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. 4. Auflage. Spektrum Akademischer Verlag, Heidelberg u. a. 1996, ISBN 3-8274-0130-5, Kapitel VI, § 2, Satz 2.4.
2. ↑ Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, S. 87 ff. 
3. ↑ Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, S. 91. 
4. ↑ Hilary Putnam: Reason, Truth and History. Cambridge University Press, Cambridge 1981, ISBN 0-521-23035-7.
5. ↑ Hilary Putnam: Realism and Reason. Cambridge University Press, Cambridge u. a. 1983, ISBN 0-521-24672-5 (Philosophical Papers 3).