Levy-Hierarchie

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 \in) heißt \Delta_0-[1], \Sigma_0- oder \Pi_0-Formel, wenn alle vorkommenden Quantifizierungen beschränkt sind, d. h. für eine Formel \phi und Variablen x,y von der Gestalt \forall x (x\in y\rightarrow\phi) (kurz \forall x\in y \phi geschrieben) oder \exist x (x\in y\wedge\phi) (kurz \exist x\in y \phi) sind. Nun definiert man induktiv: Eine \Sigma_{i+1}-Formel ist eine Formel von der Gestalt \exist x \phi für eine \Pi_i-Formel \phi und eine \Pi_{i+1}-Formel ist eine Formel von der Gestalt \forall x \psi für eine \Sigma_i-Formel \psi. Jede \Sigma_i- oder \Pi_i-Formel ist auch eine \Lambda_i-Formel, das heißt eine Formel, in der die maximale Schachtelungstiefe unbeschränkter Quantoren i ist. Die Mengen aller solcher Formeln werden \Sigma_i,\Pi_i,\Lambda_i genannt. \mathfrak{B}(\Sigma_i) bzw. \mathfrak{B}(\Pi_i) sei die Menge aller Formeln, die sich als boolesche Kombinationen von \Sigma_i- bzw. \Pi_i-Formeln ergeben.

Sei nun T eine Theorie in der Sprache der Mengenlehre (etwa die Zermelo-Fraenkel-Mengenlehre ZF). \Sigma_i^T ist dann definiert als die Menge aller Formeln \phi, für die sich die Äquivalenz zu einer \Sigma_i-Formel \psi in T beweisen lässt, d. h. T\vdash\forall x_1\ldots\forall x_n(\phi\leftrightarrow\psi), wobei x_1,\ldots,x_n die freien Variablen in \phi seien. \Pi_i^T ist analog und \Delta_i^T durch \Sigma_i^T\cap\Pi_i^T definiert[2]. T enthalte im Folgenden stets zumindest die Axiome der klassischen Prädikatenlogik erster Stufe. Jede Formel in der Sprache der Mengenlehre liegt für ein i in \Sigma_i^T, da sie sich in Pränexnormalform bringen lässt.

Als Klassen formaler Sprachen lassen sich die Teilmengen X der natürlichen Zahlen (allgemeiner sind auch Relationen möglich) unterscheiden, die \Sigma_i- bzw. \Pi_i- definierbar sind, d. h. für die eine \Sigma_i- bzw. \Pi_i-Formel \phi(x) existiert, sodass \forall x\in X (x\in Y\leftrightarrow \phi(x)) gilt.[3] Aus weiteren Eigenschaften ergibt sich, dass sich die Mengen \Sigma_i,\Pi_i,\Delta_i 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 \Delta_0 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]

  • x\subseteq y
  • Transitivität
  • x\in\mathbf{On}, d. h. x ist eine Ordinalzahl
  • x\in\N
  • x=\N
  • x\cup y=z
  • x\cap y=z
  • x\times y=z
  • x=n für jede natürliche Zahl n

Δ1-definierbar[Bearbeiten]

Σ1-definierbar[Bearbeiten]

Π1-definierbar[Bearbeiten]

Δ2-definierbar[Bearbeiten]

Σ2-definierbar[Bearbeiten]

Π2-definierbar[Bearbeiten]

Σ3-definierbar[Bearbeiten]

  • Es existiert eine superkompakte Kardinalzahl[8]

Abschlusseigenschaften[Bearbeiten]

Enthält T die Axiome von ZF ohne das Unendlichkeitsaxiom und ohne das Ersetzungsaxiom, so ist für i>0 bereits für \varphi\in\Sigma_i^T und jede Variable x auch \exist x\varphi\in\Sigma_i^T und für \varphi\in\Pi_i^T auch \forall x\varphi\in\Pi_i^T. 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 \Delta_0 ausdrücken lassen. Mitunter werden daher auch bereits in der Definition der Levy-Hierarchie Quantorenblöcke zugelassen.[2]

