# Refuting the Anti-Cantor Cranks

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?

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.

-
If they are true cranks, give up. Ain't gonna happen. – Ross Millikan Oct 15 '13 at 15:30
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
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
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
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

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.

-
@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
@DaveL.Renfro That last example is regrettably incorrect. Mothers do not reason by logic :-) – Thomas Oct 16 '13 at 0:46
@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
@Thomas This is because mothers are by definition always correct :) – Neal Oct 16 '13 at 1:22
@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

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

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

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.

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

The conversation seems almost equivalent to this hypothetical one:

ME: Suppose there are positive integers $m$, $n$ such that $m^2=2n^2$. Then we can generate a list of all prime factors and read off the exponent of $2$. This exponent should be even (because it is in the unique factorization of $m^2$) but also odd (because it is in the unique factorization of $2n^2$) so the equalilty cannot hold for any $m,n$.

THEM: Of course your proposed exponent cannot exist; it's not a well-defined integer.

ME: What do you mean? I gave you the exact procedure for constructing it: factorize that number. Check the factorization theorem.

THEM: But if we really have a list of prime factors then factor 2 has to have some exponent, right?

ME: Yes, of course, so let's say it's 57. Then it is odd and it would be also the double of an integer, that is impossible.

THEM: Exactly, it's impossible! Your definition of the exponent requires that it is both odd and even, 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 the equality $m^2=2n^2$ holds for some positive integers $m$ and $n$, 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 the assumption is true or false. It is a complete, algorithmic, unambiguous specification of an integer (the exponent of 2 in the unique prime factorization). What else could you want?

ME: Forget about the equality to be disproved for a moment. Don't you agree that for any number it's possible to construct a prime factorization and define the exponent of $2$?

THEM: No, it's only possible to define such an exponent if the number $a$ to be factorized is not such that $a=m^2=2n^2$, 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 $m^2=2n^2$?

THEM: No, I don't.

ME: But what if we took our putative number $a=m^2=2n^2$, and fed it into a computer with an algorithm that spits the exponent of $2$ in the prime factorization? Would such a computer program work?

THEM: No it wouldn't, the computer program would hit the place on the list where the exponent of $2$ would be computed and then it would get crash, because it can't produce a number that is both odd and even.

-
Interesting, can you spell out the proof that the square root of 2 is irrational using the exponent of 2? I've never seen that proof. I've only seen the conventional proof where you assume it's in simplest form and get a simpler form, or equivalently you construct an infinite descending sequence of natural numbers by continually dividing by 2. – Keshav Srinivasan Apr 30 at 20:08
But yeah, you seem to have constructed an analogous situation to the one I keep encountering with anti-Cantor cranks. So how would you explain to them the error in their reasoning in your case, and in my case? – Keshav Srinivasan Apr 30 at 20:09
It's very simple: $m^2$ must have an even exponent of $2$ in the prime factorization, $2n^2$ must have an odd exponent of $2$ – Marco Disce Apr 30 at 20:14
OK yeah, that makes sense, thanks. So how would you respond to the "them" in the dialogue? – Keshav Srinivasan Apr 30 at 20:18
Here also you can argue contrapositively, without making the initial controversial hypothesis: Let $m$ and $n$ be arbitrary positive integers. Each of $m^{2}$ and $2n^{2}$ factors uniquely into primes. However, the exponent of $2$ in $m^{2}$ is even, while the exponent of $2$ in $2n^{2}$ is odd. Since no integer is both even and odd, the factorizations of $m^{2}$ and $2n^{2}$ are distinct, and consequently $m^{2} \neq 2n^{2}$. Needless to say, I prefer this to "descent-type" arguments. :) – Andrew D. Hwang May 1 at 13:39

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

-
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 '14 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 '14 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 '14 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 '14 at 15:47
Unfortunately, this proof doesn't hold for all set theories. It relies on restricted comprehension, the same axiom that doesn't allow you to have an universal set. I don't think anything would really stop you from having a set theory where you can find natural and real numbers and an universal set; in that theory the first diagonal argument could still hold, but the one regarding power sets wouldn't. (=drawing the line at the set proof is actually drawing the line higher than you would need to to accept the different cardinalities of natural and real numbers) – byserpas May 7 '15 at 18:01

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?

-
Ok, then you are just lucky they don't claim that set of integers is finite:) – Smylic Oct 16 '13 at 1:03
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
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
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

