This articledoes notcite anysources. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged andremoved. Find sources: "Epsilon-induction" – news ·newspapers ·books ·scholar ·JSTOR(October 2025) (Learn how and when to remove this message)

Inset theory,${\displaystyle \in }$-induction, also calledepsilon-induction orset-induction, is a principle that can be used to prove that allsets satisfy a given property. Considered as anaxiomatic principle, it is called theaxiom schema of set induction.

The principle impliestransfinite induction and recursion. It may also be studied in a general context of induction onwell-founded relations.

The schema is for any given property${\displaystyle \psi }$ of sets and states that, if for every set${\displaystyle x}$, the truth of${\displaystyle \psi (x)}$ follows from the truth of${\displaystyle \psi }$for all elements of${\displaystyle x}$, then this property${\displaystyle \psi }$ holds for all sets. In symbols:

${\displaystyle \mathrm{\forall }x.((\mathrm{\forall }(y\in x).\psi (y))\to \psi (x))\to \mathrm{\forall }z.\psi (z)}$

Note that for the "bottom case" where${\displaystyle x}$ denotes theempty set${\displaystyle \{\}}$, the subexpression${\displaystyle \mathrm{\forall }(y\in x).\psi (y)}$ isvacuously true for all propositions and so that implication is proven by just proving${\displaystyle \psi (\{\})}$.

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.

One may use the language of classes to express schemata. Denote the universalclass${\displaystyle \{x\mid x=x\}}$ by${\displaystyle \mathbb{U}}$.Let${\displaystyle \mathrm{\Psi }}$ be${\displaystyle \{x\mid \psi (x)\}}$ and use the informal${\displaystyle \mathrm{\Psi }=\mathbb{U}}$ as abbreviation for${\displaystyle \mathrm{\forall }z.z\in \mathrm{\Psi }}$. The principle then says that for any${\displaystyle \mathrm{\Psi }}$,

${\displaystyle \mathrm{\forall }(x\subseteq \mathrm{\Psi }).x\in \mathrm{\Psi }\leftrightarrow \mathrm{\Psi }=\mathbb{U}}$

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

Assumingbounded separation,${\displaystyle \mathbb{U}}$ is a proper class. So the property${\displaystyle \mathrm{\forall }(x\subseteq \mathrm{\Psi }).x\in \mathrm{\Psi }}$ is exhibited only by the proper class${\displaystyle \mathbb{U}}$, 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.

For comparison to another property, note that for a class${\displaystyle \mathrm{\Sigma }}$ to be${\displaystyle \in }$-transitive means

${\displaystyle \mathrm{\forall }(x\in \mathrm{\Sigma }).x\subseteq \mathrm{\Sigma }}$

There are many transitive sets, in particular the set theoreticalordinals.

Exportation proves${\displaystyle (A\to (B\to C))\leftrightarrow (B\to (A\to C))}$. If${\displaystyle \psi (x)}$ is${\displaystyle (x\in \mathrm{\Sigma })\to P(x)}$ for some predicate${\displaystyle P}$, it thus follows that

${\displaystyle \mathrm{\forall }(x\in \mathrm{\Sigma }).((\mathrm{\forall }(y\in (x\cap \mathrm{\Sigma })).P(y))\to P(x))\to \mathrm{\forall }(z\in \mathrm{\Sigma }).P(z)}$

where${\displaystyle y\in x\cap \mathrm{\Sigma }}$ is defined as${\displaystyle y\in x\wedge y\in \mathrm{\Sigma }}$. If${\displaystyle \mathrm{\Sigma }}$ is the universal class, then this is again just an instance of the schema.But indeed if${\displaystyle \mathrm{\Sigma }}$ is any${\displaystyle \in }$-transitive class, then still${\displaystyle \mathrm{\forall }(x\in \mathrm{\Sigma }).(x\cap \mathrm{\Sigma }=x)}$ and a version of set induction for${\displaystyle P}$ holds inside of${\displaystyle \mathrm{\Sigma }}$.

Ordinals may be defined as transitive sets of transitive sets. The induction situation in the first infinite ordinal${\displaystyle \omega }$, the set ofnatural numbers, is discussed in more detail below. As set induction allows for induction in transitive sets containing${\displaystyle \omega }$, this gives what is calledtransfinite induction and definition by transfinite recursion using, indeed, the wholeproper class of ordinals. With ordinals, induction proves that all sets have ordinal rank and the rank of an ordinal is itself.

