Let $\alpha,\beta$ be ordinals. Then the lexicographic ordering of $\alpha\times\beta$ has order type $\beta\cdot\alpha$.

This theorem comes from textbook Introduction to Set Theory by Hrbacek and Jech. Below is the screenshot:

enter image description here

I think there is a typo in my textbook. I think it should be "...an isomorphism between $\alpha\times\beta$ and $\beta\cdot\alpha$..." rather than "...an isomorphism between $\alpha\times\beta$ and $\alpha\cdot\beta$..."

We have a mapping $f:\alpha\times\beta\to \beta\cdot\alpha$ such that $$\forall\zeta<\alpha,\eta<\beta:f(\zeta,\eta)=\alpha\cdot\eta+\zeta$$

Then $\operatorname{ran}(f)=\{\alpha\cdot\eta+\zeta\mid\zeta<\alpha\text{ and }\eta<\beta\}$.

I have tried but to no avail in proving $\{\alpha\cdot\eta+\zeta\mid\zeta<\alpha\text{ and }\eta<\beta\}=\beta\cdot\alpha$. Please leave me some hints to complete the proof!

  • $\begingroup$ How could that be a typo? It literally says half a sentence earlier that the antilexicographic ordering has type $\alpha\cdot\beta$, and by now you should know that $\alpha\cdot\beta\neq\beta\cdot\alpha$ in general for ordinal multiplication. $\endgroup$ – Asaf Karagila Nov 6 '18 at 7:38
  • $\begingroup$ Thank you @AsafKaragila! I have realized my bad. $\endgroup$ – LE Anh Dung Nov 6 '18 at 7:39

The proof uses the antilexicographic ordering, not the lexicographic ordering. This allows them to use $\alpha\cdot\beta$.

As for the proof, consider that for any $\eta<\beta$, we have $(0,\eta)<(1,0)$, and there are $\beta$ such elements. So you want $f(1,0)=\beta$. That the resulting range is indeed $\beta\cdot\alpha$ is, as it often is with ordinals, best proven by induction. Maybe that helps you turn things the right way.

Proof that $f$ is surjective

Take an arbitrary $\tau<\beta\cdot\alpha$. Let $$ \eta=\sup\{\gamma\mid \beta\cdot\gamma\leq\tau\} $$ This $\eta$ exists because the $\sup$ of a set of ordinals is simply the union, and the collection of $\gamma$'s is indeed an actual set as it's bounded by $\alpha$.

We have $\eta<\alpha$. To prove this, I believe you need to split into cases depending on whether $\alpha$ and $\beta$ are limit ordinals or successor ordinals.

We also have $\beta\cdot\eta\leq\tau$, because $\sup$ preserves (non-strict) inequalities. Or you may prove this directly, if you'd like.

