Refuting the Anti-Cantor Cranks

Question

I occasionally have the opportunity to argue with anti-Cantor cranks, people who for some reason or the other attack the validity of Cantor's diagonalization proof of the uncountability of the real numbers, arguably one of the most beautiful ideas in mathematics. They usually make the same sorts of arguments, so years ago I wrote up this FAQ to deal with them. Unfortunately, it's still hard to get anywhere with these people; the discussion frequently turns into something of this form:

ME: Suppose there is an ordered list containing all the real numbers. Then we can read off the diagonal entries and construct a real number that differs in the Nth decimal place from the Nth real number on the list. This real number obviously cannot be in the list. So the list doesn't contain all the real numbers.

THEM: Of course your proposed number is not on the list; it's not a well-defined real number.

ME: What do you mean? I gave you the exact procedure for constructing it. You take the Nth real number on the list, and you make it differ from that number in the Nth decimal place.

THEM: But if we really have a list of all the real numbers, then your proposed number has to be somewhere in the list, right?

ME: Yes, of course, so let's say it's in the 57th place. Then it would have to differ from itself in the 57th place, which is impossible!

THEM: Exactly, it's impossible! Your definition requires that it differs in some place from itself, which is impossible, so your definition is bad.

ME: But you're only saying that it's impossible on the basis of the assumption that there's a complete list of real numbers, and the whole point is to disprove that assumption.

THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?

ME: But that definition is a good one regardless of whether there are countably or uncountably many reals. It is a complete, algorithmic, unambiguous specification of the real number. What else could you want?

THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!

ME: Forget about the purported complete lists of real numbers for a moment. Don't you agree that for any list of real numbers, complete or incomplete, it's possible to construct a real number that differs in the Nth place from the Nth number on the list?

THEM: No, it's only possible to construct such a real number if that real number isn't on the list, otherwise it's a contradictory definition.

ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that there are countably many real numbers?

THEM: No, I don't.

ME: But what if we took our putative complete list of real numbers, and fed it in line by line into a computer with an algorithm that spits out, digit by digit, a real number that differs in the Nth digit from the Nth number on the list? Would such a computer program work?

THEM: No it wouldn't, the computer program would hit the place on the list where the number being constructed would reside, and then it would get crash, because it can't choose a digit for the number that differs in the nth place from itself.

ME: Argh!

So how do I stop going in circles and convince them that they're wrong?

Any help would be greatly appreciated.

Thank You in Advance.

Answer 1

The formulation "If $f:\mathbf{N} \to \mathbf{R}$ is an arbitrary mapping, then $f$ is not surjective" clearly fixes the original list of real numbers and sets aside the potentially combatitive issue of whether or not the list is all of $\mathbf{R}$.

Significantly, the argument is no longer by contradiction, but by direct implication: The diagonal procedure constructs a real number not in the image of $f$. Perhaps this may help circumvent the sense of double-talk presumably conveyed in first positing the existence of an enumeration of $\mathbf{R}$, then arguing that some infinite decimal is not on said list.

Answer 2

You could try limiting the discussion to the finite case of Cantor's theorem as a first step. Show them that for every function $f$ on the finite set $\{1,\ldots,n\}$ there is a subset of the domain $\{1,\ldots,n\}$ that is not an element of $\text{ran}(f)$. Show them how the construction works for some examples, say $n = 2$ and $n=3$.

If they don't accept this argument in the finite case, then challenge them to write down a counterexample $f$. If they do accept it, ask them to point out what goes wrong when $\text{dom}(f)$ is $\mathbb{N}$ (or an arbitrary set, although this may be too abstract for them.) At least you might be able to separate their confusion about diagonalization from their confusion about infinity.

EDIT: I am talking about the version of Cantor's theorem for sets of natural numbers rather than the version for real numbers. If they do not understand the correspondence between real numbers and sets of natural numbers, their notion of "real number" is probably not precise enough to have a reasonable discussion about Cantor's theorem.

Answer 3

It's not a proof, but in this situation it is reasonable to be like cranky student. When I say that his algorithm is wrong he can't agree until I show him any counterexample. So you can just ask your opponents to give you method of constructing such list. And you would always be able to show that list is incomplete:)

Anyway there are several different ways to prove that set of real numbers is uncountable. Are all of them rejected by your cranks?

Answer 4

An error of tactics and substance, made in that FAQ and an uncountable number of online debates of these matters, is to equate

reasonable objections to parts of the framework (including objections identical to ideas published and developed by accomplished mathematicians)

with

mistakes in digesting the proof on its own terms.

The first category, of coherent self-consistent criticisms that in some views or formalizations are correct objections, include

