Epsilon-induction

In mathematics, -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. This is a special case of well-founded induction.

StatementEdit

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

 

Note that for the "bottom case" where   denotes the empty set, the subexpression   is vacuously true for all propositions.

Comparison with natural number inductionEdit

The above can be compared with  -induction over the natural numbers   for number properties  . This may be expressed as

 

or, using the symbol for the tautologically true statement,  ,

 

Fix a predicate   and define a new predicate equivalent to  , except with an argument offset by one and equal to   for  . With this we can also get a statement equivalent to induction for  , but without a conjunction. By abuse of notation, letting " " denote  , an instance of the  -induction schema may thus be expressed as

 

This now mirrors an instance of the Set-Induction schema.

Conversely, Set-Induction may also be treated in a way that treats the bottom case explicitly.

Classical equivalentsEdit

With classical tautologies such as   and  , an instance of the  -induction principle can be translated to the following statement:

 

This expresses that, for any property  , either there is any (first) number   for which   does not hold, despite   holding for the preceding case, or - if there is no such failure case -   is true for all numbers.

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

 

This expresses that, for any property  , either there a set   for which   does not hold while   being true for all elements of  , or   holds for all sets. For any property, if one can prove that   implies  , then the failure case is ruled out and the formula states that the disjunct   must hold.

IndependenceEdit

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 alsoEdit