# Well-Founded Relation Determines Minimal Elements/Lemma

## Theorem

Let $\prec$ be a foundational relation on $A$.

Then $A$ has a $\prec$-minimal element.

## Proof

The general strategy of the proof is as follows:

We will recursively define a certain subset, $a$, of $A$.

We will use the fact that $\prec$ is a foundational relation to choose a minimal element, $m$, of $a$.

Then we will prove that $m$ is in fact a minimal element of $A$.

For each $x \in A$, let $\prec^{-1} \left({x}\right)$ denote the preimage under $\prec$ of $x$ in $A$.

For each class $C$, let $R \left({C}\right)$ denote the set of elements of $C$ of minimal rank, and let $R \left({\varnothing}\right) = \varnothing$.

That is:

For a given class $C$, let $\alpha_C$ be the smallest ordinal such that $C \cap V \left({\alpha_C}\right) ≠ \varnothing$,

where $V$ is the von Neumann hierarchy.

Then let $R \left({C}\right)$ denote the set $C \cap V \left({\alpha_C}\right)$.

Let $F$ be a function defined recursively:

- $F \left({0}\right) = R \left({A}\right)$
- $\displaystyle F \left({n+1}\right) = \bigcup_{y \mathop \in F \left({n}\right)} R \left({\prec^{-1} \left({y}\right)}\right)$

### Lemma

$F \left({n}\right)$ is a set for each $n \in \omega$.

### Proof

Proceed by induction:

$R \left({A}\right)$ is a set, so $F \left({0}\right)$ is a set.

Suppose that $R \left({F \left({n}\right)}\right)$ is a set.

We know that for each $y \in F \left({n}\right)$, $R \left({\prec^{-1} \left({y}\right)}\right)$ is a set, so by the Axiom of Union, $F \left({n+1}\right)$ is a set.

$\Box$

Let $\displaystyle a = \bigcup_{n \mathop \in \omega} F \left({n}\right)$.

By the Axiom of Union, $a$ is a set.

Since $F\left({n}\right)\subseteq A$ for each $n \in \omega$, $a \subseteq A$.

By Non-Empty Class has Element of Least Rank, $F \left({0}\right) \ne \varnothing$, so $a \ne \varnothing$.

Since $\prec$ is foundational, $a$ has a $\prec$-minimal element $m$.

Suppose for the sake of contradiction that $m$ is not a $\prec$-minimal element of $A$.

Then, by Characterization of Minimal Element,

- $\prec^{-1} \left({m}\right) \ne \varnothing$

By Non-Empty Class has Element of Least Rank, $\prec^{-1} \left({m}\right)$ has an element $w$ of least rank.

\(\displaystyle \) | \(\displaystyle \exists n \in \N:\) | \(\displaystyle \) | \(\displaystyle m\) | \(\in\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle F \left({n}\right)\) | \(\displaystyle \) | \(\displaystyle \) | definition of $a$ | ||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle w\) | \(\in\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle F \left({n+1}\right)\) | \(\displaystyle \) | \(\displaystyle \) | definition of $F$ | ||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle w\) | \(\in\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle a\) | \(\displaystyle \) | \(\displaystyle \) | definition of $a$ |

Therefore, $a \cap \prec^{-1} \left({m}\right) \ne \varnothing$, contradicting the fact that $m$ is $\prec$-minimal in $a$.

Thus we conclude that $m$ is a $\prec$-minimal element of $A$.

$\blacksquare$

## Also see

- Well-Founded Proper Relational Structure Determines Minimal Elements
- Proper Well-Ordering Determines Smallest Elements

These are weaker results that do not require the Axiom of Foundation.

## Sources

- Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*(1971): $\S 9.21$