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

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:

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!

• 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. – Asaf Karagila Nov 6 '18 at 7:38
• Thank you @AsafKaragila! I have realized my bad. – 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$$.

• My bad. Could you please leave some hints to prove $\{\alpha\cdot\eta+\zeta\mid\zeta<\alpha\text{ and }\eta<\beta\}=\beta\cdot\alpha$? – LE Anh Dung Nov 6 '18 at 7:21
• @LeAnhDung I added a small paragraph about where I think you went wrong. – Arthur Nov 6 '18 at 7:30
• 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! – LE Anh Dung Nov 8 '18 at 6:41
• @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. – Arthur Nov 8 '18 at 7:26
• @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. – 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$$.

• 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$. – Arthur Nov 8 '18 at 18:30
• (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$". – Arthur Nov 8 '18 at 18:30
• 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. – Arthur Nov 8 '18 at 18:33
• 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! – LE Anh Dung Nov 9 '18 at 0:35
• Hi @Arthur! When you have some free time, please take a look and address my concern in previous comment! Thank you so much! – LE Anh Dung Nov 9 '18 at 9:14