Infinite Lexicographic Order on Well-Ordered Sets is not Well-Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({S, \preceq}\right)$ be a well-ordered set.

Let $\preccurlyeq$ be the lexicographic order on the set $T$ of all ordered tuples of $S$:

$\left({x_1, x_2, \ldots, x_m}\right) \prec \left({y_1, y_2, \ldots, y_n}\right)$ iff:
$\exists k: 1 \le k \le \min \left({m, n}\right)$ such that $\forall 1 \le j < k: x_j = y_j$ but $x_k \prec y_k$ in $S$
or:
$m < n$ and $\forall 1 \le j < m: x_j = y_j$.


Then $\preccurlyeq$ is not a well-ordering on $T$.


Proof

It is straightforward to show that $\preccurlyeq$ is a total ordering on $T$.

It remains to investigate the nature of $\preccurlyeq$ as to whether or not it is a well-ordering.


Consider a set $S = \left\{{a, b}\right\}$ such that $a \prec b$.

Then the set $\left\{{\left({b}\right), \left({a, b}\right), \left({a, a, b}\right), \left({a, a, a, b}\right), \ldots}\right\}$ has no minimal element by $\preccurlyeq$.

Thus $T$ is not well-ordered by $\preccurlyeq$.

$\blacksquare$


Sources