Timeline for Non-Borel sets without axiom of choice
Current License: CC BY-SA 2.5
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 8 at 13:40 | comment | added | Joe Lamond | @PeterLeFanuLumsdaine: Sorry for commenting on such an old post, but it wouldn't be more accurate to say that there are models of $\mathsf{ZF}$ in which a countable union of countable sets is not countable? The statement "For all $X$, $X$ is a countable union of countable sets implies $X$ is countable" appears to be independent of $\mathsf{ZF}$, since in models of $\mathsf{ZF}$ where choice holds it is true. (I'm assuming throughout that $\mathsf{ZFC}$ is consistent, of course.) I suppose the potential ambiguity lies in what "doesn't imply" means. | |
| May 15, 2014 at 5:02 | comment | added | Andrés E. Caicedo | @bof Sure, that's what I should have said. The result is this: All $G_{\delta\sigma}$ sets of reals have the perfect set property (provably in $\mathsf{ZF}$), but if the reals are a countable union of countable sets, then there is an $F_{\sigma\delta}$ set without the perfect set property. This is in Arnie Miller's paper A Dedekind finite Borel set. Or, simply, one can verify that there is a $G_{\delta\sigma}$ set that is not $F_{\sigma\delta}$, provable in $\mathsf{ZF}$, and this also seems due to Miller, in his paper on long Borel hierarchies. | |
| May 15, 2014 at 3:27 | comment | added | bof | @AndresCaicedo Doesn't "best possible" mean that not every set of reals is $F_{\sigma\delta}$ or $G_{\delta\sigma}$? | |
| May 15, 2014 at 1:53 | comment | added | Andrés E. Caicedo | @bof Yes, and this is best possible (meaning, not every set of reals is $F_\sigma$ or $G_\delta$). | |
| May 14, 2014 at 23:45 | comment | added | bof | So, if $\mathbb R$ is a countable union of countable sets, does that mean that every set of real numbers is an $F_{\sigma\sigma}$ set? And also a $G_{\delta\delta}$ set, being the complement of an $F_{\sigma\sigma}$ set? | |
| Oct 11, 2013 at 12:39 | comment | added | Andrés E. Caicedo | @DK No, it doesn't. It just means that any proof that the set is not Borel uses some amount of choice. (Usually, a really small amount.) For example, define $\mathsf{WO}$ as follows: You can use the decimal expansion of a real $x$ to code a subset of $\mathbb N\times \mathbb N$, there are several standard ways of doing this; now put $x\in\mathsf{WO}$ iff the subset that is coded is a well-ordering. This set is not Borel, but the proofs require choice. In the models I discuss in the answer, $\mathsf{WO}$ is Borel, but essentially by accident. | |
| Oct 11, 2013 at 11:52 | comment | added | Denis | Does this mean that if a set is built without choice, it has to be Borel ? | |
| Jul 21, 2010 at 15:40 | history | edited | Andrés E. Caicedo | CC BY-SA 2.5 |
added 1371 characters in body
|
| Jul 21, 2010 at 15:23 | comment | added | Andrés E. Caicedo | Joel, you are right. I'll fix the answer to reflect this. | |
| Jul 21, 2010 at 12:33 | comment | added | John Stillwell | @Peter. The result that the reals can be a countable union of countable sets is due to Feferman and Levy (1963). One place to see a proof is in Jech's book The Axiom of Choice, p.142. | |
| Jul 21, 2010 at 11:49 | comment | added | Joel David Hamkins | Andres, I think you don't need any AC to get a complete analytic set, right? This just uses a $\Sigma_1$ truth definition. And these sets cannot be $\Delta^1_1$ by diagonalization. But the issue is that we don't know that $\Delta^1_1=$ Borel without $AC_\omega$, since it may not be a $\sigma$-algebra, if we are unable to make countable choices. | |
| Jul 21, 2010 at 11:20 | comment | added | Peter LeFanu Lumsdaine | @Andres: that's a very nice independence result! Can you recommend a good reference for reading up on it? | |
| Jul 21, 2010 at 11:09 | comment | added | Peter LeFanu Lumsdaine | @Anweshi: Yes; but that's OK! The reals are still uncountable, and François' construction gives a $|\mathbb{R}|$-sized $\mathbb{Q}$-independent subset. The trick is that without AC, “countable union of countable sets” doesn't imply countable! (To get a counting of the union, you need to a choice of counting of each set in the union.) | |
| Jul 21, 2010 at 10:44 | comment | added | Anweshi | But François G. Dorais constructs an "uncountable" $\mathbb Q$-linearly independent set in $\mathbb R$, presumably without axiom of choice! | |
| Jul 21, 2010 at 10:33 | vote | accept | Anweshi | ||
| Jul 21, 2010 at 10:09 | comment | added | Joel David Hamkins | You are right! | |
| Jul 21, 2010 at 5:26 | history | answered | Andrés E. Caicedo | CC BY-SA 2.5 |