Levy-Hierarchie

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

Eine Formel in der Sprache der Mengenlehre (d. h. der Prädikatenlogik erster Stufe mit Gleichheit und der zweistelligen Relation $\in$) heißt ${\mathrm{\Delta }}_0$-, ${\mathrm{\Sigma }}_0$- oder ${\mathrm{\Pi }}_0$-Formel, wenn alle vorkommenden Quantifizierungen beschränkt sind, d. h. für eine Formel $\varphi$ und Variablen $x,y$ von der Gestalt $\mathrm{\forall }x(x\in y\to \varphi )$ (kurz $\mathrm{\forall }x\in y\varphi$ geschrieben) oder $\mathrm{\exists }x(x\in y\wedge \varphi )$ (kurz $\mathrm{\exists }x\in y\varphi$) sind. Nun definiert man induktiv: Eine ${\mathrm{\Sigma }}_{i+1}$-Formel ist eine Formel von der Gestalt $\mathrm{\exists }x\varphi$ für eine ${\mathrm{\Pi }}_i$-Formel $\varphi$ und eine ${\mathrm{\Pi }}_{i+1}$-Formel ist eine Formel von der Gestalt $\mathrm{\forall }x\psi$ für eine ${\mathrm{\Sigma }}_i$-Formel $\psi$. Jede ${\mathrm{\Sigma }}_i$- oder ${\mathrm{\Pi }}_i$-Formel ist auch eine ${\mathrm{\Lambda }}_i$-Formel, das heißt eine Formel, in der die maximale Schachtelungstiefe unbeschränkter Quantoren $i$ ist. Die Mengen aller solcher Formeln werden ${\mathrm{\Sigma }}_i,{\mathrm{\Pi }}_i,{\mathrm{\Lambda }}_i$ genannt. $𝔅({\mathrm{\Sigma }}_i)$ bzw. $𝔅({\mathrm{\Pi }}_i)$ sei die Menge aller Formeln, die sich als boolesche Kombinationen von ${\mathrm{\Sigma }}_i$- bzw. ${\mathrm{\Pi }}_i$-Formeln ergeben.

