Well-Founded Relation Determines Minimal Elements/Lemma

From ProofWiki
Jump to: navigation, search

Theorem

Let $A$ be a non-empty class.

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


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


Proof

NotZFC.jpg

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 $\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) \ne \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$.

Aiming for a contradiction, suppose 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 \exists n \in \N: \ \ \) \(\displaystyle m\) \(\in\) \(\displaystyle F \left({n}\right)\) $\quad$ definition of $a$ $\quad$
\(\displaystyle w\) \(\in\) \(\displaystyle F \left({n+1}\right)\) $\quad$ definition of $F$ $\quad$
\(\displaystyle w\) \(\in\) \(\displaystyle a\) $\quad$ definition of $a$ $\quad$

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

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


Sources