Reflexive Reduction of Well-Founded Ordering is Foundational Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\preceq$ be a well-founded ordering of $S$.

Let $\prec$ be the reflexive reduction of $\preceq$.


Then $\prec$ is a foundational relation.


Proof

Let $T$ be a non-empty subset of $S$.

Since $\preceq$ is a well-founded ordering, $T$ has a minimal element with respect to the ordering $\preceq$.

That is, there is an element $m \in T$ such that $\forall x \in T: \left({x \npreceq m}\right) \lor \left({x = m}\right)$.


Let $x \in T$.

Then $x \npreceq m$ or $x = m$.

By the definition of reflexive reduction, $\prec$ is a subset of $\preceq$.

Thus if $x \npreceq m$, $x \nprec m$.

If $x = m$ then by Reflexive Reduction is Antireflexive, $x \nprec m$.

As this holds for all $x \in T$, $m$ is $\prec$-minimal in $T$.

As each non-empty subset of $S$ has a $\prec$-minimal, $\prec$ is a foundational relation on $S$.

$\blacksquare$