Is countable choice sufficient for the set of countable subsets of $\mathbb{R}$ to be equipotent with $\mathbb{R}$?

Question

I want to know if countable choice is sufficient to see that $(0,1)\cong[(0,1)]^\omega$.

If not, is dependent choice sufficient?

Haven't been able to construct an injection, and I don't know which of the classical theorems on cardinal arithmetic use full choice. For example I'm not sure if the usual $\alpha+\beta=\alpha\cdot\beta=\max\{\alpha,\beta\}$ still holds. Not accustomed to not having full choice.

Thank you for any help.

Answer 1

No, not even $\mathsf{DC}$ suffices for this. Here, $\mathsf{DC}$ is the axiom of dependent choice, which is strictly stronger than countable choice.

For instance, it is a theorem of $\mathsf{ZF}$ that for any set $X$, the set $\mathcal{WO}(X)$ of subsets of $X$ that are well-orderable has size strictly larger than the size of $X$. This is a result of Tarski.

Now, it is consistent with $\mathsf{ZF}+\mathsf{DC}$ that $\omega_1\not\le|\mathbb R|$, that is, there is no injection of $\omega_1$ into $\mathbb R$, and therefore $[\mathbb R]^{\aleph_0}=\mathcal{WO}(\mathbb R)$.

For a proof of Tarski's result, see for instance

MR1954736 (2003m:03076). Kanamori, A.; Pincus, D. Does GCH imply AC locally? In Paul Erdős and his mathematics, II (Budapest, 1999), 413–426, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002.

(A really nice paper that everyone should read, by the way.)

For the remark regarding the consistency with $\mathsf{DC}$ of $\omega_1$ not injecting into $\mathbb R$, this holds for instance in Solovay's model. Details can be found in several places, such as Section 11 of

MR1321144 (96k:03125). Kanamori, Akihiro. The higher infinite. Large cardinals in set theory from their beginnings. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1994. xxiv+536 pp. ISBN: 3-540-57071-3.

This is admittedly a rather curious result: It is provable in $\mathsf{ZF}$ that $\mathbb R$ and $\mathbb R^\omega$ have the same size, and there is a natural surjection from $\mathbb R^\omega$ onto $[\mathbb R]^{\aleph_0}$. This provides us with an example of a quotient of size strictly larger than that of the set it comes from.

Answer 2

Andrés wrote a very good and comprehensive answer. Let me complement it by adding the following related consequence:

(Sierpiński) Suppose that there is a bijection between $\Bbb R$ and $[\Bbb R]^\omega$, then there is a non-measurable set.

(You can find the proof and a discussion in this MathOverflow question.)

While it is arguable that the notion of measure might not make much sense in a model without as so much as countable choice. But, Solovay, as remarked by Andrés proved that assuming the consistency of an inaccessible cardinal with can prove that $\sf ZF+DC+\textrm{All sets of reals are measurable}$ is also consistent.

So in this model, we indeed get that there can be no bijection between $\Bbb R$ and $[\Bbb R]^\omega$ and $\sf DC$—and therefore also countable choice—holds.

---

Note that there is always a surjection from $\Bbb R$ onto $[\Bbb R]^\omega$. First, by simple cardinal arithmetic we have that there is a bijection between $\Bbb R$ and $\Bbb R^\omega$. So every real is a code for a sequence of reals; now forget the ordering of the sequence to obtain a countable set of reals (add the rationals if said set is finite).

The above shows that while there is a surjection, we cannot find a uniform enumeration for all sets of reals at the same time. Namely, it is impossible to match every countable set of reals an enumerating function without using the axiom of choice.

And since there are uncountably many countable sets of reals, there is no reason to suspect that countable choice is going to do us much good. After all, it is only letting us choose from countably many sets at the same time.