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

  • $\begingroup$ I think I wrote a proof for this at least twice if not three times before. Here on this very site. $\endgroup$
    – Asaf Karagila
    Aug 28 '14 at 9:12
  • $\begingroup$ (Here is one duplicate. I am certain there are others too. Here is one of them.) $\endgroup$
    – Asaf Karagila
    Aug 28 '14 at 9:14
  • $\begingroup$ Thanks, but I can't see an explanation why the ordering is well ordered. I understand the whole proof besides that. $\endgroup$
    – Jake1234
    Aug 28 '14 at 9:18
  • $\begingroup$ Oh, I see. Yes, that is something that is overlooked in the previous questions on this problem. $\endgroup$
    – Asaf Karagila
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.