Axiom of regularity

In mathematics, the axiom of regularity 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:
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 such that is an element of for all. With the axiom of dependent 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 was originally formulated by von Neumann; it was adopted in a formulation closer to the one found in contemporary textbooks by Zermelo. Virtually all results in the branches of mathematics based on set theory hold even in the absence of regularity. 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
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, 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.

Elementary implications of regularity

No set is an element of itself

Let be a set, and apply the axiom of regularity to, which is a set by the axiom of pairing. By this axiom, there must be an element of which is disjoint from. Since the only element of is, it must be that is disjoint from. So, since, we cannot have an element of .

No infinite descending sequence of sets exists

Suppose, to the contrary, that there is a function, f, on the natural numbers with f an element of f for each n. Define S =, 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 for some natural number k. However, we are given that f contains f, which is also an element of S. So f is in the intersection of f 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. So if one forms a non-trivial ultrapower of V_ω, then it will also satisfy the axiom of regularity. The resulting structure will contain elements, called non-standard natural numbers, that satisfy the definition of natural numbers in that structure but are not really natural numbers. They are "fake" natural numbers that are "larger" than any actual natural number. This structure will contain infinite descending sequences of elements. For example, suppose n is a non-standard natural number, then and, and so on. For any actual natural number k,. This is an unending descending sequence of elements. But this sequence is not definable in the structure and thus not a set. So no contradiction to regularity can be proved.

Simpler set-theoretic definition of the ordered pair

The axiom of regularity enables defining the ordered pair as ; see ordered pair for specifics. This definition eliminates one pair of braces from the canonical Kuratowski definition = .

Every set has an ordinal rank

This was actually the original form of the axiom in von Neumann's axiomatization.
To prove it from the axiom of regularity, suppose x is any set. Let t be the transitive closure of. Let u be the subset of t consisting of unranked sets. If u is empty, then x is ranked and we are done. Otherwise, apply the axiom of regularity to u to get an element w of u that is disjoint from u. Since w is in u, w is unranked. w is a subset of t by the definition of transitive closure. Since w is disjoint from u, every element of w is ranked. Applying the axioms of replacement and union to combine the ranks of the elements of w, we get an ordinal rank for w, to wit. This contradicts the conclusion that w is unranked. So the assumption that u was non-empty must be false and x must have rank.

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 . We see there must be an element of that 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 non-empty set S be a counter-example to the axiom of regularity; that is, every element of S has a non-empty intersection with S. We define a binary relation R on S by, which is entire by assumption. Thus, by the axiom of dependent choice, there is some sequence in S satisfying a_nRa_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 and von Neumann, meaning that if ZF without regularity is consistent, then ZF is also consistent.
The axiom of regularity was also shown to be independent from the other axioms of ZFC, 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 Rieger–Bernays permutation models, which were used for other proofs of independence for non-well-founded systems.

Regularity in ordinary mathematics

The axiom of regularity is rarely useful outside of set theory; A. A. Fraenkel, Y. Bar-Hillel and A. Levy noted that “its omission will not incapacitate any field of mathematics”. Its inclusion, therefore, can be considered as chiefly a clarification of what one means by “set”, as elaborated on by the Mostowski collapse lemma. If one performs mathematics in a more structural setting, for example by using a type theory or structural set theory like ETCS, the axiom is not used at all, since it is not needed to prove that Set, the category of sets, forms an elementary topos.
However, it does have practical uses, especially in the absence of the axiom of choice. One application is Scott's trick for constructing equivalence classes of a relation defined on proper classes, as an alternative to postulating a Grothendieck universe; it may also be used as an alternative to choice in the proof of Frucht's theorem for infinite groups.

Regularity and Russell's paradox

is inconsistent due to Russell's paradox. In early formalizations of sets, mathematicians and logicians avoided that contradiction by simply replacing the axiom schema of comprehension with the much weaker axiom schema of separation. However, this step alone takes one to theories of sets that are considered too weak. So some of the power of comprehension was added back via the other existence axioms of ZF set theory, 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 together with the axiom of pairing also prohibit such a universal set. However, Russell's paradox yields a proof that there is no "set of all sets" using the axiom schema of separation alone, without any additional axioms. In particular, ZF without the axiom of regularity already prohibits such a universal set.
If a theory is extended by adding an axiom or axioms, then any consequences of the original theory remain consequences of the extended theory. In particular, if ZF without regularity is extended by adding regularity to get ZF, then any contradiction that followed from the original theory would still follow in the extended theory.
The existence of Quine atoms is consistent with the theory obtained by removing the axiom of regularity from ZFC. Various non-wellfounded set theories allow "safe" circular sets, such as Quine atoms, without becoming inconsistent by means of Russell's paradox.

Regularity, the cumulative hierarchy, and types

In ZF it can be proven that the class, called the von Neumann universe, is equal to the class of all sets. This statement is even equivalent to the axiom of regularity. From any model that does not satisfy the axiom of regularity, a model that satisfies it can be constructed by taking only sets in.
Herbert Enderton wrote that "The idea of rank is a descendant of Russell's concept of type". Comparing ZF with type theory, Alasdair Urquhart wrote that "Zermelo's system has the notational advantage of not containing any explicitly typed variables, although in fact it can be seen as having an implicit type structure built into it, at least if the axiom of regularity is included.
Dana Scott went further and claimed that:
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.