well-foundedness and axiom of foundation
Recall that a relation on a class is well-founded if
- 1.
For any , the collection
is a set, and
- 2.
for any non-empty , there is an element such that if , then .
is called an -minimal element of . 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 Foundation (AF) is true.
We will prove this using one of the equivalent versions of AF: for every non-empty set , there is an such that .
Proof.
Suppose is well-founded and a non-empty set. We want to find such that . Since is well-founded, there is a -minimal set such that . Since no set such that and (otherwise would not be -minimal), we have that .
Conversely, suppose that AF is true. Let be any non-empty set. We want to find a -minimal element in . Let such that . Then is -minimal in , for otherwise there is such that , which implies , a contradiction.∎