Axiom of regularity

From Academic Kids

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:

<math>\forall A: A \neq \{\} \implies \exists B: B \in A \land \lnot \exist C: C \in A \land C \in B<math>

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

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.

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.

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.

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 non-empty element s 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:

<math>f(0) = g(S)\,\!<math>
<math>f(n+1) = g(f(n) \cap S).\,\!<math>

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.

External links

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools