Lexicographic Order on Products of Well-Ordered Sets

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$ of all ordered tuples of $S$.


Then:

$(1): \quad$ For a given $n \in \N: n > 0$, $\preccurlyeq$ is a well-ordering on the set $T_n$ of all ordered $n$-tuples of $S$;
$(2): \quad \preccurlyeq$ is not a well-ordering on the set $T$ of all ordered tuples of $S$.


Proof

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

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


Proof for Finite Product

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$


Proof for Infinite Product

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$