Timeline for Proofs of the uncountability of the reals
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 18, 2020 at 8:09 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question was bumped anyway)
|
| Oct 2, 2017 at 16:44 | comment | added | Michael Hardy | @JoelDavidHamkins : "Diagonal" in this context mean the set $\{(x,x) : x\in\text{some specified set} \}.$ So the question is how to view it that way. | |
| Oct 20, 2014 at 1:12 | comment | added | Toby Bartels | @Andres: The bijection between $\mathbb{R}$ and $\mathcal{P}\mathbb{N}$ is not constructive in the avoids-excluded-middle/acceptable-to-intuitionists sense. Although you can explicitly describe what appears to be a bijection, proving that it's defined everywhere requires excluded middle. In contrast, Cantor's nested-interval argument is acceptable. (Brouwer couldn't help complaining about how Cantor explained it and cleaning it up to his satisfaction, but he didn't change the argument.) This doesn't mean that it's not also a diagonalization argument, but it's a different one. | |
| Nov 23, 2010 at 22:51 | comment | added | Michael Hardy | But is the proof using shrinking intervals a "diagonal argument" in the sense in which the proof that every set has more subsets than member is a diagonal argument, or in the sense in which the usual proof of the unsolvability of the halting problem is a diagonal argument? | |
| Nov 23, 2010 at 13:45 | comment | added | Joel David Hamkins | Michael, if you reflect upon it, you will see that the two arguments are fundamentally identical. Prescribing the successive digits of a real to have certain values is the same thing as placing the resulting real in certain intervals. | |
| Nov 23, 2010 at 11:35 | comment | added | Francesco Polizzi | This information and the corresponding wikipedia link are already contained in my comment above :-) | |
| Nov 23, 2010 at 5:00 | history | edited | David Roberts♦ | CC BY-SA 2.5 |
Fixed link
|
| Nov 23, 2010 at 4:51 | history | edited | Victor Protsak | CC BY-SA 2.5 |
fixed link
|
| Nov 23, 2010 at 3:03 | comment | added | Andrés E. Caicedo | @Daniel : I am not sure I understand what you mean. The proof uses a diagonal argument. The typical diagonal argument proofs are constructive. And it is easy to describe explicitly bijections between ${\mathbb R}$ and $2^{\mathbb N}$. | |
| Nov 23, 2010 at 2:27 | comment | added | Daniel Mehkeri | +1. I consider this to be a very different proof. It is constructive, or can be made so with little change. The diagonal argument actually proves the uncountability of 2^N, and no effective bijection between R and 2^N exists. | |
| Nov 23, 2010 at 2:27 | comment | added | Andrés E. Caicedo | Unfortunately, this proof uses a diagonal argument. | |
| Nov 23, 2010 at 0:53 | history | answered | Michael Hardy | CC BY-SA 2.5 |