Hence, in this context the axiom of regularity is equivalent to the sentence that there are no downward infinite membership chains.
[2] Virtually all results in the branches of mathematics based on set theory hold even in the absence of regularity.
[3] 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
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.
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.
So if one forms a non-trivial ultrapower of Vω, then it will also satisfy the axiom of regularity.
[clarification needed] For example, suppose n is a non-standard natural number, then
This was actually the original form of the axiom in von Neumann's axiomatization.
Thus, by the axiom of dependent choice, there is some sequence (an) in S satisfying anRan+1 for all n in N. As this is an infinite descending chain, we arrive at a contradiction and so, no such S exists.
The result was announced by Paul Bernays in 1941, although he did not publish a proof until 1954.
In early formalizations of sets, mathematicians and logicians have avoided that contradiction by replacing the axiom schema of comprehension with the much weaker axiom schema of separation.
However, this step alone takes one to theories of sets which are considered too weak.
[clarification needed][citation needed] 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.
In particular, ZF without the axiom of regularity already prohibits such a universal set.
In particular, if ZF without regularity is extended by adding regularity to get ZF, then any contradiction (such as Russell's paradox) which followed from the original theory would still follow in the extended theory.
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.
, called the von Neumann universe, is equal to the class of all sets.
Herbert Enderton[10] wrote that "The idea of rank is a descendant of Russell's concept of type".
[11][12] Dana Scott[13] 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.
Indeed the best way to regard Zermelo's theory is as a simplification and extension of Russell's.
Thus mixing of types is easier and annoying repetitions are avoided.
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.
[14] The concept of well-foundedness and rank of a set were both introduced by Dmitry Mirimanoff.
[15][16] Mirimanoff called a set x "regular" (French: ordinaire) if every descending chain x ∋ x1 ∋ x2 ∋ ... is finite.
[18] Skolem[4] and von Neumann[1] pointed out that non-well-founded sets are superfluous[19] and in the same publication von Neumann gives an axiom[20] which excludes some, but not all, non-well-founded sets.
[21] In a subsequent publication, von Neumann[22] gave an equivalent but more complex version of the axiom of class foundation:[23]
The contemporary and final form of the axiom is due to Zermelo.