I recently got yet another email from a Cantor crank.
Sadly, it’s not a particularly interesting letter. It contains an argument that I’ve seen more times than I can count. But I realized that I don’t think I’ve ever written about this particular boneheaded nonsense!
I’m going to paraphrase the argument: the original is written in broken english and is hard to follow.
- Cantor’s diagonalization creates a magical number (“Cantor’s number”) based on an infinitely long table.
- Each digit of Cantor’s number is taken from one row of the table: the Nth digit is produced by the Nth row of the table.
- This means that the Nth digit only exists after processing N rows of the table.
- Suppose it takes time t to get the value of a digit from a row of the table.
- Therefore, for any natural number N, it takes N*t time to get the first N digits of Cantor’s number.
- Any finite prefix of Cantor’s number is a rational number, which is clearly in the table.
- The full Cantor’s number doesn’t exist until an infinite number of steps has been completed, at time
&infinity;*t .- Therefore Cantor’s number never exists. Only finite prefixes of it exist, and they are all rational numbers.
The problem with this is quite simple: Cantor’s proof doesn’t create a number; it identifies a number.
It might take an infinite amount of time to figure out which number we’re talking about – but that doesn’t matter. The number, like all numbers, exists, independent of
our ability to compute it. Once you accept the rules of real numbers as a mathematical framework, then all of the numbers, every possible one, whether we can identify it, or describe it, or write it down – they all exist. What a mechanism like Cantor’s diagonalization does is just give us a way of identifying a particular number that we’re interested in. But that number exists, whether we describe it or identify it.
The easiest way to show the problem here is to think of other irrational numbers. No irrational number can ever be written down completely. We know that there’s got to be some number which, multiplied by itself, equals 2. But we can’t actually write down all of the digits of that number. We can write down progressively better approximations, but we’ll never actually write the square root of two. By the argument above against Cantor’s number, we can show that the square root of two doesn’t exist. If we need to create the number by writing down all af its digits,s then the square root of two will never get created! Nor will any other irrational number. If you insist on writing numbers down in decimal form, then neither will many fractions. But in math, we don’t create numbers: we describe numbers that already exist.
But we could weasel around that, and create an alternative formulation of mathematics in which all numbers must be writeable in some finite form. We wouldn’t need to say that we can create numbers, but we could constrain our definitions to get rid of the nasty numbers that make things confusing. We could make a reasonable argument that those problematic real numbers don’t really exist – that they’re an artifact of a flaw in our logical definition of real numbers. (In fact, some mathematicians like Greg Chaitin have actually made that argument semi-seriously.)
By doing that, irrational numbers could be defined out of existence, because they
can’t be written down. In essence, that’s what my correspondant is proposing: that the definition of real numbers is broken, and that the problem with Cantor’s proof is that it’s based on that faulty definition. (I don’t think that he’d agree that that’s what he’s arguing – but either numbers exist that can’t be written in a finite amount of time, or they don’t. If they do, then his argument is worthless.)
You certainly can argue that the only numbers that should exist are numbers that can be written down. If you do that, there are two main paths. There’s the theory of computable numbers (which allows you to keep π and the square roots), and there’s the theory of rational numbers (which discards everything that can’t be written as a finite fraction). There are interesting theories that build on either of those two approaches. In both, Cantor’s argument doesn’t apply, because in both, you’ve restricted the set of numbers to be a countable set.
But that doesn’t say anything about the theory of real numbers, which is what Cantor’s proof is talking about. In the real numbers, numbers that can’t be written down in any form do exist. Numbers like the number produced by Cantor’s diagonalization definitely do. The infinite time argument is a load of rubbish because it’s based on the faulty concept that Cantor’s number doesn’t exist until we create it.
The interesting thing about this argument to be, is its selectivity. To my correspondant, the existence of an infinitely long table isn’t a problem. He doesn’t think that there’s anything wrong with the idea of an infinite process creating an infinite table containing a mapping between the natural numbers and the real numbers. He just has a problem with the infinite process of traversing that table. Which is really pretty silly when you think about it.
I’m not sure your correspondant is as ‘bone-headed’ as you are making him out to be. There is a school of constructivist mathematics which does roughly what he is proposing. This was originally proposed by Brouwer, who was told by his advisor to do good work elsewhere and secure a reputation before chasing an idea that would only provoke a serious backlash amongst mathematicians – which it did – led by Hilbert. Its also know as intuitionistic mathematics, and is fairly well developed. Whereas constructivism follows the line that was picked up by your correspondant. Intuitionism denies the law of the excluded middle. There is also school of ultra-finitistic mathematics that denies the axiom of infinity in ZFC. It appears to me your correspondant has picked up on the same idea that Brouwer (and probably other mathmeticians) had done to deny Cantor and Hilbert their paradise and find one of their own. Of course it needn’t be as black and white as that – and there might be the intellectual space to have a kind of logical pluralism in foundations.
I’m not buying that argument.
Constructivist math and intuitionistic logic are both perfectly valid and fascinating frameworks in which to do math. But they’re specific frameworks which need to be identified if you’re going to use them.
If you’re going to talk about what’s wrong with Cantor’s proof, you need to work in the realm of Cantor’s proof. If you’re going to work in a different realm, you need to state that clearly, and you need to show some understanding that you’re doing a proof that’s specific to that realm. In general, in math, one of the most important requirements of any proof is that you be clear about what your axioms are. Even if you’re doing standard mathematical work, you should state that you’re working in ZFC with Peano axioms and real numbers, or something similar. But if you’re doing work outside of the standard framework of ZFC, Peano, and Reals, you absolutely must state what system of axioms and logic you’re using.
If you don’t do that, or you don’t recognize the importance of the mathematical framework in which you’re working, then you’re a bone-headed idiot.
Sure, if you’re talking about a professional mathematician, you’d expect them to be aware of Constructivism. If they launched into a constructive argument without saying that they were, given that its still not mainstream mathematics, one would be entitled to call them a bone-headed idiot. But is your correspondant a professional mathematician or an amateur one? No doubt he is a crank, but if he (its undoubtably going to be a he), aware of constructivism? Or all the conventions and techniques of mathematics? If he’s just picked up the idea from the many popularisations of Cantors ideas, then I don’t think he’s done so badly, even if he’s being a bit cranky about it.
Cantor’s argument can quite easily be formulated in a constructively valid way. There are versions of constructive set theory where “the set of real numbers” doesn’t exist, but where it does, it isn’t going to be countable.
Interesting. There are versions of intuitionistic set theory that don’t have the natural numbers. And ones where the real numbers are equivalent to measurable functions. I’d be curious if Constructivism got started as a reaction to Cantor, I suspect it did – but I’m no historian.
Actually, Cantor’s argument does apply to computable numbers: it shows that they can’t be _computably_ enumerated.
That’s a matter of definition.
If you’re using the set of computable numbers, then you can’t computably enumerate them. But you can create a theoretical mapping. We know that there must be one, because the set of programs that generate computable numbers must be countable – therefore the set of numbers that can be generated by those programs must be likewise countable, and all countable sets are enumerable. Not necessarily computably enumerable, but still…
> That’s a matter of definition.
What is, exactly? Whether Cantor’s argument applies? It’s literally the same argument, except for considering only computable functions/enumerations/numbers.
> If you’re using the set of computable numbers, then you can’t computably enumerate them. But you can create a theoretical mapping. We know that there must be one, because the set of programs that generate computable numbers must be countable
Yes, of course (in classical mathematics), I wasn’t objecting to that.
The term ‘create’ or ‘identify’ is not important in this context. The argument is regarding existence of Cantor number.
Sorry, no. “create” versus “identify” is absolutely crucial.
The argument is based on the amount of time it takes to “produce” a digit of the so-called Cantor’s number. But the number doesn’t need to be created. For Cantor’s proof to be correct, it’s only necessary that a number that fits the description in the diagonalization exist.
We can’t actually create the so-called Cantor’s number, just like we can’t actually produce the table that it would be “created” from. But any supposed enumeration of the real numbers will be described by some kind of algorithm to produce the infinite table; similarly, given that algorithm for producing a table, we can produce an algorithm for producing the diagonalization’s counter-example to that table.
(As a quick side-comment: I really hate the term “Cantor’s number”, because it’s very misleading, in a way that leads directly to some of the common misunderstandings about Cantor’s proof. Cantor’s proof doesn’t specify a single number. Given a purported enumeration of the real numbers, it specifies a method of creating a number which is a counter-example to that specific enumeration.)
Sorry…I got the word “Cantor’s number” from your post. And I am well aware of infinite number of examples that can be ‘identified’ using diagonal argument.
The argument is not regarding whether one can create or identify counter example using diagonal argument. But there doesn’t exist any counter example ( hope you have checked and understood the proof).
You may believe that that’s what your argument says, but sadly, it isn’t. The entire argument is based on the premise that you can’t ever finish the process of figuring out what the number is.
But you don’t need to. It’s an inductive definition. You don’t like that, but that doesn’t make it wrong.
-> The entire argument is based on the premise that you can’t ever finish the process of figuring out what the number is.
The argument is based on the statement “you can never prove that the counter example is different from all the real numbers of the set used in bijection”
-> But you don’t need to. It’s an inductive definition. You don’t like that, but that doesn’t make it wrong.
The argument is valid for both inductive and constructive scenarios.
I would like to point out few irrelevant explanations you have given here.
1. The proof is regarding real numbers and there is no use of discussing difference between rational numbers and real numbers here.
2. I repeat the argument have nothing to do with representation of the number.
Hope you will come up with some valid argument to defend your side.
The whole point of Cantor’s proof is that the real numbers are fundamentally different from the other, simpler classes of numbers. Intuitively, we expect that the set of fractions should be larger than the set of irrational numbers. Cantor’s proof showed, among other things, that that intuition is wrong. The difference between the rationals and the irrationals is crucial: it’s exactly the difference that makes things interesting.
You can shout that the argument has nothing to do with the representation of the number, but if that’s your argument, you’re fighting a rather sad losing battle. Because, you see, Cantor’s proof is fundamentally tied to representation. It exploits a property of the way that we represent numbers to vastly simplify the argument. You can build up Cantor’s proof without relying on decimal representation -but to do that, you would need to create something that is, ultimately, another way of representing a number.
The key point, though, is that your argument (as I understand it) is based on the idea that the number specified by the diagonalization doesn’t exist, because doing the diagonalization takes an infinite amount of time.
If that is your argument, then it’s stupid and wrong, for exactly the reasons I discussed in my post.
If that’s *not* your argument, then go ahead and clarify.
->The key point, though, is that your argument (as I understand it) is based on the idea that the number specified by the diagonalization doesn’t exist, because doing the diagonalization takes an infinite amount of time.
My argument is “there doesn’t or cannot exist such a counter example (cantors magical number)”. It has nothing to do with time.
For your convenience I will use the concept of computation time in explaining my argument. For below explanation forget about countability and bijection between natural numbers and real numbers.
Let R be set of real numbers between 0 and 1. The numbers in the set is as shown below.
0.0000…
.
.
.
0.1111…
There exist infinite (all the real numbers between 0 and 1) in between 0.000… and 0.111… Think of above enumeration as a fraction of the number line (between 0 and 1).
Assume that there exist an infinite (or whatever be the size of set of real numbers) computing machine M.
So that M can enumerate all the real numbers in finite time.
Now use M to identify a number ‘S’ (in finite time) which is different from all the elements of the enumeration (as M can enumerate all the real numbers it should be able to do this work as well).
‘S’ will be different from all the real numbers of the enumeration. But we have considered all the real numbers between 0 and 1 (every point in number line between 0 and 1) and still we were able to identify a number S which is not in the enumeration.
My argument is that the number S cannot have any place in the number line or doesn’t belong to numbers under consideration (real numbers). That is such a number doesn’t exist (or it may not be a real number).
2 comments:
1. It seems that you first assume that the reals are
enumerable, and from that you derive the non-existence of Cantor’s number. You’re right that both cannot hold. But the whole idea of cantor’s proof is to refute your assumption.
2. You don’t need the “full existence” of Cantor’s number in order to refute that the reals are enumerable. For any list of Reals you build, you can look at the sequence of Cantor’s number prefixes. They can’t all be on your list – which is sufficient for refuting the enumerability of the Reals.
@Omer
My last comment has nothing to do with Cantor’s proof directly. I was just talking about set of real numbers. I wanted to make concept clear.
First enumerate the set of real numbers in some form. Now identify a number that is not in the enumeration.
Here one cannot conclude that enumeration was wrong. But the number identified doesn’t belong to the set of our interest.
If the concept is clear, you will get to know that same thing is happening with Canto’s proof.
But that’s the whole point – that the number doesn’t belong to your enumeration.
So, where do we stand?
You can either disallow infinite-length decimals, OR acknowledge non-enumerable sets.
If you define the set of Reals as an enumerable set of finite-representation decimal numbers, then you have a problem with geometric lengths such as $pi$ or $sqrt(2)$. Are they not Real Numbers? You can roll back the definition of the reals to what it was in Pythagorean times. (You’d have to deal with rationals such as 1/3 – but that’s solvable). But then you’re not talking about the Real Number System anymore. You’re talking only of the rationals. If you disallow infinite-length decimal numbers then you don’t have irrationals at all. This becomes a problem long before we get to talking about Cantor.
Another option – where most modern mathematicians stand – is to recognize that the Reals are not enumerable. The Real Number System is defined as the set of Dedekind cuts over the Rationals, or the set of limits of rational sequences (Cauchy’s definition). Then the Real numbers become very similar to a Power Set of the rationals – and we have the general Cantor’s proof that a power set is always bigger than the original set. There you build functions, not numbers.
At first glance, there might appear a strange middle-ground, though. Perhaps that’s where you’re going. You could add arbitrary rules to discard “unwanted” numbers whenever they pop out. so, if you have an enumeration, then you could decide to kick away that enumeration’s Cantor-number out of the system. But this won’t do. I can easily choose enumerations of the Reals in which the number 0.5 could be the unlucky Cantor’s number. So can any rational. You’d end up with an empty set of numbers, which isn’t very productive.
You could make the same argument about any number.
E.g. you can’t divide by three because it would take an infinite amount of time to write out all the digits after the decimal point.
There’s no Law Of Math that says you have to be able to write out all the digits in your lifetime.
Sure, if you’re talking about a professional mathematician, you’d expect them to be aware of Constructivism. If they launched into a constructive argument without saying that they were, given that its still not mainstream mathematics, one would be entitled to call them a bone-headed idiot. But is your correspondant a professional mathematician or an amateur one?
If he thinks that he’s qualified to overthrow Cantor, then he should damn well have done enough reading to know that.
By which time, he’ll be a professional mathematician… 🙂
Yeah, but if you’re smart enough and good enough at math to be able to finally disprove Cantor’s diagonalization, then you deserve a tenured position as a math professor at the university of your choice, along with a Fields medal!
True enough – it takes a certain amount of talent to find a weakness in an argument, and a great deal more, plus perseverance to turn make that critique constructive (pun intended!)
We have already done that, it’s called computing science. Nothing weasely about it, works perfectly well.
The problem is the fourth bullet point, “Suppose it takes time t…”
That’s a case of assuming his conclusion; there is no mathematical support for that assumption.
Which you more or less said, in explaining that we don’t have to actually produce the number.
Brouwer says we do, Vicki. His philosophical position was principled and heartfelt, although I have read that his work did not always embody those admirable finitary principles.
For my part I think that the question about the time an algorithm takes should be addressed more seriously by those mathematicians interested in fundamental questions. Is there a (mathematical) difference between Cantor’s completed infinity and a (Kronecker) succession of numbers generated by an algorithm for an indefinitely long period of time?
Unlike Mark CC I do not suppose that questions of this kind are just stupid. On the contrary, if a convincing formal distinction could be drawn between these two conceptions, the foundation of mathematics would certainly be improved – if not rescued.
I was surprised to read (further down the page) that Mark had even heard of Chaitin, given his own dogma that all numbers, however proposed, must somehow “exist”! What’s more, I don’t see why special notice must be given that one is pursuing a constructivist argument. Constructivism was never supposed to be just another branch of mathematics.
Do me a favor and don’t strawman me.
As I said in the post: it’s entirely legitimate to build an alternative mathematical framework. People can, and in fact have, done exactly that.
But if you claim to have found “the flaw” in Cantor’s proof, then you’d damn well better be working in the same framework as Cantor’s proof.
What makes the original emailer stupid isn’t that he’s thinks he’s disproving Cantor, by bringing up an objection that makes absolutely no sense in the realm of Cantor’s proof.
If you think that you can take a proof P, built in a system X using axiom set A, and then disprove it using system Y with axiom set B, then you’re an idiot.
Cantor’s diagonal argument is certainly a correct proof of the uncountability of R. Why do people dispute it? Anyway, even if it were false, it wouldn’t affect mathematics in the slightest, since there are other equally correct proofs (such as the proof based on the Baire category theorem).
There’s another, simpler, flaw in the argument above:
Cantor’s proof doesn’t need infinities at all. If “Cantor’s number” were in the table, one would get to the contradicting digit in finite time, no matter where it is.
To elaborate:
“Cantor’s number” is built upon a specific enumeration (e.g. table) of the reals. One then assumes it is computable. Hence it should be in some FINITE ROW k. But it can’t be in k. For every natural number ‘k’ it takes finite time to prove that number k in the table is not “Cantor’s number”. So… if you accept the law of excluded middle, then it follows that it’s not in the table at all. You don’t need infinities here. Just the law of excluded middle. And I very much doubt that our protagonist would have wished it gone.
As for the reason of the mail – it’s a sort of Platonism, I would guess.
My last comment has nothing to do with Cantor’s proof directly. I was just talking about set of real numbers. I wanted to make concept clear.
First enumerate the set of real numbers in some form. Now identify a number that is not in the enumeration.
Here one cannot conclude that enumeration was wrong. But the number identified doesn’t belong to the set of our interest.
If the concept is clear, you will get to know that same thing is happening with Canto’s proof.
@Omer
->But that’s the whole point – that the number doesn’t belong to your enumeration.
So, where do we stand?
->At first glance, there might appear a strange middle-ground, though. Perhaps that’s where you’re going. You could add arbitrary rules to discard “unwanted” numbers whenever they pop out. so, if you have an enumeration, then you could decide to kick away that enumeration’s Cantor-number out of the system. But this won’t do. I can easily choose enumerations of the Reals in which the number 0.5 could be the unlucky Cantor’s number. So can any rational. You’d end up with an empty set of numbers, which isn’t very productive.
It is not good to give the same reply. But I would like to make the concept more clear.
Consider the set of real numbers R between 0 and 1.First and last number of set R, 0.00000… and 0.111111…. are known respectively. Here all the real numbers between 0 and 1 is present in the set R. You are free to use functions instead of enumeration. By now try cantors diagonal argument.
Constructive method: By constructive method Cantors number N will be different from each real number by its nth digit. It goes on infinitly.And one wont be able to prove, it is different from the last real number. If one proves it, the number N wont be a real number between 0 and 1 as we have considered all real numbers between 0 and 1.
Inductive method: By Inductive method one could argue that the number N is different from all the real numbers in the set R. But as we have considered all the all real numbers between 0 and 1 in R, does N belongs to set R???
Yet we were able to *identify* or *generate* a number N of the form 0.n1n2n3… which is not in R. So where does N *belongs* to (in number system or number line), if it is a real number???
If you are using function f(N), what does it represent???
If above concept is clear we need to concluded.
1. Either N does not exist.
2. Or N is not a real number by definition.
I’m sure this has been said many times, but I do wonder why Cantor’s diagonal argument (which seems to puzzle people so much, despite its validity), is always the only mode of attack.
It’s obvious no countable set, in particular the rationals, can exhaust a real interval – simply place intervals of diminishing length around each rational, and use a sequence of lengths whose sum is less than the interval being covered; 1/5 + 1/25 + 1/125 +… is clearly less than than 1 if we are trying to cover [0,1].
I’m a long time Cantor crank. Haven’t been here since the old site. However, I will dispense with the usual and try to explain why some people have trouble with Cantor’s diagonal.
The simple reason is that they don’t believe in the square infinite matrix that Cantor uses for mapping the rows to a countable set. The usual response is that there are N digits and N rows and that’s that.
If you look at what Cantor is doing, he’s taking the N digits as his starting countable set. By using a diagonal, he ensures that each digit is mapped to a row again ensuring that a countable set of rows is used. So far so good. By flipping the digits on the diagonal he identifies a number/row not mapped by the digits. Now, mathematicians obviously assert this as proof that R is uncountable. But let us discard that possibility for a moment.
What else does Cantor’s diagonal tell us? It tells us that an “uncountable” set only requires a countable subset (of its rows) for its digit positions (N digits to represent R rows). If true, then would not a “small enough” subset of R that constitutes a countable set only require a subset of N for its digits at some point? What if all infinite set of rows only require a subset of said rows for the positions of its digits (when the list is in binary or higher base)?
Said another way, is it possible to have countable rows map one to one with its digits when listed in binary or higher base? If |R|=|N|, Cantor proved this is impossible. But without a distinct proof of this for N, we’re in circular logic land.
So in short, Cantor’s diagonal will only traverse a subset of any list given, even countable ones if |R|=|N|, but not so if |R|=/=|N| making this proof use circular logic. Many people don’t believe in the square matrix. Outside of the grid, you can map the digits one to one with the rows. But when the digits define the rows, no way.
Unfortunately, I’ve seen too many mathematicians handwave the problem away saying “subsets of N map to N, end of story” completely avoiding the fact that when one set defines another, you can’t just discard that definition (or my favourite, say that there is no mapping).
I spent the time deciphering this, so I figured I’d leave a reply no matter how late. Every natural number has a corresponding real number, so there’s at least as many real numbers as there are natural numbers. Thus, if |R| /= |N|, |R| > |N|, and thus R is not countable.
I don’t see the relevance of subsets of N, as R is a superset of N. I’m not sure how to interpret your question about subsets of N mapping to N; are you claiming there might exist a subset of N larger then it?
What’s really amusing is that those “Cantor freaks” are not even aware that Cantor didn’t use the diagonalization to prove that the set of real numbers is uncountable. He used the theorem about nested intervals (which, I belive, is due to Cauchy).
Yeah, and the same proof is still used today because it’s easier and more rigorous (check for example Jech’s “Set theory”)
This is really amazing. I feel like I understood your argument pretty well without understanding what it proves (I’m an engineer, not a mathematician, so that’s probably a tautology or something). The really cool part is I didn’t know there were math cranks!
It seems like no matter what the field or aspect of humanity, there are people who are considered illogical cranks. What I’m deducing from that is that if even in a field with such strict and well-defined rules for logic and evidence as mathematics there are still loonies, we will never be able to eliminate wrong-headedness from fuzzier topics. Medicine and paranormal phenomena spring to mind, of course.
Thanks for the rare glimpse into this social aspect of mathematics.