Axiom of regularity

From Wikipedia, the free encyclopedia

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:

$\forall A (A \neq \{\} \rightarrow \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 about well-ordering and the ordinals 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. See "Well-foundedness and hypersets" in the article Axiomatic set theory.

1 Elementary implications
2 Relationship between Russell's paradox and the axiom of regularity
3 References
4 External links

[edit] 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 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.

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.

Notice that this argument only applies to f which are sets (not undefinable classes). The hereditarily finite sets, V_ω, satisfy the axiom of regularity. So if one forms a non-trivial ultrapower of V_ω, then it will also satisfy the axiom of regularity. However, it 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)$ . So 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.

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:

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

The axiom of regularity enables defining the ordered pair (a,b) as {a,{a,b}}.

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

[edit] Relationship between Russell's paradox and the axiom of regularity

Russell's paradox is the paradox whereby the construction of "the set of all sets that do not contain themselves as members" leads to a contradiction in naive set theory; the paradox shows that that set cannot be constructed using any consistent set of axioms for set theory. Since the axiom of regularity implies that no set contains itself as a member, it is natural to ask whether the presence of the axiom of regularity in Zermelo-Fraenkel set theory (ZF) resolves Russell's paradox in this setting. It does not; if the ZF axioms without the axiom of regularity were already inconsistent, then adding the axiom of regularity could not make them consistent. The reason that the set named in Russell's paradox cannot be explicitly constructed in ZF is that there is a restriction added to the axiom of separation which causes each new set it forms to be a subset of an existing set. The collection of all sets which do not contain themselves is then seen to be a proper class.

[edit] 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.

[edit] 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.

Retrieved from "http://en.wikipedia.org../../../a/x/i/Axiom_of_regularity.html"

Categories: Axioms of set theory | Wellfoundedness