Timeline for Non-Borel sets without axiom of choice
Current License: CC BY-SA 2.5
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 22, 2010 at 1:21 | comment | added | Joel David Hamkins | Yes, I think without $AC_\omega $ you don't get that $\Sigma^1_1$ and $\Pi^1_1$ are closed under countable unions and intersections, since you have to pick the representing formulas (or indices in the universal formulas). So $\Delta^1_1$ is not a $\sigma$-algebra in this case. | |
| Jul 21, 2010 at 15:51 | comment | added | Andrés E. Caicedo | Hi David. You are right, it is in the proof of the equality of Borel and $\Delta^1_1$. Joel pointed this out in the answer I wrote, which I think I've now fixed. | |
| Jul 21, 2010 at 15:47 | comment | added | Dave Marker | Joel--where does $AC_\omega$ come into the proof that the universal $\Sigma_1^1$-set is not Borel. It seems like the diagonalization is no problem. If $U(x,y)$ is universal, we see that {$x:\neg U(x,x)$} is not $\Delta_1^1$. Does choice come into the proof that Borel sets are $\Delta_1^1$? It seems likely choice is needed to show that a countable union of $\Sigma_1^1$-sets is $\Sigma_1^1$. | |
| Jul 21, 2010 at 14:23 | comment | added | Joel David Hamkins | Anweshi, please don't worry about accepting/not accepting---of course this is not important. Andres gave the best answer to the question you asked. | |
| Jul 21, 2010 at 12:21 | comment | added | Anweshi | Ok, so to be precise, one can construct non-Borel sets using just countable choice. I see. Thanks a lot. It is really sad that I cannot accept both answers. But since I didn't specify things like "countable choice", I have no choice though this answer is extremely good. But thanks once again, as I learned quite a number of things from your answer. | |
| Jul 21, 2010 at 11:45 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 902 characters in body
|
| Jul 21, 2010 at 10:11 | comment | added | Joel David Hamkins | Andres is right---I need countable choice in order to get my map from the reals onto the Borel sets. In order to show that the collection of sets having a Borel code is a $\sigma$-algebra, one needs to be able to pick representing Borel codes from a countable set of Borel sets. | |
| Jul 21, 2010 at 3:17 | comment | added | Joel David Hamkins | It seems I have slipped some AC use into a part of my cardinality calculation, since I only have surjections both ways between Borel sets and the reals, which isn't enough to get a bijection. (One needs injections to emply Cantor-Schroeder-Bernstein.) But it is sufficient anyway for my conclusion, since Cantor shows there is no surjection $\mathbb{R}\to P(\mathbb{R})$, but I did exhibit a surjection of $\mathbb{R}$ onto the Borel sets. So we retain the conclusion that most sets are not Borel. I wonder what the exact AC content is of an actual bijection between $\mathbb{R}$ and the Borel sets? | |
| Jul 21, 2010 at 0:56 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 695 characters in body; deleted 33 characters in body
|
| Jul 21, 2010 at 0:51 | comment | added | Joel David Hamkins | $\Pi^1_1$ means that the set is definable by a statement of the form $\forall y\, \varphi(x,y,z)$, where the quantifer $y$ ranges over reals, and $\varphi$ has only quantification over natural numbers, and $z$ is a real parameter. These are also known as the co-analytic sets. | |
| Jul 21, 2010 at 0:49 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 841 characters in body
|
| Jul 21, 2010 at 0:44 | comment | added | Anweshi | Oh, I am sorry again. The part I didn't understand was not the Cardinality argument. It was the statement"....well order is a complete $\Pi_1^1$ set, and cannot be Borel.". Here I missed what is $\Pi_1^1$. | |
| Jul 21, 2010 at 0:41 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
explained Borel codes
|
| Jul 21, 2010 at 0:35 | comment | added | Anweshi | I edited the question to reflect this. I hope you don't mind it. | |
| Jul 21, 2010 at 0:33 | comment | added | Anweshi | Oops ... Of course I knew the cardinality argument. What I had in mind was concrete examples. Could you elaborate on that part a bit? I must confess I didn't understand the last two phrases. | |
| Jul 21, 2010 at 0:30 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |