Epsilon-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 {\Big (}Q(0)\land \forall n.(Q(n)\to Q(n+1)){\Big )}\ \to \ \forall m.\,Q(m)}$

Introducing some conventions for the sake of mirroring Set Induction, this may be written as

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

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

With classical tautologies such as ${\displaystyle (A\to B)\iff (\neg A\lor B)}$, 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 is ruled out and the formula states that the disjunct ${\displaystyle \forall z\,P(z)}$ must hold.