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...


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!


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.

  • $\begingroup$ 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$? $\endgroup$ – Thy Art is Math Mar 5 at 8:05
  • 1
    $\begingroup$ Yes. Which includes all the finite sets as well. $\endgroup$ – Asaf Karagila Mar 5 at 8:06
  • $\begingroup$ Ah, I see! Thank you again for your assistance. It's nice when these things finally click. $\endgroup$ – Thy Art is Math Mar 5 at 8:10
  • 1
    $\begingroup$ Yes, it's pretty damn awesome. $\endgroup$ – Asaf Karagila Mar 5 at 8:11
  • $\begingroup$ But in the provided hint, $f(R)=|R|$ if $R$ is finite, so the finite ordinals are in the range as well. $\endgroup$ – Andrés E. Caicedo Mar 7 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.