Epsilon-induction

In mathematics, ${\displaystyle \in }$-induction (epsilon-induction or set-induction) is a variant of transfinite induction.

Considered as an alternative set theory axiom schema, it is called the Axiom (schema) of (set) induction.

It can be used in set theory to prove that all sets satisfy a given property P(x). This is a special case of well-founded induction.

Statement

It states, for any property P, that if for every set x, the truth of P(x) follows from the truth of P for all elements of x, then this property P holds for all sets. In symbols:

${\displaystyle \forall x.{\Big (}\left(\forall y\in x.\,P(y)\right)\rightarrow P(x){\Big )}\ \rightarrow \ \forall z\,P(z)}$

Note that for the "bottom case" where x denotes the empty set, ${\displaystyle \forall y\in x.\,P(y)}$ is vacuously true.

Comparison with natural number induction

The above can be compared with ${\displaystyle \omega }$-induction over the natural numbers ${\displaystyle n\in \{0,1,2,\dots \}}$ for number properties Q. This may be expressed as

${\displaystyle \forall n.{\Big (}Q(n-1)\to Q(n){\Big )}\ \to \ \forall m.\,Q(m)}$

where for "bottom case" n=0 we take "${\displaystyle Q(-1)}$" to be true by definition. Note that both set-induction and ${\displaystyle \omega }$-induction could also be expressed in a way that treats the bottom case explicitly.

Classically, the above ${\displaystyle \omega }$-induction principle can be translated to the following statement:

${\displaystyle \exists n.{\Big (}Q(n-1)\land \neg Q(n){\Big )}\ \lor \ \forall m.\,Q(m)}$

This expresses that, for any property Q, either there is any first number ${\displaystyle n}$ for which Q does not hold, despite Q holding for the preceding case, or - if there is no such failure case - Q is true for all numbers.

Accordingly, in classical ZF, set-induction can be translated to the following statement, clarifying what form of counter-example prevents a set-property P to hold for all sets:

${\displaystyle \exists x.{\Big (}\left(\forall y\in x.\,P(y)\right)\,\land \,\neg P(x){\Big )}\ \lor \ \forall z\,P(z)}$

This expresses that, for any property P, either there a set x for which P does not hold while P being true for all elements of x, or P holds for all sets.

For any property, if one can prove that ${\displaystyle \forall y\in x.\,P(y)}$ implies ${\displaystyle P(x)}$, then the failure case can be ruled out and the formula states that the disjunct ${\displaystyle \forall z\,P(z)}$ must hold.

Independence

In the context of the constructive set theory CZF, adopting the Axiom of regularity would imply the law of excluded middle and also set-induction. But then the resulting theory would be standard ZF. However, conversely, the set-induction implies neither of the two. In other words, with a constructive logic framework, set-induction as stated above is strictly weaker than regularity.

See also

• Mathematical induction
• Transfinite induction
• Well-founded induction
• Constructive set theory
• Non-well-founded set theory