3
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ I suspect that you don't even need choice, you just need the law of excluded middle so that you can use the Cantor–Schröder–Bernstein theorem. But I don't have time to think about this properly right now... someone else will probably answer before I get the chance ;) $\endgroup$ – Clive Newstead Oct 23 '17 at 1:20
  • $\begingroup$ @CliveNewstead I think you will need choice - I don't see how to associate a real to each countable set of reals in an injective way. (There is an obvious injection from $(0, 1)^\omega$ into $(0, 1)$, but it doesn't work for $[(0, 1)]^\omega$ instead.) $\endgroup$ – Noah Schweber Oct 23 '17 at 3:23
  • 1
    $\begingroup$ @Noah: Maybe you don't see it because it's consistently false? $\endgroup$ – Asaf Karagila♦ Oct 23 '17 at 7:42
4
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Huh. Why was I sure that 1.4(a) was a theorem of Zermelo and not Tarski? I'm not sure... $\endgroup$ – Asaf Karagila♦ Oct 23 '17 at 7:41
  • $\begingroup$ I think because the right proof is immediate from Zermelo's argument. $\endgroup$ – Andrés E. Caicedo Oct 23 '17 at 12:46
  • 1
    $\begingroup$ It might be worth pointing out, in addition to mentioning the Solovay model (in your answer and in mine), that DC plus "$\omega_1$ does not inject into the reals" implies that $\omega_1$ is inaccessible in $L$. So large cardinals are necessary. $\endgroup$ – Asaf Karagila♦ Oct 23 '17 at 19:21
  • $\begingroup$ But I do not know that they are necessary for the task at hand rather than just for the given argument, do you? $\endgroup$ – Andrés E. Caicedo Oct 23 '17 at 19:30
  • $\begingroup$ Yeah, they are certainly not necessary. Just look at any model where $\omega_1$ is inaccessible to reals, that can be the Feferman–Levy model, or the Truss models from a singular... But of course, in those models $\omega_1$ is singular and of course that countable choice fails. $\endgroup$ – Asaf Karagila♦ Oct 23 '17 at 19:31
3
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ I had this question because I was actually reading a blog post of yours ("anti-anti-Banach-Tarski arguments") where you construct a partition of R of strictly greater cardinality. The proof starts with "fix a surjection between $(0,1)$ and $(0,1)^\omega$ (which in context seems to be countable subsets of (0,1)), how can I get this surjection then? $\endgroup$ – JKEG Oct 23 '17 at 11:11
  • $\begingroup$ Note that there is a bijection between $(0, 1)$ and $(0,1)^\omega$. This is just cardinal arithmetic at play. This gives you a sequence of reals, for each real. Now forget the sequence and only remember the set of reals (add some rationals if the sequence has finitely many points repeating). This gives you a surjection. The key point is that you cannot uniformly choose enumerations for every countable set of reals. So this surjection cannot be sectioned without using some choice. $\endgroup$ – Asaf Karagila♦ Oct 23 '17 at 11:15

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.