Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
48  
If they are true cranks, give up. Ain't gonna happen. –  Ross Millikan Oct 15 '13 at 15:30
5  
I only discussed with anti-Cantorians after I had uttered a discouraging word to a student. Serving my penance, you see. –  Jyrki Lahtonen Oct 15 '13 at 15:36
7  
Your biggest problem with this hypothetical anti-Cantor crank is that E seems to not understand proof by contradiction. I guess there should be some overlap between Cantor-truthers and people who don't understand contradiction, but my experience has been that the problem is usually more along the lines of not understanding the relationship between "sets", "lists", and "countable". Discomfort with contradiction is a separate issue that should be straightened out in a calmer setting, not in a case where the result is so unintuitive. –  Eric Stucky Oct 15 '13 at 15:41
14  
Point out to them that, by their argument "we assume a list of all real numbers, so it's impossible to construct a number not on the list", you could also prove that the only color is black, since assuming that black is the only color we cannot find another one. If that doesn't work then they don't understand logic and will never be convinced of anything. –  Ryan Reich Oct 15 '13 at 15:42
4  
I think that you may need to more clearly distinguish between the "Set of all Reals" and a "List of all Reals". The point of Cantor's proof is that there is such a set, but there cannot be such a list. –  RBarryYoung Oct 15 '13 at 21:24

7 Answers 7

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.

share|improve this answer
2  
@Keshav Srinivasan: I've never really understood why some people have such difficulty with proofs by contradiction, since so many arguments in everyday life have the same form. For example, a person accused of murder might argue that he couldn't have killed 'X' because he was at a dinner party with several witnesses when 'X' was killed, so the assumption of killing 'X' contradicts his being not being able to be in two places at the same time. The same if you're a child and your mother accuses you of taking some cookies, and you've been in school all day. –  Dave L. Renfro Oct 15 '13 at 19:25
2  
@DaveL.Renfro That last example is regrettably incorrect. Mothers do not reason by logic :-) –  Thomas Oct 16 '13 at 0:46
2  
@user8921 Bridges and planes can be made to work with 64 bit floating-point numbers. No "real" numbers are involved. The role of pi is played by an actor named 3.1415926535, or similar. –  Kaz Oct 16 '13 at 0:49
2  
@Thomas This is because mothers are by definition always correct :) –  Neal Oct 16 '13 at 1:22
3  
@Kaz, very true, but on a finite stage, the role of Cantor's diagonal argument would be played by another actor with an uncanny resemblance to the infinitary Cantor diagonal argument. –  zyx Oct 16 '13 at 4:31

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.

share|improve this answer
    
These people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. And in any case they're usually constructivists of some stripe, so they probably wouldn't accept the existence of the power set of N. –  Keshav Srinivasan Oct 15 '13 at 16:22
    
@KeshavSrinivasan I appreciate your point, but I was hoping that they would be able to deal with the set theory in the finite case. Also, I purposefully phrased my answer so as not to mention the power set of $\mathbb{N}$, and not to rely on the power set axiom at all. If they don't accept the collection of all subsets of $\mathbb{N}$ as a class, then I don't see what they could possibly construe the real numbers to be. –  Trevor Wilson Oct 15 '13 at 16:27
4  
@KeshavSrinivasan Then maybe they are right, and there really are only countably many points on the number line ;-) You have to commit to some formal definition of the real numbers for Cantor's theorem to be a theorem, and if they understand this formal definition, then they should be able to understand how real numbers correspond to sets of natural numbers. If they don't, then you have a more fundamental problem to deal with first. –  Trevor Wilson Oct 15 '13 at 16:34
1  
@KeshavSrinivasan But what if they are requiring the real numbers to be computable, but are not requiring the function $f : \mathbb{N} \to \mathbb{R}$ to be computable? My point is just that if you expect to convince them that you are right and they are wrong, then first you should fix precisely a context where this is true, and make sure they know what it is. If they have a precise understanding of "infinite decimal", they must also have a precise understanding of "set of natural numbers". –  Trevor Wilson Oct 15 '13 at 17:11
1  
...I'm not saying they need to accept arbitrary sets; we can restrict our attention to the case where the domain of $f$ is either a natural number or $\mathbb{N}$ itself. –  Trevor Wilson Oct 15 '13 at 17:11

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.

