well-foundedness and axiom of foundation

Recall that a relationMathworldPlanetmath R on a class C is well-founded if

  1. 1.

    For any xC, the collectionMathworldPlanetmath {yCyRx} is a set, and

  2. 2.

    for any non-empty BC, there is an element zB such that if yRz, then yB.

z is called an R-minimal element of B. It is clear that the membership relation in the class of all sets satisfies the first condition above.

Theorem 1.

Given ZF, is a well-founded relation iff the Axiom of FoundationMathworldPlanetmath (AF) is true.

We will prove this using one of the equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath versions of AF: for every non-empty set A, there is an xA such that xA=.


Suppose is well-founded and A a non-empty set. We want to find xA such that xA=. Since is well-founded, there is a -minimal set x such that xA. Since no set y such that yx and yA (otherwise x would not be -minimalPlanetmathPlanetmath), we have that xA=.

Conversely, suppose that AF is true. Let A be any non-empty set. We want to find a -minimal element in A. Let xA such that xA=. Then x is -minimal in A, for otherwise there is yA such that yx, which implies yxA=, a contradictionMathworldPlanetmathPlanetmath. ∎

Title well-foundedness and axiom of foundation
Canonical name WellfoundednessAndAxiomOfFoundation
Date of creation 2013-03-22 17:25:34
Last modified on 2013-03-22 17:25:34
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Theorem
Classification msc 03E30