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

From ProofWiki
Jump to navigation Jump to search


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

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

$\tuple {x_1, x_2, \ldots, x_n} \prec \tuple {y_1, y_2, \ldots, y_n}$ 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_l$ is a well-ordering on $T_n$.


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

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

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

It is clear that $\struct {T_1, \preccurlyeq_l}$ is order isomorphic to $\struct {S, \preccurlyeq}$.

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

Now, let us assume that $\preccurlyeq_l$ 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 $\preccurlyeq$, it follows that $A_1$ contains a minimal element $x$ by $\preccurlyeq_l$.

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_l$.

So $A_x$ contains a minimal element $\tuple {x, x_2, x_3, \ldots, x_{k + 1} }$ by $\preccurlyeq_l$.

This element $\tuple {x, x_2, x_3, \ldots, x_{k + 1} }$ is the minimal element of $A$ by $\preccurlyeq_l$.

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

The result follows by induction.