[proofplan] We prove by transfinite induction on $\alpha$ that $\omega_\alpha \times \omega_\alpha$ is in bijection with $\omega_\alpha$, equivalently $\aleph_\alpha \cdot \aleph_\alpha = \aleph_\alpha$. The base case $\alpha = 0$ is classical: $\mathbb{N} \times \mathbb{N}$ is countable. For $\alpha > 0$, we equip $\omega_\alpha \times \omega_\alpha$ with the **maximum-first order** $<_*$ — comparing pairs first by $\max(x, y)$ and then lexicographically within each "square" — and show this well-ordering has order type exactly $\omega_\alpha$. The key estimate is that every proper initial segment $I_{(x, y)}$ is contained in $\beta \times \beta$ for some $\beta < \omega_\alpha$, so its cardinality is controlled by the inductive hypothesis applied to the smaller aleph below $\beta$. Combined with the trivial injection $\omega_\alpha \hookrightarrow \omega_\alpha \times \omega_\alpha$, this pins down the order type precisely at $\omega_\alpha$. [/proofplan] [step:Restate the theorem in order-type form and set up the induction] We prove by transfinite induction on $\alpha \in \operatorname{Ord}$ that \begin{align*} \omega_\alpha \times \omega_\alpha \leftrightarrow \omega_\alpha, \end{align*} where $\leftrightarrow$ denotes the existence of a bijection. Equivalently, we prove that $\operatorname{card}(\omega_\alpha \times \omega_\alpha) = \aleph_\alpha$, i.e., $\aleph_\alpha \cdot \aleph_\alpha = \aleph_\alpha$. Here $\omega_\alpha$ is the $\alpha$-th infinite initial ordinal — the least ordinal of cardinality $\aleph_\alpha$. Recall that $\aleph_\alpha = \operatorname{card}(\omega_\alpha)$, and $\omega_0 = \omega$. [/step] [step:Settle the base case $\alpha = 0$: $\mathbb{N} \times \mathbb{N}$ is countable] We must show $\omega \times \omega \leftrightarrow \omega$. The map \begin{align*} \pi : \omega \times \omega &\to \omega \\ (m, n) &\mapsto \frac{(m + n)(m + n + 1)}{2} + n \end{align*} (the Cantor pairing function) is a bijection. One verifies directly that $\pi$ is injective: if $\pi(m, n) = \pi(m', n')$, then the diagonal $m + n$ is recovered as the unique $k \in \omega$ with $\pi(m, n) \in [\tfrac{k(k+1)}{2}, \tfrac{(k+1)(k+2)}{2})$, hence $m + n = m' + n'$, and then $n = n'$ from $\pi(m, n) - \frac{k(k+1)}{2}$, giving $m = m'$. Surjectivity follows by induction: $\pi(0, 0) = 0$, and each consecutive value is attained by moving along diagonals. Hence $\omega \times \omega \leftrightarrow \omega$, proving the base case \begin{align*} \aleph_0 \cdot \aleph_0 = \aleph_0. \end{align*} [/step] [step:Assume the inductive hypothesis and define the maximum-first order $<_*$ on $\omega_\alpha \times \omega_\alpha$] Now fix $\alpha > 0$ and assume inductively: \begin{align*} \text{for every } \alpha' < \alpha, \quad \omega_{\alpha'} \times \omega_{\alpha'} \leftrightarrow \omega_{\alpha'}. \end{align*} Define the binary relation $<_*$ on $\omega_\alpha \times \omega_\alpha$ by \begin{align*} (x, y) <_* (x', y') \iff \begin{cases} \max(x, y) < \max(x', y'), & \text{or} \\ \max(x, y) = \max(x', y') \text{ and } (x, y) <_{\mathrm{lex}} (x', y'), \end{cases} \end{align*} where $<_{\mathrm{lex}}$ is the lexicographic order on $\omega_\alpha \times \omega_\alpha$ (say, with the second coordinate dominant: $(x, y) <_{\mathrm{lex}} (x', y') \iff y < y'$, or $y = y'$ and $x < x'$). We claim $<_*$ is a well-ordering of $\omega_\alpha \times \omega_\alpha$. [claim:TheMaxFirstOrderIsAWellOrder] $(\omega_\alpha \times \omega_\alpha, <_*)$ is a well-ordered set. [/claim] [proof] **Linearity.** Given any two distinct pairs $(x, y)$ and $(x', y')$, either $\max(x, y) \ne \max(x', y')$ — in which case trichotomy on the ordinals gives one strictly below the other — or $\max(x, y) = \max(x', y')$, in which case the distinct pairs differ lexicographically, and $<_{\mathrm{lex}}$ is a linear order. **Well-foundedness.** Let $S \subseteq \omega_\alpha \times \omega_\alpha$ be non-empty. Let \begin{align*} M := \min\{\max(x, y) : (x, y) \in S\}, \end{align*} which exists since $\{\max(x, y) : (x, y) \in S\}$ is a non-empty set of ordinals. The subset $S_M := \{(x, y) \in S : \max(x, y) = M\}$ is non-empty. Within $S_M$, the $y$-coordinates form a non-empty set of ordinals, hence have a minimum $y_*$. The subset $\{(x, y) \in S_M : y = y_*\}$ is non-empty, and among its elements we pick the one with minimum $x$-coordinate, call it $(x_*, y_*)$. This is the $<_*$-minimum of $S$: any other $(x, y) \in S$ either has $\max(x, y) > M$ (so $(x_*, y_*) <_* (x, y)$), or $\max(x, y) = M$ and $y > y_*$ (so again $(x_*, y_*) <_{\mathrm{lex}} (x, y)$), or $y = y_*$ and $x > x_*$ (same). [/proof] [guided] The naïve attempt to well-order $\omega_\alpha \times \omega_\alpha$ "from the left" — using lexicographic order with first coordinate dominant — fails. That order makes $\omega_\alpha \times \omega_\alpha$ into $\omega_\alpha$ copies of $\omega_\alpha$ stacked end to end, giving order type $\omega_\alpha \cdot \omega_\alpha$ (ordinal multiplication), which is the ordinal $\omega_\alpha^2$ and is strictly larger than $\omega_\alpha$. The initial segment $\{0\} \times \omega_\alpha$ already has order type $\omega_\alpha$, which is "too much" for an initial segment. The fix is to enumerate by **squares** rather than **rows**. Think of $\omega_\alpha \times \omega_\alpha$ as a large matrix; instead of reading across rows, we enumerate the pairs shell by shell: - The $0$-th shell: $\{(0, 0)\}$ (pairs with $\max = 0$), size $1$. - The $1$-st shell: $\{(0, 1), (1, 0), (1, 1)\}$ (pairs with $\max = 1$), size $3$. - More generally, the $\beta$-th shell $\{(x, y) : \max(x, y) = \beta\}$. The key property is that all pairs in shells before $\beta$ lie in $\beta \times \beta$, which — by the inductive hypothesis applied at the level below $\omega_\alpha$ — has cardinality strictly less than $\aleph_\alpha$. We define $(x, y) <_* (x', y')$ to mean: "$(x, y)$ is in an earlier shell than $(x', y')$, or they share a shell and $(x, y)$ comes lexicographically earlier within that shell." We just need to verify this is a well-ordering (linear + well-founded). **Linearity.** If $(x, y) \neq (x', y')$, there are two cases. If $\max(x, y) \neq \max(x', y')$, trichotomy on ordinals gives one strictly less; the other is therefore $<_*$ larger. If $\max(x, y) = \max(x', y')$, the pairs differ, so they differ lexicographically (any lex order on a linear order is a linear order on tuples). **Well-foundedness.** Let $S$ be a non-empty subset of $\omega_\alpha \times \omega_\alpha$. We successively minimise three ordinal coordinates: 1. Minimise $\max(x, y)$ over $(x, y) \in S$; call the minimum $M$. 2. Within the sub-collection where $\max(x, y) = M$, minimise $y$; call the minimum $y_*$. 3. Within the sub-collection where $\max(x, y) = M$ and $y = y_*$, minimise $x$; call the minimum $x_*$. Each step succeeds because we are minimising over a non-empty set of ordinals. The element $(x_*, y_*)$ is the $<_*$-minimum of $S$: any other element either fails the first minimisation (so sits in a later shell), the second (so is lex-larger within the shell), or the third. Thus $<_*$ is a well-ordering. [/guided] [/step] [step:Bound the order type of each proper initial segment by invoking the inductive hypothesis] Since $<_*$ is a well-ordering, $(\omega_\alpha \times \omega_\alpha, <_*)$ is isomorphic (as a linearly ordered set) to a unique ordinal, its **order type**, which we denote $\tau$. We now show $\tau \leq \omega_\alpha$. Let $(x, y) \in \omega_\alpha \times \omega_\alpha$ and consider the proper initial segment \begin{align*} I_{(x, y)} := \{(x', y') \in \omega_\alpha \times \omega_\alpha : (x', y') <_* (x, y)\}. \end{align*} Set $\beta := \max(x, y) + 1$. Since $x, y < \omega_\alpha$ and $\omega_\alpha$ is a limit ordinal (being $\omega_\alpha$ for $\alpha \geq 1$, it is even uncountable and in particular a limit), we have $\max(x, y) < \omega_\alpha$ and hence $\beta < \omega_\alpha$. Moreover, we may take $\beta$ to be infinite: if $\max(x, y) + 1$ is finite, replace $\beta$ by any infinite ordinal below $\omega_\alpha$ containing both coordinates, say $\beta = \omega$; since $\omega \leq \omega_\alpha$ (as $\alpha \geq 1$), this is below $\omega_\alpha$. If $(x', y') <_* (x, y)$, then by the definition of $<_*$, $\max(x', y') \leq \max(x, y) < \beta$. Hence both $x', y' < \beta$, so $(x', y') \in \beta \times \beta$. Therefore \begin{align*} I_{(x, y)} \subseteq \beta \times \beta. \end{align*} We now control $\operatorname{card}(\beta \times \beta)$ using the inductive hypothesis. Since $\beta < \omega_\alpha$ and $\beta$ is infinite, $\operatorname{card}(\beta) = \aleph_{\alpha'}$ for some $\alpha' < \alpha$. By the inductive hypothesis applied at $\alpha'$: \begin{align*} \aleph_{\alpha'} \cdot \aleph_{\alpha'} = \aleph_{\alpha'}. \end{align*} Hence $\operatorname{card}(\beta \times \beta) = \operatorname{card}(\beta) \cdot \operatorname{card}(\beta) = \aleph_{\alpha'} < \aleph_\alpha$. Consequently \begin{align*} \operatorname{card}(I_{(x, y)}) \leq \operatorname{card}(\beta \times \beta) = \aleph_{\alpha'} < \aleph_\alpha. \end{align*} The order type of $I_{(x, y)}$ under the induced order $<_*$ is an ordinal whose cardinality equals $\operatorname{card}(I_{(x, y)}) < \aleph_\alpha$. Any ordinal of cardinality strictly less than $\aleph_\alpha$ is strictly less than $\omega_\alpha$ (since $\omega_\alpha$ is, by definition, the least ordinal of cardinality $\aleph_\alpha$). Hence the order type of $I_{(x, y)}$ is $< \omega_\alpha$. [guided] The strategy at this step is: bound each proper initial segment's order type by $\omega_\alpha$, using the inductive hypothesis at smaller alephs. Fix $(x, y) \in \omega_\alpha \times \omega_\alpha$. We ask: how big is the set $I_{(x, y)}$ of pairs that come $<_*$-before $(x, y)$? **Containment in a small square.** Choose $\beta$ large enough that both $x, y < \beta$ and small enough that $\beta < \omega_\alpha$. Concretely, let $\beta$ be any infinite ordinal with $\max(x, y) < \beta < \omega_\alpha$ — such $\beta$ exists because $\omega_\alpha$ is a limit ordinal. (In fact $\omega_\alpha$ is an uncountable limit for $\alpha \geq 1$, but we only use "limit.") We claim $I_{(x, y)} \subseteq \beta \times \beta$. Indeed, $(x', y') \in I_{(x, y)}$ means $(x', y') <_* (x, y)$, which by the definition of $<_*$ forces \begin{align*} \max(x', y') \leq \max(x, y) < \beta, \end{align*} so both coordinates of $(x', y')$ are $< \beta$, i.e., $(x', y') \in \beta \times \beta$. **Cardinality of the small square.** Now we use the induction. Let $\alpha'$ be the ordinal with $\operatorname{card}(\beta) = \aleph_{\alpha'}$. Since $\beta$ is infinite and $\beta < \omega_\alpha$, we have $\aleph_{\alpha'} < \aleph_\alpha$, i.e., $\alpha' < \alpha$. The inductive hypothesis at $\alpha'$ says \begin{align*} \aleph_{\alpha'} \cdot \aleph_{\alpha'} = \aleph_{\alpha'}. \end{align*} Multiplying cardinalities, \begin{align*} \operatorname{card}(\beta \times \beta) = \operatorname{card}(\beta) \cdot \operatorname{card}(\beta) = \aleph_{\alpha'} \cdot \aleph_{\alpha'} = \aleph_{\alpha'} < \aleph_\alpha. \end{align*} **Transfer to order types.** An order-type $\tau$ (= ordinal) has cardinality equal to $\operatorname{card}(\tau)$. The initial segment $I_{(x, y)}$, as an ordered set, has some order type $\tau' \in \operatorname{Ord}$, and $\operatorname{card}(\tau') = \operatorname{card}(I_{(x, y)}) \leq \aleph_{\alpha'} < \aleph_\alpha$. Since $\omega_\alpha$ is **defined** as the least ordinal of cardinality $\aleph_\alpha$, any ordinal of cardinality strictly less than $\aleph_\alpha$ is strictly less than $\omega_\alpha$. So $\tau' < \omega_\alpha$. Hence every proper initial segment of $(\omega_\alpha \times \omega_\alpha, <_*)$ has order type strictly less than $\omega_\alpha$. [/guided] [/step] [step:Deduce the order type of $\omega_\alpha \times \omega_\alpha$ is exactly $\omega_\alpha$] Let $\tau$ be the order type of $(\omega_\alpha \times \omega_\alpha, <_*)$. **Upper bound $\tau \leq \omega_\alpha$.** Suppose for contradiction $\tau > \omega_\alpha$. Then there exists $(x, y) \in \omega_\alpha \times \omega_\alpha$ whose position in the order type is exactly $\omega_\alpha$ (the unique element of $\tau$ corresponding to the ordinal $\omega_\alpha$ under the canonical order-isomorphism). The proper initial segment $I_{(x, y)}$ would then have order type $\omega_\alpha$, contradicting Step 4 (which shows every proper initial segment has order type $< \omega_\alpha$). Equivalently: under the order-isomorphism $(\omega_\alpha \times \omega_\alpha, <_*) \cong \tau$, each $(x, y) \in \omega_\alpha \times \omega_\alpha$ corresponds to an ordinal $\xi(x, y) < \tau$, and $\xi(x, y)$ is the order type of $I_{(x, y)}$. By Step 4, $\xi(x, y) < \omega_\alpha$ for every pair. Hence \begin{align*} \tau = \sup\{\xi(x, y) + 1 : (x, y) \in \omega_\alpha \times \omega_\alpha\} \leq \omega_\alpha. \end{align*} **Lower bound $\tau \geq \omega_\alpha$.** Define the map \begin{align*} \iota: \omega_\alpha &\to \omega_\alpha \times \omega_\alpha \\ \xi &\mapsto (\xi, 0). \end{align*} This is an injection. It is also order-preserving from the usual ordinal order on $\omega_\alpha$ to $<_*$: if $\xi < \xi'$, then $\max(\xi, 0) = \xi < \xi' = \max(\xi', 0)$, so $(\xi, 0) <_* (\xi', 0)$. Hence $\omega_\alpha$ order-embeds into $(\omega_\alpha \times \omega_\alpha, <_*)$. Since the order type of $\omega_\alpha$ is $\omega_\alpha$, we have $\omega_\alpha \leq \tau$. **Combining.** $\tau = \omega_\alpha$. Consequently, the order-isomorphism $(\omega_\alpha \times \omega_\alpha, <_*) \cong \omega_\alpha$ is in particular a bijection of underlying sets: \begin{align*} \omega_\alpha \times \omega_\alpha \leftrightarrow \omega_\alpha, \end{align*} so $\aleph_\alpha \cdot \aleph_\alpha = \operatorname{card}(\omega_\alpha \times \omega_\alpha) = \operatorname{card}(\omega_\alpha) = \aleph_\alpha$. This completes the inductive step and the proof. [guided] We have now established: under $<_*$, every proper initial segment of $\omega_\alpha \times \omega_\alpha$ has order type strictly less than $\omega_\alpha$ (Step 4). We pin down the order type $\tau$ of the full set. **Upper bound: $\tau \leq \omega_\alpha$.** Under the canonical order-isomorphism \begin{align*} (\omega_\alpha \times \omega_\alpha, <_*) \cong \tau, \end{align*} each pair $(x, y)$ is sent to an ordinal $\xi(x, y) < \tau$, and the map is an order-isomorphism. By a general property of ordinals, $\xi(x, y)$ equals the order type of the proper initial segment below $(x, y)$, i.e., the order type of $I_{(x, y)}$. By Step 4, this is strictly less than $\omega_\alpha$. Hence every element of $\tau$ (in the image) is $< \omega_\alpha$, forcing $\tau \leq \omega_\alpha$. **Lower bound: $\tau \geq \omega_\alpha$.** We need to embed $\omega_\alpha$ order-preservingly into $(\omega_\alpha \times \omega_\alpha, <_*)$. The simplest candidate is the "horizontal axis" \begin{align*} \iota(\xi) = (\xi, 0). \end{align*} This is injective. For order preservation: if $\xi < \xi'$ in $\omega_\alpha$, then $\max(\xi, 0) = \xi < \xi' = \max(\xi', 0)$, so by the definition of $<_*$ (first clause), $(\xi, 0) <_* (\xi', 0)$. Thus $\iota$ is an order-embedding, and $\operatorname{type}(\omega_\alpha) \leq \operatorname{type}(\omega_\alpha \times \omega_\alpha, <_*) = \tau$. Since $\operatorname{type}(\omega_\alpha) = \omega_\alpha$, we get $\omega_\alpha \leq \tau$. **Conclusion.** Together, $\omega_\alpha \leq \tau \leq \omega_\alpha$, so $\tau = \omega_\alpha$. The order-isomorphism \begin{align*} (\omega_\alpha \times \omega_\alpha, <_*) \cong \omega_\alpha \end{align*} is in particular a bijection of sets, so $\omega_\alpha \times \omega_\alpha \leftrightarrow \omega_\alpha$, i.e., \begin{align*} \aleph_\alpha \cdot \aleph_\alpha = \aleph_\alpha. \end{align*} This completes the inductive step, and the transfinite induction closes. The theorem holds for every ordinal $\alpha$. [/guided] [/step]