Diagonalization proceeds from a list of real numbers to another real number (D) that's not on that list (because D's nth digit differs from that of the nth number on the list).

But this argument only works if D is a real number and this does not seem obvious to me!

Especially given that in Cantor's time there was no developed theory of computability, I could imagine someone of that era saying "ah, Cantor, you are pulling a trick here! D seems like a real number at first glance but when you look closely it's infinitely difficult to calculate or really talk about with precision in any way. In this regard it's unlike every real number I've ever encountered and you must make an additional argument to make me consider it a genuine real."

My question is this: was Cantor's diagonalization argument—at the time he made it—rigorous? Either in the sense that it proceeds from axioms or in the sense that it contains a convincing answer the above skeptic? Does D's real number-ness require a justification and did Cantor offer a sufficient one?

Of course I am not questioning whether the reals are actually uncountable. I'm interested in extent to which Cantor actually proved this versus giving an intuitive argument in favor of believing it.

  • 2
    $\begingroup$ another real number (D) that is not a real number ? In what sense ? "infinitely difficult to calculate" ? Only a "very small" portion of real numbers are "computable". The argument does not assume that we can compute them: it assumes that we have a listing whatever. $\endgroup$ – Mauro ALLEGRANZA Oct 16 '18 at 15:30
  • $\begingroup$ See the post : When does the diagonal cantor argument apply as well as the post : Is Cantor’s diagonal logic right ? $\endgroup$ – Mauro ALLEGRANZA Oct 16 '18 at 15:34
  • 1
    $\begingroup$ The argument that the number constructed in Cantor's Theorem's Proof is unlike every real number you've ever encountered is completely irrelevant here: who care what real numbers have you, or anyone else for that matter, "encountered"? Perhaps you need to meet more of those...? The proof is completely rigorous and logic. That we cannot "know" that number in the same manner we know number 5. -3 or 18 means nothing. One could also ask how well you "know" the number $\;\pi\;$ ....in what sense, really?! $\endgroup$ – DonAntonio Oct 16 '18 at 15:46
  • 3
    $\begingroup$ @DonAntonio: I know $\pi$ very well. We meet for coffee or lunch every couple of weeks. He is very irrational, but after taking a course in transcendental meditation he became more focused. All in all, a pretty rounded fella. $\endgroup$ – Asaf Karagila Oct 16 '18 at 16:55
  • 1
    $\begingroup$ @AsafKaragila :)) That was good laugh, really. Thanks. $\endgroup$ – DonAntonio Oct 16 '18 at 17:28

You seem to be assuming a very peculiar set of axioms - e.g. that "only computable things exist." This isn't what mathematics uses in general, but even beyond that it doesn't get in the way of Cantor: Cantor's argument shows, for example, that:

For any computable list of reals, there is a computable real not on the list.

This is roughly because we can compute the $n$th bit of the antidiagonal real by looking at the $n$th bit of the $n$th real on the list. (I'm hiding some details about numbers with two decimal expansions here, but they're easily overcome.) So even if you only believe in computable objects - which, again, isn't what mathematicians generally do - you're stuck with Cantor.

Put another way, if you want to restrict attention to computable objects, then you're stuck with only computable lists as well. And at this point Cantor's theorem is just the usual computability-theoretic fact that there is no computable enumeration of all the computable reals.

What we're seeing here is that Cantor's argument applies in pretty much any coherent "mathematical world" - restricting attention to "concrete objects" doesn't break it since the "antidiagonal real" is as concrete as the list it "responds" to. One way to make this observation precise is via category theory, where we can observe that Cantor's theorem holds in an arbitrary topos, and this has the benefit of also subsuming a variety of other diagonalization arguments (e.g. the uncomputability of the halting problem and Godel's incompleteness theorem).

Second, let's address the historical aspect. Cantor's argument of course relies on a rigorous definition of "real number," and indeed a choice of ambient system of axioms. But this is true for every theorem - do you extend the same kind of skepticism to, say, the extreme value theorem? Note that the proof of the EVT is much, much harder than Cantor's arguments, and in fact isn't computably true!

Basically, the issues with formalizing the reals and mathematics in general carry no more weight here than they do with other, apparently-less-objectoinable, theorems.

  • 1
    $\begingroup$ Maybe stress the point that if only computable objects exist, then the enumerations are also computable. In particular, no enumeration of all computable reals is computable. $\endgroup$ – Asaf Karagila Oct 16 '18 at 18:32
  • $\begingroup$ Thanks! Question on "For any computable list of reals, there is a computable real not on the list."—how can this be true if the set of computable reals is countable? I.e., if you only believe in computable objects aren't you good with "just" the natural numbers? (Albeit the natural numbers used to represent computer programs versus quantities?) $\endgroup$ – Tom Lehman Oct 17 '18 at 16:46
  • 1
    $\begingroup$ "For any computable list of reals" The computable reals are countable, but not "computably countable." If you only believe incomputable objects, you have to be very careful how you phrase things. In particular, the idea that every computable real has an index doesn't mean what we might think it means in the "computable universe:" we can't computably determine which naturals are indices for computable reals (as opposed to indices for non-halting computations). So in a sense the computable reals are "computably sub-countable" but aren't "computably countable." (cont'd) $\endgroup$ – Noah Schweber Oct 17 '18 at 16:49
  • 1
    $\begingroup$ Basically, the point is that when you work in a restricted mathematical framework you have to be very, very careful about how you treat various concepts. E.g. the way we think about cardinality isn't quite appropriate to the computable universe, and makes it look like Cantor's argument leads to a contradiction in the computable universe. (Another situation where this sort of thing happens is when we restrict the ambient logic, e.g. constructive mathematics.) $\endgroup$ – Noah Schweber Oct 17 '18 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.