Equivalence of Definitions of Strict Well-Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Strict Well-Ordering are equivalent:

Definition:Strict Well-Ordering/Definition 1

Let $\prec$ be a strict total ordering on a class $A$.

Then $\prec$ is a strict well-ordering on $A$ if and only if $\prec$ is a foundational relation on $A$.

That is, expressed symbolically:

${\prec} \mathrel{\operatorname{We}} A \iff \left({\prec \operatorname{Or} A \land {\prec} \mathrel{\operatorname{Fr}} A}\right)$

Definition:Strict Well-Ordering/Definition 2

Let $A$ be a set or class.

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


Then $\prec$ is a strict well-ordering of $A$ if and only if:

$\prec$ connects $A$
$\prec$ is well-founded. That is, whenever $b$ is a non-empty subset of $A$, $b$ has a $\prec$-minimal element.


Proof

Let $A$ be a class.

Let $B$ be a non-empty subset of $A$.


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


Definition 1 implies Definition 2

Suppose that $\prec$ is a foundational strict total ordering of $A$.

By the definition of strict total ordering, $\prec$ connects $A$.

$\Box$


Definition 2 implies Definition 1

Suppose that $\prec$ connects $A$ and that $\prec$ is a well-founded relation.

That is:

for any $x, y \in A$, either $x = y$, $x \prec y$, or $y \prec x$
whenever $b$ is a non-empty subset of $A$, $b$ has a $\prec$-minimal element.

$\prec$ is transitive:

Let $x, y, z \in A$.

Let $x \prec y$ and $y \prec z$.

Since $\prec$ connects $A$, either $x \prec z$ or $z \prec x$.

By Foundational Relation has no Relational Loops it is not the case that $x \prec y$, $y \prec z$ and $z \prec x$.

Thus we conclude that $x \prec z$.

As this holds for all such $x, y, z$, $\prec$ is transitive.

$\prec$ is antireflexive by Foundational Relation is Antireflexive.

Thus $\prec$ is a strict total ordering.

$\blacksquare$