Axiom of regularity

This article includes inline citations, but they are not properly formatted. Please improve this article by correcting them. Parenthetical referencing has been deprecated; convert to shortened footnotes. (September 2020) (Learn how and when to remove this message)

In mathematics, the axiom of regularity (also known as the axiom of foundation) is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set A contains an element that is disjoint from A. In first-order logic, the axiom reads:

${\displaystyle \forall x\,(x\neq \varnothing \rightarrow \exists y(y\in x\ \land y\cap x=\varnothing )).}$

The axiom of regularity together with the axiom of pairing implies that no set is an element of itself, and that there is no infinite sequence (a_n) such that a_i+1 is an element of a_i for all i. With the axiom of dependent choice (which is a weakened form of the axiom of choice), this result can be reversed: if there are no such infinite sequences, then the axiom of regularity is true. Hence, in this context the axiom of regularity is equivalent to the sentence that there are no downward infinite membership chains.

The axiom is the contribution of von Neumann (1925); it was adopted in a formulation closer to the one found in contemporary textbooks by Zermelo (1930). Virtually all results in the branches of mathematics based on set theory hold even in the absence of regularity; see chapter 3 of Kunen (1980). However, regularity makes some properties of ordinals easier to prove; and it not only allows induction to be done on well-ordered sets but also on proper classes that are well-founded relational structures such as the lexicographical ordering on ${\displaystyle \{(n,\alpha )\mid n\in \omega \land \alpha {\text{ is an ordinal }}\}\,.}$

Given the other axioms of Zermelo–Fraenkel set theory, the axiom of regularity is equivalent to the axiom of induction. The axiom of induction tends to be used in place of the axiom of regularity in intuitionistic theories (ones that do not accept the law of the excluded middle), where the two axioms are not equivalent.

In addition to omitting the axiom of regularity, non-standard set theories have indeed postulated the existence of sets that are elements of themselves.