Epsilon-Induktion

Unter Epsilon-Induktion (auch ∈-Induktion) versteht man in der Mathematik ein spezielles Beweisverfahren der Mengenlehre. Gilt es zu beweisen, dass eine Aussage 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

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

Die Gültigkeit der Epsilon-Induktion lässt sich in ZF (das Auswahlaxiom ist dafür nicht notwendig) beweisen. Maßgeblich geht in den Beweis das Regularitätsaxiom ein. So lässt sich 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.

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

Beweisskizze

Meist beweist man die Epsilon-Induktion durch Widerspruch. Wäre sie falsch, so gäbe es bei erfüllter Voraussetzung also eine Menge ${\displaystyle x}$, welche ${\displaystyle A(x)}$ nicht erfüllt. Nun betrachtet man die Menge

${\displaystyle M:=\{y\in TC(x)|\neg A(y)\},}$

wobei ${\displaystyle TC(x)}$ die transitive Hülle von ${\displaystyle x}$ ist, also eine transitive Menge, die ${\displaystyle x}$ als Teilmenge enthält. Per Voraussetzung kann ${\displaystyle M}$ nicht leer sein, also liefert uns die Regularität ein epsilon-minimales Element ${\displaystyle y\in M}$. Jedes Element von ${\displaystyle y}$ kann wegen der Epsilon-Minimalität von ${\displaystyle y}$ nicht mehr in ${\displaystyle M}$ sein. Die Elemente von ${\displaystyle y}$ sind aber aufgrund der Transitivität von ${\displaystyle TC(x)}$ in ${\displaystyle TC(x)}$. Also gilt für alle ${\displaystyle z\in y}$ die Aussage ${\displaystyle A(z)}$. Die Voraussetzung liefert uns nun ${\displaystyle A(y)}$, dies impliziert aber den gewünschten Widerspruch ${\displaystyle y\notin 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 ${\displaystyle x}$ findet man also eine Ordinalzahl ${\displaystyle \alpha }$ mit ${\displaystyle x\in V_{\alpha }}$. In dem entsprechenden Beweis ist die Aussage ${\displaystyle A(x)}$ also durch

${\displaystyle 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.