Levy-Hierarchie

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Unter dem Begriff der Levy-Hierarchie werden in der mathematischen Logik, insbesondere der Mengenlehre, eine Reihe von Hierarchien von Formeln und formalen Sprachen subsumiert. Formeln der Mengenlehre werden dabei in einem gewissen Sinne nach ihrer Komplexität geordnet. Formale Sprachen werden nach der Komplexität der sie beschreibenden Formeln in die Hierarchie eingeordnet. Auf solche angewandt reicht die Levy-Hierarchie weit über die arithmetische und die analytische Hierarchie hinaus. Die Betrachtung niedriger Stufen der Hierarchie erlaubt Aussagen über die Übertragbarkeit der Gültigkeit von Aussagen zwischen Modellen der Mengenlehre.

Die Hierarchie wurde 1965 von Azriel Levy eingeführt.

Eine Formel in der Sprache der Mengenlehre (d. h. der Prädikatenlogik erster Stufe mit Gleichheit und der zweistelligen Relation ) heißt -[1], - oder -Formel, wenn alle vorkommenden Quantifizierungen beschränkt sind, d. h. für eine Formel und Variablen von der Gestalt (kurz geschrieben) oder (kurz ) sind. Nun definiert man induktiv: Eine -Formel ist eine Formel von der Gestalt für eine -Formel und eine -Formel ist eine Formel von der Gestalt für eine -Formel . Jede - oder -Formel ist auch eine -Formel, das heißt eine Formel, in der die maximale Schachtelungstiefe unbeschränkter Quantoren ist. Die Mengen aller solcher Formeln werden genannt. bzw. sei die Menge aller Formeln, die sich als boolesche Kombinationen von - bzw. -Formeln ergeben.

Sei nun eine Theorie in der Sprache der Mengenlehre (etwa die Zermelo-Fraenkel-Mengenlehre ). ist dann definiert als die Menge aller Formeln , für die sich die Äquivalenz zu einer -Formel in beweisen lässt, d. h. , wobei die freien Variablen in seien. ist analog und durch definiert[2]. enthalte im Folgenden stets zumindest die Axiome der klassischen Prädikatenlogik erster Stufe. Jede Formel in der Sprache der Mengenlehre liegt für ein in , da sie sich in Pränexnormalform bringen lässt.

Als Klassen formaler Sprachen lassen sich die Teilmengen der natürlichen Zahlen (allgemeiner sind auch Relationen möglich) unterscheiden, die - bzw. - definierbar sind, d. h. für die eine - bzw. -Formel existiert, sodass gilt.[3] Aus weiteren Eigenschaften ergibt sich, dass sich die Mengen in hinreichend starken Axiomensystemen tatsächlich objektsprachlich, ohne Bezugnahme auf Modelle oder Beweisbarkeit, definieren lassen (s. u.).

Ähnliche Hierarchien lassen sich auch bilden, indem auf der Stufe zusätzliche Formeln zugelassen werden – etwa solche, die Terme für bestimmte Mengen wie zum Beispiel Potenzmengen enthalten – und die Definition über die Abschlusseigenschaften entsprechend fortgesetzt wird.

Beispiele von Definierbarkeit

[Bearbeiten | Quelltext bearbeiten]

Hier folgen einige Beispiele, auf welcher Stufe der Levy-Hierarchie sich wichtige mengentheoretische Eigenschaften definieren lassen (ZF vorausgesetzt).[4]

Δ0-definierbar

[Bearbeiten | Quelltext bearbeiten]
  • Transitivität
  • , d. h. ist eine Ordinalzahl
  • für jede natürliche Zahl

Δ1-definierbar

[Bearbeiten | Quelltext bearbeiten]
  • Addition, Multiplikation und Exponentiation auf den natürlichen Zahlen und allgemeiner den Ordinalzahlen[5]
  • ist eine Wohlordnung auf [6]
  • Die Menge aller erblich endlichen Mengen
  • ist Ordinalzahl und die Stufe in der konstruierbaren Hierarchie

Σ1-definierbar

[Bearbeiten | Quelltext bearbeiten]

Π1-definierbar

[Bearbeiten | Quelltext bearbeiten]

Δ2-definierbar

[Bearbeiten | Quelltext bearbeiten]

Σ2-definierbar

[Bearbeiten | Quelltext bearbeiten]

Π2-definierbar

[Bearbeiten | Quelltext bearbeiten]

Σ3-definierbar

[Bearbeiten | Quelltext bearbeiten]
  • Es existiert eine superkompakte Kardinalzahl[8]

Abschlusseigenschaften

[Bearbeiten | Quelltext bearbeiten]

