Ordering where every Subclass has Smallest Element is Well-Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A$ be a class.

Let $\RR$ be an ordering on $A$.

Let $\RR$ be such that every subclass of $A$ has a smallest element under $\RR$.


Then $\RR$ is a well-ordering.


Proof

We are given that $\RR$ is an ordering.

It will be shown that $\RR$ is a total ordering, from which the fact that it is a well-ordering follows directly by hypothesis.


Let $x$ and $y$ be elements of $A$.

Then $\set {x, y}$ is a subclass of $A$.

Hence by hypothesis $\set {x, y}$ has a smallest element.

That is, either $x \mathrel \RR y$ or $y \mathrel \RR x$.

As $x$ and $y$ are arbitrary, it follows that:

$\forall x, y \in A: x \mathrel \RR y \lor y \mathrel \RR x$

Hence, by definition, $\RR$ is a total ordering.

So, we have that $\RR$ is a total ordering on $A$ such that every subclass of $A$ has a smallest element under $\RR$.

That is, $\RR$ is a well-ordering.

$\blacksquare$


Sources