Condition for Well-Foundedness/Reverse Implication/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \preceq}$ be an ordered set.

Suppose that there is no infinite sequence $\sequence {a_n}$ of elements of $S$ such that $\forall n \in \N: a_{n + 1} \prec a_n$.

Then $\struct {S, \preceq}$ is well-founded.


Proof

Suppose $\struct {S, \preceq}$ is not well-founded.

So by definition there exists a non-empty subset $T$ of $S$ which has no minimal element.

Let $a \in T$.

Since $a$ is not minimal in $T$, we can find $b \in T: b \prec a$.

Since this holds for all $a \in T$, $\prec \restriction_{T \times T}$, the restriction of $\prec$ to $T \times T$, is a right-total endorelation on $T$.

So, by the Axiom of Dependent Choice, it follows that there is an infinite sequence $\sequence {a_n}$ in $T$ such that $\forall n \in \N: a_{n + 1} \prec a_n$.

$\Box$


Axiom of Dependent Choice

This theorem depends on the Axiom of Dependent Choice.

Although not as strong as the Axiom of Choice, the Axiom of Dependent Choice is similarly independent of the Zermelo-Fraenkel axioms.

The consensus in conventional mathematics is that it is true and that it should be accepted.