Goedel well-ordering on the square of the ordinals

Question

I am trying to show that $<_{G}$ is a well-ordering on $\mathrm{Ord}^2$. Recall that if $\alpha, \beta, \gamma, \delta$ are ordinals, then $$ (\alpha,\beta) <_{G} (\gamma, \delta) \iff (\max(\alpha,\beta) < \max(\gamma,\delta)) \, \lor \, (\max(\alpha,\beta) = \max(\gamma,\delta) \, \land \, (\alpha,\beta) <_{\mathrm{lex}} (\gamma,\delta)), $$ where $<_{\mathrm{lex}}$ is the lexicographic order on $\mathrm{Ord}^2$. My attempt is as follows: since $<_{G}$ is the natural extension of the so-called square ordering on $\omega^2$, my intuition is that the minimal element of a subclass $\mathcal{C} \subseteq \mathrm{Ord}^2$ is the one in the "bottom left" corner. Following this intuition, call $\mathcal{C}_0$ the projection of $\mathcal{C}$ on the first coordinate, and $\mathcal{C}_1$ the projection on the second coordinate. Let $\alpha := \min(\mathcal{C}_1)$, and $$ \beta := \min(\{\gamma \in \mathcal{C}_1: \exists \tau \in \mathcal{C}_0 \, \exists \xi \in \mathcal{C}_1 \,(\alpha,\xi) <_{\mathrm{lex}} (\tau,\gamma)\} \cup \{\gamma \in \mathcal{C}_1: (\alpha,\gamma) \in \mathcal{C}\}).$$ I claim that $(\alpha, \beta)$ is the sought minimum of $\mathcal{C}$. Let $(\gamma, \delta) \in \mathcal{C}$, then either $\gamma = \alpha$ or $\gamma > \alpha$. In the latter case, $(\alpha, \beta) <_{\mathrm{lex}} (\gamma, \delta)$ (#): if $\max(\alpha,\beta) = \alpha$, then since $\max(\gamma,\delta) > \alpha$ we can conclude that $(\alpha,\beta) <_{G} (\gamma,\delta)$; if $\max(\alpha,\beta) = \beta$ and $\max(\gamma,\delta) = \delta$, by definition $\delta \geq \beta$ and hence $\max(\gamma,\delta) \geq \max(\alpha,\beta)$ and the thesis follows from (#), while if $\max(\gamma,\delta) = \gamma$ we have that $\gamma \geq \delta \geq \beta$ and once again the thesis follows from (#). If, at last, $\gamma = \alpha$, then by definition $\delta \geq \beta$ and hence either $(\gamma, \delta) = (\alpha,\beta)$ or $(\alpha,\beta) <_{\mathrm{lex}} (\gamma,\delta)$. The proof, if correct, is slightly convoluted and admittedly a little "hands-on", so I'd also be interested in a more elegant one.

Answer 1

I guess you meant that $\alpha=\min\mathcal C_0$. But your proof cannot work.

Consider $\cal C$ to be $\{(1,n)\mid n\in\omega\}\cup\{(0,\omega)\}$. Then $\alpha=0$, but then $\beta=\omega$. But $(1,n)<_G(0,\omega)$ for all $n<\omega$.

This shows that working coordinate-wise is the wrong approach. To overcome this, first collect all the pairs with the minimum maximal coordinate, then use the usual approach for proving the lexicographic product of two well-orders is a well-order.

---

Another approach is to suppose that $(\alpha_n,\beta_n)$ is a weakly decreasing sequence in $<_G$, that is $(\alpha_{n+1},\beta_{n+1})<_G(\alpha_n,\beta_n)$ or $(\alpha_{n+1},\beta_{n+1})=(\alpha_n,\beta_n)$ for all $n<\omega$. Now argue that $\gamma_n=\max\{\alpha_n,\beta_n\}$ form a weakly decreasing sequence of ordinals, so it must stabilise, so without loss of generality $\gamma_n=\gamma$ for all $n$, and therefore the sequence is ordered in the lexicographic product of $\gamma+1\times_{\rm lex}\gamma+1$, which is a well-ordered set, and thus must be eventually constant.

But this another approach is almost the same, as your can see with a bit of thinking.