# Well-Founded Relation Determines Minimal Elements/Lemma

## Theorem

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

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

## Proof

*This page is beyond the scope of ZFC, and should not be used in anything other than the theory in which it resides.*

*If you see any proofs that link to this page, please insert this template at the top.*

*If you believe that the contents of this page can be reworked to allow ZFC, then you can discuss it at the talk page.*

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 $\map {\prec^{-1} } x$ denote the preimage under $\prec$ of $x$ in $A$.

For each class $C$, let $\map R C$ denote the set of elements of $C$ of minimal rank, and let $\map R \O = \O$.

That is:

For a given class $C$, let $\alpha_C$ be the smallest ordinal such that:

- $C \cap \map V {\alpha_C} \ne \O$

where $V$ is the von Neumann hierarchy.

Then let $\map R C$ denote the set $C \cap \map V {\alpha_C}$.

Let $F$ be a function defined recursively:

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

### Lemma

$\map F n$ is a set for each $n \in \omega$.

### Proof

Proceed by induction:

$\map R A$ is a set, so $\map F 0$ is a set.

Suppose that $\map R {\map F n}$ is a set.

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

$\Box$

Let $\displaystyle a = \bigcup_{n \mathop \in \omega} \map F n$.

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

Since $\map F n \subseteq A$ for each $n \in \omega$, $a \subseteq A$.

By Non-Empty Class has Element of Least Rank, $\map F 0 \ne \O$, so $a \ne \O$.

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

Aiming for a contradiction, suppose that $m$ is not a $\prec$-minimal element of $A$.

Then, by Characterization of Minimal Element,

- $\map {\prec^{-1} } m \ne \O$

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

\(\displaystyle \exists n \in \N: \ \ \) | \(\displaystyle m\) | \(\in\) | \(\displaystyle \map F n\) | Definition of $a$ | |||||||||

\(\displaystyle w\) | \(\in\) | \(\displaystyle \map F {n + 1}\) | Definition of $F$ | ||||||||||

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

Therefore, $a \cap \map {\prec^{-1} } m \ne \O$, 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

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