share|improve this answer
    
Well, in the FAQ I do discuss one legitimate philosophical objection, but I just say something like "If you don't accept ordinary Platonistic mathematics in the first place, then Cantor's theorem is about fictitious things anyway, so there's no need to dwell on it." The problem is that most people who take issue with Cantor's proof are not motivated by some coherent philosophical principle, they just have some basic misconception about mathematics, like "infinitely large set of numbers must contain infinitely large numbers". But I respect, e.g., legitimate predicativists: tinyurl.com/nelpa –  Keshav Srinivasan Oct 16 '13 at 1:16
2  
The FAQ item 1 is incorrect as it implies that definable reals (or sequences) are countable. This is only true in a non-definable mathematics. If you take the FAQ's suggestion to use definable objects only, then Cantor's theorem is still correct, but one has to formulate it for a definable world. It also is not true that not accepting Platonism or infinite sets invalidates diagonalization. –  zyx Oct 16 '13 at 1:27
    
The thing is, the people the FAQ is intended for are not spending their energy arguing against some narrow version of Cantor's proof about effective enumerations of computable real numbers, for instance. They're arguing against the standard proof for the Platonistic result, and they're not realizing that they reject the presuppositions which even the statement of the theorem are based on. They're willing to accept that the statement of the theorem is meaningful, they just think it happens to be false, so I'm trying to say that that's not a coherent viewpoint. –  Keshav Srinivasan Oct 16 '13 at 1:36
3  
It is not likely you can formulate an unassailable argument that will succeed in every case. However, where an objection consists of coherent and incoherent parts, removing the dispute about the coherent part reduces the number of things in contention, and might help clarify to the skeptic that the incoherent part is not correct. Besides that, it is misleading both to the objector and to any observers should it be done in an online forum, to not handle the coherent part as being valid. –  zyx Oct 16 '13 at 1:42
1  
Thank you for standing up for reason. I am baffled by the number of people in mathematics who will loudly defend straw-man tactics when they are aesthetically favorable. It would make as much sense to ban anyone without a Ph.D. from discussing the diagonalization proof, on the grounds that they do not truly understand the foundations. As beautiful as Cantor's work is, I think that what has been done with topoi is even more so. It is thus a good thing, as you point out, that we do not really have to choose—at least so long as we don't get carried away by unfair and oppositional attitudes. –  Slade Oct 16 '13 at 2:26

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$.

share|improve this answer
    
The problem is, these people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. Cantor's diagonal proof of the uncountability of the reals is usually the only proof they can comprehend. –  Keshav Srinivasan Feb 19 at 15:13
    
@KeshavSrinivasan: Apperently you are complaining it is just another proof they cannot comprehend. Note that the only "set theory" really used is that one can define a subset by telling which elements to keep and which ones not to keep. You can view sets as lists of their elements if you like, and get close to the traditional diagonal, without having to bother about reals. I think if they cannot comprehend maps from a set to its power set, there is really no point in discussing countability of real numbers with them in the first place. –  Marc van Leeuwen Feb 19 at 15:30
    
If they learned enough set theory, they'd probably abandon their objections to Cantor's diagonal proof anyway. But in any case, I suppose the objection I described in my question could be carried over to the Cantor's theorem case: they would say that the definition of $Y_f$ doesn't make sense in the case when $f$ is surjective, and that the contradiction you get in the case when $f$ is surjective indicates that $Y_f$ does not exist, not that $f$ is not surjective. The fundamental problem with these people is that they're misattributing the source of the contradiction. –  Keshav Srinivasan Feb 19 at 15:39
    
Usually they don't know enough set theory to even understand power sets. But I find that it's still productive talking with (at least some of) them, because if you can resolve their confusion.concerning Cantor's diagonal proof, then very often it leads them to want to learn more about set theory and transfinite numbers. That's reward enough for arguing with them. –  Keshav Srinivasan Feb 19 at 15:47

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?