The theory ofVon Neumann ordinals describes such sets and, there,${\displaystyle y\in x}$ models the order relation, whichclassically is provablytrichotomous andtotal. Of interest there is the successor operation${\displaystyle x\mapsto x\cup \{x\}}$ that maps ordinals to ordinals. In the classical case, the induction step for successor ordinals can be simplified so that a property must merely be preserved between successive ordinals (this is the formulation that is typically understood as transfinite induction.) The sets are${\displaystyle \in }$-well-founded.

For a binary relation${\displaystyle R_D}$ on a set${\displaystyle D}$,well-foundedness can be defined by requiring a tailored induction property:${\displaystyle y\in x}$ in the condition is abstracted to${\displaystyle R_D(y,x)}$, i.e. one always assumes${\displaystyle R_D(y,x)\wedge y\in D}$ in place of the intersection${\displaystyle y\in (x\cap D)}$ used in the statement above. It can be shown that for a well-founded relation${\displaystyle R_D}$, there are no infinite descending${\displaystyle R_D}$-sequences and so also${\displaystyle \mathrm{\forall }y.\mathrm{\neg }{R}_D(y,y)}$.Further, function definition by recursion with${\displaystyle R_D}$ can be defined on the domain of${\displaystyle R_D}$, and so on.

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

This section concerns the case of set induction and its consequences for predicates that are of a negated form,${\displaystyle \psi (x):=\mathrm{\neg }S(x)}$.Constructively, the resulting statements are generally weaker than set induction for general predicates. To establish equivalences, valid principles such as

${\displaystyle \mathrm{\forall }x.(A(x)\to \mathrm{\neg }B(x))\leftrightarrow \mathrm{\neg }\mathrm{\exists }x.(A(x)\wedge B(x))}$,

are commonly made use of, both sides saying that two predicates${\displaystyle A}$ and${\displaystyle B}$ can not, for any value, be validated simultaneously. The situation when double-negation elimination is permitted is discussed in the following section.

Denoting the class${\displaystyle \{x\mid S(x)\}}$ by${\displaystyle \mathrm{\Sigma }}$, this amounts to the special case of above with, for any${\displaystyle x}$,${\displaystyle P(x)}$ equal to the false statement${\displaystyle x\ne x}$.One has${\displaystyle x\cap \mathrm{\Sigma }=\{\}}$ denoting${\displaystyle \mathrm{\neg }\mathrm{\exists }(y\in \mathrm{\Sigma }).y\in x}$. Writing${\displaystyle \mathrm{\Sigma }=\{\}}$ for the statement that all sets are not members of the class${\displaystyle \mathrm{\Sigma }}$, the induction schema reduces to

${\displaystyle \mathrm{\neg }\mathrm{\exists }(x\in \mathrm{\Sigma }).x\cap \mathrm{\Sigma }=\{\}\leftrightarrow \mathrm{\Sigma }=\{\}}$

In words, a property (a class) such that there is no${\displaystyle \in }$-minimal set for it is simply the false property (the empty set). (A minimal${\displaystyle x}$ for a relation${\displaystyle R}$ is one for which there does not exist another${\displaystyle y}$ with${\displaystyle R(y,x)}$. Here the membership relation restricted to${\displaystyle \mathrm{\Sigma }}$ is considered, i.e. a minimal element with respect to${\displaystyle \mathrm{\Sigma }}$ is one without a${\displaystyle y\in x\cap \mathrm{\Sigma }}$.)

Theantecedent in the above implication may be expressed as${\displaystyle \mathrm{\forall }(x\in \mathrm{\Sigma }).\mathrm{\neg }\mathrm{\neg }\mathrm{\exists }(y\in \mathrm{\Sigma }).y\in x}$. It holds for empty setvacuously. In the presence of any descending membership chain as a function on${\displaystyle \omega }$, theaxiom of replacement proves existence of a set${\displaystyle \mathrm{\Sigma }}$ that also fulfills this. So assuming the induction principle makes the existence of such a chain contradictory.

In this paragraph, assume theaxiom of dependent choice in place of the induction principle. Any consequences of the above antecedent is also implied by the${\displaystyle \mathrm{\forall }\mathrm{\exists }}$-statement obtained by removing the double-negation, which constructively is a stronger condition. Consider aset${\displaystyle \mathrm{\Sigma }}$ with this${\displaystyle \mathrm{\forall }\mathrm{\exists }}$-property. Assuming the set isinhabited, dependent choice implies the existence of an infinite descending membership chain as sequence, i.e. a function${\displaystyle \omega \to \mathrm{\Sigma }}$ on the naturals. So establishing (or even postulating) the non-existence of such a chain for a set with the${\displaystyle \mathrm{\forall }\mathrm{\exists }}$-property implies the assumption was wrong, i.e. also${\displaystyle \mathrm{\Sigma }=\{\}}$.

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.

