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

Question

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!

Answer 1

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

Answer 2

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