• there can be no actual or completed infinity
• proof by contradiction and/or excluded middle logic, is bad
• there should be an effective procedure/definition for every number
• the number of effective procedures/definitions is countable

You cannot overcome these criticisms as such. Instead, the explanation is to present Cantor's proof in a way that is compatible with the criticism either by showing that the disputed concept does not appear in the proof, or formulating the diagonalization argument as it would be stated in a finitist, constructive, predicative, computable, or definable mathematics.

Answer 5

Instead of entering a discussion about the proof for real numbers, I would propose discussing instead the abstract version, which gives far less opportunity for polemic. Let the "crank" decide what he thinks about the abstract version and its proof, and then see where to go from there. If he refuses the abstract version, he should either be able to find fault with the proof, or accept being inconsistent (if finding no fault in the proof but still rejecting the conclusion). When accepting the abstract version one can still refuse application for the real numbers (for instance by denying the existence of infinite sets, or maybe accepting existence of the natural numbers but not of their power set), but it forces one to draw a line somewhere; once this is done there is really nothing left to discuss. For reference, here it is:

Proposition. For every set $X$ and every map $\def\P{\mathcal P}f:X\to\P(X)$ there exists $Y_f\in\P(X)$ such that for all $x\in X$ one has $Y_f\neq f(x)$.

Proof. Take $Y_f=\{\, z\in X\mid z\notin f(z)\,\}$. For $x\in Y_f$ one has $x\notin f(x)$ so $Y_f\neq f(x)$. For $x\in X$ with $x\notin Y_f$ one has $x\in f(x)$, so $Y_f\neq f(x)$. This establishes $Y_f\neq f(x)$ for all $x\in X$.

Answer 6

I think the only way would be to find a different proof that holds against the main concern of the typical objections:
Does the constructed number actually exist?

I'll try to illustrate a proof that can address this concern.
Let's consider lists of real numbers written in base 10 and build a number from the list using this rule:

If the n^th digit of the n^th number of the list is 1, we change it to 2, otherwise we change it to 1.

We're assuming the list is made of infinite rows; if not, we could always repeat the same numbers from the beginning in the same order and get our new number.
Let's give a name to numbers that can be obtained from lists with this particular rule: if I wanted to be specific, I would call them something like "(1->2)(else->1) diagonals", but for the sake of brevity i'll call them diagonals.
Any real with some digit different than 1 or 2 is not diagonal.
If a real only has ones and twos, it could be diagonal.

Note that if reals are countable, both diagonals and not diagonals are countable (as you could just list them in the order you found for the reals)

Now, what if we listed all the not diagonals? From where we are, we couldn't immediately conclude that the not diagonals are uncountable, since the diagonal number of the list of course wouldn't be in the list of not diagonal numbers.
But it exists: it's something made of just ones and twos. probably more ones.
So, there are diagonal numbers: you can easily imagine them in this setting.

But, what if we listed all diagonal numbers?

It's a list, so it has a diagonal number, not in the list by construction.
But it's a list of diagonals: it should have its diagonal number. So, usual argument, usual contradiction, just in a slightly different setting: in here, you can conclude that diagonal numbers aren't countable, but you can't say the same about not diagonal numbers. (at least, not immediately) But it doesn't matter, because the real numbers are made of diagonals and not diagonals, and if diagonals are not countable, neither are real numbers!

So, my hope is that this argument could break the chain a bit, since it does provide a list of real numbers that doesn't contain its diagonal (the not diagonals), which you don't need to prove are uncountable, but also a list of real numbers that, if it existed, it couldn't contain its diagonal nor not contain it.
Basically, good cop and bad cop i guess? Except with lists.

Answer 7

First off, there are formally verified proofs of the theorem. In fact, every major theorem proof system or proof explorer has proved it, and it is number 22 in the classic "100 theorems" benchmark: http://www.cs.ru.nl/~freek/100/

The problem is one may not accept the axioms and rules of inference.

However, that is not the only problem. One may not even accept the statement as it is stated. I will show an alternative statement, which may be what the cranks have in mind.

Consider a Gödel numbering or any similar scheme from the naturals to the formulas of set theory. Clearly, this numbering lists all the possible formulas of set theory.

Since real numbers are merely formulas of set theory, the encoding will define every real number. This last statement is bound to be controversial, but nonetheless it's a valid definition of what it means to be a real number and your cranky friends could be utilizing it. (In fact, if I am understanding Asaf correctly, interestingly enough, this is the usual definition: Undefinable Real Numbers )

No idea why this got a down-vote and a delete request. The point was not brought forward in the previous answers and is based on Hamkin's answer: https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb#answer-44129

Simply substitute definable real number in place of real number and the diagonalization proof no longer works. Note that each real number may be definable.