For a contradiction, assume there exists an inhabited set${\displaystyle s}$ with the particular property that it is equal to its own singleton set,${\displaystyle s=\{s\}}$. Formally,${\displaystyle \mathrm{\forall }y.(y\in s\leftrightarrow y=s)}$, from which it follows that${\displaystyle s\in s}$, and also that all members of${\displaystyle s}$ share all its properties, e.g.${\displaystyle \mathrm{\forall }(y\in s).s\in y}$. From the previous form of the principle it follow that${\displaystyle s=\{\}}$, a contradiction.

Discussed using the other auxiliary terminologies above, one studies set induction for the class${\displaystyle \mathrm{\Psi }}$ of sets that are not equal to such an${\displaystyle s}$. So in terms of the negated predicate,${\displaystyle S(x)}$ is the predicate${\displaystyle x=s}$, meaning a set that exhibits${\displaystyle S}$ has the defining properties of${\displaystyle s}$. Using the set builder notation, one is concerned with${\displaystyle \mathrm{\Sigma }=\{s\}}$. Assuming the special property of${\displaystyle s}$, any empty intersection statement${\displaystyle x\cap s=\{\}}$ simplifies to just${\displaystyle s\notin x}$. The principle in the formulation in terms of${\displaystyle \mathrm{\Sigma }}$ reduces to${\displaystyle s\notin s}$, again a contradiction. Back to the very original formulation, it is concluded that${\displaystyle \mathrm{\forall }z.z\ne s}$ and${\displaystyle \mathrm{\Psi }}$ is simply the domain of all sets. In a theory with set induction, a${\displaystyle s}$ with the described recursive property is not actually a set in the first place.

A similar analysis may be applied also to more intricate scenarios. For example, if${\displaystyle u=\{0,v\}}$ and${\displaystyle v=\{1,u\}}$ were both sets, then the inhabited${\displaystyle \{v,u\}}$ would exists bypairing, but this also has the${\displaystyle \mathrm{\forall }\mathrm{\exists }}$-property.

The contrapositive of the form with negation is constructively even weaker but it is only one double negation elimination away from the regularity claim for${\displaystyle \mathrm{\Sigma }}$,

${\displaystyle \mathrm{\Sigma }\ne \{\}\to \mathrm{\neg }\mathrm{\neg }\mathrm{\exists }(x\in \mathrm{\Sigma }).x\cap \mathrm{\Sigma }=\{\}}$

With double-negations in antecedent and conclusion, the antecedent may equivalently be replaced with${\displaystyle \mathrm{\exists }z.(z\in \mathrm{\Sigma })}$.

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

${\displaystyle \mathrm{\forall }z.P(z)\vee \mathrm{\exists }x.\mathrm{\neg }P(x)}$

With this, using the disjunctive syllogism, ruling out the possibility of counter-examples classically proves a property for all terms.This purely logical principle is unrelated to other relations between terms, such elementhood (or succession, see below).Using that${\displaystyle (B\vee \mathrm{\neg }A)\to (A\to B)}$ is classically an equivalence, and also using double-negation elimination, the induction principle can be translated to the following statement:

${\displaystyle \mathrm{\forall }z.P(z)\vee \mathrm{\exists }x.(\mathrm{\neg }P(x)\wedge \mathrm{\forall }(y\in x).P(y))}$

This expresses that, for any predicate${\displaystyle P}$, either it holds for all sets, or there is some set${\displaystyle x}$ for which${\displaystyle P}$ does not hold while${\displaystyle P}$ is at the same time true for all elements of${\displaystyle x}$. Relating it back to the original formulation: If one can, for any set${\displaystyle x}$, prove that${\displaystyle \mathrm{\forall }(y\in x).P(y)}$ implies${\displaystyle P(x)}$, which includes a proof of the bottom case${\displaystyle P(\{\})}$, then the failure case is ruled out and, then, by thedisjunctive syllogism the disjunct${\displaystyle \mathrm{\forall }z.P(z)}$ holds.

For the task of proving${\displaystyle P}$ 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.

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

${\displaystyle \mathrm{\Sigma }\ne \{\}\to \mathrm{\exists }(x\in \mathrm{\Sigma }).x\cap \mathrm{\Sigma }=\{\}}$

In words, any property that is exhibited by at least one set is also exhibited by a "minimal set"${\displaystyle x}$, as defined above. In terms of classes, this states that every non-empty class${\displaystyle \mathrm{\Sigma }}$ has a member${\displaystyle x}$ that is disjoint from it.

