Proving existence of a surjection $2^{\aleph_0} \to \aleph_1$ without AC

Question

I'm quite sure I'm missing something obvious, but I can't seem to work out the following problem (web search indicates that it has a solution, but I didn't manage to locate one -- hence the formulation):

Prove that there exists a surjection $2^{\aleph_0} \to \aleph_1$ without using the Axiom of Choice.

Of course, this surjection is very trivial using AC (well-order $2^{\aleph_0}$). I have been looking around a bit, but an obvious inroad like injecting $\aleph_1$ into $\Bbb R$ in an order-preserving way is impossible.

Hints and suggestions are appreciated.

Answer 1

In what follows, by a "real", I mean a subset of $\omega\times\omega$, that is, a binary relation on $\omega$. (You can start with a bijection $\pi:\mathbb R\to\mathcal P(\omega\times\omega)$, which can be constructed without choice, so this is fine.)

If this relation happens to be a well-order of $\omega$ in order type $\omega+\alpha$, map the real to $\alpha$. Otherwise, map the real to $0$. This map is a surjection.

By the way, without choice, you cannot inject $\aleph_1$ into $\mathbb R$.

Answer 2

One of my favorite ways is to fix a bijection between $\Bbb N$ and $\Bbb Q$, say $q_n$ is the $n$th rational.

Now we map $A\subseteq\Bbb N$ to $\alpha$ if $\{q_n\mid n\in A\}$ has order type $\alpha$ (ordered with the usual order of the rationals), and $0$ otherwise.

Because every countable ordinal can be embedded into the rationals, for every $\alpha<\omega_1$ we can find a subset $\{q_i\mid i\in I\}$ which is isomorphic to $\alpha$, and therefore $I$ is mapped to $\alpha$. Thus we have a surjection onto $\omega_1$.