# well-foundedness and axiom of foundation

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

1. 1.

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

2. 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, $\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=\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=\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=\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=\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=\varnothing$, a contradiction. ∎

Title well-foundedness and axiom of foundation WellfoundednessAndAxiomOfFoundation 2013-03-22 17:25:34 2013-03-22 17:25:34 CWoo (3771) CWoo (3771) 6 CWoo (3771) Theorem msc 03E30