Infirst-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, theaxiom of regularity is a single axiom, formulated with a universal quantifier only over elements of the domain of discourse, i.e. over sets. If${\displaystyle \mathrm{\Sigma }}$ is a set and the induction schema is assumed, the above is the instance of the axiom of regularity for${\displaystyle \mathrm{\Sigma }}$. Hence, assuming set induction over a classical logic (i.e. assuming thelaw of excluded middle), all instances of regularity hold.

In a context with anaxiom 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 theconstructive set theory CZF, which hastype-theoretic models. So within such a set theory framework, set induction is a strong principle strictly weaker than regularity. When adopting theaxiom of regularity and full separation, CZF equals standardZF.

Because of its use in the set theoretical treatment of ordinals, the axiom of regularity was formulated byvon Neumann in 1925. Its motivation goes back toSkolem's 1922 discussion of infinite descending chains inZermelo set theory${\displaystyle \mathsf{Z}}$, a theory without regularity or replacement.

The theory${\displaystyle \mathsf{Z}}$ 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.

Assuming regularity, one may use classical principles, like the reversal of a contrapositive. Moreover, an induction schema stated in terms of a negated predicate${\displaystyle \mathrm{\neg }S}$ is then just as strong as one in terms of a predicate variable${\displaystyle P}$, as the latter simply equals${\displaystyle \mathrm{\neg }(\mathrm{\neg }P)}$. As the equivalences with the contrapositive of set induction have been discussed, the task is to translate regularity back to a statement about a general class${\displaystyle \mathrm{\Sigma }}$. This is possible because theaxiom of separation allows for intersection between sets and classes. Regularity only concerns intersectioninside a set and this can be flattened using transitive sets.

The proof is by manipulation of the regularity axiom instance

${\displaystyle s\ne \{\}\to \mathrm{\exists }(x\in s).x\cap s=\{\}}$

for a particular subset${\displaystyle s\subseteq \mathrm{\Sigma }}$ of the class${\displaystyle \mathrm{\Sigma }}$. Observe that given a class${\displaystyle \mathrm{\Sigma }}$ and any transitive set${\displaystyle t}$, one may define${\displaystyle s=t\cap \mathrm{\Sigma }}$, which has${\displaystyle x\in s\to (x\in \mathrm{\Sigma }\wedge x\subseteq t)}$ and also${\displaystyle (x\subseteq t)\to (x\cap s=x\cap \mathrm{\Sigma })}$. With this, the set${\displaystyle s}$ may always be replaced with the class${\displaystyle \mathrm{\Sigma }}$ in the conclusion of the regularity instance.

It remains to obtain a statement that also has${\displaystyle s}$ replaced by${\displaystyle \mathrm{\Sigma }}$ in the antecedent, that is, establish the principle holds when assuming the more general${\displaystyle \mathrm{\Sigma }\ne \{\}}$. So assume there is some${\displaystyle z\in \mathrm{\Sigma }}$, together with the existence of some transitive set${\displaystyle t}$ that has${\displaystyle z}$ as subset. An intersection${\displaystyle s_z}$ may be constructed as described and it also has${\displaystyle (z\cap \mathrm{\Sigma })\subseteq s_z}$. Consider excluded middle for whether or not${\displaystyle t}$ is disjoint from${\displaystyle \mathrm{\Sigma }}$, i.e.${\displaystyle s_z=\{\}}$. If${\displaystyle s_z}$ is empty, then also${\displaystyle z\cap \mathrm{\Sigma }=\{\}}$ and${\displaystyle x=z}$ itself always fulfills the principle. Otherwise,${\displaystyle \mathrm{\exists }(x\in s_z)}$ by regularity and one can proceed to manipulate the statement by replacing${\displaystyle s_z}$ with${\displaystyle \mathrm{\Sigma }}$ as discussed. In this case, one even obtains a slightly stronger statement than the one in the previous section, since it carries the sharper information that${\displaystyle x\in s_z}$ and not just${\displaystyle x\in \mathrm{\Sigma }}$.

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

The stronger statement of existence of thetransitive closure with respect to membership, for any set, can be derived using some additional standard axioms. This needs theaxiom of infinity for${\displaystyle \omega }$ as a set, recursive functions on${\displaystyle \omega }$, theaxiom of replacement on${\displaystyle \omega }$ and finally theaxiom of union. I.e. it needs many standard axioms, just sparing theaxiom of powerset. In a context without strong separation, suitable function-space principles may have to be adopted to enable recursive function definition.${\displaystyle \mathsf{Z}\mathsf{F}}$ minus infinity also only proves the existence of transitive closures whenRegularity is promoted to Set induction.

