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

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!

## 1 Answer

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.

• Thank you for this helpful answer! As a brief follow up question -- in the modified hint you provided, what changes? Clearly the function $f$ will still hit all the $\text{type}(R)$'s of $R$'s which well-order $\omega$. But now it will also hit, for example, all $\text{type}(R)$'s where $R$ well-orders some subset of $\omega$? – Thy Art is Math Mar 5 at 8:05
• Yes. Which includes all the finite sets as well. – Asaf Karagila Mar 5 at 8:06
• Ah, I see! Thank you again for your assistance. It's nice when these things finally click. – Thy Art is Math Mar 5 at 8:10
• Yes, it's pretty damn awesome. – Asaf Karagila Mar 5 at 8:11
• But in the provided hint, $f(R)=|R|$ if $R$ is finite, so the finite ordinals are in the range as well. – Andrés E. Caicedo Mar 7 at 20:38