\Sigma_i^T, \Pi_i^T, \Delta_i^T, \Lambda_i^T und \mathfrak{B}(\Sigma_i)^T sind abgeschlossen unter Konjunktion und Disjunktion. \Delta_i^T, \Lambda_i^T und \mathfrak{B}(\Sigma_i)^T sind zudem abgeschlossen unter Negation. Die Negationen von \Sigma_i^T-Formeln sind gerade \Pi_i^T-Formeln und umgekehrt. Enthält T ZF ohne das Unendlichkeitsaxiom, so sind für jedes i die besagten fünf Stufen auch abgeschlossen unter beschränkter Quantifizierung. Die Idee ist die folgende: \forall x\in y \forall z \varphi ist äquivalent zu \forall z\forall x\in y \varphi und \forall x\in y \exist z \varphi ist für eine Formel \varphi^\prime, die in derselben Stufe liegt wie \varphi, äquivalent zu \exist z\forall x\in y \varphi^\prime, wobei z nun als Funktion von x 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 i>0 auch die Abgeschlossenheit der \Sigma_i-, \Pi_i-, \Delta_i-, \Lambda_i- und \mathfrak{B}(\Sigma_i)-definierbaren Sprachen unter Urbildbildung bzgl. einer rekursiven Funktion

Absolutheit[Bearbeiten]

Eine Formel der Mengenlehre \varphi in den n freien Variablen x_1,\ldots,x_n heißt aufwärts absolut für eine Klasse M, wenn \forall x_1,\ldots,x_n\in M (\varphi^M(x_1,\ldots,x_n)\rightarrow\varphi(x_1,\ldots,x_n)) gilt, wobei \varphi^M die Relativierung von \varphi auf M bezeichne. Analog dazu heißt sie abwärts absolut, wenn \forall x_1,\ldots,x_n\in M (\varphi(x_1,\ldots,x_n)\rightarrow\varphi^M(x_1,\ldots,x_n)) gilt. Eine Formel heißt absolut, wenn sie aufwärts und abwärts absolut ist.

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

Sei TC(x) der transitive Abschluss von x, d. h. die minimale transitive Menge, die x enthält. Ist \kappa eine überabzählbare Kardinalzahl, so ist jede \mathfrak{B}(\Sigma_1)-Formel absolut für die Menge \left\{x \mid |TC(x)|<\kappa\right\}.[10][11]

Definierbarkeit von Wahrheit, Trennung und Vollständigkeit[Bearbeiten]

