Proving (without AC) that there is a surjective function from $\mathcal{P}(\omega)$ to $\omega_1$.

Question

Problem

I am working on the following exercise from page 60 of Kunen's Foundations of Mathematics:

Prove, without using AC, that one can map $\mathcal{P}(\omega)$ onto $\omega_1$.

In my copy of the text, he provides the following hint:

Define $f:\mathcal{P}(\omega\times\omega)\xrightarrow{\text{onto}}\omega_1$ so that $f(R)=\text{type}(R)$ whenever $R$ is a well-order of $\omega$ and $f(R)=|R|$ whenever $R$ is finite.

My instructor added to this hint, by saying that $f(R)=0$ (or any other number of your choice) otherwise.

---

Attempt at Solution

Ok, so I need to establish that there is a surjective function from $\mathcal{P}(\omega)$ to $\omega_1$, and the function Kunen provided as a hint is going to help me do this. With the help of my instructor, I made a rough roadmap for this proof:

1. Ensure $f$ is a well-defined function that does not require the Axiom of Choice. $\checkmark$
2. Show that $f$ (as given above) is surjective.
3. Establish the fact that $\mathcal{P}(\omega\times\omega)\approx \mathcal{P}(\omega)$, i.e. there is a bijection $g:\mathcal{P}(\omega)\rightarrow \mathcal{P}(\omega\times\omega)$. $\checkmark$
4. Conclude desired result by taking the composition $g\circ f$, i.e. $g\circ f=h:\mathcal{P}(\omega)\rightarrow \omega_1$. $\checkmark$

As indicated by the $\checkmark$'s, I understand all of the steps required of this proof other than showing that $f$ is surjective.

I know that $\omega_1$ is the (first) uncountable ordinal containing all countable ordinals. So to show surjectivity, I need to show that for any ordinal $\alpha\in\omega_1$ we have some $R\in\mathcal{P}(\omega\times\omega)$ such that $f(R)=\alpha$.

My first thought was to think of $\omega_1$ as containing two different types of countable ordinals: countable and finite, and countable and infinite.

So if $R$ is a well-order of $\omega$, then $f(R)=\text{type}(R)=\text{type}(\omega;R)=\alpha$, where $\alpha$ is the unique ordinal such that $(\omega;R)\simeq(\alpha;\in)$. I don't think I understand order type very well, but in my head this means that all ordinals $\alpha\geq \omega$ will get "hit". Then the rest of the ordinals $<\omega$ will get hit via $f(R)=|R|$ (or $0$?).

But this feels wrong...

---

Question

Clearly I am struggling with showing this function is surjetive, if the absolute mess of thoughts above wasn't indication enough. I am wondering if you kind souls would be willing to help me fill in the gaps in my understanding (as it pertains to showing $f$ is surjective), so that I may finally be able to complete this proof.

Thank you in advance!

Answer 1

You are right, both in your outline, and in your struggle.

The hint will only provide you with a surjection onto $\omega_1\setminus\omega$. And the correct hint should be considering $\operatorname{type}(R)$ such that $R$ is a well-ordering of its domain, rather than of $\omega$.

One can solve this in a myriad of ways, though. From noting that for well-ordered sets the "usual" cardinal arithmetic holds, so omitting $\aleph_0$ points from $\omega_1$ will still give you a set of size $\aleph_1$; or noting that this surjection you define only really involves infinite sets, so you can just map the finite sets to their cardinality. Both options are good. I prefer the "better" hint.