share|improve this answer
    
Ok, then you are just lucky they don't claim that set of integers is finite:) –  Smylic Oct 16 '13 at 1:03
1  
Well, sometimes the cranks have a claim that they have constructed a complete list of real numbers, but a lot of the time they just reject Cantor's claim that such a list cannot exist, as opposed to making an affirmative claim on their part. Or they cite a reason that the real numbers are countable, but that reason does not actually give you a procedure for making a complete list of real numbers. And yes, there are other proofs of uncountability, but for instance you need a fair amount of math background for the proof that a perfect set is uncountable, whereas Cantor requires little. –  Keshav Srinivasan Oct 16 '13 at 1:03
2  
I was 13 when I got to know about 5 different proofs and had understood all of them. I think the following is not too hard. Consider a numbered list of all real numbers of $[0, 1]$. Let cover $i$th of them by open interval of length $3^{-i}$. Since each point is inside its own inteval (which has positive length) then is should be covered by at least one inteval. But cumulative length of all invervals is $\frac12$, so union of them all can't cover all points of $[0, 1]$. –  Smylic Oct 16 '13 at 1:13
    
Why wouldn't that proof show equally well that there are uncountably many rational numbers between $0$ and $1$? –  Keshav Srinivasan Oct 16 '13 at 5:12
1  
Not every point of $[0, 1]$ is rational, so covering every rational point doesn't mean covering every point and the whole segment. –  Smylic Oct 16 '13 at 15:32

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.

As a 'crank', my response to this is thus:

Congratulations, you have shown the inconsistency of infinite sets. Welcome to the wonderful world of para-consistent logic. Although we should really drop the adjective and just call it 'logic'. Working with explosive logics is not just a matter of taste; its just plain wrong. The only way to get an explosive logic is to refuse to define a clear procedure for symbol-lookup. Which variant of our conflicing symbol to substitute in our expression? Whichever one the logician feels like at the moment! Instead of 'logic' and 'para-consistent logic', we should be using the terms 'jazzy-logic' and 'logic' instead, respectively.

There is nothing deep about Cantors diagonal argument; the crux of the matter is that Cantor (rather arbitrarily) decides to resolve the contradiction he finds himself in, by letting go of one of the ingredients that went into his contradiction that he liked the least. Its not about his deductions; they are perfectly sound. Its about the choice of axioms that is sneaked in under the radar while the unsuspecting student is trying to wrap his head around the contradiction presented to him.

A less convoluted example of the same historical development can be seen with Galileo's paradox. Is the number of natural numbers larger than the number of even numbers? The 'modern' (~1900AD) solution, is to gut the notion of 'same size', and deny axiomatic status to the notion that if you take something away from something, it has become smaller. If that floats your boat, all the more power to you. But personally, id rather throw the consistency of infinite sets under the bus. (Killing a whole flock of birds with one stone here!). Are there more naturals than odds numbers? Obviously no, and obviously yes. That's a philosophically weighty choice to make, but from a pragmatic perspective: so what?

Fundamentally, we don't have a disagreement over how to apply the rules; you are perfectly correct using your ruleset, as am I. But we have a meta-mathematical disagreement about what the rules should be. What may be held against the Cantorites though, is that this point tends to go over their heads, and they don't teach the arbitrary nature of their choices alongside with them, but rather present the particular axiomatization preferred by Cantors as inescapable fact. (edit: I should clarify: this point goes over the heads of the vast majority of anti-cantorites as well; they do not realize that what they are intuitively rebelling against is not cantors deductions, but his axioms.)

share|improve this answer
    
I'm not saying that there is any issue with paraconsistent logic, but any claim "it's not a matter of taste; it's just wrong" does not belong to a discussion like this one. –  Asaf Karagila Jan 10 at 10:18
    
Don't get me wrong; I love jazz music. I just think logic ought to have clearly defined rules. Unless you disagree with that notion, classical logic is 'wrong', or at least 'flawed'. Note, one may still choose Cantors preferred mathematical axioms while using non-explosive logic; but the historical motivation for this rather arbitrary choice completely falls apart. –  Eelco Hoogendoorn Jan 10 at 10:31
    