Cantor's proof is not about numbers at all (there is a problem with trying to use it on numbers), it is about infinite strings of two characters. See http://www.logicmuseum.com/cantor/diagarg.htm.

Call them Cantor Strings. Cantor used "M" and "W" which, while they are visually interesting, are hard to distinguish. You can use "0" and "1" and claim they represent fractions in binary representation, but there is a problem. For example, 5/16 has two such binary representations: 0.01010000... and 0.01001111... . So you can't claim a number is missing, if all you prove is that a string is missing.

Ignoring this fault, as most treatments do, your very first statement is not what Cantor does "ME: Suppose there is an ordered list containing all the (Cantor Strings)." The first step of Cantor's Proof is "Consider ANY list that links every natural number to a unique Cantor String." Nowhere is it assumed that this means all Cantor Strings.

In fact, diagonalization proves the opposite. It proves: "If you have a set of Cantor Stings that can be listed this way, then it does not include all Cantor Strings."

It is a simple trick of logic to invert the statement "If A, then B" to get the 100% equivalent statement "If NOT B, then NOT A." So diagonalization also proves "If you have a set of all Cantor Strings, then it can't be listed this way."

Elegant, no?

The reason so many Anti-Cantor cranks exists, is because we don;t seem to teach Cantor's proof correctly.

-
I actually make the point that you're making later on in the dialogue; look at where it says "Forget about the purported complete lists of real numbers for a moment..." The problem is, when I phrase the proof that way, the cranks' retort is that they do not think that the diagonalization procedure will always work in constructing a well-defined real number (or infinite string if you prefer). They think that the diagonalization procedure is not well-defined if you start with a list that happens to be complete. The problem is that they're misdiagnosing the source of the contradiction. – Keshav Srinivasan Apr 16 at 20:27
I'd agree, if you you'd said "They think that the diagonalization procedure is not well-defined if you start with a list that happens to be INFINITE." The two are not the same, and I do feel it is the "infinite" part that confuses them. Not the "complete" part. – JeffJo Apr 17 at 19:09
No, they're fine with infinite lists. Like if you start with an infinite list of the form .0111111... then .1011111... then .1101111... etc., they think diagonalization is a well-defined procedure. But they think that if the list happens to be complete, then the diagonalization process is not well-defined. That's because if the list was complete and the diagonalization procedure was well-defined, then the number being constructed would be somewhere in the list, say the Nth spot. And then Nth digit of that number would be ill-defined, because it's required to differ from itself. – Keshav Srinivasan Apr 17 at 19:51
So they think that the diagonalization process is only well-defined for those lists which do not contain the number which would be constructed through diagonalization. Like I said, the problem is that they're misdiagnosing the source of the contradiction. They don't understand that the diagonalization process is well-defined for all lists. – Keshav Srinivasan Apr 17 at 19:54
And I think that their difficulty comes when they try to correlate the infinite length of the strings, to the infinite length of the assumed "complete" list. The question they have - the one behind the imagined contradiction you describe - is "If the list is infinite, how can it not contain all possible strings?" The answer is that you can correlate two infinities in more than one way, and some ways miss elements of one.. – JeffJo Apr 18 at 13:56

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

-
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 '14 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 '14 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 '14 at 10:37
I don't like people who patronize me. Have a nice day. – Asaf Karagila Jan 10 '14 at 14:16
@EelcoHoogendoorn why don't you describe paraconsistent logic and show exactly where the classical, proof of Cantor's diagonalization uses inferences that taken together lead to the principle of explosion? – Vladimir Sotirov Jan 10 '14 at 15:18

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.

-
I think they would still make the same objection I discuss in my question: they would say that it's possible to construct a diagonal for the list of all non-diagonals, but it's impossible to construct a diagonal for the list of all diagonals. And their reasoning would be that if the diagonal for the list of diagonals did exist, then it would have to differ from itself, which is impossible. Therefore, the list of diagonals can't have a diagonal. The fundamental problem is that they don't realize that taking the diagonal is a valid operation for all lists. – Keshav Srinivasan May 7 '15 at 20:23
Well, the arguments in the essence are the same, so yes, it's likely things wouldn't change at all. But, sometimes a minimal superficial change can trigger a different reaction, even if the math behind it is the same... I mean, the reasoning to get is that one, there's no way around it. One can only arrange the same arguments in a different fashion, so that the counterarguments can fall in a different way until they hopefully unclick by themselves. – byserpas May 7 '15 at 20:43

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.

