Löwenheim-Skolem-Theorem

aus Wikipedia, der freien Enzyklopädie

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

Inhaltsverzeichnis 1 Erläuterung und Konsequenzen 2 Geschichte 3 Das Skolem-Paradox 4 Weblinks

[Bearbeiten] Erläuterung und Konsequenzen

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 A mindestens so groß wie eine Menge B, wenn es eine surjektive Funktion von A auf B gibt, also eine Funktion, die B voll ausschöpft.

Ein verglichen mit dem Satz von Löwenheim-Skolem verhältnismäßig leicht zu beweisendes Resultat der Modelltheorie besagt, dass, wenn eine Menge von Aussagen durch ein bestimmtes unendliches Modell erfüllt ist, sie immer auch durch ein Modell mit einer größeren Domäne erfüllt ist. Zusammen mit dem Satz von Löwenheim-Skolem ergibt sich, dass eine 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 in bis zur Isomorphie eindeutiger Weise beschrieben werden können.

[Bearbeiten] Geschichte

Der Satz wird zuerst von Leopold Löwenheim im Jahr 1915 bewiesen. Historisch gesehen handelt es sich wohl um das erste nicht-triviale Resultat der Modelltheorie. Aus Löwenheims Beweis folgen eine ganze Reihe interessanter Konsequenzen, die zum Teil von ihm selbst nicht gesehen worden sind. So zeigt Löwenheim ebenfalls:

• dass der einstellige Prädikatenkalkül erster Stufe entscheidbar ist,
• dass der Prädikatenkalkül erster Stufe auf den zweistelligen Prädikatenkalkül erster Stufe reduzierbar ist
• dass es erfüllbare Aussagen des Prädikatenkalküls zweiter Stufe gibt, die kein abzählbares Modell haben.

1920 verallgemeinert Albert Thoralf Skolem Löwenheims Resultat. Zum einen zeigt 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 beweist 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 Modelltheorie meist als Korollar aus dem Vollständigkeits-Satz der Prädikationlogik präsentiert. Zu Zeiten Löwenheims und Skolems war die Vollständigkeit noch nicht bewiesen, so dass sie auf diesem Resultat nicht aufbauen konnten. Umgekehrt gilt, dass zumindest Skolems Beweis leicht in einen Vollständigkeitsbeweis hätte umgeformt werden können.

[Bearbeiten] Das Skolem-Paradox

Skolem selbst hat das Resultat als paradox betrachtet, daher rührt der Ausdruck "Skolem-Paradox". Das Paradoxe besteht darin, dass sich in manchen Theorien erster Stufe (wie der Zermelo-Fraenkel-Mengenlehre) die Existenz von überabzählbar großen Mengen beweisen lässt. Hier scheinen also überabzählbar unendlich viele Individuen vorausgesetzt. Gemäß dem Satz werden jedoch in Wirklichkeit nur abzählbar viele Individuen unterstellt. Der Widerspruch löst sich wie folgt auf: Beim Beweis der Nicht-Existenz einer Surjektion von der "überabzählbaren" auf die abzählbaren Menge werden nicht alle möglichen Funktionen zwischen den beiden Mengen in Betracht gezogen, sondern nur eine Teilmenge davon. D.h. die Zermelo-Fraenkel-Mengentheorie simuliert in gewisser Weise die Folgerungsverhältnisse zwischen einer überabzählbaren und einer abzählbaren Menge anhand zweier abzählbaren Mengen. Obwohl sich nun kein formaler Widerspruch mehr ergibt, bleiben nach Skolem Zweifel an der Geeignetheit der Zermelo-Fraenkel-Mengentheorie für mathematische Untersuchungen.

[Bearbeiten] Weblinks

• Geschichte der Logik von 1900 bis 1935