Axiom Of Regularity
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the axiom of regularity (also known as the axiom of foundation) is an axiom of
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes suc ...
that states that every non-empty
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
''A'' contains an element that is disjoint from ''A''. In
first-order logic First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
, the axiom reads: \forall x\,(x \neq \varnothing \rightarrow (\exists y \in x) (y \cap x = \varnothing)). The axiom of regularity together with the
axiom of pairing In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of pairing is one of the axioms of Zermelo–Fraenkel set theory. It was introduced by as a special case of his axiom of elementary sets ...
implies that no set is an element of itself, and that there is no infinite
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
(a_n) such that a_ is an element of a_i for all i. With the
axiom of dependent choice In mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. T ...
(which is a weakened form of the
axiom of choice In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
), 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 In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of f ...
theories (ones that do not accept the
law of the excluded middle In logic, the law of excluded middle or the principle of excluded middle states that for every proposition, either this proposition or its negation is true. It is one of the three laws of thought, along with the law of noncontradiction and th ...
), 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 A be a set, and apply the axiom of regularity to \, which is a set by the
axiom of pairing In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of pairing is one of the axioms of Zermelo–Fraenkel set theory. It was introduced by as a special case of his axiom of elementary sets ...
. By this axiom, there must be an element of \ which is disjoint from \. Since the only element of \ is A, it must be that A is disjoint from \. So, since A \cap \ = \varnothing, we cannot have A an element of A (by the definition of disjointness).


No infinite descending sequence of sets exists

Suppose, to the contrary, that there is a function, ''f'', on the
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s with ''f''(''n''+1) an element of ''f''(''n'') for each ''n''. Define ''S'' = , the range of ''f'', which can be seen to be a set from the
axiom schema of replacement In set theory, the axiom schema of replacement is a Axiom schema, schema of axioms in Zermelo–Fraenkel set theory (ZF) that asserts that the image (mathematics), image of any Set (mathematics), set under any definable functional predicate, mappi ...
. 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 In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
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 set In mathematics and set theory, hereditarily finite sets are defined as finite sets whose elements are all hereditarily finite sets. In other words, the set itself is finite, and all of its elements are finite sets, recursively all the way down to t ...
s, ''V''ω, satisfy the axiom of regularity (and all other axioms of ZFC except the
axiom of infinity In axiomatic set theory and the branches of mathematics and philosophy that use it, the axiom of infinity is one of the axioms of Zermelo–Fraenkel set theory. It guarantees the existence of at least one infinite set, namely a set containing ...
). So if one forms a non-trivial
ultrapower The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direct product of a family of structures. All fact ...
of Vω, then it will also satisfy the axiom of regularity. The resulting
model A model is an informative representation of an object, person, or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin , . Models can be divided in ...
will contain elements, called non-standard 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 non-standard natural number, then (n-1) \in n and (n-2) \in (n-1), and so on. For any actual natural number ''k'', (n-k-1) \in (n-k). 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 set-theoretic definition of the ordered pair

The axiom of regularity enables defining the ordered pair (''a'',''b'') as ; see
ordered pair In mathematics, an ordered pair, denoted (''a'', ''b''), is a pair of objects in which their order is significant. The ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a''), unless ''a'' = ''b''. In contrast, the '' unord ...
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 the axiom in von Neumann's axiomatization. Suppose ''x'' is any set. Let ''t'' be the
transitive closure In mathematics, the transitive closure of a homogeneous binary relation on a set (mathematics), set is the smallest Relation (mathematics), relation on that contains and is Transitive relation, transitive. For finite sets, "smallest" can be ...
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'' which 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 \textstyle \operatorname (w) = \cup \. 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 (which exists by the axiom of pairing). We see there must be an element of 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 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 aRb :\Leftrightarrow b \in S \cap a, which is entire by assumption. 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.


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 (with regularity) is also consistent. The axiom of regularity was also shown to be
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in Pennsylvania, United States * Independentes (English: Independents), a Portuguese artist ...
from the other axioms of ZFC, assuming they are consistent. The result was announced by
Paul Bernays Paul Isaac Bernays ( ; ; 17 October 1888 – 18 September 1977) was a Swiss mathematician who made significant contributions to mathematical logic, axiomatic set theory, and the philosophy of mathematics. He was an assistant and close collaborator ...
in 1941, although he did not publish a proof until 1954. The proof involves (and led to the study of) Rieger-Bernays permutation models (or method), 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 In mathematical logic, the Mostowski collapse lemma, also known as the Shepherdson–Mostowski collapse, is a theorem of set theory introduced by and . Statement Suppose that ''R'' is a binary relation on a class ''X'' such that *''R'' is s ...
(which provides the converse: that not only is membership on every set a well-founded and extensional relation, but that any such relation admits a corresponding set). If one performs mathematics in a more structural setting, for example by using a
type theory In mathematics and theoretical computer science, a type theory is the formal presentation of a specific type system. Type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundation of ...
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 In mathematics, a topos (, ; plural topoi or , or toposes) is a category that behaves like the category of sheaves of sets on a topological space (or more generally, on a site). Topoi behave much like the category of sets and possess a notion ...
. However, it does have practical uses, especially in the absence of the
axiom of choice In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
. One application is
Scott's trick In set theory, Scott's trick is a method for giving a definition of equivalence classes for equivalence relations on a proper class (Jech 2003:65) by referring to levels of the cumulative hierarchy. The method relies on the axiom of regularity bu ...
for constructing equivalence classes of a relation defined on proper classes, as an alternative to postulating a
Grothendieck universe In mathematics, a Grothendieck universe is a set ''U'' with the following properties: # If ''x'' is an element of ''U'' and if ''y'' is an element of ''x'', then ''y'' is also an element of ''U''. (''U'' is a transitive set.) # If ''x'' and ''y'' ...
; 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

