The

**axiom of regularity**, (also known as the

**axiom of foundation**) is one of the axioms of Zermelo-Fraenkel set theory.

In the formal language of the Zermelo-Fraenkel axioms, the axiom reads:

∀ **S**, (¬**S** = {} → ∃ **a**, (**a** ∈ **S** ∧ **a** ∩ **S** = {}));

or in words:

For every non-empty set **S** there is an element **a** in it which is disjoint from **S**.

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*is an element of

_{i+1}*a*for all

_{i}*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 two statements are equivalent.

## Proofs

*Axiom of regularity implies that no set is an element of itself*

Let *a* be an element of itself. Then define *B* = {*a*}, which is a set by the pair axiom. Applying the axiom of foundation to *B*, we see that the only element of *B*, namely, *a*, must be disjoint from *B*. But by the definitions of *a* and *B* we see that they have an element in common (namely, *a* again). This is a contradiction, and hence no such *a* exists.

*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.

*No infinite descending sequence of sets implies axiom of regularity*

Let the non-empty set *S* be a counter-example to the axiom of regularity, that is every element *x* 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:

*n*,

*f*(

*n*) is an element of

*S*and so the 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.

## External link

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.