well-foundedness and axiom of foundation

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

1. For any $x\in C$, the collection $\{y\in C\mid yRx\}$ is a set, and

2. for any non-empty $B\subseteq C$, there is an element $z\in B$ such that if $yRz$, then $y\notin B$.

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

Theorem 1.

Given ZF, $\mathrm{\in }$ 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 $A$, there is an $x\in A$ such that $x\cap A=\mathrm{\varnothing }$.

Proof.

Suppose $\in$ is well-founded and $A$ a non-empty set. We want to find $x\in A$ such that $x\cap A=\mathrm{\varnothing }$. Since $\in$ is well-founded, there is a $\in$-minimal set $x$ such that $x\in A$. Since no set $y$ such that $y\in x$ and $y\in A$ (otherwise $x$ would not be $\in$-minimal), we have that $x\cap A=\mathrm{\varnothing }$.

Conversely, suppose that AF is true. Let $A$ be any non-empty set. We want to find a $\in$-minimal element in $A$. Let $x\in A$ such that $x\cap A=\mathrm{\varnothing }$. Then $x$ is $\in$-minimal in $A$, for otherwise there is $y\in A$ such that $y\in x$, which implies $y\in x\cap A=\mathrm{\varnothing }$, a contradiction. ∎

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