Timeline for Proofs of the uncountability of the reals
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 26, 2022 at 0:42 | history | edited | Timothy Chow | CC BY-SA 4.0 |
Added a second addendum
|
| Aug 12, 2020 at 18:21 | history | edited | Timothy Chow | CC BY-SA 4.0 |
Addendum about paper by Normann and Sanders
|
| Oct 25, 2017 at 15:04 | comment | added | Timothy Chow | @NathanBeDell : thanks for the reference, which is interesting and which I didn't know about. However, I still think that this paper gives us no idea how to answer the original question, which is a question about classical logic. One could formulate an analogous question in the context of a non-classical logic, and maybe even answer it, but it would still not address the original question of whether every classical proof of the classical theorem must use diagonalization. | |
| Oct 25, 2017 at 12:50 | comment | added | Nathan BeDell | @TimothyChow From what I've seen, I agree with you that this sort of mathematics hasn't been studied at nearly the level required to prove such a theorem, but "nobody has any idea", I don't think is a very good way to surmise the situation. In particular, for set theory developed over a certain paraconsistent logic, Cantor's theorem is unprovable. See "What is wrong with Cantor's diagonal argument?" by Ross Brady and Penelope Rush. So, if one developed enough of reverse mathematics in such a context, one could I think meaningfully ask this question. | |
| Oct 3, 2017 at 19:12 | comment | added | Joshua Grochow | @TimothyChow: I agree with you in terms of clarity of the underlying issue. However, the point of mentioning Reverse Math is that it is an active area of mathematical research that deals precisely with questions of the form "Is A necessary to prove B?", but it is an area of math that many mathematicians are not aware even exists (and they cannot even conceive how one might prove such a statement). So, in that sense, I suppose mentioning this area of math is more for the benefit of advertising than anything else. | |
| Oct 2, 2017 at 23:42 | comment | added | Timothy Chow | @JoshuaGrochow : I don't really see what is gained by using the term "reverse math" here. It comes down to what I said at first: one needs to construct a plausible system for mathematics in which the reals are countable. I think that this is a clearer and more accurate way to describe the obstacle than to talk about "how to formalize the notion of diagonalization within reverse math." | |
| Oct 2, 2017 at 21:19 | comment | added | Joshua Grochow | @TimothyChow: I agree with both you and Amit. Following on Amit's comments, I'd like to draw your attention to the seeming conflict between your answer to his question 1, and the first sentence of your posted answer. I think a fairer answer, which I hope you'd agree with, might be to say that Reverse Math would be the right domain in which to try to prove that diagonalization is necessary for uncountability of the reals, but the difficulty is that no one has any idea how to formalize the notion of "diagonalization" within Reverse Math. | |
| Nov 29, 2010 at 21:17 | comment | added | Timothy Chow | @Amit: 1. No. 2. No, I'm not presuming that "diagonalization is necessary for Cantor's theorem"; that's what Solomon was conjecturing, and I'm just saying we're not in a position to prove such a thing. 3. Maybe it's possible, but I don't think anyone has any idea how to do it. I don't think your proposal about non-stratifiable formulas will work, but if you can do it, more power to you. Here's another context where we'd love to axiomatize diagonalization: in computational complexity, folklore says that "diagonalization relativizes." There's still no good axiomatization of this "fact." | |
| Nov 26, 2010 at 1:22 | comment | added | Amit Kumar Gupta | Actually following Terry's comment, "being able to diagonalize" might be axiomatized a scheme for Comprehension or Separation involving non-stratifiable formulas. | |
| Nov 25, 2010 at 8:44 | comment | added | Amit Kumar Gupta | 1. Are you saying reverse math never proves results of the form "Argument A is necessary for Theorem T" (in some reasonable sense of the word "necessary")? 2. You presume that diagonalization is necessary for Cantor's theorem - someone who believes not wouldn't need a model where the reals are countable. 3. Why is it that "being able to diagonalize" can't be axiomatized? A huge variety of arguments get referred to as compactness arguments, so naively one would think you couldn't axiomatize "being able to do a compactness argument", but doesn't Weak Konig's Lemma sort of do just that? | |
| Nov 24, 2010 at 2:28 | comment | added | Timothy Chow | @Amit: Yes, I'm familiar with reverse mathematics. But let me repeat what I said above: Think closely! How would you axiomatize what it means to be able to diagonalize? What candidate do you have in mind for a model in which the reals are countable? I stand by what I said; nobody has a clue. | |
| Nov 23, 2010 at 18:27 | comment | added | Amit Kumar Gupta | Reverse mathematics (en.wikipedia.org/wiki/Reverse_mathematics) is almost exactly about studying which axioms and arguments are necessary for certain theorems. If you want to know whether axiom X is necessary for a theorem Y, you can try to see if there's a model of Y in which X doesn't hold. It's not as easy to see whether a certain argument is necessary, but often you can axiomatize what it means to be able to do a certain argument, e.g. there are systems which capture what it means to be able to use a compactness argument, or induction, or transfinite recursion, etc. | |
| Nov 23, 2010 at 14:54 | vote | accept | Unknown | ||
| Nov 23, 2010 at 11:55 | comment | added | Unknown | Thank you. Now, I know that it is possible to block diagonalization in some setting. | |
| Nov 22, 2010 at 23:28 | comment | added | Terry Tao | Well, there is Quine's New Foundations in set theory, in which the diagonal argument is blocked from disproving the existence of a set of all sets, because of the inability to express the predicate $x \not \in x$. But I gather that NF does not block the diagonal argument from demonstrating the uncountability of the reals, so this isn't quite an answer to the problem at hand... | |
| Nov 22, 2010 at 18:49 | comment | added | Unknown | Oh...Thank you. I did not think the question will go this far. So, the question is pretty like the statement in Cosmology: "The observable universe is finite but nobody yet knows whether it is infinite or not, let alone boundedness." | |
| Nov 22, 2010 at 18:25 | history | answered | Timothy Chow | CC BY-SA 2.5 |