The axiom of regularity (also known as the axiom of foundation) is one of the axioms of Zermelo-Fraenkel set theory. In first-order logic the axiom reads: Zermelo-Fraenkel set theory, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ... It has been suggested that Predicate calculus be merged into this article or section. ...

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". In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, a sequence is a list of objects (or events) arranged in a linear fashion, such that the order of the members is well defined and significant. ...

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 two statements are equivalent. In mathematics, the axiom of choice, or AC, is an axiom of set theory. ...

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. In addition to omitting the axiom of regularity, non-standard set theories have indeed postulated the existence of sets that are elements of themselves. See "Well-foundedness and hypersets" in the article Axiomatic set theory. Zermelo-Fraenkel set theory, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ... Set theory is a branch of mathematics created principally by the German mathematician Georg Cantor at the end of the 19th century. ... Set theory is a branch of mathematics created principally by the German mathematician Georg Cantor at the end of the 19th century. ...

Elementary implications

Axiom of regularity implies that 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 the intersection of A and B is just A. Thus B does not satisfy the axiom of regularity and we have a contradiction, proving that A cannot exist. 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. ...

Axiom of regularity implies that no infinite descending sequence of sets exists

Let f be a function of 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 formal definition of a function. Applying the axiom of regularity to S, let f(k) be an element of S which is disjoint from S. But by the definitions of f and S, f(k) and S have an element in common (namely f(k+1)). This is a contradiction, hence no such f exists. Partial plot of a function f. ...

Assuming the axiom of choice, no infinite descending sequence of sets implies the axiom of 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: In mathematics, the axiom of choice, or AC, is an axiom of set theory. ...

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.

The axiom of regularity enables defining the ordered pair (a,b) as {a,{a,b}}. An ordered pair is a collection of two objects such that one can be distinguished as the first element and the other as the second element. ...

This definition eliminates one pair of braces from Kuratowski's canonical definition (a,b) = {{a},{a,b}}.

Common misconception: Russell's paradox and the axiom of regularity

Russell's paradox is the paradox whereby consideration of "the set of all sets that do not contain themselves as members" leads to a contradiction in naive set theory. Since the axiom of regularity implies that no set contains itself as a member, it can be tempting for the non-expert to think that the presence of the axiom of regularity in Zermelo-Fraenkel set theory (ZF) has something to do with the way in which ZF resolves Russell's paradox. (For example, this misconception is perpetuated in David Foster Wallace's Everything and More.) In fact, the contradiction of Russell's paradox is avoided because the separation axioms in ZF are of limited power (as compared with naive set theory). Indeed, a contradiction can only be eliminated from a theory by weakening or removing axioms; adding the axiom of regularity (or any other axiom) to a theory only makes it more likely that a contradiction will be encountered. The axiom of regularity is irrelevant to the resolution of Russell's paradox. Russells paradox (also known as Russells antinomy) is a paradox discovered by Bertrand Russell in 1901 which shows that the naive set theory of Frege is contradictory. ... Robert Boyles self-flowing flask fills itself in this diagram, but perpetual motion machines cannot exist. ... In abstract mathematics, naive set theory1 was the first development of set theory, which was later to be framed more carefully as axiomatic set theory. ... Zermelo-Fraenkel set theory, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ... David Foster Wallace (born February 21, 1962 in Ithaca, New York) is an American novelist, essayist, and short story writer. ... Everything and More by novelist and essayist David Foster Wallace examines the history of infinity in about 400 pages. ... In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, or axiom schema of separation, or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory. ...

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.