The transitivevon Neumann model${\displaystyle \omega }$ of thestandard natural numbers is the first infinite ordinal. There, the binary membership relation "${\displaystyle \in }$" of set theory exactly models the strict ordering of natural numbers "". Then, the principle derived from set induction iscomplete induction.

In this section, quantifiers are understood to range over the domain offirst-order Peano arithmetic${\displaystyle \mathsf{P}\mathsf{A}}$ (orHeyting arithmetic${\displaystyle \mathsf{H}\mathsf{A}}$). Thesignature includes the constant symbol "${\displaystyle 0}$", the successor function symbol "${\displaystyle S}$" and the addition and multiplication function symbols "${\displaystyle +}$" resp "${\displaystyle \ast }$". With it, the naturals form asemiring, which always come with a canonical non-strict preorder "${\displaystyle \le }$", and theirreflexive may be defined in terms of that. Similarly, the binary ordering relation is also definable as${\displaystyle \mathrm{\exists }m.k+Sm=n}$.

For any predicate${\displaystyle Q}$, the complete induction principle reads

Making use of, the principle is already implied bystandard form of the mathematical induction schema. The latter is expressed not in terms of the decidable order relation "" but the primitive symbols,

${\displaystyle (\varphi (0)\wedge \mathrm{\forall }n.(\varphi (n)\to \varphi (Sn)))\to \mathrm{\forall }m.\varphi (m)}$

Lastly, a statement may be proven that merely makes use of the successor symbol and still mirrors set induction: Define a new predicate${\displaystyle Q_{-1}(n)}$ as${\displaystyle (n=0)\vee \mathrm{\exists }p.(Sp=n\wedge Q(p))}$. It holds for zero by design and so, akin to the bottom case in set induction, the implication${\displaystyle Q_{-1}(0)\to Q(0)}$ is equivalent to just${\displaystyle Q(0)}$. Using induction,${\displaystyle \mathsf{P}\mathsf{A}}$ proves that every${\displaystyle n}$ is either zero or has a computable unique predecessor, a${\displaystyle q}$ with${\displaystyle Sq=n}$. Hence${\displaystyle Q_{-1}(Sq)\leftrightarrow Q(q)}$. When${\displaystyle n}$ is the successor of${\displaystyle n-1}$, then${\displaystyle Q_{-1}(n)}$ expresses${\displaystyle Q(n-1)}$. By case analysis, one obtains

${\displaystyle \mathrm{\forall }n.(Q_{-1}(n)\to Q(n))\to \mathrm{\forall }m.Q(m)}$

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

It expresses that, for any predicate${\displaystyle Q}$, either${\displaystyle Q}$ hold for all numbers, or there is some natural number${\displaystyle n}$ for which${\displaystyle Q}$ does not hold despite${\displaystyle Q}$ holding for all predecessors.

Instead of, one may also use${\displaystyle Q_{-1}(n)}$ and obtain a related statement. It constrains the task of ruling out counter-examples for a property of natural numbers: If the bottom case${\displaystyle Q(0)}$ is validated and one can prove, for any number${\displaystyle n}$, that the property${\displaystyle Q}$ is always passed on to${\displaystyle Sn}$, then this already rules out a failure case. Moreover, if a failure case exists, one can use theleast number principle to even prove the existence of aminimal such failure case.

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.

Let${\displaystyle \mathrm{\Theta }}$ denote the set of natural numbers${\displaystyle \{n\in \omega \mid T(n)\}}$ validating a property${\displaystyle T}$. In the Neumann model, a natural number${\displaystyle n}$ is extensionally equal to, the set of numbers smaller than${\displaystyle n}$. Theleast number principle, obtained from complete induction, here expressed in terms of sets, reads

${\displaystyle \mathrm{\Theta }\ne \{\}\to \mathrm{\neg }\mathrm{\neg }\mathrm{\exists }(n\in \mathrm{\Theta }).n\cap \mathrm{\Theta }=\{\}}$

In words, if it cannot be ruled out that some number has the property${\displaystyle T}$, then it can also not be consistently ruled out that a least such number${\displaystyle n}$ exists. In classical terms, if there is any number validating${\displaystyle T}$, then there also exists a least such number validating${\displaystyle T}$. Least here means that no other number is validating${\displaystyle T}$. This principle should be compared with regularity.

For decidable${\displaystyle T}$ and any given${\displaystyle m}$ with${\displaystyle T(m)}$, all can be tested.Moreover, adoptingMarkov's principle in arithmetic allows removal of double-negation for decidable${\displaystyle T}$ in general.

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

• Mathematical induction
• Wellfoundedness

• Articles with short description
• Short description matches Wikidata
• Articles lacking sources from October 2025
• All articles lacking sources