In set theory, -induction, also called epsilon-induction or set-induction, is a principle that can be used to prove that all sets satisfy a given property. Considered as an axiomatic principle, it is called the axiom schema of set induction.

The principle implies transfinite induction and recursion. It may also be studied in a general context of induction on well-founded relations.

Statement

for all holds for all sets. In symbols:

denotes the empty set is vacuously true.

In words, if a property is persistent when collecting any sets with that property into a new set (which, as edge case, also means that the property holds for the empty set), then the property is simply true for all sets. Said differently, persistence of a property with respect to set formation suffices to reach each set in the domain of discourse.

In terms of classes

One may use the language of classes to express schemata. Denote the universal class,

Here the quantifier ranges over all sets. In words this says that any class that contains all of its subsets is simply just the class of all sets.

Assuming bounded separation, and in particular by no set. Indeed, note that any set is a subset of itself and under some more assumptions, already the self-membership will be ruled out.

-transitive means

There are many transitive sets, in particular the set theoretical ordinals.

Related notions of induction

Exportation, it thus follows that

.

Ordinals

, the set of natural numbers, this gives what is called transfinite induction and definition by transfinite recursion using, indeed, the whole proper class of ordinals. With ordinals, induction proves that all sets have ordinal rank and the rank of an ordinal is itself.

The theory of Von Neumann ordinals, which classically is provably trichotomous and total-well-founded.

Well-founded relations

, well-foundedness, and so on.

Classically, well-foundedness of a relation on a set can also be characterized by the strong property of minimal element existence for every subset. With dependent choice, it can also be characterized by the weak property of non-existence of infinite descending chains.

For negative predicates

. Constructively, the resulting statements are generally weaker than set induction for general predicates. To establish equivalences, valid principles such as

1. ,

can not, for any value, be validated simultaneously. The situation when double-negation elimination is permitted is discussed in the following section.

, the induction schema reduces to

.)

Infinite descending chains

The antecedent. In this form with the universal quantifier in the front, it is clear that the empty set just fulfills it vacuously.

, i.e. with the inhabited elements along a sequence, the axiom of replacement that fulfills the above also. So assuming the induction principle makes the existence of such a chain contradictory.

In this paragraph, assume the axiom of dependent choice-statement obtained by removing the double-negation, which constructively is a stronger condition. Consider a set-property. Assuming the set is inhabited.

So set induction relates to the postulate of non-existence of infinite descending chains. But given the extra assumptions required in the latter case, the mere non-existence postulate is relatively weak in comparison.

Self-membership

, a contradiction.

with the described recursive property is not actually a set in the first place.

would exists by pairing-property.

Contrapositive

,

.

Classical equivalents

Disjunctive form

The excluded middle statement for a universally quantified predicate can classically be expressed as follows: Either it holds for all terms, or there exist a term for which the predicate fails

is classically an equivalence, and also using double-negation elimination, the induction principle can be translated to the following statement:

, then the failure case is ruled out and, then, by the disjunctive syllogism holds.

by ruling out the existence of counter-examples, the induction principle thus plays a similar role as the excluded middle disjunction, but the former is commonly also adopted in constructive frameworks.

Relation to regularity

The derivation in a previous section shows that set induction classically implies

that is disjoint from it.

In first-order set theories, the common framework, the set induction principle is an axiom schema, granting an axiom for any predicate (i.e. class). In contrast, the axiom of regularity. Hence, assuming set induction over a classical logic (i.e. assuming the law of excluded middle), all instances of regularity hold.

In a context with an axiom of separation, regularity also implies excluded middle (for the predicates allowed in one's separation axiom). Meanwhile, the set induction schema does not imply excluded middle, while still being strong enough to imply strong induction principles, as discussed above. In turn, the schema is, for example, adopted in the constructive set theory CZF, which has type-theoretic models. So within such a set theory framework, set induction is a strong principle strictly weaker than regularity. When adopting the axiom of regularity and full separation, CZF equals standard ZF.

History

Because of its use in the set theoretical treatment of ordinals, the axiom of regularity was formulated by von Neumann in 1925. Its motivation goes back to Skolem's 1922 discussion of infinite descending chains in Zermelo set theory, a theory without regularity or replacement.

does not prove all set induction instances. Regularity is classically equivalent to the contrapositive of set induction for negated statements, as demonstrated. The bridge from sets back to classes is demonstrated below.

Set induction from regularity and transitive sets

. This is possible because the axiom of separation allows for intersection between sets and classes. Regularity only concerns intersection inside a set and this can be flattened using transitive sets.

The proof is by manipulation of the regularity axiom instance

for a particular subset in the conclusion of the regularity instance.

.

Transitive set existence

The proof above assumes the existence of some transitive set containing any given set. This may be postulated: the transitive containment axiom.

The stronger statement of existence of the transitive closure with respect to membership, for any set, can be derived using some additional standard axioms. This needs the axiom of infinity, the axiom of replacement and finally the axiom of union. I.e. it needs many standard axioms, just sparing the axiom of powerset minus infinity also only proves the existence of transitive closures when Regularity is promoted to Set induction.

Comparison of epsilon and natural number induction

The transitive von Neumann model of the standard". Then, the principle derived from set induction is complete induction.

In this section, quantifiers are understood to range over the domain of first-order Peano arithmetic (or Heyting arithmetic). The signature". With it, the naturals form a semiring", and the irreflexive.

, the complete induction principle reads

, the principle is already implied by standard form of the mathematical induction schema" but the primitive symbols,

. By case analysis, one obtains

Classical equivalents

Using the classical principles mentioned above, the above may be expressed as

holding for all predecessors.

, then this already rules out a failure case. Moreover, if a failure case exists, one can use the least number principle to even prove the existence of a minimal such failure case.

Least number principle

As in the set theory case, one may consider induction for negated predicates and take the contrapositive. After use of a few classical logical equivalences, one obtains a conditional existence claim.

. The least number principle, obtained from complete induction, here expressed in terms of sets, reads

. This principle should be compared with regularity.

can be tested. Moreover, adopting Markov's principle in general.

See also

• Constructive set theory

• Mathematical induction

• Non-well-founded set theory

• Transfinite induction

• Well-founded induction

Reference