## You are here

Homewell-foundedness and axiom of foundation

## Primary tabs

# 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, $\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. ∎

## Mathematics Subject Classification

03E30*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections