ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# Axiom of regularity

In set theory, the axiom of regularity, also known as the axiom of foundation, is an axiom that states that 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 (an) such that ai+1 is an element of ai 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 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 foundation 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:

Then for each 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.

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.

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.