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

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

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.1$: Mathematical Induction: Exercise $15 \ \text{(e)}$