I don't understand your jazz reference. I don't follow the rest of your comment. I get this feeling that you're just trying to be slick and write a smooth comment to express the alleged superiority of someone who doesn't understand infinities, or is trapped in this reality and doesn't understand infinities. –  Asaf Karagila Jan 10 at 10:37
    
I assume you are familiar with the principle of explosion? If not, look it up. The 'flaw' in reasoning, if you think calling it plain wrong is too strong a statement, is the lack of a well-defined notion of symbol lookup in classical logic. In any modern formal language, there are clearly defined rules for what it means to invoke a symbol. In classical logic, the logician is free to substitute into an expression whichever instance of a symbol one prefers. Hence 'jazzy'. I don't understand your 'being trapped in this reality'; are you just trying to be slick here? ;) –  Eelco Hoogendoorn Jan 10 at 11:28
    
I don't like people who patronize me. Have a nice day. –  Asaf Karagila Jan 10 at 14:16

As a Cantor crank I will admit that is is useless to argue with many of them. However, I think questioning the math orthodoxy is a good thing. In the past most mathematicians assumed all numbers are rational and parallel lines never meet. They were wrong just as many of the things most mathematicians believe today are probably wrong. In the spirit of Cantor cranks everywhere I give a counter example to Cantor's diagonal argument. I will create a list of binary real numbers that contains the anti-diagonal number.

I will create the anti-diagonal in the usual way. If the $2^{-i}$ bit of the $ith$ entry is $0$ set the $2^{-i}$ bit of the anti-diagonal to $1$ else set it to $0$. This is my list:

1.000..., 0.000..., 0.000..., 0.000..., 0.000..., . . .

The anti-diagonal is 0.111.. which equals the first number in the list.

share|improve this answer
    
In this proof we need to include each number with finit number of significan bits twice: as $\overline{d_k\ldots d_0.d_{-1}d_{-2}\ldots d_{-n}}$ and as $\overline{d_k\ldots d_0.d_{-1}d_{-2}\ldots (d_{-n}-1)(b-1)(b-1)\ldots}$, where $b$ is base of notation. –  Smylic Oct 16 '13 at 1:19
5  
"In the past most mathematicians assumed all numbers are rational and parallel lines never meet. They were wrong just as many of the things most mathematicians believe today are probably wrong." Rrrrgh, I shouldn't argue in comments, but this is just such a wrongheaded way of thinking about math, and science more generally. –  Neal Oct 16 '13 at 1:27
7  
Nobody promised that Cantor's diagonalization algorithm for binary sequences (the proof of his theorem that there are more sets of natural numbers, than natural numbers) can be applied without modification to prove the analogous fact about binary expansions of real numbers. Noticing that a correct proof of statement A can be transformed into a false proof of (true) statement B (that has a correct proof very similar to that of A) is not a counterexample to anything. –  zyx Oct 16 '13 at 4:24
4  
Russell, let me quote Louis CK on creationists. It's fine that some people don't believe in evolution, but their arguments against it are usually... stupid "Well, I ain't a monkey... and my daddy ain't a monkey... and my granddaddy ain't a monkey!!!"; it's not a problem of questioning traditional mathematics, it's the question of how to do that. And the problem with cranks is that they insist that they know the rules of classical mathematics better than you, but they don't. They never do. And that's the key problem with cranks. –  Asaf Karagila Oct 18 '13 at 14:24
2  
@Val, Russell's response is correct. You asked a question that is ambiguous, and later resolved the ambiguity against the interpretation that Russell chose in answering, which happens to be the interpretation that made logical sense: that you were asking about the argument he actually did present, which allows freedom of selection of the "list". Cantor's argument also allows this freedom, as explained in the highest-voted answer. So it is not clear why anyone should have read your first comment and deduced that you were challenging this aspect of Russell's example. –  zyx Oct 21 '13 at 3:29

protected by Arthur Fischer Feb 19 at 8:28

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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