Axiom of regularity

 related topics {math, number, function} {group, member, jewish}

In mathematics, the axiom of regularity (also known as the axiom of foundation) is one of the axioms of Zermelo-Fraenkel set theory and was introduced by von Neumann (1925). In first-order logic the axiom reads:

Or in prose:

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 dependent choice (which is a weakened from of 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 dependent 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 3 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.

Given the other ZF axioms, the axiom of regularity is equivalent to the axiom of induction.

Contents

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.