Die Gültigkeit von \Delta_0-Formeln mit gegebener Interpretation freier Variablen – repräsentiert durch eine Kodierung als natürliche Zahlen – lässt sich durch eine \Pi_1-Formel ausdrücken: Man betrachte den transitiven Abschluss T der Menge der Werte der freien Variablen. Für die Wahrheit einer jeden Teilformel einer gegebenen Formel reicht es, die Relativierung auf T zu betrachten. Es lässt sich nun mit einer \Pi_1-Formel die Relation R\subseteq\N\times T^* definieren, sodass genau dann (n,x)\in R, wenn die durch n kodierte \Delta_0-Formel \phi unter der Interpretation x der freien Variablen gültig ist. R ist \Pi_1-definierbar, da es sich als minimale Menge mit bestimmten Abschlusseigenschaften ergibt. Tatsächlich genügt sogar ZF ohne das Unendlichkeitsaxiom, um eine \Pi_1-Definition der Gültigkeit von \Delta_0-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 \Pi_1-Formeln \Pi_1-definierbar (es muss einfach der eine unbeschränkte Allquantor aus der Kodierung extrahiert werden). Es folgt, dass die Gültigkeit von \Sigma_1-Formeln \Sigma_1-definierbar ist (da die Wahrheit von \phi ist äquivalent zur Falschheit von \neg\phi ist) und induktiv ist für jedes n>0 die Wahrheit von \Pi_n-Formeln \Pi_n-definierbar und die von \Sigma_n-Formeln \Sigma_n-definierbar. Hieraus folgt mit dem Undefinierbarkeitssatz von Tarski, dass es sich bei der Levy-Hierarchie tatsächlich um eine Hierarchie handelt: Umfasst T ZF ohne das Unendlichkeitsaxiom und ist das \Delta_n-Fragment von T konsistent, so gilt \Sigma^T_n\subsetneq\Delta^T_{n+1}\subsetneq\Sigma^T_{n+1} und \Pi^T_n\subsetneq\Delta^T_{n+1}\subsetneq\Pi^T_{n+1}, andernfalls würde die Hierarchie für n stationär, es wäre die Wahrheit von \Delta_n-Formeln dann \Delta_n-definierbar, was dem Undefinierbarkeitssatz widerspricht, da die Menge der \Delta_n-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 \Pi_n- bzw. \Sigma_n-Definierbarkeit einer formalen Sprache als objektsprachliche Eigenschaften aufzufassen. In ZF (mit dem Unendlichkeitsaxiom) lässt sich die Trennung sogar beweisen, da die Konsistenz jedes \Delta_n-Fragments von ZF in ZF beweisbar ist. Dies folgt unter Verwendung der Wahrheitsdefinition für \Sigma_n-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 \mathfrak{B}(\Sigma_i)^{ZF}\subsetneq\Lambda_i^{ZF} für i>0.[14]

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

Bezug zur Arithmetik[Bearbeiten]

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

\exist x \forall y 2\cdot y=x

in den \Pi_1-Satz

\forall \N \left(\N\text{ ist die Menge der nat. Zahlen }\right)\rightarrow \exist x\in\N \forall y\in\N 2\cdot y=x

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

\exist X \forall y 2\cdot y\in X

in den \Pi_2-Satz (V ist hier eine Menge, die \mathcal{P}^n(\N) für n\in\N enthält)

\forall V\ \forall \N \left(\N\text{ ist die Menge der nat. Zahlen }\wedge V\text{ transitiv }\wedge\N\in V\wedge\forall P\left(\exist M\in V\ \forall S\in P\ S\subseteq M\right)\rightarrow P\in V\right)\rightarrow \exist X\in V\ X\subseteq\N\wedge\forall y\in X\ 2\cdot y\in X

übersetzen, \Sigma_2 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 (\forall x\subseteq y etc.) zulässt, so fällt die so entstehende Hierarchie ab der Stufe \Delta_2 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 HF bildet ein Modell von ZF ohne das Unendlichkeitsaxiom. Die in diesem Modell \Sigma_1-definierbaren Teilmengen X der natürlichen Zahlen, in dem Sinne, dass eine \Sigma_1-Formel \varphi(x) existiert, sodass n\in X \Leftrightarrow HF\vDash\varphi(x), sind gerade die rekursiv aufzählbaren Mengen, die \Delta_1-definierbaren Teilmengen fallen mit den rekursiven Mengen zusammen. Allgemeiner ist die Levy-Hierarchie für dieses Modell gerade die arithmetische Hierarchie (von der Stufe 0 je nach Definition abgesehen), von der sie in diesem Sinne eine Abstraktion bildet.[15]

Literatur[Bearbeiten]

Weblinks[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 elemantary embeddings of V. Abgerufen am 25. März 2013 (PDF; 558 kB).
  5. a b  Richard Kaye, Tin Lok Wong: On Interpretations of Arithmetic and Set Theory. In: Notre Dame Journal of Formal Logic. Bd. 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. S. 45, abgerufen am 22. März 2013 (PDF; 459 kB).
  13.  Azriel Levy: Axiom schemata of strong infinity in axiomatic set theory. In: Pacific Journal of Mathematics. Bd. 10, Nr. 1, 1960, S. 223–238 (online).
  14. Levy, 1965, S. 68.
  15. Barwise, S. 47.