Sei nun $T$ eine Theorie in der Sprache der Mengenlehre (etwa die Zermelo-Fraenkel-Mengenlehre $ZF$). ${\mathrm{\Sigma }}_i^T$ ist dann definiert als die Menge aller Formeln $\varphi$, für die sich die Äquivalenz zu einer ${\mathrm{\Sigma }}_i$-Formel $\psi$ in $T$ beweisen lässt, d. h. $T⊢\mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_n(\varphi \leftrightarrow \psi )$, wobei $x_1,\dots ,x_n$ die freien Variablen in $\varphi$ seien. ${\mathrm{\Pi }}_i^T$ ist analog und ${\mathrm{\Delta }}_i^T$ durch ${\mathrm{\Sigma }}_i^T\cap {\mathrm{\Pi }}_i^T$ definiert. $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 ${\mathrm{\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 ${\mathrm{\Sigma }}_i$- bzw. ${\mathrm{\Pi }}_i$- definierbar sind, d. h. für die eine ${\mathrm{\Sigma }}_i$- bzw. ${\mathrm{\Pi }}_i$-Formel $\varphi (x)$ existiert, sodass $\mathrm{\forall }x\in X(x\in Y\leftrightarrow \varphi (x))$ gilt. Aus weiteren Eigenschaften ergibt sich, dass sich die Mengen ${\mathrm{\Sigma }}_i,{\mathrm{\Pi }}_i,{\mathrm{\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 ${\mathrm{\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

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

Δ₀-definierbar

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

Δ₁-definierbar

• Addition, Multiplikation und Exponentiation auf den natürlichen Zahlen und allgemeiner den Ordinalzahlen
• $<$ ist eine Wohlordnung auf $x$
• Die Menge aller erblich endlichen Mengen
• $x$ ist Ordinalzahl und $y$ die Stufe $L_x$ in der konstruierbaren Hierarchie

Σ₁-definierbar

• Endlichkeit
• Abzählbarkeit
• Gleichmächtigkeit

Π₁-definierbar

• $x=𝒫(y)$, d. h. $x$ ist die Potenzmenge von $y$.
• $x\in 𝐂𝐧$, d. h. $x$ ist eine Kardinalzahl.
• Regularität einer Kardinalzahl
• Limes-Kardinalzahlen
• Starke Unerreichbarkeit einer Kardinalzahl
• $x$ ist Ordinalzahl und $y$ die Stufe $V_x$ in der Von-Neumann-Hierarchie

Δ₂-definierbar

• Kontinuumhypothese
• $y$ ist eine $x$-superkompakte Kardinalzahl

Σ₂-definierbar

• Es existiert eine stark unerreichbare Kardinalzahl
• Es existiert eine messbare Kardinalzahl

Π₂-definierbar

• Konstruierbarkeitsaxiom $V=L$
• Entscheidungsproblem in der Dependence Logic
• $x$ ist eine superkompakte Kardinalzahl

Σ₃-definierbar

• Es existiert eine superkompakte Kardinalzahl

Abschlusseigenschaften

Enthält $T$ die Axiome von ZF ohne das Unendlichkeitsaxiom und ohne das Ersetzungsaxiom, so ist für $i>0$ bereits für $\phi \in {\mathrm{\Sigma }}_i^T$ und jede Variable $x$ auch $\mathrm{\exists }x\phi \in {\mathrm{\Sigma }}_i^T$ und für $\phi \in {\mathrm{\Pi }}_i^T$ auch $\mathrm{\forall }x\phi \in {\mathrm{\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 ${\mathrm{\Delta }}_0$ ausdrücken lassen. Mitunter werden daher auch bereits in der Definition der Levy-Hierarchie Quantorenblöcke zugelassen.

${\mathrm{\Sigma }}_i^T$, ${\mathrm{\Pi }}_i^T$, ${\mathrm{\Delta }}_i^T$, ${\mathrm{\Lambda }}_i^T$ und $𝔅({\mathrm{\Sigma }}_i{)}^T$ sind abgeschlossen unter Konjunktion und Disjunktion. ${\mathrm{\Delta }}_i^T$, ${\mathrm{\Lambda }}_i^T$ und $𝔅({\mathrm{\Sigma }}_i{)}^T$ sind zudem abgeschlossen unter Negation. Die Negationen von ${\mathrm{\Sigma }}_i^T$-Formeln sind gerade ${\mathrm{\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: $\mathrm{\forall }x\in y\mathrm{\forall }z\phi$ ist äquivalent zu $\mathrm{\forall }z\mathrm{\forall }x\in y\phi$ und $\mathrm{\forall }x\in y\mathrm{\exists }z\phi$ ist für eine Formel ${\phi }^{\prime }$, die in derselben Stufe liegt wie $\phi$, äquivalent zu $\mathrm{\exists }z\mathrm{\forall }x\in y{\phi }^{\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 ${\mathrm{\Sigma }}_i$-, ${\mathrm{\Pi }}_i$-, ${\mathrm{\Delta }}_i$-, ${\mathrm{\Lambda }}_i$- und $𝔅({\mathrm{\Sigma }}_i)$-definierbaren Sprachen unter Urbildbildung bzgl. einer rekursiven Funktion

Absolutheit

Eine Formel der Mengenlehre $\phi$ in den $n$ freien Variablen $x_1,\dots ,x_n$ heißt aufwärts absolut für eine Klasse $M$, wenn $\mathrm{\forall }{x}_1,\dots ,x_n\in M({\phi }^M(x_1,\dots ,x_n)\to \phi (x_1,\dots ,x_n))$ gilt, wobei ${\phi }^M$ die Relativierung von $\phi$ auf $M$ bezeichne. Analog dazu heißt sie abwärts absolut, wenn $\mathrm{\forall }{x}_1,\dots ,x_n\in M(\phi (x_1,\dots ,x_n)\to {\phi }^M(x_1,\dots ,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 ${\mathrm{\Delta }}_0$-Formel absolut. Daraus ergibt sich, dass jede ${\mathrm{\Sigma }}_1$-Formel für jede transitive Klasse aufwärts absolut und jede ${\mathrm{\Pi }}_1$-Formel abwärts absolut ist.

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 $𝔅({\mathrm{\Sigma }}_1)$-Formel absolut für die Menge $\{x\mid |TC(x)|<\kappa \}$.

Definierbarkeit von Wahrheit, Trennung und Vollständigkeit

Die Gültigkeit von ${\mathrm{\Delta }}_0$-Formeln mit gegebener Interpretation freier Variablen – repräsentiert durch eine Kodierung als natürliche Zahlen – lässt sich durch eine ${\mathrm{\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 ${\mathrm{\Pi }}_1$-Formel die Relation $R\subseteq \mathbb{N}\times T^{*}$ definieren, sodass genau dann $(n,x)\in R$, wenn die durch $n$ kodierte ${\mathrm{\Delta }}_0$-Formel $\varphi$ unter der Interpretation $x$ der freien Variablen gültig ist. $R$ ist ${\mathrm{\Pi }}_1$-definierbar, da es sich als minimale Menge mit bestimmten Abschlusseigenschaften ergibt. Tatsächlich genügt sogar ZF ohne das Unendlichkeitsaxiom, um eine ${\mathrm{\Pi }}_1$-Definition der Gültigkeit von ${\mathrm{\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 ${\mathrm{\Pi }}_1$-Formeln ${\mathrm{\Pi }}_1$-definierbar (es muss einfach der eine unbeschränkte Allquantor aus der Kodierung extrahiert werden). Es folgt, dass die Gültigkeit von ${\mathrm{\Sigma }}_1$-Formeln ${\mathrm{\Sigma }}_1$-definierbar ist (da die Wahrheit von $\varphi$ ist äquivalent zur Falschheit von $\mathrm{\neg }\varphi$ ist) und induktiv ist für jedes $n>0$ die Wahrheit von ${\mathrm{\Pi }}_n$-Formeln ${\mathrm{\Pi }}_n$-definierbar und die von ${\mathrm{\Sigma }}_n$-Formeln ${\mathrm{\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 ${\mathrm{\Delta }}_n$-Fragment von $T$ konsistent, so gilt ${\mathrm{\Sigma }}_n^T⊊{\mathrm{\Delta }}_{n+1}^T⊊{\mathrm{\Sigma }}_{n+1}^T$ und ${\mathrm{\Pi }}_n^T⊊{\mathrm{\Delta }}_{n+1}^T⊊{\mathrm{\Pi }}_{n+1}^T$, andernfalls würde die Hierarchie für $n$ stationär, es wäre die Wahrheit von ${\mathrm{\Delta }}_n$-Formeln dann ${\mathrm{\Delta }}_n$-definierbar, was dem Undefinierbarkeitssatz widerspricht, da die Menge der ${\mathrm{\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 ${\mathrm{\Pi }}_n$- bzw. ${\mathrm{\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 ${\mathrm{\Delta }}_n$-Fragments von ZF in ZF beweisbar ist. Dies folgt unter Verwendung der Wahrheitsdefinition für ${\mathrm{\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.

Es lässt sich zeigen, dass $𝔅({\mathrm{\Sigma }}_i{)}^{ZF}⊊{\mathrm{\Lambda }}_i^{ZF}$ für $i>0$.

Eine ${\mathrm{\Pi }}_n$- bzw. ${\mathrm{\Sigma }}_n$-Menge $C$ natürlicher Zahlen heißt ${\mathrm{\Pi }}_n$- bzw. ${\mathrm{\Sigma }}_n$-vollständig, wenn für jede andere ${\mathrm{\Pi }}_n$- bzw. ${\mathrm{\Sigma }}_n$-Menge $A\subseteq \mathbb{N}$ durch eine berechenbare Funktion $f:\mathbb{N}\to \mathbb{N}$ auf $C$ reduzierbar ist, also $x\in A\iff f(x)\in C$ gilt. Offenbar sind die Mengen der Kodierungen wahrer ${\mathrm{\Pi }}_n$- bzw. ${\mathrm{\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 ${\mathrm{\Pi }}_n$-vollständige Mengen nicht ${\mathrm{\Sigma }}_n$-definierbar und umgekehrt.

Bezug zur Arithmetik

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

$\mathrm{\exists }x\mathrm{\forall }y2\cdot y=x$

in den ${\mathrm{\Pi }}_1$-Satz

$\mathrm{\forall }\mathbb{N}\left(\mathbb{N}\text{ ist die Menge der nat. Zahlen }\right)\to \mathrm{\exists }x\in \mathbb{N}\mathrm{\forall }y\in \mathbb{N}2\cdot y=x$

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

$\mathrm{\exists }X\mathrm{\forall }y2\cdot y\in X$

in den ${\mathrm{\Pi }}_2$-Satz ($V$ ist hier eine Menge, die ${𝒫}^n(\mathbb{N})$ für $n\in \mathbb{N}$ enthält)

$\mathrm{\forall }V\mathrm{\forall }\mathbb{N}(\mathbb{N}\text{ ist die Menge der nat. Zahlen }\wedge V\text{ transitiv }\wedge \mathbb{N}\in V\wedge \mathrm{\forall }P(\mathrm{\exists }M\in V\mathrm{\forall }S\in PS\subseteq M)\to P\in V)\to \mathrm{\exists }X\in VX\subseteq \mathbb{N}\wedge \mathrm{\forall }y\in X2\cdot y\in X$

übersetzen, ${\mathrm{\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 ($\mathrm{\forall }x\subseteq y$ etc.) zulässt, so fällt die so entstehende Hierarchie ab der Stufe ${\mathrm{\Delta }}_2$ mit der Levy-Hierarchie zusammen.

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 ${\mathrm{\Sigma }}_1$-definierbaren Teilmengen $X$ der natürlichen Zahlen, in dem Sinne, dass eine ${\mathrm{\Sigma }}_1$-Formel $\phi (x)$ existiert, sodass $n\in X\iff HF\models \phi (x)$, sind gerade die rekursiv aufzählbaren Mengen, die ${\mathrm{\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.

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur

Weblinks

• Vorlage:NLab