Some “axiom of choice” and “dependent choice” issues

I am probably about to ask some fairly basic questions, and yet I have found it quite hard to find the answers to these.

If I understand correctly, mathematicians tend to be quite happy working with ZF+DC, but other forms of choice that are not implied by DC can be more controversial.

[Therefore it seems natural that people should give higher priority to discussing the differences in provable theorems between ZFC and ZF+DC -- or at least, the differences in provable theorems between ZFC and ZF+(countable choice) -- than to discussing the differences in provable theorems between ZFC and ZF. (Indeed, you basically can't do any analysis in just ZF.)]

My questions are:

1. Is it consistent with ZF+DC that every subset of $\mathbb{R}$ is Borel-measurable?
2. If the answer to Q1 is no: Is it consistent with ZF+DC that a countably generated $\sigma$-algebra can have a cardinality strictly larger than that of the continuum?
3. Is it a theorem of ZF+DC that there exists an injective map from the set $\omega_1$ of well-orderings of $\mathbb{N}$ into $\mathbb{R}$?

Thanks.

• I think the answer to each of these questions is no. For example if $\omega_1$ injects into reals, then there is an uncountable set of reals without perfect subset and this fails in Solovay's model for DC. For (2), it suffices to note that every set in a countably generated sigma algebra can be coded by a well founded subtree of $\omega^{< \omega}$ and being well-founded is absolute under ZF + DC. Solovay's paper should have details on all this. – Ashutosh Sep 21 '15 at 21:33
• I don't think I know anyone who's happy with DC but unhappy with stronger forms of choice. I think plenty of mathematicians are happy with full choice. I personally am conditionally happy with the ultrafilter principle but it'd be nice to do without it. I also find the claim that you can't do any analysis in ZF pretty terrifying. Surely you can at least do enough analysis to run through one of the analytic proofs of the fundamental theorem of algebra? – Qiaochu Yuan Sep 22 '15 at 1:02
• @QiaochuYuan I think people who are constructively-minded have various levels of philosophical justification for DC, see for instance ncatlab.org/nlab/show/dependent+choice#acceptability. I'd also be interested to know about FTA in ZF. Why not ask a new question? The nlab page (ncatlab.org/nlab/show/…) says FTA (I guess using Dedekind complex numbers) is true using Weak Countable Choice, and always true for Cauchy complex numbers. – David Roberts Sep 22 '15 at 2:33
• @David: No, that works fine as it is. I think you can probably squeeze it from absoluteness as well. If $f$ is a polynomial, look at $L[f]$, there choice holds, there are roots for $f$, and this is upwards absolute. – Asaf Karagila Sep 22 '15 at 5:35
• @QiaochuYuan : In the usual hierarchy of subsystems of first-order arithmetic, ACA_0 is enough for most basic analysis, including the fundamental theorem of algebra. – Timothy Chow Sep 22 '15 at 20:08

To elaborate a bit on Ashutosh's comment, my answer to this question shows that even countable AC, which is strictly weaker than DC, suffices to show that most sets of reals are not Borel. Thus, the answer to question (1) is negative. The argument there shows also that the answer to question (2) is negative, since one can code the sets by well-founded trees, just as Ashutosh mentions in his comments.

• Thank you to Joel David Hamkins and Asaf Karagila for the answers to my question. If I may, one further question: In my question mathoverflow.net/questions/214479/…, one of the questions I asked is whether a Polish metric and a non-separable metric can share the same Borel $\sigma$-algebra. I was given a very nice answer, which made use of uncountable choice at a couple of points. Is it consistent with ZF+DC that a Polish metric and a non-separable metric can share the same Borel $\sigma$-algebra? – Julian Newman Sep 22 '15 at 12:22

Let me add that the answer to (3) is negative, if you are willing to assume that inaccessible cardinals are consistent.

We say that $\omega_1$ is inaccessible to reals if for every real $x$, $\omega_1^{L[x]}<\omega_1$. This implies that $\omega_1$ is a limit cardinal in $L$. But if we also assume $\sf DC$, then $\omega_1$ is regular, in which case it is also regular in $L$. The conjunction of the two means that it is inaccessible there.

It is consistent that there is no injection from $\omega_1$ into the reals, e.g. in Solovay's model, where $\sf DC$ holds. And on the other hand, if $\omega_1$ is accessible to reals, then for some real number $x$, there is an injection from $\omega_1$ into the reals constructible from $x$, and in particular into $\Bbb R$.

So we see that it is consistent that $\omega_1$ is inaccessible to reals, and that there is no injection from $\omega_1$ into $\Bbb R$. (Of course it is consistent that $\omega_1$ is inaccessible to reals and there is such an injection. Simply look at the model obtained by collapsing an inaccessible to be $\omega_1$.)

• Perhaps it would be helpful to state explicitly that the consistency strength of ZF+DC+"$\omega_1$ does not inject into the reals" is precisely ZFC + an inaccessible cardinal. Given a model of the latter theory, then Solovay's model satisfies the former; given a model of the former theory, then true $\omega_1$ must be inaccessible in $L$. – Joel David Hamkins Sep 21 '15 at 23:45
• Yes. Maybe it's a hint that I should go to bed. I felt like this answer wasn't... ideally formulated, at least in terms of clarity. Thank you for the helpful comment! – Asaf Karagila Sep 21 '15 at 23:46
• Hmm, that consistency strength is surprising! What if we don't have DC? – David Roberts Sep 22 '15 at 2:31
• @David, then no inaccessible is needed. Plain ZF. – Asaf Karagila Sep 22 '15 at 5:20
• @David: I guess proof by authority is not enough here, eh? :-P Alright. The Fefeman-Levy model (where the reals are a countable union if countable sets) and the Truss models for the perfect set property (where the countable union of countable sets if reals is countable, but every set is Borel). In both $\omega_1$ is singular (and it has to be to avoid the inaccessible) – Asaf Karagila Sep 22 '15 at 5:40