Epsilon induction

Under epsilon-induction (also ∈-induction) is understood in mathematics , a special proof method of set theory . If it is necessary to prove that a statement is valid for all sets, then according to the epsilon induction it is sufficient to show that it is valid for the sets for whose elements it is valid. To put it precisely, the epsilon induction means

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

The validity of the epsilon induction can be proven in ZF (the axiom of choice is not necessary for this). The axiom of regularity is decisive in the proof . So it can even be shown that the epsilon induction is equivalent to the regularity axiom. That is, if one exchanged the regularity axiom for the epsilon induction in ZF, an equivalent axiom system would arise.

The epsilon induction owes its name to the Greek lowercase letter ε , from which today's element symbol developed.

Evidence sketch

Usually one proves the epsilon induction by contradiction. If it were wrong, there would be a set that does not fulfill if the assumption is fulfilled. Now look at the crowd ${\ displaystyle x}$ ${\ displaystyle A (x)}$

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

where the transitive shell of is, i.e. a transitive set that contains as a subset. By assumption, it can not be empty, so regularity gives us an epsilon-minimal element . Each element of can no longer be in because of the epsilon minimality of . The elements of but because of the transitive in . So the statement applies to all of them . The premise now gives us, but this implies the desired contradiction . ${\ displaystyle TC (x)}$ ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle M}$ ${\ displaystyle y \ in M}$ ${\ displaystyle y}$ ${\ displaystyle y}$ ${\ displaystyle M}$ ${\ displaystyle y}$ ${\ displaystyle TC (x)}$ ${\ displaystyle TC (x)}$ ${\ displaystyle z \ in y}$ ${\ displaystyle A (z)}$ ${\ displaystyle A (y)}$ ${\ displaystyle y \ notin M}$

application

For example, the epsilon induction is used to show that any set is in the Von Neumann hierarchy . So for every set one finds an ordinal number with . In the corresponding proof, the statement is through ${\ displaystyle x}$ ${\ displaystyle \ alpha}$ ${\ displaystyle x \ in V _ {\ alpha}}$ ${\ displaystyle A (x)}$

{\ displaystyle A (x) \ equiv \ exists \ alpha \ in \ operatorname {Ord} .x \ in V _ {\ alpha}}

Are defined.

literature

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