-
"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
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
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
If one wants to argue that something is wrong, and to be taken seriously, then one should at least be familiar with that thing. Saying that we have to use the axiom of choice because we are sentient beings and have free choice in the world; and that natural transformations are transformations which are modeled after changes you can find in nature, and therefore modern mathematics is getting closer to the holistic side of the spiritual world... are both claims that I have heard. And those are ridiculous. Anti-Cantor cranks [usually] make equally ridiculous claims about the rules of mathematics. – Asaf Karagila Oct 18 '13 at 14:26
@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

I have a beautifully simple argument which will help you to show many doubters the true situation. If you project the real number line on to a circle it is clear that the real numbers are dense everywhere, while the natural numbers are dense only at infinity. This creates a strong, visualisable argument that there are more real numbers than integers.

The greatest mathematicians are painstakingly meticulous. Somebody's reluctance to accept the argument is more likely a good sign that they will only accept as true, ideas of the greatest quality, and after the greatest scrutiny, so don't be frustrated by it.

The diagonal argument proves that the rule of a unique successor (taken from the axiom of infinity in ZFC) always leaves at least one element of some definable enumeration of infinite sets not enumerated. But it is quite a leap to argue that this renders uncountable sets "greater than" countable sets, since countable sets have no maximal element and as such no identifiable element of a countable set ever completes their enumeration either.

A "crackpot" will point out to you that there is no set of transcendental numbers which does not have both a pair of algebraic numbers either end of it, and an algebraic number in-between every pair and therefore $\mathbb{T}$ cannot be strictly greater in number.

The fundamental truth in this is that "countable" sets are infinite by virtue of every element having a unique successor in some ordering, while "uncountable" sets are infinite by virtue of every pair of elements in at least one infinite subset thereof, having an element in-between. Cardinality therefore requires comparison of a discrete entity with a continuous one and as such, many will find it more natural to believe that the two are in some way "incomparable" rather than one strictly greater than the other.

Your best solution therefore is to explain that the notion of cardinality somehow rises above "counting", combines it with "measuring" so as to compare the discrete with the continuous in such a way that measuring a continuum is strictly greater than counting a list.

-
The argument in the first paragraph isn't sound, since it would work for rationals just as fine, and as we know rationals are equinumerous with integers. Also, from my experience, most (or at least many) anti-Cantor cranks don't argue with the very fact of uncountability of reals, but rather with Cantor's diagonal proof of this fact. – Wojowu May 21 at 9:14
This answer seems to assume that comparing cardinalities of sets is in any way related to orderings on those sets (and that the terms "continuous" and "discrete" can be applied to sets). – Tobias Kildetoft May 21 at 10:44
Unfortunately your answer is mistaken in so many ways. But let me focus on just this sentence: "The fundamental truth in this is that "countable" sets are infinite by virtue of every element having a unique successor in some ordering, while "uncountable" sets are infinite by virtue of every pair of elements in at least one infinite subset thereof, having an element in-between." It is a theorem of ZFC that all sets, countable and uncountable, can be put into an ordering where each element has a unique successor. And between every pair of rational numbers there is a rational number. – Keshav Srinivasan May 21 at 15:33
@RobertFrost Sorry, I don't understand your question. You want me to prove that "$s$ as described in the Wikipedia description of the diagonal argument is not necessarily the unique successor of some element in $T$". When you say "unique successor", what ordering are you referring to? Are you referring to the sequence $(s_n)$ which is assumed to exist and which it is the goal of the diagonal argument to disprove the existence of? If so, it's easy to prove that $s$ can't be the successor of any element in that sequence, because then it would be an element of the sequence and that's impossible. – Keshav Srinivasan May 21 at 16:25
@RobertFrost "Prove that there is no ordering of $T$ in which $s$ is the unique successor to some element of $T$." Do you want to me to prove this under the assumption that the sequence $(s_n)$ covers all of $T$, or without that assumption? Because if we're proceeding without that assumption, then what you're asking me to prove is not even true; it is a theorem of ZFC that for any element $x$ of $T$ there exists an ordering of $T$ such that every element of $T$ has a unique successor and $x$ is the successor of some element. That theorem applies just as well to $s$ as to any other element. – Keshav Srinivasan May 21 at 17:44

## protected by arjafi♦Feb 19 '14 at 8:28

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).