Well-Order

WO#DEF. Well-Order.

A well-order on $W$ is a total order such that every non-empty subset of $W$ has a least element.

WO#DEF-S. Strict Well-Order.

A strict well-order on $W$ is a strict total order such that every non-empty subset of $W$ has a least element.

WO#PROP-S.

$\leq$ is a well-order if and only if $<$ is a strict well-order.

WO#PROP-INC.

If $W$ is a well-ordered set and $f:W\to W$ is strictly increasing, then $x\leq f(x)$ for every $x\in W$.

Proof.Assume $A=\{x\in W:f(x)<x\}$ were non-empty. Let $z=\min A$, then

a contradiction.

WO#PROP-AUT.

The only automorphism on a well-ordered set is the identity function $\id_W$.

Proof.Let $f$ be an automorphism on a well-ordered set $W$. By OH#PROP-MON, both $f$ and $f^{-1}$ are strictly increasing. By WO#PROP-INC, $x\leq f(x)$ and $x\leq f^{-1}(x)$ for every $x\in W$, which follows that $x\leq f(x)$ and $f(x)\leq x$ for every $x\in W$.

WO#PROP-ISO.

If two well-ordered sets $W$ and $W’$ are isomorphic, then the isomorphism is unique.

Proof.If $f$ and $g$ are isomorphisms from $W$ onto $W’$, $f\circ g^{-1}$ is an automorphism on $W$. By WO#PROP-AUT, $f\circ g^{-1}=\id_W$.

WO#DEF-SEG.

Let $W$ be a well-ordered set and $u\in W$. The initial segment of $W$ given by $u$ is

\[\init_u W = \{x\in W : x<u\}.\]

$S\subseteq W$ is an initial segment of $W$, if $S=\init_u W$ for some $u$.

WO#PROP-SEG.

No well-ordered set is isomorphic to an initial segment of itself.

Proof.Let $W$ be a well-ordered set. For any $u\in W$, if

then $f(u)<u$. By WO#PROP-INC, $f$ can not be an isomorphism.

WO#PROP-C.

If $W$ and $W’$ are well-ordered sets, then exactly one of the following cases holds:

1. $W$ is isomorphic to $W’$.
2. $W$ is isomorphic to an initial segment of $W’$.
3. $W’$ is isomorphic to an initial segment of $W$.