Enthält die Axiome von ZF ohne das Unendlichkeitsaxiom und ohne das Ersetzungsaxiom, so ist für bereits für und jede Variable auch und für auch . Dies folgt daraus, dass sich ein Block von Existenz- bzw. Allquantoren durch einen einzigen Existenz- bzw. Allquantor ersetzen lässt, wobei die Variable, über die quantifiziert wird, dann als Tupel aufgefasst wird und sich Operationen auf Tupeln in ausdrücken lassen. Mitunter werden daher auch bereits in der Definition der Levy-Hierarchie Quantorenblöcke zugelassen.[2]

, , , und sind abgeschlossen unter Konjunktion und Disjunktion. , und sind zudem abgeschlossen unter Negation. Die Negationen von -Formeln sind gerade -Formeln und umgekehrt. Enthält ZF ohne das Unendlichkeitsaxiom, so sind für jedes die besagten fünf Stufen auch abgeschlossen unter beschränkter Quantifizierung. Die Idee ist die folgende: ist äquivalent zu und ist für eine Formel , die in derselben Stufe liegt wie , äquivalent zu , wobei nun als Funktion von aufgefasst wird, wobei für den Beweis der letzteren Äquivalenz das Ersetzungsaxiom verwendet wird. Analog verfährt man mit einem beschränkten Existenzquantor und erhält letztlich induktiv die Abgeschlossenheit. Aus der Abgeschlossenheit unter beschränkter Quantifizierung ergibt sich unter Benutzung des Ersetzungsaxioms und der Definierbarkeit berechenbarer Funktionen mittels der Arithmetik für auch die Abgeschlossenheit der -, -, -, - und -definierbaren Sprachen unter Urbildbildung bzgl. einer rekursiven Funktion

Eine Formel der Mengenlehre in den freien Variablen heißt aufwärts absolut für eine Klasse , wenn gilt, wobei die Relativierung von auf bezeichne. Analog dazu heißt sie abwärts absolut, wenn gilt. Eine Formel heißt absolut, wenn sie aufwärts und abwärts absolut ist.

Für jede transitive Klasse ist jede -Formel absolut. Daraus ergibt sich, dass jede -Formel für jede transitive Klasse aufwärts absolut und jede -Formel abwärts absolut ist.[2]

Sei der transitive Abschluss von , d. h. die minimale transitive Menge, die enthält. Ist eine überabzählbare Kardinalzahl, so ist jede -Formel absolut für die Menge .[10][11]

Definierbarkeit von Wahrheit, Trennung und Vollständigkeit

[Bearbeiten | Quelltext bearbeiten]

Die Gültigkeit von -Formeln mit gegebener Interpretation freier Variablen – repräsentiert durch eine Kodierung als natürliche Zahlen – lässt sich durch eine -Formel ausdrücken: Man betrachte den transitiven Abschluss der Menge der Werte der freien Variablen. Für die Wahrheit einer jeden Teilformel einer gegebenen Formel reicht es, die Relativierung auf zu betrachten. Es lässt sich nun mit einer -Formel die Relation definieren, sodass genau dann , wenn die durch kodierte -Formel unter der Interpretation der freien Variablen gültig ist. ist -definierbar, da es sich als minimale Menge mit bestimmten Abschlusseigenschaften ergibt. Tatsächlich genügt sogar ZF ohne das Unendlichkeitsaxiom, um eine -Definition der Gültigkeit von -Formeln anzugeben, da es genügt, die Betrachtung auf die endliche Menge der Teilformeln der gegebenen Formeln zu beschränken.

Tatsächlich ist sogar die Wahrheit von -Formeln -definierbar (es muss einfach der eine unbeschränkte Allquantor aus der Kodierung extrahiert werden). Es folgt, dass die Gültigkeit von -Formeln -definierbar ist (da die Wahrheit von ist äquivalent zur Falschheit von ist) und induktiv ist für jedes die Wahrheit von -Formeln -definierbar und die von -Formeln -definierbar. Hieraus folgt mit dem Undefinierbarkeitssatz von Tarski, dass es sich bei der Levy-Hierarchie tatsächlich um eine Hierarchie handelt: Umfasst ZF ohne das Unendlichkeitsaxiom und ist das -Fragment von konsistent, so gilt und , andernfalls würde die Hierarchie für stationär, es wäre die Wahrheit von -Formeln dann -definierbar, was dem Undefinierbarkeitssatz widerspricht, da die Menge der -Formeln abgeschlossen unter Negation ist und mit der enthaltenen Arithmetik hinreichend mächtig, sodass das Diagonallemma gilt. Auch für die entsprechende Hierarchie formaler Sprachen gelten somit diese echten Inklusionsbeziehungen. Die jeweilige Definierbarkeit der Wahrheit erlaubt zudem erst, die - bzw. -Definierbarkeit einer formalen Sprache als objektsprachliche Eigenschaften aufzufassen. In ZF (mit dem Unendlichkeitsaxiom) lässt sich die Trennung sogar beweisen, da die Konsistenz jedes -Fragments von ZF in ZF beweisbar ist. Dies folgt unter Verwendung der Wahrheitsdefinition für -Formeln aus dem Reflexionsprinzip, wie es von Levy 1960 veröffentlicht wurde und das unter Voraussetzung der übrigen Axiome äquivalent zum Ersetzungsaxiom zusammen mit dem Unendlichkeitsaxiom ist.[12][13]

