Levy-Hierarchie

Hierarchien von Formeln in der Mengenlehre

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.

Definition

Bearbeiten

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

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

Δ0-definierbar

Bearbeiten
  •  
  • Transitivität
  •  , d. h.   ist eine Ordinalzahl
  •  
  •  
  •  
  •  
  •  
  •   für jede natürliche Zahl  

Δ1-definierbar

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

Π1-definierbar

Bearbeiten
  •  , d. h.   ist die Potenzmenge von  .
  •  , d. h.   ist eine Kardinalzahl.
  • Regularität einer Kardinalzahl
  • Limes-Kardinalzahlen
  • Starke Unerreichbarkeit einer Kardinalzahl
  •   ist Ordinalzahl und   die Stufe   in der Von-Neumann-Hierarchie

Δ2-definierbar

Bearbeiten

Σ2-definierbar

Bearbeiten

Π2-definierbar

Bearbeiten

Σ3-definierbar

Bearbeiten
  • Es existiert eine superkompakte Kardinalzahl[8]

Abschlusseigenschaften

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

Absolutheit

Bearbeiten

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

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

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]

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

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.