Countable subsets of reals injecting into reals implies $\omega_1$ distinct reals

Question

I am working through this problem: work in ZF, assume there is an injection $f:\mathcal{P}_{\omega_1}(\mathbb{R})\rightarrow \mathbb{R}$, show that there are $\omega_1$ distinct reals. Here, $\mathcal{P}_{\omega_1}(\mathbb{R})$ denotes the set of all countable subsets of reals.

I think I have the right approach but I am stuck on finishing off the argument. Here's my attempt: without loss of generality we identify $\Bbb R$ with $\mathcal{P}(\omega)$; there is a surjection $\pi: \mathcal{P}(\omega)\rightarrow \omega_1$ by mapping codes of well-orderings to their ordertypes, and non-codes to $0$. Then, by taking pointwise preimage of $\pi$, there is an injection $g:\omega_1\to \mathcal{P(P}(\omega))$. I think the next thing to do is to somehow restrict the range of $g$ to $\mathcal{P}_{\omega_1}(\mathcal{P}(\omega))$ and then compose it with the injection we assume exists. But I don't know how to proceed.

Answer 1

In order to build a well-ordered sequence of reals (which is how "$\omega_1$-many reals" should be thought of in the $\mathsf{ZF}$ setting), the most natural tool to look at is transfinite recursion. Without the axiom of choice, this is really the only good way we have of building long well-ordered sequences.

So suppose $f:\mathcal{P}_{\omega_1}(\mathbb{R})\rightarrow\mathbb{R}$ is injective. Do you see a way to "iteratively" use $f$ to build a long sequence of reals?

HINT: start with $f(\emptyset)$ ...

We define a sequence of reals $(a_\eta)_{\eta<\omega_1}$ recursively as follows: $$a_\eta=f(\{a_\beta:\beta<\eta\}).$$

This $\omega_1$-sequence of reals is clearly well-defined, so all we have to do is show that it's injective: no real appears twice in the sequence. This is where we use the injectivity of $f$; think about how a real arises as an element of this sequence.

---

Note that here I've used the broad notion of countable, where finite sets are considered countable. What if we don't? That is what if $f$ only acts on countably infinite sets of reals?

Well, then we hit a bit of a problem: we have to worry about "stalling." Since our recursion can't start at $\emptyset$ anymore, we have to start by picking some countably infinite $X\subset\mathbb{R}$ to feed into $f$. The problem now is if $f$ spits out an element of $X$ - either now, or later on down the road - we'll stop generating new elements of our sequence. Put another way, we need to find an $X$ such that the recursively-defined sequence $$r_\alpha=f(\{r_\beta:\beta<\alpha\}\cup X)$$ never hits $X$.

If no such $X$ exists, then we can extract from $f$ a choice function for countably infinite sets of reals: just take $r_\alpha$ for the least $\alpha$ which yields an element of $X$. So the "strong" version of the question reduces to:

Does "There is a choice function for the set of countably infinite sets of reals" imply "There is an $\omega_1$-sequence of distinct reals?"

This actually seems nontrivial to me - by which I mean I don't know how to solve it. :P Presumably Asaf knows ...