Every ordinal $\alpha>0$ can be expressed uniquely as $\alpha=\omega^{\beta_1}\cdot k_1+\omega^{\beta_2}\cdot k_2+\cdots+\omega^{\beta_n}\cdot k_n$

175 Views Asked by At

Every ordinal $\alpha>0$ can be expressed uniquely as

$$\alpha=\omega^{\beta_1}\cdot k_1+\omega^{\beta_2}\cdot k_2+\cdots+\omega^{\beta_n}\cdot k_n$$

where $\beta_1>\beta_2>\cdots>\beta_n$ and $k_1>0,k_2>0,\cdots,k_n>0$ are finite.

Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly appreciated. Thank you for your help!


My attempt:

Existence

Assume that $\xi$ can be expressed as normal form for all $\xi<\alpha$.

Let $\beta=\max\{\xi\in\rm Ord\mid\omega^\xi\le\alpha\}$. Then there is $\delta$ and $\rho<\omega^\beta$ such that $\alpha=\omega^\beta\cdot\delta+\rho$. Since $\rho<\omega^\beta$, $\rho<\alpha$ and thus $\delta>0$. I claim that $\delta$ is finite. If not, $\delta$ is infinite and thus $\delta\ge\omega$. Then $\omega^{\beta+1}=\omega^\beta\cdot\omega\le\omega^\beta\cdot\delta\le\alpha$ and thus $\omega^{\beta+1}\le\alpha$. This contradicts the maximality of $\beta$. Thus $\delta$ is finite. Let $\beta_1=\beta$ and $k_1=\delta$. If $\rho=0$, then $\alpha=\omega^{\beta_1}\cdot k_1$. If $\rho>0$, then $\rho=\omega^{\beta_2}\cdot k_2+\cdots+\omega^{\beta_n}\cdot k_n$ for some $\beta_2>\cdots>\beta_n$ and finite $k_2,\cdots,k_n>0$ by inductive hypothesis. We have $\omega^{\beta_2}\le\rho<\omega^{\beta_1}$, then $\beta_2<\beta_1$. As a result, $\alpha=\omega^{\beta_1}\cdot k_1+\omega^{\beta_2}\cdot k_2+\cdots+\omega^{\beta_n}\cdot k_n$ as desired.

We observed that $\beta<\gamma\implies\forall k\in\omega:\omega^\beta\cdot k<\omega^\gamma$. This is because $\omega^\beta\cdot k<\omega^\beta\cdot\omega=\omega^{\beta+1}\le\omega^\gamma$. It follows that if $\alpha=\omega^{\beta_1}\cdot k_1+\omega^{\beta_2}\cdot k_2+\cdots+\omega^{\beta_n}\cdot k_n$ is in normal form and $\beta_1<\gamma$, then $\alpha<\omega^\gamma$.

Uniqueness

Assume that the normal form of $\xi$ is unique for all $\xi<\alpha$.

Let $\alpha=\omega^{\beta_1}\cdot k_1+\omega^{\beta_2}\cdot k_2+\cdots+\omega^{\beta_n}\cdot k_n=\omega^{\gamma_1}\cdot l_1+\omega^{\gamma_2}\cdot l_2+\cdots+\omega^{\gamma_m}\cdot l_m$. The previous observation implies that $\beta_1=\gamma_1$. Let $\delta=\omega^{\beta_1}=\omega^{\gamma_1}$, $\rho=\omega^{\beta_2}\cdot k_2+\cdots+\omega^{\beta_n}\cdot k_n$, and $\sigma=\omega^{\gamma_2}\cdot l_2+\cdots+\omega^{\gamma_m}\cdot l_m$. Then $\alpha=\delta\cdot k_1+\rho=\delta\cdot l_1+\sigma$ where $\rho<\delta$ and $\sigma<\delta$. Thus $k_1=l_1$ and $\rho=\sigma$. By inductive hypothesis, the normal form of $\rho$ is unique and thus $m=n$, $\beta_2=\gamma_2,\cdots,\beta_n=\gamma_n, k_2=l_2,\cdots,k_n=l_m$. It follows that the normal form of $\alpha$ is unique.

1

There are 1 best solutions below

4
On BEST ANSWER

"The previous observation implies that $\beta_1 = \gamma_1$." I don't see that. For the existence part, I don't see any errors.

Also, this looks similar to the proof in section 3 of the excelent article "A short introduction to Ordinal Notations", by Simmons. It's freely available online; you should check it out. (Are you doing a thesis on ordinal notations?)

I like Simmon's way of writing the proof because it feels more like an algorithm :-). However, it's basically the same as yours.