This means that there is a unique $\zeta$ such that $\tau=\beta\cdot\eta+\zeta$. The only thing left to prove is $\zeta<\beta$, which is done by contradiction. If $\zeta\geq\beta$, then $\zeta=\beta+\delta$ for some ordinal $\delta$, giving $$ \tau=\beta\cdot\eta+\zeta\\ =\beta\cdot\eta+\beta+\delta\\ =\beta\cdot(\eta+1)+\delta $$ This contradicts the $\sup$ definition of $\eta$.

  • $\begingroup$ My bad. Could you please leave some hints to prove $\{\alpha\cdot\eta+\zeta\mid\zeta<\alpha\text{ and }\eta<\beta\}=\beta\cdot\alpha$? $\endgroup$ – LE Anh Dung Nov 6 '18 at 7:21
  • $\begingroup$ @LeAnhDung I added a small paragraph about where I think you went wrong. $\endgroup$ – Arthur Nov 6 '18 at 7:30
  • $\begingroup$ Hi @Arthur! While I'm able to prove that $f$ is injective, I could not prove that $f$ is surjective, i.e. $\tau<\alpha\cdot\beta\implies \tau=\alpha\cdot\eta+\zeta\text{ for some }\eta<\beta,\zeta<\alpha$. Please shed me some lights! $\endgroup$ – LE Anh Dung Nov 8 '18 at 6:41
  • $\begingroup$ @LeAnhDung I added a proof that $f$ is surjective. (You still haven't noticed that you need $f(\eta,\zeta)=\beta\cdot\eta+\zeta$, I see.) There are a few details to fill in, but I hope it helps. $\endgroup$ – Arthur Nov 8 '18 at 7:26
  • 1
    $\begingroup$ @LeAnhDung You can't really expect me to take a look within an hour, can you? I made the surjectivity edit on my way to work, I'm at work right now. I can't take the time to look at your answer in the detail it needs until after. Please be a bit more patient. $\endgroup$ – Arthur Nov 8 '18 at 10:33

On the basis of @Arthur's answer, I present a detailed proof here. All credits are given to @Arthur.

$\tau<\alpha\cdot\beta\implies \tau=\alpha\cdot\eta+\zeta$ for a unique $\eta<\beta,\zeta<\alpha$

For $\tau<\alpha\cdot\beta$, let $X=\{\gamma\mid\alpha\cdot\gamma\le\tau\}$ and $\eta=\sup X$. Since $\tau<\alpha\cdot\beta$, $\forall\gamma\in X:\gamma<\beta$ and thus $\eta\le\beta$.

First, we prove that $\eta<\beta$.

  • If $\beta=\beta'+1$, then $\forall\gamma\in X:\gamma\le\beta'$ and thus $\eta=\sup X\le\beta'<\beta$.

  • If $\beta$ is a limit ordinal, we assume the contrary that $\eta=\beta$. Then $\gamma<\beta\implies\gamma<\eta=\sup X$ $\implies\gamma<\gamma'$ for some $\gamma'\in X$ $\implies\alpha\cdot\gamma<\alpha\cdot\gamma'\le\tau$ for some $\gamma'\in X$. Thus $\gamma<\beta\implies$ $\alpha\cdot\gamma<\tau$. We have $\alpha\cdot\beta=\sup\{\alpha\cdot\gamma\mid\gamma<\beta\}\le\sup\{\tau\mid\gamma<\beta\}=\tau$, which is a contradiction. It follows that $\eta\neq\beta$ and thus $\eta<\beta$.

Second, we prove $\alpha\cdot\eta\le\tau$.

  • If $\eta\in X$, then $\eta=\gamma$ for some $\gamma\in X$. It follows that $\alpha\cdot\eta=\alpha\cdot\gamma\le\tau$.

  • If $\eta\notin X$, then $\eta$ is clearly a limit ordinal. We have $\gamma<\eta\implies\gamma<\sup X\implies\gamma<\gamma'$ for some $\gamma'\in X$ $\implies\alpha\cdot\gamma<\alpha\cdot\gamma'\le\tau$ for some $\gamma'\in X$. It follows that $\gamma<\eta\implies\alpha\cdot\gamma<\tau$. Then $\alpha\cdot\eta=\sup\{\alpha\cdot\gamma\mid\gamma<\eta\}\le\sup\{\tau\mid\gamma<\eta\}=\tau$. Thus $\alpha\cdot\eta\le\tau$ and hence $\eta\in X$, which contradicts to our very first assumption that $\eta\notin X$. As a result, this case does not exist.

As a result, there is a unique $\zeta$ such that $\tau=\alpha\cdot\eta+\zeta$.

Finally, we prove $\zeta<\alpha$. Assume the contrary that $\alpha\le\zeta$, then $\alpha+\delta=\zeta$ for some $\delta$. Then $\tau=\alpha\cdot\eta+\zeta=\alpha\cdot\eta+(\alpha+\delta)=(\alpha\cdot\eta+\alpha)+\delta=\alpha\cdot(\eta+1)+\delta$. This contradicts the fact that $\eta=\sup X$.

  • 1
    $\begingroup$ Your limit ordinal bullet points are a bit messy. For $\eta<\beta$, we're assuming $\eta = \beta$ is a limit ordinal. From there, we want to reach a contradiction. We get one by definition of multiplication with limit ordinals. If for all $\gamma<\eta$ we have $\alpha\cdot\gamma <\tau$, then we have $\alpha\cdot \eta\leq \tau$, as $\alpha\cdot\eta$ is the infimum of all ordinals $\sigma$ such that $\alpha\cdot\gamma<\sigma$. $\endgroup$ – Arthur Nov 8 '18 at 18:30
  • 1
    $\begingroup$ (cont.) For $\alpha\cdot\eta\leq\tau$, again, the proof is basically the same, except we don't care about $\beta$ this time: $\eta$ is a limit ordinal, and thus $\alpha\cdot\eta$ is the smallest ordinal such that $\alpha\cdot \gamma <\alpha\cdot\eta$ for all $\gamma<\eta$. We also have $\alpha\cdot \gamma<\tau$, so $\alpha\cdot\eta\leq \tau$. Finally, there is no need to involve $\gamma$ in "If $\eta\in X$, then by definition of $X$ it follows that $\alpha\cdot\eta\leq\tau$". $\endgroup$ – Arthur Nov 8 '18 at 18:30
  • 1
    $\begingroup$ This sounds like a lot of criticizing, but that's because you're really close to a full, complete, well-written proof. That means there is a lot to take from and look at. $\endgroup$ – Arthur Nov 8 '18 at 18:33
  • $\begingroup$ Hi @Arthur@ These are really useful comments! Please correct me If I'm wrong! I think you mentioned that my proof is a bit messy NOT because it's wrong, but because I'm too unnecessarily detailed in the part $\gamma<\beta\implies\alpha\cdot\gamma<\tau$ and in the part $\gamma<\eta\implies\alpha\cdot\gamma<\tau$. Finally, besides the fact that my proof is messy, is there any logical mistake/gap in my proof? Many thanks for your persistent help! $\endgroup$ – LE Anh Dung Nov 9 '18 at 0:35
  • $\begingroup$ Hi @Arthur! When you have some free time, please take a look and address my concern in previous comment! Thank you so much! $\endgroup$ – LE Anh Dung Nov 9 '18 at 9:14

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.