Epsilon-Induktion

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

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle A}$ betrachtet man eine transitive Menge.

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

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

Der Beweis geht von der erfüllten Induktions-Voraussetzung für ${\displaystyle 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 ${\displaystyle x}$ für die ${\displaystyle \neg A(x)}$ gilt. Damit gilt auch ${\displaystyle x\in M}$, sodass ${\displaystyle M}$ nicht leer ist. Somit liefert die Regularität von ${\displaystyle M}$ ein epsilon-minimales Element ${\displaystyle m\in M}$, also ein Element mit ${\displaystyle \neg A(m)}$ welches einen leeren Schnitt mit ${\displaystyle M}$ hat. Jedes Element von ${\displaystyle m}$ ist aufgrund der Transitivität von ${\displaystyle TC(x)}$ wieder in ${\displaystyle TC(x)}$, kann aber wegen der Epsilon-Minimalität von ${\displaystyle m}$ nicht auch in ${\displaystyle M}$ sein. Da ${\displaystyle M}$ durch die Negation des Prädikats ${\displaystyle A}$ charakterisiert ist gilt für alle ${\displaystyle z\in m}$ die Aussage ${\displaystyle A(z)}$. Die Implikation in der Voraussetzung des Induktions-Schemas liefert damit aber wiederum ${\displaystyle A(m)}$, im Widerspruch zum etablierten ${\displaystyle \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 ${\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.