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 nonempty set A contains an element that is disjoint from A. In firstorder logic the axiom reads:

\forall x\,(x \neq \varnothing \rightarrow \exists y \in x\,(y \cap x = \varnothing)).
The axiom 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, the axiom of regularity is equivalent, given the axiom of dependent choice, to the alternative axiom that there are no downward infinite membership chains.
The axiom of regularity was introduced by 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 wellordered sets but also on proper classes that are wellfounded relational structures such as the lexicographical ordering on \{ (n, \alpha) \vert 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, nonstandard set theories have indeed postulated the existence of sets that are elements of themselves.
Elementary implications of regularity
No set is an element of itself
Let A be a set, and apply the axiom of regularity to {A}, which is a set by the axiom of pairing. We see that there must be an element of {A} which is disjoint from {A}. Since the only element of {A} is A, it must be that A is disjoint from {A}. So, since A ∈ {A}, we cannot have A ∈ A (by the definition of disjoint).
No infinite descending sequence of sets exists
Suppose, to the contrary, that there is a function, f, on the natural numbers with f(n+1) an element of f(n) for each n. Define S = {f(n): n a natural number}, the range of f, which can be seen to be a set from the axiom schema of replacement. Applying the axiom of regularity to S, let B be an element of S which is disjoint from S. By the definition of S, B must be f(k) for some natural number k. However, we are given that f(k) contains f(k+1) which is also an element of S. So f(k+1) is in the intersection of f(k) and S. This contradicts the fact that they are disjoint sets. Since our supposition led to a contradiction, there must not be any such function, f.
The nonexistence of a set containing itself can be seen as a special case where the sequence is infinite and constant.
Notice that this argument only applies to functions f that can be represented as sets as opposed to undefinable classes. The hereditarily finite sets, V_{ω}, satisfy the axiom of regularity (and all other axioms of ZFC except the axiom of infinity). So if one forms a nontrivial ultrapower of V_{ω}, then it will also satisfy the axiom of regularity. The resulting model will contain elements, called nonstandard natural numbers, that satisfy the definition of natural numbers in that model but are not really natural numbers. They are fake natural numbers which are "larger" than any actual natural number. This model will contain infinite descending sequences of elements. For example, suppose n is a nonstandard natural number, then (n1) \in n and (n2) \in (n1), and so on. For any actual natural number k, (nk1) \in (nk). This is an unending descending sequence of elements. But this sequence is not definable in the model and thus not a set. So no contradiction to regularity can be proved.
Simpler settheoretic definition of the ordered pair
The axiom of regularity enables defining the ordered pair (a,b) as {a,{a,b}}. See ordered pair for specifics. This definition eliminates one pair of braces from the canonical Kuratowski definition (a,b) = .
Every set has an ordinal rank
This was actually the original form of von Neumann's axiomatization.
For every two sets, only one can be an element of the other
Let X and Y be sets. Then apply the axiom of regularity to the set {X,Y}. We see there must be an element of {X,Y} which is also disjoint from it. It must be either X or Y. By the definition of disjoint then, we must have either Y is not an element of X or vice versa.
The axiom of dependent choice and no infinite descending sequence of sets implies regularity
Let the nonempty set S be a counterexample to the axiom of regularity; that is, every element of S has a nonempty intersection with S. We define a binary relation R on S by aRb :\Leftrightarrow b \in S \cap a, which is entire by assumption. Thus, by the axiom of dependent choice, there is some sequence (a_{n}) in S satisfying a_{n}Ra_{n+1} for all n in N. As this is an infinite descending chain, we arrive at a contradiction and so, no such S exists.
Regularity and the rest of ZF(C) axioms
Regularity was shown to be relatively consistent with the rest of ZF by Skolem (1923) and von Neumann (1929), meaning that if ZF without regularity is consistent, then ZF (with regularity) is also consistent. For his proof in modern notation see Vaught (2001, §10.1) for instance.
The axiom of regularity was also shown to be independent from the other axioms of ZF(C), assuming they are consistent. The result was announced by Paul Bernays in 1941, although he did not publish a proof until 1954. The proof involves (and led to the study of) RiegerBernays permutation models (or method), which were used for other proofs of independence for nonwellfounded systems (Rathjen 2004, p. 193 and Forster 2003, pp. 210–212).
Regularity and Russell's paradox
Naive set theory (the axiom schema of unrestricted comprehension and the axiom of extensionality) is inconsistent due to Russell's paradox. Set theorists have avoided that contradiction by replacing the axiom schema of comprehension with the much weaker axiom schema of separation. However, this makes set theory too weak. So some of the power of comprehension was added back via the other existence axioms of ZF set theory (pairing, union, powerset, replacement, and infinity) which may be regarded as special cases of comprehension. So far, these axioms do not seem to lead to any contradiction. Subsequently, the axiom of choice and the axiom of regularity were added to exclude models with some undesirable properties. These two axioms are known to be relatively consistent.
In the presence of the axiom schema of separation, Russell's paradox becomes a proof that there is no set of all sets. The axiom of regularity (with the axiom of pairing) also prohibits such a universal set, however this prohibition is redundant when added to the rest of ZF. If the ZF axioms without regularity were already inconsistent, then adding regularity would not make them consistent.
The existence of Quine atoms (sets that satisfy the formula equation x = {x}, i.e. have themselves as their only elements) is consistent with the theory obtained by removing the axiom of regularity from ZFC. Various nonwellfounded set theories allow "safe" circular sets, such as Quine atoms, without becoming inconsistent by means of Russell's paradox.(Rieger 2011, pp. 175,178)
Regularity, the cumulative hierarchy, and types
In ZF it can be proven that the class \bigcup_{\alpha} V_\alpha \! (see cumulative hierarchy) is equal to the class of all sets. This statement is even equivalent to the axiom of regularity (if we work in ZF with this axiom omitted). From any model which does not satisfy axiom of regularity, a model which satisfies it can be constructed by taking only sets in \bigcup_{\alpha} V_\alpha \! .
[Boolos 1971]." Urquhart (2003, p. 305)
Dana Scott (1974) went further and claimed that:
The truth is that there is only one satisfactory way of avoiding the paradoxes: namely, the use of some form of the theory of types. That was at the basis of both Russell's and Zermelo's intuitions. Indeed the best way to regard Zermelo's theory is as a simplification and extension of Russell's. (We mean Russell's simple theory of types, of course.) The simplification was to make the types cumulative. Thus mixing of types is easier and annoying repetitions are avoided. Once the later types are allowed to accumulate the earlier ones, we can then easily imagine extending the types into the transfinite—just how far we want to go must necessarily be left open. Now Russell made his types explicit in his notation and Zermelo left them implicit. [emphasis in original]
In the same paper, Scott shows that an axiomatic system based on the inherent properties of the cumulative hierarchy turns out to be equivalent to ZF, including regularity. (Lévy 2002, p. 73)
History
The concept of wellfoundedness and Sangiorgi 2011, pp. 17–19, 26).
Skolem (1923) and von Neumann (1925) pointed out that nonwellfounded sets are superfluous (on p. 404 in van Heijenoort 's translation) and in the same publication von Neumann gives an axiom (p. 412 in translation) which excludes some, but not all, nonwellfounded sets (Rieger 2011, p. 179). In a subsequent publication, von Neumann (1928) gave the following axiom (rendered in modern notation by A. Rieger):

\forall x\,(x \neq \emptyset \rightarrow \exists y \in x\,(y \cap x = \emptyset)).
See also
References



reprinted in














Skolem, Thoralf (1923). "Axiomatized set theory". Reprinted in From Frege to Gödel, van Heijenoort, 1967, in English translation by Stefan BauerMengelberg, pp. 291–301.



; translation in



; translation in
External links

http://www.trinity.edu/cbrown/topics_in_logic/sets/sets.html contains an informative description of the axiom of regularity under the section on ZermeloFraenkel set theory.

Axiom of Foundation at PlanetMath.org.
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.