# Axiom of regularity

In mathematics, the

**axiom of regularity**(also known as the**axiom of foundation**) is one of the axioms ofZermelo-Fraenkel set theory and was introduced by harvtxt|von Neumann|1925. Infirst-order logic the axiom reads::$forall\; A\; (exists\; B\; (B\; in\; A)\; ightarrow\; exists\; B\; (B\; in\; A\; land\; lnot\; exist\; C\; (C\; in\; A\; land\; C\; in\; B))).$

Or in prose::Every non-empty set "A" contains an element "B" which is disjoint from "A".

Two results which follow from the axiom are 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 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 choice, to the alternative axiom that there are no downward infinite membership chains.The axiom of regularity is arguably the least useful ingredient of

Zermelo-Fraenkel set theory , since virtually all results in the branches of mathematics based on set theory hold even in the absence of regularity (see Chapter III of [Kunen 1980] ). However, it is used extensively in establishing results aboutwell-ordering and theordinals in general. In addition to omitting the axiom of regularity, non-standard set theories have indeed postulated the existence of sets that are elements of themselves.Given the other

ZFC axioms, the axiom of regularity is equivalent to the axiom of induction.**Elementary implications of Regularity****No set is an element of itself**Let "A" be a set such that "A" is an element of itself and define "B" = {"A"}, which is a set by the

axiom of pairing . Applying the axiom of regularity to "B", we see that the only element of "B", namely, "A", must be disjoint from "B". But "A" is both an element of itself and an element of "B". Thus "B" does not satisfy the axiom of regularity and we have a contradiction, proving that "A" cannot exist.**No infinite descending sequence of sets exists**Suppose, to the contrary, that there is a function, "f", on the

natural number s 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 theaxiom 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".Notice that this argument only applies to functions "f" which can be represented as sets as opposed to undefinable classes. The

hereditarily finite set s, V_{ω}, satisfy the axiom of regularity (and all other axioms ofZFC except theaxiom of infinity ). So if one forms a non-trivial ultrapower of V_{ω}, then it will also satisfy the axiom of regularity. The resulting model will contain elements, called non-standard natural numbers, which 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.**The axiom of 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". Let "g" be a choice function for "S", that is, a map such that "g"("s") is an element of "s" for each non-empty subset "s" of "S". Now define the function "f" on the non-negative integers recursively as follows:

:$f(0)\; =\; g(S),!$:$f(n+1)\; =\; g(f(n)\; cap\; S).,!$

Then for each "n", "f"("n") is an element of "S" and so its intersection with "S" is non-empty, so "f"("n"+1) is well-defined and is an element of "f"("n"). So "f" is an infinite descending chain. This is a contradiction, hence no such "S" exists.

**impler set-theoretic 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 canonicalKuratowski definition ("a","b") = "a"},{"a","b".**Regularity does not resolve Russell's paradox**In

naive set theory ,Russell's paradox is the fact "the set of all sets that do not contain themselves as members" leads to a contradiction. The paradox shows that that set cannot be constructed using any consistent set of axioms for set theory. Even though the axiom of regularity implies that no set contains itself as a member, that axiom does not banish Russell's paradox fromZermelo-Fraenkel set theory (ZF). In fact, if the ZF axioms without Regularity were already inconsistent, then adding Regularity would not make them consistent. Russell's paradox is impossible in ZF because the sets that ZF'saxiom of separation allows must besubset s of some existing set. Hence the collection of all sets which do not contain themselves is not a set but aproper class .**Regularity and cumulative hierarchy**In ZF it can be proven that the class $igcup\_\{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 $igcup\_\{alpha\}\; V\_alpha\; !$.**ee also***

Non-well-founded set theory

*Zermelo-Fraenkel set theory **References***Jech, Thomas, 2003. "Set Theory: The Third Millennium Edition, Revised and Expanded". Springer. ISBN 3-540-44085-2.

*Kunen, Kenneth, 1980. "Set Theory: An Introduction to Independence Proofs". Elsevier. ISBN 0-444-86839-9.

*citation|last=von Neumann|year=1925|title=Eine axiomatiserung der Mengenlehre|journal=J. f. Math.|volume=154|pages=219-240**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 Zermelo-Fraenkel set theory.

*planetmath reference|id=3485|title=Axiom of Foundation

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Axiom schema of specification**— For the separation axioms in topology, see separation axiom. In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, axiom schema of separation, subset axiom scheme or… … Wikipedia**Axiom of extensionality**— In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of extensionality, or axiom of extension, is one of the axioms of Zermelo Fraenkel set theory. Formal statement In the formal language of… … Wikipedia**Separation axiom**— In topology and related fields of mathematics, there are several restrictions that one often makes on the kinds of topological spaces that one wishes to consider. Some of these restrictions are given by the separation axioms. These are sometimes… … Wikipedia**Non-well-founded set theory**— Non well founded set theories are variants of axiomatic set theory which allow sets to contain themselves and otherwise violate the rule of well foundedness. In non well founded set theories, the foundation axiom of ZFC is replaced by axioms… … Wikipedia**Zermelo–Fraenkel set theory**— Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics.ZFC consists of a single primitive ontological notion, that of… … Wikipedia**Constructive set theory**— is an approach to mathematical constructivism following the program of axiomatic set theory. That is, it uses the usual first order language of classical set theory, and although of course the logic is constructive, there is no explicit use of… … Wikipedia**Ordered pair**— In mathematics, an ordered pair (a, b) is a pair of mathematical objects. In the ordered pair (a, b), the object a is called the first entry, and the object b the second entry of the pair. Alternatively, the objects are called the first and… … Wikipedia**Regular**— The term regular can mean normal or obeying rules. Regular may refer to:In organizations: * Regular Army for usage in the U.S. Army * Regular clergy, members of a religious order subject to a rule of life * Regular Force for usage in the Canadian … Wikipedia**Zermelo set theory**— Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted. This article… … Wikipedia**List of axioms**— This is a list of axioms as that term is understood in mathematics, by Wikipedia page. In epistemology, the word axiom is understood differently; see axiom and self evidence. Individual axioms are almost always part of a larger axiomatic… … Wikipedia