Antilexicographic Product on Pair of Well-Ordered Sets is Well-Ordered

From ProofWiki
Jump to navigation Jump to search


Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be well-ordered sets.

Let $S_1 \otimes^a S_2 = \struct {S_1 \times S_2, \preccurlyeq_a}$ be the antilexicographic product of $S_1$ and $S_2$.

Then $\struct {S_1 \times S_2, \preccurlyeq_a}$ is itself a well-ordered set.


By definition, a well-ordered set is a totally ordered set which is well-founded.

From Antilexicographic Product of Totally Ordered Sets is Totally Ordered, we have that $\preccurlyeq_a$ is a totally ordered set.

It remains to be shown that $\preccurlyeq_a$ is a well-founded relation.

Let $T = S_1 \times S_2$.

Let $A$ be a non-empty subset of $T$.

Let $A_2$ be the set of all of the second cooordinates of the ordered pairs that comprise $A$:

$A_2 = \set {b \in S_2: \tuple {a, b} \in A}$

We have that:

$A_2$ is a non-empty subset of $S_2$
$S_2$ is well-ordered by $\preccurlyeq_2$

Hence $A_2$ contains a minimal element $y$ by $\preccurlyeq_a$.

Let $A_y$ be the subset of $A$ in which the second cooordinate equals $y$.

$A_y = \set {\tuple {a, b} \in A: b = y}$

Let $A_x$ be the set of first cooordinates of $A_y$.

$A_x = \set {a \in S_1: \tuple {a, y} \in A}$


$A_x$ is a non-empty subset of $S_1$
$S_1$ is well-ordered by $\preccurlyeq_1$

So $A_x$ contains a minimal element $x$.

Thus we have constructed $\tuple {x, y}$, which is the minimal element of $A$ by $\preccurlyeq_a$.

As $A$ is arbitrary, it follows that every non-empty subset of $T$ has a minimal element by $\preccurlyeq_a$.

That is, $\preccurlyeq_a$ is a well-founded relation.

Hence, by definition, $T$ is well-ordered by $\preccurlyeq_a$.