$\kappa\cdot\kappa= \kappa,$ for infinite cardinals

Question

I am trying to understand the proof that uses a maximal-lexicographic ordering.

For an infinite ordinal $\kappa,$ the canonical well-ordering of $\kappa \times \kappa,$ denoted by $<_{cw}$ is defined as follows: $(\alpha_1, \beta_1)<_{cw} < (\alpha_2, \beta_2)$ iff either one of the following holds.

$(1): \max\{\alpha_1,\beta_1\} < \max\{\alpha_2,\beta_2\}$

$(2): \max\{\alpha_1,\beta_1\} =\max\{\alpha_2,\beta_2\}$ and $\alpha_1<\alpha_2$

$(3): \max\{\alpha_1,\beta_1\} =\max\{\alpha_2,\beta_2\}$ and $\alpha_1 = \alpha_2$ and $\beta_1 < \beta_2.$

How would I prove that this ordering is well ordered?

EDIT: I'm not looking for a proof of $\kappa\cdot\kappa= \kappa,$ for infinite cardinals, I'm looking for a proof that the ordering as it's defined is well ordered on $\kappa\times\kappa$.

Answer 1

If you have a non-empty subset $A$ of $\kappa\times\kappa$, consider the set of ordinals $A_1=\{\max\{\alpha,\beta\}\mid(\alpha,\beta)\in A\}$. $A_1$ has a minimal element $\gamma_1$. Let $A_2$ be $\{\alpha\mid(\alpha,\beta)\in A\land\max\{\alpha,\beta\}=\gamma_1\}$ and let $\gamma_2$ bet the minimum of this set of ordinals. Now set $A_3=\{\beta\mid(\gamma_2,\beta)\in A\land \max\{\gamma_2,\beta\}=\gamma_1\}$ and let $\gamma_3$ be its minimum. Then $(\gamma_2,\gamma_3)$ is the minimum of $A$ w.r.t. to the canonical w.o.

Answer 2

Checking that something is a well-order is really just a tedious exercise in verifying definitions. But let's do that. Recall that a well-ordering has the following three properties:

1. Irreflexive and transitive.
2. Linear.
3. Every non-empty set has a least element.

Let's prove these hold.

1. Irreflexive is easy, since none of the three conditions hold when $\alpha_1=\alpha_2$ and $\beta_1=\beta_2$.

   Transitivity is not hard either. Suppose $(\alpha_1,\beta_1)<_{cw}(\alpha_2,\beta_2)<_{cw}(\alpha_3,\beta_3)$, now there are plenty of the cases to check.

   • If $\max\{\alpha_1,\beta_1\}=\max\{\alpha_2,\beta_2\}<\max\{\alpha_3,\beta_3\}$, then we are done. Similarly if the first equality is inequality.

   • Otherwise the maximum of all three pairs is equal. We check against $\alpha_1,\alpha_2$ and $\alpha_3$. If $\alpha_1<\alpha_3$ we are done.

   • Otherwise it has to be that $\beta_1<\beta_2<\beta_3$ (or else at least two of these pairs are equal, in which case the assumption that they satisfy $<_{cw}$ between them is false).

2. The fact this is linear is also pretty easy. I'll leave it to you to verify.

3. Finally, to see that every non-empty set has a least element, suppose $A\subseteq\kappa\times\kappa$ is non-empty. Consider $A_0=\{\max\{\alpha,\beta\}\mid (\alpha,\beta)\in A\}$, this is a non-empty set of ordinals so it has a least element, $\eta$. Now consider $B=\{(\alpha,\beta)\in A\mid\max\{\alpha,\beta\}=\eta\}$, this is a non-empty subset of $A$. Note that by the assumption on $B$, $(B,<_{cw})$ and $(B,<_{Lex})$ have the same order.

   Since the lexicographic product of two well-ordered set is a well-order, $B$ has a least element, $(\alpha,\beta)$. And this has to be a least element of $A$ in $<_{cw}$ as well.