Epsilon-Induktion

Unter Epsilon-Induktion (auch ∈-Induktion) versteht man in der Mathematik ein spezielles Beweisverfahren der Mengenlehre. Gilt es zu beweisen, dass eine Aussage $A$ für alle Mengen gilt, so reicht es laut Epsilon-Induktion zu zeigen, dass sie für die Mengen gilt, für deren Elemente sie gilt. Präzise ausgedrückt besagt die Epsilon-Induktion also

$\forall x((\forall y\in x.A(y))\rightarrow A(x))\rightarrow \forall xA(x).$

Ihren Namen hat die Epsilon-Induktion dem griechischen Kleinbuchstaben ε zu verdanken, aus dem sich das heutige Elementzeichen entwickelte.

Verhältnis zu Regularität

Die Gültigkeit der Epsilon-Induktion lässt sich für jedes $A$ in ZF beweisen und das Auswahlaxiom ist dafür nicht notwendig.

Maßgeblich geht in den Beweis das klassische Regularitätsaxiom ein. Die Epsilon-Induktion ist ein Axiomenschema, während das Regularitätsaxiom ein einziges Axiom ist, welches nur Mengen betrifft. Es lässt sich dennoch sogar zeigen, dass die Epsilon-Induktion zum Regularitätsaxiom äquivalent ist. Das heißt, tauschte man in ZF das Regularitätsaxiom gegen die Epsilon-Induktion aus, so entstünde ein äquivalentes Axiomensystem. Das Unendlichkeitsaxiom spielt im Beweis der Äquivalenz ebenfalls eine wesentliche Rolle.

Beweis

Zum Beweis der Epsilon-Induktion für $A$ betrachtet man eine transitive Menge.

Für eine gegebene Menge $x$ existiert in ZF die transitive Hülle $TC(x)$, welche auch $x$ als Teilmenge enthält. Man betrachtet damit weiters die Menge

$M:=\{y\in TC(x)\cup \{x\}\mid \neg A(y)\}$

Der Beweis geht von der erfüllten Induktions-Voraussetzung für $A$ aus und demonstriert die Induktions-Behauptung durch herbeiführen eines Widerspruchs im Falles deren Negation: Wäre die Epsilon-Induktion falsch, dann gäbe es eine Menge $x$ für die $\neg A(x)$ gilt. Damit gilt auch $x\in M$, sodass $M$ nicht leer ist. Somit liefert die Regularität von $M$ ein epsilon-minimales Element $m\in M$, also ein Element mit $\neg A(m)$ welches einen leeren Schnitt mit $M$ hat. Jedes Element von $m$ ist aufgrund der Transitivität von $TC(x)$ wieder in $TC(x)$, kann aber wegen der Epsilon-Minimalität von $m$ nicht auch in $M$ sein. Da $M$ durch die Negation des Prädikats $A$ charakterisiert ist gilt für alle $z\in m$ die Aussage $A(z)$. Die Implikation in der Voraussetzung des Induktions-Schemas liefert damit aber wiederum $A(m)$, im Widerspruch zum etablierten $\neg A(m)$.

Anwendung

Die Epsilon-Induktion wird zum Beispiel dafür benutzt, zu zeigen, dass jede Menge in der Von-Neumann-Hierarchie enthalten ist. Zu jeder Menge $x$ findet man also eine Ordinalzahl $\alpha$ mit $x\in V_{\alpha }$. In dem entsprechenden Beweis ist die Aussage $A(x)$ also durch

$A(x)\equiv \exists \alpha \in \operatorname {Ord} .x\in V_{\alpha }$

definiert.

Literatur

• Thomas Jech: Set Theory. Springer-Verlag, Berlin Heidelberg New York 2002, ISBN 3-540-44085-2.