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

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \preccurlyeq}$ be a well-ordered set.

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

$\tuple {x_1, x_2, \ldots, x_m} \prec \tuple {y_1, y_2, \ldots, y_n}$ if and only if:
$\exists k: 1 \le k \le \map \min {m, n}$ 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_l$ is not a well-ordering on $T$.


Proof

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



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


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

Then the set $\set {\tuple b, \tuple {a, b}, \tuple {a, a, b}, \tuple {a, a, a, b}, \ldots}$ has no minimal element by $\preccurlyeq_l$.



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

$\blacksquare$


Sources