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

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

• I think I wrote a proof for this at least twice if not three times before. Here on this very site. Aug 28 '14 at 9:12
• (Here is one duplicate. I am certain there are others too. Here is one of them.) Aug 28 '14 at 9:14
• Thanks, but I can't see an explanation why the ordering is well ordered. I understand the whole proof besides that. Aug 28 '14 at 9:18
• Oh, I see. Yes, that is something that is overlooked in the previous questions on this problem. Aug 28 '14 at 9:47

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.

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.