Show that $f$ is an order isomorphism from $\mathbb{N}$ to $I_{\omega}$

52 Views Asked by At

Am reading Folland's Real Analysis book, and on page 10 he introduces the set $\Omega$ of countable ordinals. This set is the unique (up to order isomorphism) uncountable well ordered set such that each initial segment $I_x$ of $\Omega$ is countable (proposition 0.18). This set has the property that every countable subset of $\Omega$ has an upper bound (proposition 0.19).

Folland writes : The set $\mathbb{N}$ can be identified with a subset of $\Omega$ as follows. Set $f(1)=\min\Omega$, and proceeding inductively set $f(n)=\min \big(\Omega\setminus\{f(1),\dots,f(n-1)\}\big )$. The reader may verify that $f$ is an order isomorphism from $\mathbb{N}$ to $I_{\omega}$, where $\omega$ is the smallest element of $\Omega$ such that $I_\omega$ is infinite.

Is this proof correct?

  1. First we need to show the existence of $\omega$ by showing that the set $\{x\in\Omega: I_x \text{ is infinite}\}$ is nonempty. Since $\Omega$ is uncountable there exist a countably infinite subset $A\subset\Omega$, and by proposition 0.19 $A$ has an upper bound $\alpha$ in $\Omega$. Then $A\subset I_{\alpha}\cup\{\alpha\}$ and since $A$ is infinite so is $I_{\alpha}$.

  2. Second we show that $f:\mathbb{N}\to I_{\omega}$ is an order isomorphism. From the definition of $f$ we have $f(n)<f(n+1)$ and $I_{f(n)}=\{f(1),\dots,f(n-1)\}$ for each $n$, and so the range of $f$ is indeed a subset of $I_{\omega}$. To show that $f$ is surjective, let $x\in I_\omega$. If $I_x=\emptyset$ then $x=f(1)=\min \Omega$. Otherwise let $x_1<x_2<\dots<x_m$ denote the elements of $I_x$ ($m\geq1$). It is clear that $x_1=f(1)=\min \Omega$. Assuming $x_k=f(k)$ for all $k=1,\dots,n<m$, it follows that $x_{n+1}$ is the smallest element of $\Omega\setminus\{f(1),\dots,f(n)\}$, that is $x_{n+1}=f(n+1)$. By strong induction it follows that $x_k=f(k)$ for all $k=1,\dots, m$, which in turn implies $x=f(m+1)$. This shows that $f$ is surjective. Finally an induction on $n-m$ shows that $n<m$ implies $f(n)<f(m)$, and so $f$ is order preserving and injective. Altogether we get that $f$ is an order isomorphism.

Any feedback is very appreciated.