Naive set theory Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It de ...
(the axiom schema of
unrestricted comprehension In many popular versions of axiomatic set theory, the axiom schema of specification, also known as the axiom schema of separation (''Aussonderungsaxiom''), subset axiom, axiom of class construction, or axiom schema of restricted comprehension is ...
and the
axiom of extensionality The axiom of extensionality, also called the axiom of extent, is an axiom used in many forms of axiomatic set theory, such as Zermelo–Fraenkel set theory. The axiom defines what a Set (mathematics), set is. Informally, the axiom means that the ...
) is inconsistent due to
Russell's paradox In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox published by the British philosopher and mathematician, Bertrand Russell, in 1901. Russell's paradox shows that every set theory that contains ...
. 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 In many popular versions of axiomatic set theory, the axiom schema of specification, also known as the axiom schema of separation (''Aussonderungsaxiom''), subset axiom, axiom of class construction, or axiom schema of restricted comprehension is ...
. However, this step alone takes one to theories of sets which are considered 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 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 (possibly undesirable) 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 (such as Russell's paradox) which followed from the original theory would still follow in the extended theory. The existence of
Quine atom Quine may refer to: * Quine (computing), a program that produces its source code as output * Quine's paradox, in logic * Quine (surname), people with the surname ** Willard Van Orman Quine (1908–2000), American philosopher and logician See ...
s (sets that satisfy the formula equation ''x'' = , i.e. have themselves as their only elements) 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 \bigcup_ V_\alpha , called the
von Neumann universe In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by ''V'', is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory ( ...
, 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 the axiom of regularity, a model which satisfies it can be constructed by taking only sets in \bigcup_ V_\alpha . Herbert Enderton wrote that "The idea of rank is a descendant of Russell's concept of ''type''". Comparing ZF with
type theory In mathematics and theoretical computer science, a type theory is the formal presentation of a specific type system. Type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundation of ...
, 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.


History

The concept of well-foundedness and rank of a set were both introduced by Dmitry Mirimanoff. Mirimanoff called a set ''x'' "regular" () if every descending chain ''x'' ∋ ''x''1 ∋ ''x''2 ∋ ... is finite. Mirimanoff however did not consider his notion of regularity (and well-foundedness) as an axiom to be observed by all sets; in later papers Mirimanoff also explored what are now called non-well-founded sets ( in Mirimanoff's terminology). Skolem and von Neumann pointed out that non-well-founded sets are superfluous and in the same publication von Neumann gives an axiom which excludes some, but not all, non-well-founded sets. In a subsequent publication, von Neumann gave an equivalent but more complex version of the axiom of class foundation:cf. and A \neq \emptyset \rightarrow \exists x \in A\,(x \cap A = \emptyset). The contemporary and final form of the axiom is due to Zermelo.


Regularity in the presence of urelements

Urelements are objects that are not sets, but which can be elements of sets. In ZF set theory, there are no urelements, but in some other set theories such as ZFA, there are. In these theories, the axiom of regularity must be modified. The statement "x \neq \emptyset" needs to be replaced with a statement that x is not empty and is not an urelement. One suitable replacement is (\exists y) \in x/math>, which states that ''x'' is inhabited.


See also

*
Non-well-founded set theory Non-well-founded set theories are variants of axiomatic set theory that allow sets to be elements of themselves and otherwise violate the rule of well-foundedness. In non-well-founded set theories, the foundation axiom of ZFC is replaced by axio ...
*
Scott's trick In set theory, Scott's trick is a method for giving a definition of equivalence classes for equivalence relations on a proper class (Jech 2003:65) by referring to levels of the cumulative hierarchy. The method relies on the axiom of regularity bu ...
*
Epsilon-induction In set theory, \in-induction, also called epsilon-induction or set-induction, is a principle that can be used to prove that all sets satisfy a given property. Considered as an axiomatic principle, it is called the axiom schema of set induction. ...


References


Sources

* * * Reprinted in * * * * * * * * * * * * * * Reprinted in ''From Frege to Gödel'', van Heijenoort, 1967, in English translation by Stefan Bauer-Mengelberg, pp. 291–301. * * * * Translation in * * * Translation in


External links

*
Inhabited set
an
the axiom of foundation
on nLab {{DEFAULTSORT:Axiom Of Regularity Axioms of set theory Wellfoundedness