Does there always exist a surjection from $\Bbb R$ to $\omega_1$?

Question

I'm pretty sure that, with the axiom of choice, there always exists a surjection from $\Bbb R$ to $\omega_1$ (well-order $\Bbb R$, send the first $\omega_1$ elements to the corresponding ordinals, if there are any reals left over send them to whatever). What happens in the absence of choice?

Answer 1

There is still such a surjection: send $r$ to the countable ordinal it codes if it codes a countable ordinal, and to (say) $17$ otherwise.

---

Specifically, we can assign (exercise) a relation $R_r$ on $\mathbb{N}\times\mathbb{N}$ to each real $r$, in such a way that every binary relation on $\mathbb{N}$ winds up being of the form $R_r$ for at least one $r$. Now say $r$ codes a countable ordinal $\alpha$ if $(\mathbb{N},R_r)$ is a well-ordering of type $\alpha$.

---

A more computability-theoretic approach: to each real $r$, assign its relative Church-Kleene ordinal $\omega_1^{CK}(r)$ (this is the least ordinal with no copy computable from $r$). The set $\{\omega_1^{CK}(r): r\in\mathbb{R}\}$ is cofinal in $\omega_1$ (exercise - this is basically the previous paragraph!), and so we can "collapse" it to get a surjection $\mathbb{R}\rightarrow\omega_1$. By "collapse," I mean the following: for a set $S$ of ordinals, map $x\in S$ to the ordertype of $(\{y\in S: y\in x\}, \in)$. The image of $S$ under this map is an ordinal (exercise), and if $S$ is a cofinal subset of $\omega_1$ the image is in fact $\omega_1$ (exercise).

Interestingly, we don't need the regularity of $\omega_1$ to do this second exercise - which is good, since $\omega_1$ need not be regular in ZF alone!

Answer 2

Yes, such a surjection always exists. Without choice, there is a bijection from $\mathbb{R}$ to $\mathcal{P}(\mathbb{N}\times\mathbb{N})$, the set of relations on $\mathbb{N}$. There is also a surjection $\mathcal{P}(\mathbb{N}\times\mathbb{N})\to\omega_1$ which sends each well-ordering of a subset of $\mathbb{N}$ to its order type and every relation that is not a well-ordering of a subset of $\mathbb{N}$ to $0$. Composing these gives a surjection $\mathbb{R}\to\omega_1$.