Es lässt sich zeigen, dass für .[14]

Eine - bzw. -Menge natürlicher Zahlen heißt - bzw. -vollständig, wenn für jede andere - bzw. -Menge durch eine berechenbare Funktion auf reduzierbar ist, also gilt. Offenbar sind die Mengen der Kodierungen wahrer - bzw. -Sätze für ihre jeweilige Klasse vollständig, muss einfach so gewählt werden, dass es eine entsprechende Einsetzung vornimmt. Aufgrund der Abgeschlossenheit unter berechenbaren Urbildern sind -vollständige Mengen nicht -definierbar und umgekehrt.

Bezug zur Arithmetik

[Bearbeiten | Quelltext bearbeiten]

In diesem Abschnitt wird ZF vorausgesetzt. Aus der -Definierbarkeit von natürlichen Zahlen und der arithmetischen Operationen ergibt sich, dass sich jede Formel der Arithmetik erster Stufe bereits als -Formel ausdrücken lässt. Etwa lässt sich der -Satz

in den -Satz

übersetzen, einen -Satz erhält man entsprechend durch Negationen. Somit enthalten die -definierbaren Sprachen bereits alle -Sprachen, das heißt die gesamte arithmetische Hierarchie. In lassen sich sogar beliebige -Formeln der Arithmetik beliebiger Stufe übersetzen, insbesondere ist die gesamte analytische Hierarchie enthalten. Etwa lässt sich der -Satz

in den -Satz ( ist hier eine Menge, die für enthält)

übersetzen, entsprechend. Die Beziehung ergibt sich auch aus folgender allgemeinerer Beobachtung: Erweitert man die Levy-Hierarchie, indem man als beschränkte Quantifizierung auch beschränkte Quantifizierung über alle Teilmengen ( etc.) zulässt, so fällt die so entstehende Hierarchie ab der Stufe mit der Levy-Hierarchie zusammen.[5]

Die Levy-Hierarchie lässt sich auch in einem konkreten Modell der Mengenlehre betrachten. Die Menge aller erblich endlichen Mengen bildet ein Modell von ZF ohne das Unendlichkeitsaxiom. Die in diesem Modell -definierbaren Teilmengen der natürlichen Zahlen, in dem Sinne, dass eine -Formel existiert, sodass , sind gerade die rekursiv aufzählbaren Mengen, die -definierbaren Teilmengen fallen mit den rekursiven Mengen zusammen. Allgemeiner ist die Levy-Hierarchie für dieses Modell gerade die arithmetische Hierarchie (von der Stufe je nach Definition abgesehen), von der sie in diesem Sinne eine Abstraktion bildet.[15]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Jon Barwise: Admissible Sets and Structures: An Approach to Definability Theory. Springer Science+Business Media, Berlin 1975, ISBN 3-540-07451-1, S. 10 (online).
  2. a b c Devlin, S. 27.
  3. Väänänen, S. 140.
  4. Marios Koulakis: Large cardinals and elementary embeddings of V. (PDF; 558 kB) Abgerufen am 25. März 2013.
  5. a b Richard Kaye, Tin Lok Wong: On Interpretations of Arithmetic and Set Theory. In: Notre Dame Journal of Formal Logic. Band 48, Nr. 4, 2007, S. 505, doi:10.1305/ndjfl/1193667707.
  6. Devlin, S. 29.
  7. a b c d Väänänen, S. 151.
  8. a b c Akihiro Kanamori: The Higher Infinite. Large Cardinals in Set Theory from Their Beginnings. 2. Auflage. Springer, 2009, ISBN 978-3-540-88867-3, S. 302, doi:10.1007/978-3-540-88867-3.
  9. Väänänen, S. 140.
  10. Väänänen, S. 138.
  11. Drake, S. 104.
  12. Joan Bagaria: A gentle introduction to the theory of large cardinals. (PDF; 459 kB) 2011, S. 45, abgerufen am 22. März 2013.
  13. Azriel Levy: Axiom schemata of strong infinity in axiomatic set theory. In: Pacific Journal of Mathematics. Band 10, Nr. 1, 1960, S. 223–238 (online).
  14. Levy, 1965, S. 68.
  15. Barwise, S. 47.