Finite Lexicographic Order on Well-Ordered Sets is Well-Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set which is well-ordered by $\preceq$.

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

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


Then for a given $n \in \N_{>0}$, $\preccurlyeq$ is a well-ordering on $T_n$.


Proof

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

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


Consider $T_n$ where $n \in \N_{>0}$.

It is clear that $\left({T_1, \preccurlyeq}\right)$ is order isomorphic to $\left({S, \preceq}\right)$.

Thus as $\preceq$ is a well-ordering on $S$, $\preccurlyeq$ is a well-ordering on $T_1$.


Now, let us assume that $\preccurlyeq$ is a well-ordering on $T_k$ for some $k \in \N: k \ge 1$.

Let $A$ be a non-empty subset of $T_{k+1}$.

Let $A_1$ be the set of all of the first components of the ordered $n$-tuples that comprise $A$.

Since $A_1$ is a non-empty subset of $S$, and $S$ is itself well-ordered by $\preceq$, it follows that $A_1$ contains a minimal element $x$ by $\preccurlyeq$.

Let $A_x$ be the subset of $A$ in which the first component equals $x$.

We may consider $A_x$ to be a subset of $T_k$ where this first component $x$ has been suppressed.

But we assumed that $T_k$ is well-ordered by $\preccurlyeq$.


So $A_x$ contains a minimal element $\left({x, x_2, x_3, \ldots, x_{k+1}}\right)$ by $\preccurlyeq$.

This element $\left({x, x_2, x_3, \ldots, x_{k+1}}\right)$ is the minimal element of $A$ by $\preccurlyeq$.

Hence, by definition, $T_{k+1}$ is well-ordered by $\preccurlyeq$.

The result follows by induction.

$\blacksquare$


Sources