Poor Georg Cantor.
During his life, he suffered from dreadful depression. He was mocked by
his mathematical colleagues, who didn’t understand his work. And after his
death, he’s become the number one target of mathematical crackpots.
As I’ve mentioned before, I get a lot of messages either from or
about Cantor cranks. I could easily fill this blog with nothing but
Cantor-crankery. (In fact, I just created a new category for Cantor-crankery.) I generally try to ignore it, except for that rare once-in-a-while that there’s something novel.
A few days ago, via Twitter, a reader sent me a link to a new monstrosity
that was posted to arxiv, called Cantor vs Cantor. It’s novel and amusing. Still wrong,
of course, but wrong in an amusingly silly way. This one, at least, doesn’t quite
fall into the usual trap of ignoring Cantor while supposedly refuting him.
You see, 99 times out of 100, Cantor cranks claim to have
some construction that generates a perfect one-to-one mapping between the
natural numbers and the reals, and that therefore, Cantor must have been wrong.
But they never address Cantors proof. Cantors proof shows how, given any
purported mapping from the natural numbers to the real, you can construct at example
of a real number which isn’t in the map. By ignoring that, the cranks’ arguments
fail: Cantor’s method still generates a counterexample to their mappings. You
can’t defeat Cantor’s proof without actually addressing it.
Of course, note that I said that he didn’t quite fall for the
usual trap. Once you decompose his argument, it does end up with the same problem. But he at least tries to address it.
Enough preliminaries. Let’s dive in and see what he did. His abstract
gives about a coherent a description as anything else in the paper, so
we’ll start with that.
Cantor’s diagonal argument makes use of a hypothetical table
T containing all real numbers within the real interval (0,1). That table
can be easily redefined in order to ensure it contains at least all rational
numbers within (0,1). In these conditions, could the rows of T be reordered
so that the resulting diagonal and antidiagonal were rational numbers? In
that case not only the set of real numbers but also, and for the same reason,
the set of rational numbers would be nondenumerable. And then we would
have a contradiction since Cantor also proved the set of rational numbers is
denumerable. Should, therefore, Cantor’s diagonal argument be suspended
until it be proved the impossibility of such a reordering? Is that reordering
possible? This paper address both questions.
To understand this, let’s do a quick review of Cantor’s diagonalization.
Cantor is trying to prove that the set of real numbers is strictly larger than
the set of natural numbers. He uses proof by contradiction: he starts by
supposing that the naturals and the reals have the same size, then shows how
that inevitably leads to a contradiction.
If the set of real numbers is the same size as the set of natural numbers,
then there is a one-to-one mapping f from the natural numbers to the real
numbers in the range (0, 1). So he uses that to lay out a table, where the
first row is f(0), the second row is f(1), etc. In the table, the first column
is the first digit; the second column is the second digit, and so on.
If the mapping is really one-to-one, then every real number must be in the
table. But Cantor shows how you can easily create a new real number which is
not in the table. All you do is look at the digit in position (1,1)
in the grid – and change it. Then look at the digit in position (2,2), and
change that. Then the digit in (3,3). And so on: for row N in the table, you
change digit #n. What that procedure does is generate a number which is
different from every number in the table in at least one digit. Therefore it’s
not in the table. That’s a contradiction: we said that every real number had to
be in the table, but we’ve just constructed a real number which isn’t.
What our author is proposing is to take Cantor’s diagonalization,
and do two things to it.
First, he changes it so that it’s a mapping from the natural numbers
to the rationals instead of the natural numbers to the reals.
Then, he looks at the diagonal of the and re-arrange the rows of it.
He re-arranges the rows of the table until the number in the diagonal is
a rational. Now he’s got a table which contains all of the rationals, and whose
Cantor diagonal is a rational number. So it looks like he’s got a counter-example
for the idea that there’s a one-to-one map between the naturals and the
rationals. If that were the case, then Cantor would be in real trouble: Cantor
also wrote a well-known proof that there’s a one-to-one mapping between the
natural numbers and the rationals. So if our intrepid author is correct, then
either Cantor is wrong about there being no mapping between the
naturals and the reals; or he’s wrong about there being a mapping between the
naturals and the rationals; or his entire system of comparing the cardinality
of infinite sets is completely inconsistent.
Looked at naively, it seems sort of compelling: if we can build
a Cantor table that shows that the rationals aren’t countable, then
Cantor is wrong. So what’s wrong with this proof?
Reordering.
Remember: in this proof, we start with a standard Cantor diagonal over the
rationals. That is, we start with an enumeration of rationals, lay it out in a
table, and then read off a number which isn’t in the set of rational numbers.
In other words, we’ve used a Cantor table to produce an irrational number. At
this point, there’s nothing remotely compelling: we know that there
are irrational numbers, and all that the construction did at this level is
generate one. This is neither surprising nor particularly interesting, and
it’s certainly no threat to Cantor’s famous proof.
Once he’s got the construction of the irrational, he re-arranges
the rows of the table. He tries to re-arrange it so that the number that reads
down the diagonal of the table is a rational. This is exactly the problem: he
can’t do that.
Why not? Because the construction of the re-ordering is invalid. To
quote the paper:
If it were possible to reorder the rows of T in such a way that a rational antidiagonal
could be defined, then we would have two contradictory results: the set Q of
rational numbers would and would not be denumerable
That is, the re-ordering is absolutely critical to his argument. But
the re-ordering is, itself, self-contradictory.
The argument for the existence of the re-ordering is that
even irrational numbers generally have some probabilistic properties
about their digits. Using those, we can define an initial table
where its counter-example number has a desired set of properties
in the distribution of its digits. (You could use a variety of
properties – but, for example, if the distribution of digits is
uniform, then you could conceptually re-order the rows to produce
0.12345678901234567890…)
So far so good. Now, you re-order the rows, so that the diagonal is
a rational number.
Here’s the problem: you’re constructing a chosen rational
number. That is, you know what rational number you’re re-ordering the
rows to create. Since it’s a rational, it’s got to be in the table. And since
you know what rational it is, you’ve got to know what row in the table
it’s going to be. So go look at that row.
By the definition of the diagonalization, the value of the diagonal must
be different from the value of any of the rows by at least one digit. So the
rational number that you’re forming must be different from itself by
at least one digit.
Bzzt. No good. The re-ordered rational diagonalization is self-contradictory.
In fact, it’s a classic self-referential foulup.
This is an obvious problem, and it’s appalling that the author
of the paper, who is supposedly a math professor, couldn’t see it. For all
of the crazy rigamarole he goes through to construct his re-ordering, he never
bothers to look at this simple problem. What kind of mathematician could build
a construction like this and never consider the self-referential case?
I’ll give the author one thing: at least he actually addressed Cantor’s
proof. Most authors never bother to do that. Still, he doesn’t really appear to understand
the way that it works – else he’d have have noticed the self-reference problem.
Back at the beginning of the post, I said he almost avoids the usual problem of ignoring the diagonalization. The catch is that, as we’ve seen above,
he got it wrong, because he didn’t remember to consider the key
property of the diagonalization: that it’s different from every row in the
table. By trying to construct a diagonal that is equal to a row in the table,
he’s doing something self-contradictory. But he ignores that property – and then when
doing something self-contradictory results in a contradiction, he tries to claim that
it shows that one of history’s most profound and important mathematical results is
wrong.
Bozo.
This is not true. You keep saying it, and unfortunately sound like a crackpot yourself as a result.
If someone gives an alleged proof that all groups are commutative, you don’t have to do anything beyond give a counterexample to show that the proof is fallacious. Depending on circumstances, it might be nice to understand where the proof went wrong, but logically speaking, such a step is optional.
Read errata notices in the journals. Sometimes the author will thank someone for identifying the hole in the proof, but sometimes they will thank someone for giving a counterexample, at which point the author usually figures out his mistake. Both are legitimate. And yes, there are retractions based on counterexamples with no identification of what wrong in the original paper.
In the case of Cantor’s diagonal argument, giving a bijection between N and R would of course refute Cantor, end of discussion. The universal problem with the cranks’ proofs is simply that they do not give such bijections. We know ahead of time they don’t, because we understand Cantor’s proof. And because Cantor’s proof is constructive, we can even go one step further and see how it refutes their alleged bijection.
In fact, many if not most of the Cantor cranks do claim to identify Cantor’s alleged fallacy, contrary to your claim. But it’s always in terms of invented and undefined notions that somehow imply Cantor made a grievous error by writing down the proof in the first place, after which the technical details can’t possibly matter.
Bravo, Mark
You sure picked an interesting one to write about. When I first saw the title I thought it was going to be another ‘I’ve got a bijection’ crank.
@William e emba
In order to prove that one has a bijection from N to R, one must address Cantor’s proof showing how it is wrong.
Cantor’s proof says that if one has a bijection, then by the definition of bijection…
Re 1 & 2… A counterexample is a counterexample is a counterexample, even if you don’t understand “why”… is it not? Emba’s response seems quite sound. I was taught quite unequivocally in math theory class that all you need to destroy any proof, is to provide a real counterexample. As everyone here points out, most of the proposed “counterexamples” are simply not, in reality, counterexamples. It doesn’t matter if you take the extra step to explain why it is a counterexample… false is false!
@william e emba,
Even if you have a bijection between N and some set R for which you claim that it is countably infinite and contains all of R, someone can always come along and create a bijection from R to an R’ that will fail Cantor’s diagonalization. That is, even if you could prove that R is countable, there is always a way in ZF Set Theory to show that your proof is incorrect. And given that Set Theory is known to be consistent (and probably is), there isn’t much you can do about it. R could never be countable, even if it is.
Paul.
Correction to #3: “ALL of the proposed counterexamples are simply not,” of course!
It seems to me on reading the paper that construction of the ordering is not well defined – at the very least it looks like it needs countable choice (to pick one of the right rationals to exchange as you build the ordering) and an infinite construction process.
Also, it seems to break down in binary. With it construction the bits on the diagonal in his reordered list must be .10101010… and the only other number you can construct by changing the bits is .01010101. But there is nothing stopping us from making that number 2 in our original list. So there’s something wrong.
@1, 3:
The problem with Cantor crank counterexamples is that they aren’t counterexamples.
Cantor’s proof shows how, given any mapping of the naturals to the reals, you can produce a counterexample showing that it’s an incomplete map.
If you want to show that Cantor is wrong by producing an mapping of the naturals to the reals, you need to show just why Cantor’s diagonalization won’t provide a counterexample to your mapping.
In every case that I’ve seen of people claiming to produce perfect mappings of the naturals to the reals, they don’t do that. That is, they claim “Look! I’ve got a perfect mapping! Cantor is wrong!”; but if you apply the diagonalization procedure, you produce a counterexample showing that their mapping is wrong.
What Cantors proof does is show how to produce a counterexample of any mapping. You can’t refute that by showing a mapping, unless you can also show why the counter-example generated by the diagonalization doesn’t work for your mapping.
As I spelled out quite clearly, this is complete nonsense. It’s one thing to have a misconception, it’s quite another to maintain it when it’s explained why it is complete nonsense.
Here it is again, quite simple: in order to prove one has a bijection from N to R, one must prove the existence of a function whose domain is N, whose range is R, and which is 1-1 and onto. Nothing about Cantor necessary.
The crackpots who claim to have found such a bijection usually give a function whose range is not R, and they do not notice they have made a mistake, usually when asserting the range is all of R.
Tell me, would anyone in his right mind claim that in order to validate Cantor’s proof, one has to go down every single last crackpot and find the mistake in their proofs? Of course not. Why? Because Cantor’s proof is a sequence of logically valid steps that stand on their own, QED. All legitimate proofs are of that form. Not one of them needs to address the content of any other claimed proof whatsoever.
It’s good form, when giving a counterexample to an alleged proof, to identify where the alleged proof went wrong, but it is not required. It is certainly not an error to not do so.
In the case of Cantor diagonalization, it happens to be that understanding Cantor’s proof usually leads to almost instant understanding of where the crackpot went wrong, but that is a mere bonus. Claiming anything beyond bonus status is complete nonsense, and repeatedly claiming so is crackpot nonsense, highly embarrassing on this blog.
— But there is nothing stopping us from making that number 2 in our original list.
I think I got that wrong. It now looks to me like .010101… could not be in our original list at all, so the assumption that the list of rationals could be reordered must be wrong. Thus, his construction of the reordering would continue to push .010101… down further and further in the list of as-net-unordered rationals and could never actually put it in the ordered part.
Exactly.
You can refute it by giving a mapping. It’s just that the crackpots don’t do that.
This is a bonus. It is not logically required. A correct counterexample would suffice to reveal there must be some flaw in Cantor’s proof, and in particular, there wouldn’t be any worry that the proof when applied to the correct counterexample leads to a refutation of the counterexample.
And indeed, in various limited set theories, Cantor’s theorem is not true. These show up in certain topoi and in the fine structure of the constructible universe. A good exposition reveals just how diagonalization fails, but as always, good exposition is optional in mathematics.
Real numbers don’t exist except by fiat,like i.(Please don’t say that 1, etc are also real numbers.)
If they do, please show me an example(abbreviations not accepted).
Pure mathematicians just like completed infinite sets, the axiom of choice and the continuum (all the “holes” must be filled).
All that matters is accuracy compared with some standard.
Cantor was a very smart guy but where did it get him (or us)? Large cardinals? Duh…
Here it is again, quite simple: in order to prove one has a bijection from N to R, one must prove the existence of a function whose domain is N, whose range is R, and which is 1-1 and onto. Nothing about Cantor necessary.
No. Cantor’s theorem applies to any mapping from the naturals to the reals. If you have such a mapping that you think is complete, the diagonalization operates by constructing, based entirely on the mapping that you yourself have provided a real number that is not in your mapping. In short, the diagonalization attempts to disprove the completeness of your mapping by presenting a counterexample. If your mapping is indeed a bijection, then by logical necessity your proof must on some level address the counterexample. If you can’t show that the diagonalization *is* in fact in your mapping, then Cantor wins and your mapping is bogus. Hell, to paraphrase you:
If someone gives an alleged proof that there exists a bijection between the naturals and the reals, you don’t have to do anything beyond give a counterexample to show that the proof is fallacious.
And that’s exactly what the diagonalization does. It’s generality does not detract from this fact.
Yes, it does. SO WHAT??????
Sheesh, this is real simple. A counterexample is a counterexample is a counterexample. That’s it. When giving a counterexample, you are under zero logical obligation to explain why an alleged proof that your counterexample can’t possibly exist is in error.
In the case of the crackpot, he has not given a counterexample. That is his mistake. Had he understood how to apply Cantor’s theorem, he would have realized his mistake. But it is not a logical error on his part to not take that step. It is merely part of his overall incompetence.
He’s a high school science teacher as far as I can see.
This guy is even qualified to endorse others for arXiv … oh dear!
Sheesh, this is real simple. A counterexample is a counterexample is a counterexample. That’s it. When giving a counterexample, you are under zero logical obligation to explain why an alleged proof that your counterexample can’t possibly exist is in error.
Look. You propose that you’ve come up with a bijection from the naturals to the reals. You cannot simply assert this. You have to prove it. The only way to do that is to demonstrate conclusively that your mapping generates all possible real numbers.
The result of Cantor’s diagonalization is indisputably a real number. It is therefore, by definition, an element of the very set that your mapping must be able to completely enumerate. As a result, any proof that your mapping is a bijection *must* be capable of generating the diagonalization. It doesn’t have anything to do with Cantor per se. Even if he had never been born and the diagonalization had never been “discovered,” any alleged bijection between the naturals and the reals nevertheless *must* generate it at some point, or it isn’t actually a bijection from the naturals to the reals.
This is all that anyone means when they say that Cantor can’t simply be ignored: that an honest-to-dog bijection from the naturals to the reals must generate the diagonalization.
I think that the disagreement is coming from two different standards being applied to “need”.
No, they do not “need”, in the sense that not addressing Cantor’s proof creates an automatic logic error.
They “need” to address Cantor’s argument in the sense that a defense lawyer will need to provide an innocent explanation for how his client came to be covered with the victim’s blood no matter how solid his argument is that his client was two blocks away at the time of the victim’s death. Having no explanation for the blood should be a big flashing sign that there’s something wrong with the reasoning establishing the location of his client. Presenting such a case – besides probably being malpractice against his client – is a rather extreme insult to the judge and jury; at the very least, the lawyer should have the decency to admit up front to the blood problem.
Cantor’s diagonalization argument is right there sitting in the room and a cursory glance at it blows most Cantor cranks out of the water (and a longer look takes care of this one). Not even examining it at all is just downright rude to anyone who has to waste mental effort/time/blood pressure on what they’re spewing out.
They don’t need to address Cantor’s argument as a matter of logic but as a matter of common human decency.
@william e emba:
But if someone claims to have a counterexample to Cantor’s theorem, isn’t the burden of proof on them to show that it is, in fact, a counterexample? If so, how can they show that a mapping is a real counterexample to Cantor, without showing how Cantor’s theorem fails for that mapping?
Reordering of infinite tables or series is generally a bad idea. You can construct all sorts of nonsense with this. Take the question what is the limit of the infinite series +1, -1, +1, -1… (it clearly doesn’t converge). Let’s just shift all the -1 to the end and then the limit is + infinity. You probably know better than I but I believe there’s a theorem telling you what sort of rearrangement is okay (depends on the convergence properties of the series or so.)
Daniel,
I disagree. You must address Cantor. Forget about the diagonalization for a second and think of it this way:
If you claim to have a bijection from the naturals to the reals, anyone who wants to is allowed to come up to you and test your mapping.
So if I stroll up and say, “Oh yeah? Well, show me the mapping for .04534563,” you have to be able to pull out the natural number that maps to it, plug it into your function, and have .04534563 pop out. And you have to be able to repeat the process for any arbitrary real number I throw at you. It’s not just a matter of courtesy. It isn’t negotiable. If you can’t do it, it’s back to the drawing board. Math is a jerk like that.
In this context, Cantor’s diagonalization is just another real number that your mapping is expected to cope with; just another test. Cantor’s corresponding claim that it’s impossible for your mapping to include the diagonalization is actually totally irrelevant. Whether he’s right about that or not, any bijection from the naturals to the reals still *must* include the diagonalization.
Exactly.
Which is what they haven’t done. Which, therefore, is their mistake. Period. End of discussion.
Like I said, this is real simple.
Now, an understanding of Cantor’s theorem happens to reveal the explicit step they failed to do. SO WHAT????? In fact, their proofs are usually so pathetic that a cursory inspection reveals their N->R isn’t onto. You know, something like they’ve got all finite decimals in the range of their alleged bijection, or some such joke.
If my professional colleague sends me a 200 page proof of the Riemann Hypothesis for inspection, and I notice his really complicated lemma with a proof on pages 25-50 happens to imply there are only finitely many primes, I will tell him that. Depending on circumstances, I may or may not figure out why his proof is wrong. He may or may not figure it out. But we both know it’s wrong, whether or not we’ve identified his mistake.
It’s the same with Cantor crackpots. There is the added twist here that Cantor’s proof is so constructive that it will normally reveal quite explicitly one aspect of why the crackpot is mistaken. That is merely bonus.
You’re all missing a major point: We don’t know that the background theory is consistent. Our assumptions about set existence have been faulty before.
Consider the following question: Is there a largest possible set? Cantor said “no”: for every set S, the set P(S) of subsets of S is larger. There is a 1–1 function S → P(S), which sends x ∈ S to {x}; but there is no onto function S → P(S) by a version of diagonalization. So P(S) is strictly larger than S.
But Bertrand Russell said “yes”: just take V to be the set of all mathematical objects, including all sets. Every set is a subset of V, therefore no bigger than V.
Both Cantor and Russell were correct, given their background assumptions. It’s just that those assumptions, taken together, were not consistent. Indeed, it was by applying Cantor’s argument to V that Russell constructed his paradox. History has sided with Cantor’s intuitions more than Russell’s, but there are formalizations of both (ZF and NF, respectively).
Back to the present argument. Cantor’s diagonal argument, proving that there is no onto function N → R and no onto function S → P(S) for any set S, is correct. It’s easy to check, and probably machine-verifiable at this point.
That does not automatically mean that one of these cranks has an incorrect argument. It is possible — vanishingly unlikely, but possible — that one of the arguments is correct, and exposes a contradiction in our collective intuition about sets and in formalizations such as ZF (or whatever the crank needs to make his argument work). Strictly speaking, each argument must be addressed on its own merits (as Mark has admirably done here and before).
Think of it this way: if we dismiss their arguments simply because they conflict with ours, can’t they dismiss our arguments on the same principle?
@Chad Groft
I don’t remember my history all that well, but I believe that Russell was in fact showing that there is no ‘set of all sets’, by contradiction in assuming there is one. This is the famous ‘Russel’s Paradox’, which is based upon the Epimenides Paradox: “This sentence is false.”
Here’s an example: Captain Bozo claims that his map 1->.1, 2->.02, 3->.003, 4->.0004, etc. refutes Cantor. His mistake is that he has not given an onto map N->R. You point out he has missed .2, .3, etc. So he comes back with 1->.1, 2->.2, …, 9->.9, 10-> .02, 11->.003, 12->.0004, etc. Now you point out he has missed .01, .03, .04, etc. So he comes with another miss in the next decimal column, which you point out, so now he comes back with saying he’ll iterate infinitely this process, ie, 1-9 to .1 to .9, 10-18 to .01 to .09, 19-27 to .001 to .009, etc.
It’s entirely possible to point out his errors by eyeballing an obviously missing real. There is absolutely no need to invoke diagonalization. Captain Bozo’s failure was his inaccurate claim. Period.
In all cases, Captain Bozo has simply not given a bijection N->R. That is his error. If he understood Cantor, he’d realize it was a hopeless cause, but that is a different issue.
#11:
> Real numbers don’t exist except by fiat,like i.(Please don’t say that 1, etc are also real numbers.)
> If they do, please show me an example(abbreviations not accepted).
“It doesn’t exist if I can’t touch it”?
Do you acknowledge that there exists a number that, when squared, produces 2? I’m assuming not.
Calculus is useless to you, you’ll need something “better” than epsilon-delta proofs for limits and continuity. (http://www.math.tamu.edu/~tvogel/gallery/node6.html)
Everything in math comes from definition. There are obviously good definitions, obviously bad ones, and some that are debated. Completely throwing out all irrational numbers eliminates many algebraic numbers (there goes a lot of abstract algebra) as well as fundamental constants such as e and pi. Arguing that those constants exist only to an approximation is just stupid, as we can make that approximation arbitrarily precise.
#21:
> Now, an understanding of Cantor’s theorem happens to reveal the explicit step they failed to do. SO WHAT?????
You’re missing the point. Cantor proved a theorem and then provided a counter-example any possible counter-example. Think of it this way: Theorem A (no bijection between N and R) has been asserted. Construction B (a bijection between N and R) contradicts A. Theorem C (a counter-example to construction B) says that B cannot exist.
The real argument in attacking Cantor’s work is not over attacking theorem A, but over attacking theorem C. Any work B that attacks theorem A is over-ruled by the stronger result of theorem C. The specific case of the set size inequality is a weaker result of a stronger theorem.
Simply put: Cantor’s big result was NOT “there is no bijection”, it was “here’s why your bijection is wrong”; “there is no bijection” was just a fascinating corollary. If you come up with a bijection, no one is interested in why it contradicts the corollary, they’re interested in how it contradicts the stronger theorem that denies said construction existence.
In looser terms, you must provide a counter-example to his counter-example of your potential counter-example. That is the real battleground. You can’t get hung up on on providing a bijection. Cantor showed there is no bijection ONLY because we hold the key to a counter-example to any bijection.
Counter-example to a bijection => there is no bijection. A=>B. Attack A, not B.
You wrote
“99 times out of 100, Cantor cranks claim ….”
Maybe it would have been more appropriate to say
” 0.99999… times out of 1″
jw
Think of it this way: if we dismiss their arguments simply because they conflict with ours, can’t they dismiss our arguments on the same principle?
Yes, but only to a point. The takeaway from Cantor’s theorem – that infinite sets can have different cardinalities – certainly cannot be asserted as a priori truth and thus grounds for the dismissal of conflicting claims. That the diagonalization itself is a real number and therefore must be enumerable by any N->R bijection, however, simply isn’t contestable under any reasonable system of evaluation.
This whole thread has been a long (and probably unfortunate) semantical argument about what precisely it means to “address Cantor’s proof.” William holds that it isn’t necessary to even understand, much less address, Cantor’s theorem in order to construct a N->R bijection (provided such a construction is possible, of course), and that that therefore Mark’s requirement that such a bijection address Cantor is bogus.
My whole thing is that William’s point falls squarely into the “distinction without difference” category. A N->R bijection will contain the diagonalization and thus refute Cantor regardless of whether the person who comes up with the mapping takes the time to point it out. It “addresses” Cantor just by containing the thing that Cantor claimed it can’t contain.
The other issue is this: to disprove Cantor’s theorem, really, is not even to come up with a bijection but to show that the diagonalization can be constructed using some fundamentally different means than what Cantor provided. That’s what our crank here tried to do (show the diagonalization can be a rational number. The rationals are directly enumerable, ergo the diagonalization can be built that way instead of using Cantor’s table, etc.). If you’re explicitly trying to show that Cantor’s diagonalization can be built in a way that makes it directly enumerable, you do have to make sure the alternate diagonalization you come up with has all of the properties that Cantor defined a diagonalization to have.
#22:
No and no. Russell’s paradox was that there is no set B = {x : x ∉ x} of all sets which are not elements of themselves, even though the definition looks legitimate. (If B exists, then B ∈ B iff B ∉ B, contradiction.)
Now: how did we build B in the first place? First we collected up all the sets in the mathematical universe, then we filtered out all the sets which were self-containing. One of those steps must have been invalid. Either there is no universal set V, or it is not valid to use formulae like “x ∉ x” to create sets.
In modern math, we take the first position; a set is a collection of objects that can somehow be “captured”, and by capturing that collection, we have created a new object. In fact, it is a consequence of the full axiom system ZF that no set contains itself as an element.
Russell instead took the position, later formalized by Quine in the New Foundations axioms, that the formulae leading to sets were precisely those which could be “ramified”: each variable x can be assigned a natural number t(x) so that, if “x = y” appears, then t(x) = t(y), and if “x ∈ y” appears, then t(y) = t(x) + 1. Now “x ∉ x” cannot be ramified, because t(x) ≠ t(x) + 1 for any value of t(x). The formulae “x = x” and “x ≠ x”, on the other hand, are easily ramified, and the corresponding sets are V and ∅ respectively.
NF never really caught hold, as it has a lot of ugly consequences. It’s not possible to show that NF is consistent, even if we assume that ZF is, so that’s unattractive. We can’t build a lot of the types of sets we want to build: there’s no way to construct, say, a sequence of sets of natural numbers. Also it’s possible to disprove the Axiom of Choice from the NF axioms, and that just was not happening.
#27: That’s a fair point. At least Russell had the sense to apply diagonalization to his counterexample and specify the exact contradiction. The fact that cranks don’t do that is what makes them cranks, and what makes me unlikely to take them seriously.
All I’m saying is, that’s a reasonable heuristic, not mathematical proof.
To #11:
We, speaking as a mathematician (though only grad student), do not assume the existence real numbers because they are nice. In face we have constructed them using Dedekind Cuts (and at least one other way) and not only does the construction provide a completion of the rational numbers but obeys all operations that are used. Now I’ll admit if for some reason if we were not able to construct the real numbers we would probably assume they existed. And I’d bet it would be a strange world where we couldn’t construct them or even more generally the completion of any set (provided the operations aren’t strange).
Now to emba and your statement about counter examples.
Cantor says this: if you give me any enumeration of the reals, which you call a counter example to Cantor’s proof, my proof breaks your enumeration by constructing a real that isn’t in it. It doesn’t matter what you call your enumeration Cantor’s proof gives a number that isn’t in there. So any possible “counterexample”, enumeration, MUST address cantor’s proof.
Not only that but so many people seem to get hung up Cantor’s argument not realizing that there are other proofs the reals are uncountable that look nothing like Cantor’s argument (an easy corollary to the Baire Category Theorem provides a good one) so if you do manage to break Cantor’s proof all your proof will do is suggest is that for some deep reason Cantor was wrong. Which may or may not go all the way down to ZF, neither of the proofs mentioned or the construction of the reals need the axiom of choice.
Last week and yesterday I attended a 3-hour 2-part lecture on Borel matchings by Alexander Sotirios (Alekos) Kechris (born 1946), a descriptive set theorist at Caltech. He has made major contributions to the theory of Borel equivalence relations.
Kechris earned his Ph.D. in 1972 under the direction of Yiannis N. Moschovakis, with a dissertation entitled Projective Ordinals and Countable Analytic Sets.
He reviewed some 1957 nice graph theory proofs, then generalized to infinite graphs, where intuition is easily wrong. To be careful, he restricted the proofs to locally infinite graphs, with a finite number of edges meeting at any vertex. He was general enough that the graph could be uncountably infinite.
I phased in and out of really understanding his proofs, as I took notes, partly because of a habit of his of trailing off into inaudibility in sentences, as he out-thought his vocal output buffer.
The grad students and post-docs there were way ahead of me.
On the other, I had an intuition of another way to generalize this, with locally finite hypergraphs, and we exchanged emails about that.
Point is, at the end of the 2nd lecture, he showed published alleged counterexamples and alleged counter-counterexamples. The literature is very unclear. Intuition is a poor tool for wrestling with infinities, even in those who do it for a living.
Great thread again, Mark!
William’s point might be practically irrelevant for Cantor cranks, but he’s right that Mark ought to be more careful here.
If, tomorrow, I find three positive integers a, b, and c such that a^5 + b^5 = c^5, then Wiles’ work on Fermat’s Last Theorem is flawed. I don’t understand his work, but that doesn’t matter, because I’ve found a counterexample.
As I read it, many posters are objecting that Cantor has already shown that there are no counterexamples. That’s true, but Mark went further: “You can’t defeat Cantor’s proof without actually addressing it,” and in the comments, “If you want to show that Cantor is wrong by producing an mapping of the naturals to the reals, you need to show just why Cantor’s diagonalization won’t provide a counterexample to your mapping.” If I had a genuine counterexample, then this would be nonsense, just as it would be nonsense to insist that I understand modular forms to propose a counterexample to Wiles’ theorem.
“If I had a genuine counterexample” to Cantor’s diagonalization proof has the same logical value as “If I had a triangle with four edges.”
I had no idea there was such a thing as Cantor Cranks out there. That makes my day.
I guess all the angle trisectors and square doublers have moved on to other things, huh? Or are they still around, too?
#32
> That’s true, but Mark went further: “You can’t defeat Cantor’s proof without actually addressing it,” and in the comments, “If you want to show that Cantor is wrong by producing an mapping of the naturals to the reals, you need to show just why Cantor’s diagonalization won’t provide a counterexample to your mapping.” If I had a genuine counterexample, then this would be nonsense, just as it would be nonsense to insist that I understand modular forms to propose a counterexample to Wiles’ theorem.
Sigh. Technically, yes, but only technically.
A bijection would indeed disprove Cantor’s related work. However, if you had such a bijection, you would also be able to disprove his counter-example-based proof.
Read my above post, #25. The main battleground here is not “there is no bijection”, it’s the *stronger* theorem that “your bijection is wrong”.
Exemplifying a bijection would indeed solve the problem, but ONLY because it ALSO would have to contradict his stronger theorem that constructed a counter-example to any bijection. That, right there, is the key.
#33
> “If I had a genuine counterexample” to Cantor’s diagonalization proof has the same logical value as “If I had a triangle with four edges.”
Not really. A triangle is a definition. Cantor’s result is a proof. Logical constructions are not equivalent to definitions. A definition is never “wrong”, logical constructions are human-made and can be flawed. It’s more like saying “if pi were an algebraic number”.
I don’t think that’s it. I think the author thinks that even if you perform an infinite number of exchanges, each row still has to end up somewhere in the table, even if it’s after an infinite number of predecessors. (I’m not sure how else to interpret paragraph 2-14.)
It took me some thinking to see what MarkCC was getting at by showing that a particular rational must never appear in the table.
The rearranged table “works” just fine. The author’s proof that for any n, the first n rows satisfy the constraint, is just fine. And indeed the table constructed by that algorithm has the diagonal he wants.
The problem is the assumption that if you continually (infinitely many times) swap two elements of an infinite list, you still have all the elements of the original list.
The exact same algorithm could be used on the set of counting numbers to prove that they “aren’t countable”: for instance, use the permutation to bring up n+1 into the nth spot. Now we have a rearranged list of counting numbers with no 1 in it!
I haven’t thought about infinite permutations before so this result seems pretty counterintuitive to me still. The composition of infinitely many pairwise swaps isn’t a permutation any more?
>”As I read it, many posters are objecting that Cantor has already shown that there are no counterexamples. That’s true, but Mark went further: ‘You can’t defeat Cantor’s proof without actually addressing it,'”
Mark is right on this one.
B-Con in 35 says it nicely. Cantor’s Proof is more than just “there is no bijective mapping.” Cantor showed that there are diagonalization elements with any mapping, which is different from stating that there is no bijective mapping.
William e emba is saying that a proof of a bijection does not need to address Cantor to disprove Cantor; it only needs to be a proof of a bijection. But a proof of a bijection would inherently contain a disproof of Cantor because the mapping must define elements to the diagonalizations.
If we were to read a proof of a bijection between the naturals and the reals it would be very clear exactly how Cantor was wrong. Every element of the reals, including our diagonals, would have an element from the naturals being mapped to it. It’s preposterous but that is what the proof must show.
@35
Hmm. What about “Let S be the set of all sets which do not contain themselves”?
Emba’s quibble is pretty silly, if you ask me. It all depends on the relative complexity of the proof vis-à-vis its putative counterexamples.
For Cantor’s diagonalization, we say, “Ah! This proof is so fucking simple to understand that whenever someone says they have a counterexample we can just point and laugh at them.”
For Fermat’s Last Theorem, we say, “Oh, you have a counterexample? Well, no one understands Wiles’ proof, but here, let me just plug in your numbers real quick… hmm… you got this off that Simpsons episode, didn’t you.”
Does there exist complexity sufficient enough for a proof to not show what elements map to diagonalizations?
#39:
> Hmm. What about “Let S be the set of all sets which do not contain themselves”?
A nonexistent set. Or a “bad” definition. But “wrong” usually implies an incorrect application of logic. At least, that’s my understanding of the common vocabulary.
Two sides in this thread are quibbling over semantics, which is annoying. William Emba is right that the Cantor cranks not providing counterexamples is the problem, Mark is right that not addressing the diagonalization is the problem. To show that your counterexample is valid, you’d either have to show that it survives the diagonalization or that the premises of the diagonalization are faulty.
jefu: For what it’s worth, Cantor’s argument doesn’t work in binary anyway without a lot of care, because the numeral that you could construct may end in a recurring 1, which has a similar problem to recurring 9’s in decimal. Cantor’s argument in decimal, when posed carefully, avoids recurring 9’s.
Two sides in this thread are quibbling over semantics, which is annoying.
This sentence just made my night.
Of course they’re quibbling over semantics – they’re mathematicians. We are talking about a group of people who created their own language with very strict semantics just so they’d all be certain of what the arguments are all about after all.
@11:
hbar.
Hmm. What about “Let S be the set of all sets which do not contain themselves”?
A nonexistent set. Or a “bad” definition. But “wrong” usually implies an incorrect application of logic. At least, that’s my understanding of the common vocabulary.
Posted by: B-Con Author Profile Page | January 30, 2010 3:31 PM
Wrong! In naive set theory a perfectly good and totally valid definition. In fact to stop it being valid one has to add additional conditions to the axiom system that are 1) ugly and 2) counter intuitive.
I believe you are all crackpots because you believe in Cantor’s diagonal. Heck, I don’t want to give you a list of all reals. I’ll settle for a list where you can give more than a single 1 digit on any row. Put a 1 digit along the diagonal (and 0’s everywhere else) and that’s all the numbers you can create according to Cantor’s argument. These are all rational numbers, but there are other rationals than that (like zero). And yet, I’m limited by what I can provide.
Cantor uses ONE SPECIFIC MAPPING. This is the flaw in Cantor’s argument. No matter what list I give you, you will intentionally never use it all. And no matter how much you repeat that it’s not one specific mapping doesn’t make it so. I repeat, Cantor uses ONE SPECIFIC MAPPING and it’s not one to one. He limits the list to be equivalent to base 1 (where only one digit can be different from the rest). Allow the full range of base 2 (ie. stop mapping by digits in different bases and start mapping by element or at least use the same base) and you’ll see Cantor’s diagonal argument fall apart.
BTW, i->i/|N|
@47
B-Con was not writing about naive set theory, rather, more likely, Zermelo–Fraenkel set theory, which I find neither ugly nor counter intuitive.
@Vorlath
1. You don’t understand quantifiers: ‘one, specific mapping vs. any mapping.’
2. You make completely false statements with no proof or explanation: “Put a 1 digit along the diagonal (and 0’s everywhere else) and that’s all the numbers you can create according to Cantor’s argument.”
3. You don’t bother to define the non-canonical words you use: “…base 1 (where only one digit can be different from the rest). Allow the full range of base 2 (ie. stop mapping by digits in different bases and start mapping by element or at least use the same base)…”
Vorlath, you exemplify everything mark describes in a crank.
What that procedure does is generate a number which is different from every number in the table in at least one digit. Therefore it’s not in the table.
False. 0.100000… and 0.099999… differ in at least one digit, but they represent the same real number. What you have proven is that there is some base-10 representation that is not in the table, but that is not the same as proving there is some number not in the table.
This flaw is correctable, of course — I am no “Cantor Crank”. But your summary of Cantor’s argument is simply wrong.
@49 (Mike):
1. It is you that do not understand what Cantor is doing. Cantor is using ONE SPECIFIC MAPPING! That’s the flaw. No matter what list someone gives you, you don’t use the whole list.
2. My statement is not false. It’s my list. If Cantor can retrieve a diagonal, then I can set it to all 1’s with 0’s everywhere else. There is nothing wrong with that list. All the rows represent naturals. However, the entire grid is full leaving no room for numbers with any other format. This is true for the same reason that the diagonal in Cantor’s argument is different than any other number. If you disagree with what I’ve said here, then Cantor’s argument is trivially flawed.
3. You say I don’t define the terms I use, yet you quote my explaining it in parentheses. Base 1 is where only 1 digit can be different from the others or where all the digits before a certain point are different from all the digits afterwards. Other bases are where you can have more than one symbol per digit.
Seriously, you are a nutjob. BTW, I’m laughing my head off at your comment. You exemplify what crackpottery is all about. I commend your lack of logic.
However, if you believe you are not a nutjob, please answer how come it’s impossible to list all the rationals in Cantor’s grid.
Correction: In 2. It should be
All the rows represent rationals.
Vorlath, if you give a mapping from naturals to reals where each number only has a single 1 and everything else is 0s, then that mapping is trivially incomplete (it misses, eg, .11), and Cantor’s diagonal produces a number that is in fact not on that list: 0, or 0.2~, depending on the precise format of Cantor’s argument you use.
That number, being not on the list, proves that the list is not a list of all real numbers, which is exactly what Cantor’s argument claims.
If you provide some list that you claim contains all real numbers and produces a Cantor diagonal of .1~, then you are simply wrong – your list cannot contain .1~ or else Cantor’s diagonal would have a 0 (or a 2, or anything other than a 1, it doesn’t matter!) at whatever position of your list is .1~, which is a contradiction to your claim.
btw it is not at all impossible to list all rationals, but Cantor’s argument doesn’t say it is, either. Cantor’s argument requires infinite non-repeating decimals – which the reals have but the rationals, by definition, do not.
@Vorlath
Once again I stress quantifiers, proofs and definitions.
It is possible to use a specific bijective function in a proof *without loss of generality* to represent all bijective functions so long as nothing is added to its definition beyond ‘bijective function.’
“…If Cantor can retrieve a diagonal, then I can set it to all 1’s with 0’s everywhere else…”
How does Cantor ‘retrieve’ a diagonal? How can you ‘set’ ‘it’? What does that logically imply and why would it be true? You spin me around in circles with sentences like these.
Then you end that same paragraph with this, “If you disagree with what I’ve said here, then Cantor’s argument is trivially flawed.”
I don’t know what that means but it certainly begs for some explanation.
“You say I don’t define the terms I use, yet you quote my explaining it in parentheses.”
So what is the “full range of base 2”? “mapping by digits”? “mapping by element”? Are you talking about strings, numbers, fingers,…? Call me ignorant but I have no idea what you are talking about.
Sure, I may be an illogical nutjob. But if your writing is beyond scrutiny because no one can understand it then you haven’t proven anything.
I don’t care about the list of all reals yet. Don’t you get it? I’ve only BEGUN to create my list by starting with a subset of the rationals. But so far, I’ve only given you a portion of them. The fact that 0.11 is not in the list is fatal against Cantor. The diagonal being all 1’s is only a portion of my full list of rationals. I know for a fact that |Q|=|N|, but Cantor’s grid says no as I’ve demonstrated and you’ve agreed.
QED.
@54 (mike):
This is from Mark’s article.
Do you understand that? Ok, so imagine the PARTIAL list I’m giving you has 1’s in those positions and 0’s everywhere else.
Do you get it now? I’ve given you only a PORTION of the rationals, but there’s no room left for the other numbers that I KNOW for a fact map one to one with the naturals.
No! You have it exactly backwards! 0.11 is not in your list, so your list is not a list of all the rationals OR all the reals. So when Cantor’s diagonalization algorithm finds a number that is not in your list, all that shows is that your incomplete list is incomplete, which is not a problem!
Meanwhile, if you list all rationals – for which there are many methods – Cantor’s algorithm will produce an irrational number, which is in fact not rational and also not on the list.
The list is infinitely long, and so is Cantor’s generated number. Therefore there is no such thing as “no room left” as you can always extend it.
You don’t understand the consequence of this. I WANT TO INCLUDE 0.11 IN THE LIST BUT CANTOR’S GRID WON’T ALLOW IT!!!
GET IT? I want to give you 0.11, but it can’t possibly fit in the grid. That’s a fatal flaw in Cantor’s diagonal argument.
Geez.
No. This is just absurd. This contradicts the very reasoning behind Cantor’s diagonal. It even defies the principle of mapping one to one. Heck, you’re saying that different infinities can’t exist. That’d be the end of the story right there.
The digits of the grid map one to one with the naturals. So by having a 1 at the diagonal, I am in effect mapping each digit to each row one to one. This mapping is in fact what makes the diagonal argument possible in the first place.
But I have more rationals. For example, the number 0. To map this new row to a digit, I need to find a digit that has never been set in any prior row. But there aren’t any. There is always exactly one previous row that has that digit set regardless which digit I choose.
So this proves that Cantor’s grid can never use the entire list I give you. EVEN IF THEY ONLY CONTAIN RATIONALS!!!
QED.
Uh, no, Vorlath, you need to define your list in a systematic fashion. Some definitions – such as the one you gave – provide a proper subset of the rationals, so automatically leave out rationals.
Here is a list that does not leave out any rationals:
The first thing we put on the list is 0.
After that, we have a rather long procedure:
First, define a square grid of infinite extent in both X and Y.
Second, for each entry in the grid (as needed – you don’t have to fill out the “whole thing” ever), record the rational of the X position over the Y position, with the starting point being 1/1. There will be repeated rationals, this is fine.
Third, trace a path through the grid, starting at 1/1, then going to 2/1, then go diagonally down to 1/2, then go down to 1/3, then diagonally up to 2/2, then diagonally up to 3/1, etc. This is an infinite path, obviously, and covers every rational. (I can expand upon this if you so desire – do you so desire, or do you follow my description?)
Fourth, for each entry on the path in order, convert it to an (infinitely repeating) decimal, then check to see if that entry has been added to the list thus far. If not, add it to the list. If so, do nothing.
This list will contain all rationals once and only once, and as each rational has a position on the list, it is also a one to one mapping between the rationals and the natural numbers. Do you agree or disagree? (PS: Negatives can be handled too if you so desire – simply add the negative version of a number right after the number.)
Now, if you apply Cantor’s diagonalization to the above mapping, the number produced clearly cannot be on the list. I agree with this, but this is not a problem, because the number produced will be an irrational number.
Therefore, this mapping between natural numbers and the rationals is not a one to one mapping between the natural numbers and the reals, because there is a real for which there can be no natural number.
PS: Vorlath, I have no idea why you think Cantor’s grid won’t allow you to put .11 onto the list. Literally no idea whatsoever. If you define a list that contains .11 at a specific place – which is required for your list to even potentially be a one to one mapping between the natural numbers and anything – then Cantor’s method will generate a number that differs from .11 in that specific digit. If that place is 1 or 2, then Cantor’s method will generate a number whose first or second decimal digit (respectively) is not a one – and if that place is 3 or higher, Cantor’s method will generate a number whose appropriate decimal digit is not a zero.
So why do you think you can’t put .11 into the list? Cantor’s method only requires that each number appear in a specific location – it doesn’t even require that location to be unique!
@60:
You haven’t proved that you can put all the entries in your list into Cantor’s grid. My counterproof shows how it’s not possible. So your objection is irrelevant since I actually use the fact that |Q|=|N| in my couterproof.
I’ve explained it. In order to build the diagonal, each digit must be mapped to a row. The point of the diagonal is that the digits are countable, but the rows in the full list of reals are not (ie. the new number provided via the diagonal).
I’ve pointed out that rows that have a single 1 digit in it will map to all digits leaving no unmapped digit. So you cannot add any more entries without going over |N| if we follow Cantor’s logic. It’s the same principle behind the diagonal process in Cantor’s argument. So you cannot disagree with what I’ve said without also disagreeing with Cantor’s diagonal.
But if we go over |N|, then |Q|>|N| and we know that’s not true. Contradiction.
QED
@60:
So you’re saying the diagonal process only considers a proper subset??? Gee, thanks for making my point for me.
Let me restate Cantor’s result in constructive form.
Let f be a function from N to R+. Then there exists ‘x’ in R+, such that f(i) /= x for all i in N.
Proof:
Let d_i_j be the j-th digit after the decimal point in f(i).
Define x so that the j-th digit after the decimal point is:
– 7 if d_j_j = 5
(The 3/7 construction avoids problems with numbers with two different expansions.)
x is not equal to f(i) for any i; they have incompatible digits at the i-th spot after the decimal point.
QED.
@64:
You still haven’t addressed the issue with Cantor’s diagonal. Do you agree that there are strings that only have a single digit set to 1? If so, then there will be one of these strings for each digit. In order for me to add a new string to my list, I must also find a digit that hasn’t yet been set to 1 so that it may be included in Cantor’s diagonal so that you can say they have an incompatible digit at the i-th spot after the decimal. But there’s aren’t any digits that don’t already have a row associated with it.
QED.
The problem with your proof is that d_j_j doesn’t reach all rows.
This was the most entertaining read I’ve had all week, and I’ve been reading political blogs.
Chad won the thread in the middle: “You’re all missing a major point: We don’t know that the background theory is consistent. Our assumptions about set existence have been faulty before.”
Quibbling aside, in the Emba vs. Mark part of the thread, Chad’s right. IF ZFC is consistent, then any counterexample of Cantor *will* address Cantor. If ZFC isn’t consistent, then it won’t necessarily have to do so.
So if you have what *you think* is a disproof of Cantor by counterexample, you really ought not to start crowing that you disproved Cantor, that’s a trivial result. *My* first step (well, after I spent probably a decade trying to figure out what I did wrong, because I would be absolutely convinced that I was wrong for quite a while) would be to start crowing that I’d broken ZFC set theory by showing that it is inconsistent, which would be a much bigger claim.
Ah hah! I’ve got it!
So, I think we’d all agree that there are countless Cantor cranks out there, and that there is no bounds to the kinds of bizarre proofs they will concoct.
I propose, therefore, to assign each Cantor crank a natural number designation in the historical order in which they appeared, i.e. the first person post-Cantor to offer a supposed mapping between the naturals and the reals which disproves Cantor would be assigned “1”, the next person “2”, and so on.
For each Cantor crank, apply Cantor’s proof to their purported mapping, thus generating a real which is not part of said Crank’s mapping. This provides us with a mapping from all natural numbers to some subset of reals.
As a premise, we agreed that there were countless Cantor cranks, i.e. the number of Cantor cranks is uncountably infinite. So that subset of reals to which we have identified in the mapping proposed in the previous paragraph is uncountably infinite. Furthermore, we also agreed in the premise that there are “no bounds” on what methods will be employed, from which it follows there can be no bounds on what reals will be generated when applying Cantor’s proof to the various Cantor “disproofs” — in other words, no way to specify which reals have been mapped by our proposed mapping and which haven’t.
In other words, we have successfully mapped an uncountably infinite unbounded subset of reals, i.e. all the reals.
And there you have it: The existence of countless false disproofs of Cantor’s proof inherently disproves Cantor. QED.
Or, we could just use Vorlath’s Theorem to disprove Cantor: Cantor used ONE SPECIFIC MAPPING! QED.
Vorlath, I’m confused. What do you mean by “Do you agree that there are strings that only have a single digit set to 1?”
I agree that there are such strings in R; there may or may not be such strings in the range of f.
And I don’t know what you mean by “I must also find a digit that hasn’t yet been set to 1”. Construct your function f any way you like, and the result above will find a real number not in the range.
I think the problem with Vorlath’s argument is that he doesn’t realise that for some sets S, a proper subset of S can have the same cardinality as S itself. He has constructed a subset R of Q consisting of the decimals where a single digit is 1 and every other digit is 0 (i.e. 1/10^n for some natural number n). He has then shown that this subset has the same cardinality as N (which is true). He then claims that since Q consists all of of the elements of R, as well as some other elements (like 0.11), Q must have greater cardinality than N.
In actual fact, Q and R have the same cardinality, despite R being a proper subset of Q. I don’t think this is any harder to believe than the fact that Q and N have the same cardinality, despite N being a proper subset of Q.
@70:
HAHAHAHAHAHAHA!!!!
C’mon, someone tell me what digit of the row for string of all zeros will be included into Cantor’s diagonal. Just give me a natural number for the index. Any will do. I’m not picky. I will then show you how a string already exists with that single digit set to one and is already included in the diagonal. I’ll even let you pick another index. And another.
The fact that single 1 strings are a proper subset is the very point I’m trying to make because it kills the diagonal process. If Cantor’s grid doesn’t work with proper subsets, then you can’t tell if N isn’t a proper subset of R in Cantor’s grid mapping via digits.
What the fuck, Vorlath? I just did that by construction. I gave a procedure by which we can generate any position we so desire, and that’s enough to put it into the grid.
Here, let’s do the first few entries of the list, then build the portion of the grid corresponding to those:
0 is first, of course. Then 1/1 = 1. Then 2/1 = 2, then 1/2 = .5, then 1/3 = .3~, then 2/2 = 1 again so we discard it, then 3/1 = 3, then 4/1 = 4, then 3/2 = 1.5, then 2/3 = .6~, then 1/4 = .25… so now we put it into the grid.
0.0000000000
1.0000000000
2.0000000000
0.5000000000
0.3333333333
3.0000000000
4.0000000000
1.5000000000
0.6666666666
0.2500000000
So one minor detail is that Cantor’s proof as usually presented is done on the range from 0 to 1 to limit the number’s growth to be in one direction instead of two. Well, what we’ll do here is just, for Cantor’s grid, ignore everything before the decimal point, and generate a number that is in the range [0..1],
So, what’s the diagonal of the grid?
It starts with 0000300060.
Okay, so if we use post 64’s version of Cantor’s number, it starts out as … 0.77777777737. It will continue on forever, and will never repeat. We know it will never repeat, because if it DID repeat, there would be a rational that represents it, and we could find the position of that rational in the grid, and then find the value of the corresponding digit, and if that value is a 3 then by the construction it must be a 7, and if it is a 7 then it must be a 3, therefore we’ve finished the circle of death and found a contradiction in the claim that our number will repeat.
All that means, though, is that there is a real number that is not a rational number.
Can you identify any specific flaws in this? Do not say “it does not contain some number” without specifying precisely what that number is, because then you are not providing a specific flaw in the argument. Also do not say that this proves Cantor wrong, because it is completely consitent with his claim that the rationals are a proper subset of the reals – what it shows is that putting all the natural numbers into a one to one mapping with all the rational numbers is not sufficient to put them into a one to one mapping with all the reals.
@72:
What you don’t understand is that no matter what digit you THINK is in the diagonal, that digit has already been included in the diagonal by another row that has a single 1 in that position.
Simply being any other value is handwaving. I want to know WHAT digit you are using. No matter what digit you pick, that digit is already in the diagonal from another row.
@73:
No, you didn’t. Specifically, what digit are you including in the diagonal for the number zero for example? No matter what digit you select, there is already a row that has that single digit set and where that digit is already in the diagonal. This means that the number zero cannot have a digit included in the diagonal. This means |Q|>|N|. This is EXACTLY what Cantor is doing with his diagonal. He’s shown how the diagonal is different from all rows. I too have shown how zero is different from all rows. You can’t argue against what I say without also arguing against the diagonal.
But now we come to your mapping and we know that |Q|=|N|. Contradiction! So I actually do use everything you say. It’s the other part of my counterproof by contradiction.
So you can keep arguing about it all you want. I agree with you except for the diagonal. You are simply making the case for me.
C’mon. Anyone???? Can ANYONE tell me what digit is in the diagonal for the number zero????
Pick one. Give me any natural number for the index.
You are all CRACKPOTS, just like Cantor.
HAHAHAHA!!!
That’s me laughing at all of you.
Wanted to clarify when I say “I too have shown how zero is different from all rows.”, I’m talking about digit selection. I’ve show that zero would require a different digit for the diagonal than all other rows, but there aren’t any. In the same way, the diagonal also traverses all digits (and rows associated to those digits).
“Can anyone tell me what digit is in the diagonal for the number zero?”
Zero. If i is an element of N and f(i) maps to 0 in Q or R, then the ith digit of the decimal expansion of 0 is the digit that 0 contributes to the diagonal in the ith digit.
Vorlath, you have no mathematical rigor in anything you write and you lack basic understanding of Cantor’s arguments. For example, your quote,
“…This means that the number zero cannot have a digit included in the diagonal. This means |Q|>|N|…”
In order to show that |Q|>|N| you must prove that an element, namely the diagonal, is in Q and not in N. You certainly did nothing of the sort and I’m not even sure you understood that.
Commenters are patiently replying to you with plainly-stated mathematical arguments. Your responses amount to spam on Mark’s blog.
@76:
What is the value of i? That’s what I want. And note that the string with a single digit set to 1 at the ith digit has this ith digit already in the diagonal. So pick wisely. You cannot choose the same i twice. But if you want to include the string for zero, then this is exactly what you must do.
Oh goodness! Another crackpot that doesn’t understand Cantor’s diagonal argument.
Cantor wants to show that a new number x is different by at least one digit from all rows given. That’s it. The diagonal is a means to an end. If Cantor can use the diagonal to show that all digits are accounted for, then I can use the same thing. I simply note that the subset of all reals that has a single digit set to 1 must form a diagonal as per Cantor’s construction.
If the full list of reals is used, the diagonal must still cross that subset of rationals. Each of those rationals will have one digit in the diagonal. Because of this, all digit indexes must be in the diagonal. So how is it possible for any digit of the other reals to find their way into the diagonal if all the indexes are already in the diagonal?
Seriously, are there any non-crackpots here?
Vorlath, let me ask you one question, since everyone else’s attempts to show you that you’re glaringly incorrect aren’t getting through.
Which is odd, because the graphical representation of Cantor’s diagonal argument on Wikipedia is a fairly easy read.
Supposing your trivial construct actually shows what you think it shows (as opposed to showing that you don’t understand the construct of the diagonal in the first place)… can you explain why nobody else has thought of it in the last 140 years? It would seem likely that someone else would have offered this brilliant insight. Cantor certainly had detractors, I’d suggest that you start there.
@78:
I wonder how Cantor would have answered your question.
1. Every single person that has replied to me about the flaw in Cantor’s diagonal in this thread does not understand Cantor’s diagonal. I’m not talking about my stuff. I’m talking about Cantor’s argument by itself. So right there, you know that most of the population that claims to understand Cantor does not. They are crackpots calling other people crackpots.
2. Ironically, I’d guess that everyone believes I don’t understand Cantor’s argument. At what point in the last 140 years do you suppose this would have been different for anyone else claiming to oppose Cantor’s argument and be taken seriously and know that the person DOES in fact understand Cantor’s diagonal argument?
3. People like a bandwagon.
4. Going against an accepted “proof” can be a terrifying proposition for many people. For one, you get to be called names and be prominently set up for ridicule as I have been on this very blog.
5. No one actually looks at the flaw. They always handwave it away.
6. Cantor’s argument uses circular logic, so you cannot use a counter-example against circular logic. This removes one of the best tools to counter proofs. So people asking for a list or ask what natural maps to PI are just nuts, but people who oppose the argument often fall into the trap.
7. There actually have been several counter proofs against Cantor’s argument over the years. They have been handwaved away.
8. I am a programmer. I work with bases all the time and only in the past 50 years has this profession existed to any large degree. Realistically, before the 90’s, it would have been slim picking. Most programmers have never even heard of the halting problem. Still, many programmers see the flaw right away even though they may not be able to formulate it into a proof.
9. Enumerations use base 1. This is something most people don’t realize or know anything about. It’s a clever trick which allows to compare different bases for the same amount of digits without knowing it. If Cantor compared base 2 vs base 3, everyone would laugh at it. But he compares base 1 vs base 2. That’s not so obvious and not even programmers would recognize it because no one uses bases that way. Well, except for Cantor. You really do have to be mad to think up of something this messed up.
I could go on. But I hope it’s obvious there’s been obstacles to recognize the flaw in Cantor’s argument in the last 140 years. But to say no one saw it is ridiculous. Mark has a topic about people opposing this all the time. Over the past 140 years, there have been countless attempts to explain the flaw. They all saw it. Explaining it is a different beast when circular logic is what you have to defeat.
Hope that answers your question.
I’ll ask Vorlath: “Can you please define ‘crackpot’ — without attacking anyone including yourself (which risks a diagonalization argument), and without using any Math?”
For example: is it possible that I am a crackpot, and the referees and editors who publish my papers are also crackpots trying the fool the world? Is it possible that I am a crackpot, and the people who gave me the B.S. degree at Caltech are crackpots, and the people who gave me passing grades in Math at graduate school, and the people who gave me a secondary school math teaching certificate are crackpots, and my co-authors including the Physics Nobel Laureate are all crackpots, and the people who hired me to be Math professor were crackpots, and the people for whom I did Math on contract for Boeing, Burroughs, European Space Agency, Federal Aviation Administration, Ford, General Motors, Hughes, JPL, Lear Astronics, NASA, Systems Development Corporation, U.S. Army, U.S. Navy, U.S. Air Force, Venture Technologies, and Yamaha are crackpots — and we are all engaged in a vast global conspiracy to keep your genius from being ranked above Cantor? If so, what is our motivation? And why are you the center of this enormous effort, you, there, at the center of the mathematical universe? Or are you the only person in the world, and you are making a solipsist joke? Also, which actor should play you in the movie about you when the truth at last sweeps from continent to continent, and you are bowed to by adoring masses? Just wondering…
I’m just hard pressed to figure out what digit index can be used for Cantor’s diagonal when it comes to other rationals (and reals) considering that the infinite identity matrix (a subset of R) has the i-th digit of each row in Cantor’s diagonal for all i.
That’s it.
If someone can explain this to me, I’d be grateful.
The real fun with this paper is, that it actually finds and addresses what’s wrong with itself in section 2-13.
There are numbers which are not n-modular for any n, for example 0.2121… and therefore the map P does not map onto such a number.
Only the author fails to see that this means that P is not a bijection and therefore the new list is not a bijection between N and the rationals in (0,1).
I know this is probably beating my head against a brick wall, but…
Vorlath:
You realise that proper subsets of a countably infinite set can also be countably infinite, presumably, right? For example, N is a proper subset of Q, but |N|=|Q|. Similarly, if I define E to be the set of even numbers (i.e. 2N), 2N is a proper subset of N, but again |2N|=|N| via the obvious bijection N –> 2N : f(n)=2n
Now, lets take a look at the set (I’ll call it V) you’re using in your table — V={(0.1)^n | n is a natural number}. You seem to be saying that the result you get, that |V|=|N| obviously shows up a flaw in Cantor’s argument as otherwise, where could we put the rest of Q in order to give us the result we know we should get — that |Q|=|N|.
In fact, it is trivial to show that |V|=|N|, as a bijection is built directly into the definition of the set; the function N–>V : f(n) = (0.1)^n (and inverse V–>N : f( (0.1)^n ) = n )
The result, however counterintuitive, is that |V|=|Q|. More than that, |2N|=|N|=|V|=|Q|.
Hopefully, that should clear something up…
Vorlath, I think what you’re doing (and you’ve mentioned being a programmer a couple of times), is using programming metaphors, where the other posters are using a math training that permits more choices and generalities.
I think you’ve claimed that since you can come up with a listing of R that correspond to N, n -> 10^(-n), then that’s the ONLY listing anyone else might be allowed, and that they have to use that one.
Can you consider a renumbering of sorts? Consider that the odd naturals, for instance (we could use even similarly) are as numerous as all the naturals. Ie, in N, map n -> 2n-1. So {1,2,3,4,..} maps to {1,3,5,7,…}. Then the renumbering .. renumber please your 1-down-the-diagonal grid with odd numbers. So .1 corresponds to 1, and .01 corresponds to 3 (not 2 but 3), and .001 corresponds to 5, etc. Then, aren’t all the even naturals still “available” to be used for anything else? Remember the odd naturals are as numerous as ALL the naturals, so just using them, the mapping you were concerned with is “taken care” of. Then we have all the evens free to use for anything else, for adding to the list the elements you thought were missing. And since the evens are also as numerous as all the naturals, we got all the room we need to hold the rationals as described above in the x,y plane methods of enumerating them all. We can even store your number .000000~ there. We could pick ‘2’ to index to zero, for instance. And still the evens 4 and above are “free” to use. Don’t you see that that’s possible? That because one mapping “consumed” or “used-up” all the naturals we didn’t have to stick to using just that one?
I think your argument, no offense, was that since ONE thing you came up with didn’t work, that no correspondance could work. But that’s the generality that math rigor provides, and that the other posters are using, and that I think you’ve skipped since you’re using (stuck with?) the metaphors and cautions and paradigms of practical machine programming. Cantor’s argument is more like challenge/response than just one mapping. Like Mark CC alludes to, Cantor “says bring me your mapping” .. “ahh here’s why it won’t work”, … “bring me another mapping” .. “ah here’s why that won’t work” .. See? It’s like the delta/epsilon definition for limits .. it says, you bring me this, and I’ll show you that I can respond with that. So it’s a reasoning on challenge/response that way, that’s why it works for all comers.
@83:
I agree 100% with everything you’ve said. All of it. I’ve been trying to explain exactly that for eons. Your comment is the exact same argument I’m using against Cantor.
Cantor doesn’t say “Don’t use this mapping or that.” He says “Bring it on!” So my list R with V as a subset stands.
See, the grid shows that |Q|>|N|.
But we know that |Q|=|N|.
That’s a contradiction.
I know full well that you can remap Q to N outside of the grid. That’s not important. What’s important is that Cantor’s grid is supposed to tell us when two mappings have different cardinalities. It failed in that task. I’ve shown one case where it does not work. So why should we trust it at any other time? Why should we believe that |R|>|N| if it can’t be trusted? If you can say that V is a proper subset of Q, then why can’t I say that N is a proper subset of R?
No matter what you do, you cannot remove V from R in the grid. Outside of that grid, remap as you please. And it doesn’t have to be V specifically. It’s just that the identity matrix shows quite clearly that each row maps to each digit.
@84:
I said that if I give you R, then there is a subset within R that is the same as the infinite identity matrix. But you don’t need to use the identity matrix. I just use it because it’s easier to see that each row is mapped to a digit. You can use any reals. Sticking with the rationals is better because you can use the contradiction between |Q|>|N| and |Q|=|N|.
So I only ever use R. This is exactly the same assumption by Cantor.
Cantor says his diagonal argument works for all mappings, so no, you can’t renumber it. Stick with Cantor’s grid and the list I gave you.
And really? Would you take me seriously if I asked you to only take a proper subset of the digits when constructing Cantor’s diagonal? There are just as many. So what the heck, eh?
Vorlath says:
‘Cantor doesn’t say “Don’t use this mapping or that.” He says “Bring it on!” So my list R with V as a subset stands.’
True. What you’re missing here is that Cantor is not trying to say “Regardless of what ordered set you’re using, this will prove that there are more reals than naturals.” He’s saying, “Regardless of what ordered set you’re using, there will be a number k in the set of Reals not in your set.” All he’s doing with the diagonal argument is demonstrating how to identify a k for any given set. So, if all you’re doing is giving a set V which includes the elements: for all n>0: (.1)^n, then Cantor’s diagonal argument will demonstrate a real number which is not in V. Which is, quite frankly, not that hard.
Vorlath, there are two obvious errors in your argument above.
The first is you claim your mapping shows that |Q| > |N|. This is not the case. Instead you have shown that N can be put in bijection with a subset of Q. N can also be put into bijection with a subset of itself (e.g. every natural corresponds one-to-one with an even natural); this does not prove that |N| > |N|, does it? So you have proved nothing about cardinalities. The fact that we can put Q and N in bijection proves that they have the same cardinality.
The second is that Cantor’s grid and diagonal argument is not, as you apparently think, “supposed to tell us when two mappings have different cardinalities”. Clear this error from your mind before proceeding. What the diagonal argument is is to systematically generate a real R that corresponds to no natural N for any proposed bijection between R and N. I see that Cuddles has just made the same point.
You are in the peculiar position of proposing a mapping between R and N which is definitely not a bijection- since we know, independently of any diagonal argument, that there exist reals not mapped to any N by your mapping – and then claiming that this proves something about proposed bijections. It doesn’t.
Vorlath, when you change your mapping, Cantor gets to change his number. You can’t say “the i’th digit is already taken!” because the only way the i’th digit can be taken is if you already specified it by specifying the i’th row – in which case you’re trying to specify the same row to have two different values, which is a contradiction and proves preciesly nothing.
Of course by now it’s clear Vorlath is not actually engaging with us, and any lurkers who might have been confused by Vorlath’s first post or two surely can see that, so I am done here.
I think Ralston in 88 points out another error with Vorlath not understanding quantifiers and loss of generality.
Correction to my 76:
I meant to write, “In order to show that |Q|>|N| you must prove that for any bijective f:N->Q, an element, namely the diagonal, is in Q and not in f(N). You certainly did nothing of the sort…”
And Ralston in 73 proved that a diagonal from a mapping from N to Q is not in Q.
> 7. There actually have been several counter
> proofs against Cantor’s argument over the
> years. They have been handwaved away.
No, they haven’t (well, some of them have, because they’re wrong). Others rely on set theory constructs that do not use ZFC. Naive set theory is not the tool we use to describe cardinality of infinite sets.
> 8. I am a programmer. I work with bases all
> the time and only in the past 50 years has
> this profession existed to any large degree.
> Realistically, before the 90’s, it would
> have been slim picking. Most programmers
> have never even heard of the halting problem.
> Still, many programmers see the flaw right
> away even though they may not be able to
> formulate it into a proof.
I now believe I see the problem.
You realize that the proof of the halting problem is basically the same exact proof as the one we’re talking about, right? That’s undoubtedly why you don’t grok it, because you have a problem with the halting problem.
The halting problem *is* decidable (in theory, anyway) for deterministic machines with limited memory (which is what you’re used to using), but that has nothing to do with Turing machines.
Turing machines weren’t created to model *computers*, they were created to model *computation*.
Similarly, set theory was created to model mathematical structure, not mathematical operations.
@86:
My list is R. I’m simply pointing out that the digits, when forming Cantor’s diagonal, can only map to a subset of my list. So your assertion is wrong. V isn’t the only subset. There are infinitely many subsets. I simply chose the identity matrix because it’s easier to visualize.
@87:
I agree that |Q|=|N| if you remap them OUTSIDE of the grid. But you don’t understand what I’m saying. INSIDE the grid, |Q|>|N| ALWAYS. That’s the contradiction. You even say it yourself, but don’t realize it. That N can be put into a bijection with Q is exactly right. This is what refutes Cantor’s argument because his diagonal can only show |Q|>|N| which is incorrect.
So your assertion is wrong too.
So you’re saying that |R|=|N| if you can find a real not in the list? I’m using the same argument as Cantor BTW. I don’t think anyone realizes that.
This actually refutes Cantor’s argument and you don’t know it. INSIDE Cantor’s grid, you cannot put at least one digit of all Q in the diagonal . IMPOSSIBLE! That’s the contradiction. The diagonal does NOT work. Even though we KNOW OUTSIDE of the grid that |Q|=|N|, the grid tells us that |Q|>|N|.
You’re wrong again. Next.
@88:
You don’t understand. I NEVER change my mapping. I use R just as Cantor does. I’m simply pointing out that no matter how many digits you have, the diagonal will have to cross at least one digit of all the rationals that have only one digit set leaving no digits for the other rationals that ARE in my list.
Nope. Different rows, same digits. You have it backwards.
You’re wrong too. Next.
@89:
I AM NOT TRYING TO PROVE |Q|>|N|.
PLEASE LISTEN!!!! THAT IS NOT WHAT I AM DOING!!!
I am showing that it is Cantor’s grid that can only show this. NOT ME.
The fact that OUTSIDE the grid, |Q|=|N| is the contradiction. QED.
So you’re wrong too. Next.
90 doesn’t know what he’s talking about, so I’ll leave that alone.
—
C’mon. This is silly. YES, we all know that |Q|=|N|. This is correct. But if Cantor’s grid showing |Q|>|N| is wrong, then we cannot trust its conclusion of |R|>|N| either because it is done using exactly the same flawed method.
Every single one of you is using circular logic I’m afraid.
If |Q|=|N| OUTSIDE of the grid, who’s to say that |R|=|N| can’t be done OUTSIDE the grid as well? Get it?
Let me ask all of you a simpler question. Suppose I have N digits. I have two lists. The first list can have two symbols per digit and the other list can have three symbols per digit.
Which list has the higher cardinality? Remember that I am matching digits from one list to the digits of the other list.
Your answer will determine if Cantor’s argument is flawed or not.
I want to add one last thing that may not have been clear. When I say that Cantor’s grid shows |Q|>|N|, I’m saying that he’s showing this when he’s showing |R|>|N|. You cannot separate the two conclusions.
IOW, if Cantor’s grid shows |R|>|N|, then his grid MUST also show |Q|>|N|. Both conclusions are reached the same way and should both be correct, but they are not. So if |Q|>|N| is incorrect, then |R|>|N| is also incorrect as shown by Cantor. I’m not saying that |R|=|N|, only that Cantor cannot show |R|>|N| with his grid without also showing that |Q|>|N|.
Cantor’s diagonal is self-defeating.
I also now know with 100% certainty that it is flawed. Thanks for your answers.
@89:
I think you deserve a better answer. I don’t need to show |Q|>|R|. I only need to show that Cantor doesn’t use all rows. And if he doesn’t use all rows, then I most certainly cannot use the diagonal because it is flawed. See, you’re using circular logic.
This is how he obtains the bogus result of |Q|>|N| and |R|>|N|. So your assertion is incorrect. I don’t need to use the diagonal at all.
The only way you can show that the new number created is different from all other rows is to make sure that you have at least ONE digit from each row and check that it’s different. That’s the purpose of the diagonal.
When you consider that the diagonal that runs through R in Cantor’s grid MUST also go through all the elements of the identity matrix found in R, then you have a serious problem. The identity matrix uses ALL digits. It MUST by definition. The order of R is irrelevant. Regardless of the order of the list, the diagonal MUST use one digit of every row of the identity matrix found in R.
This means that there are no other digits. This means that the diagonal has been formed. Take the inverse and you get zero. |Q|>|N| and |R|>|N|. But we know that |Q|=|N|. Contradiction. If that’s wrong, then |R|>|N| is wrong too. At least, we can’t use Cantor’s diagonal because it misses rows.
And you don’t need to use the identity matrix. Any infinite subset will work since you are mapping by digits. And the diagonal can use ANY digit of any row in the subset. Doesn’t matter. Even if the diagonal produces an irrational number, it doesn’t matter because I’ve shown that the diagonal missed other rationals.
Again, all I need to do is prove that the diagonal misses rows. I don’t need to use the diagonal or anything else.
And That’s how the diagonal produces new number. It omits items in R. At the very least, we know it omits rationals.
Just answer me this. What digit index isn’t used by the elements of the identity matrix when those elements are in R? What digit index can be used for the diagonal for the other rows of R?
I’m still waiting for a natural number for those index.
Vorlath: Cantor’s argument does not show that |Q| > |N|. To do so, it would need to also show that the number on the diagonal is in Q.
Vorlath says:
and also
There is a problem here, and you should really set aside your blanket dismissal of our arguments and your assertions that you’re “using Cantor’s argument”. It’s not helpful.
The identity ordered set indeed can be represented by an infinitely long list of numbers, all 0s except for 1 in a diagonal from top left to bottom right. This is a countably infinite list of numbers. However, infinity works in ways that are not intuitive. Order matters. You can make a list of numbers that consists in only the identity numbers which will never have others, and it will be countably infinite, but you can also make other lists of numbers of which the identity list is a subset, which are also countably infinite. The fact that |Q| > |I| in conventional terms (saying there are elements in |Q| that are not in |I|) does not change the fact that there can be a one to one correspondence between elements in |Q| and elements in |I|. This is really counterintuitive, and one of the hardest things to grasp about infinity. Both sets are countably infinite. Notice that this whole paragraph has mentioned nothing about Cantor except this sentence. But if you cannot accept that these sets have the same size, despite having elements in |Q| not in |I|, there’s really no point in continuing past this particular point. Now, I’m anticipating you saying that you KNOW all this, but the two quotes above strongly suggest that you do not. In fact, you EXPLICITLY say that the order is irrelevant, but order in infinite lists is vital.
IOW, if Cantor’s grid shows |R|>|N|, then his grid MUST also show |Q|>|N|
It mustn’t and indeed it doesn’t! End of argument!
That would depend on how the proposed list of R is defined. If the first element of the identity matrix to appear on the the purported list of the reals is at row 100,000,000,000,000 there are immediately 99,999,999,999,999 rows we know are included in the construction of the diagonal.
To clear things up for non-maths people who may be getting confused about what it is that Cantor’s diagonal argument actually says:
1. Cantor says, “Give me a list of numbers.”
2. You comply.
3. Cantor says, “Here is a number that is not on that list.”
4. You say, “Gee-willickers, you’re right!”
This doesn’t cause a problem for a list of the natural numbers, because Cantor can always just give you a rational number. It doesn’t matter for a list of the rational numbers, because Cantor can always just give you an irrational number.
But it matters greatly for a ‘list’ of the real numbers, because the number you get in return must also be a real number. Thus, there is no way to make a complete list of the real numbers — a simpler way of saying that you cannot put them in a one-to-one correspondence with the counting numbers.
Immediately from this, you get the counter-intuitive result that some infinities are bigger than others. The moral of the story is: Infinities are weird, and may break your brain.
It seems to me that one can also construct a diagonal argument using a continued fraction expansion of your reals. This avoids problems such as 0.1999… = 0.2000…, and since every rational number has a finite expansion, it becomes immediately clear that the “counterexample” you construct for a mapping N->Q cannot be a rational number.
Anyone see any objections to this?
Look up Peter Johnstone Sketches of an Elephant, volume 2. (Unfortunately, only volume 1 is available online for free.) Theorem D4.1.8 is a proof that in a Boolean topos, Cantor’s theorem holds. Example D4.1.9 is a non-Boolean topos in which Cantor’s theorem fails. Johnstone does not address the question of why diagonalization actually fails here. It is left as an implicit exercise for the interested reader.
One remark: you write: Cantor is trying to prove that the set of real numbers is strictly larger than the set of natural numbers. Strictly speaking, it can be misleading to think of uncountable as “bigger than countable”. While it’s natural to think of the reals as a superset of the natural numbers, an uncountable set may also be a subset of a countable one, e.g. we can enumerate the Turing machines, but not those that halt on the empty input.
I’m just gonna sum it up.
1. For those mentioning |Q|=|N|, please look up proof by contradiction.
2. For those mentioning that I should use the diagonal, I am showing how it is flawed. So using it is pointless.
3. For those mentioning that you can add rows, good answer. Now tell me again… What’s the difference between the identity matrix and Cantor’s diagonal?
4. And to those who believe I am constructing a new number, I am not.
Good luck!
Vorlath, it’s pretty telling that you only seem to be able to explain(sic) your case using informal English. Is there some reason why you can’t formulate your argument as a logical proof? I’m a software developer not a mathematician, but this thread is like listening to someone who claims to have a comparison based sort that works in linear time but who steadfastly refuses to provide source code.
An informal argument is to a proof what doodling on a whiteboard is to working software.
By George, I think I’ve got it – and dammit, Vorlath @93 must be right! As he says:
Don’t you all see: Cantor’s argument says that given any supposed enumeration of the reals, expressed as infinite decimals, he can produce another infinite decimal/real, which must differ in at least one decimal place from any other decimal/real in the list (since it differs from the nth decimal/real in the list in at least its nth decimal place). Hence, he claims, the supposed enumeration of the reals does not include all reals. And since this could be done for any supposed enumeration, any such enumeration must be flawed.
But in exactly the same way, Vorlath could argue that for any supposed enumeration of the rationals, he can also produce an infinite decimal, using exactly the same diagonal construction as Cantor used; and in the same way, he (Vorlath) has exhibited an infinite decimal that isn’t present in the list. So by Cantor’s argument, the rationals cannot be enumerated either; yet we know they can, so the diagonalisation argument must be flawed. It isn’t clear why yet, but it obviously must be!
Oh, there’s one other small detail to be cleared up, probably not worth mentioning, which I’m sure Vorlath could fill in for me: for the argument to hold for the rationals (“both conclusions are reached the same way”), it would be necessary to show that the infinite decimal constructed by the diagonal argument would have to be rational, as otherwise it wouldn’t prove that there was any flaw with the enumeration; there wouldn’t be any particular relevance if Vorlath had constructed an irrational. I’ve tried to do this, but it seems quite a tricky little proof; I couldn’t even establish it for the mapping given in Michael Ralston’s post 73, let alone a general proof. But that’s just me; once Vorlath has shown us a proof of that (probably quite trivial) little lemma, Cantor’s diagonalisation argument goes into the dustbin of history!
Yes, this is logic 101. Similarly, a counterexample to Fermat’s last theorem would reveal that Wiles (or maybe Serre or Ribet before him) made a very subtle error somewhere. The point is that Cantor’s proof is so constructive and borderline trivial that it is pretty obvious that an explicit counterexample would reveal a hole in the proof very quickly, whereas a Fermat counterexample could keep lots of people very busy for quite some time.
Meanwhile, a giver of an alleged counterexample to Cantor is not required to take that step. We’re just all quite cognizant that such a giver is failing to educate himself one step more, but his not doing so is not, and never will be, a mathematical mistake on his part. For Mark to imply that it is remains complete nonsense.
@105: Vorlath hasn’t shown any such thing, because he hasn’t even got as far as dealing with an enumeration of the rationals. He’s taking an enumeration of a countably infinite subset of the rationals, and the grid gives us a real not in that subset. Big whoop.
Suppose we do the enumeration of the rationals and write the list as decimals. Then we use the diagonal argument and get a new infinite decimal that isn’t in the rationals. That would be what we call a real number, no? It’s not a counterexample to the enumerability of the rationals unless you can prove that your new infinite decimal is a rational number. Which is isn’t, since it differs in its decimal expansion from all _rational_ numbers in at least one place.
Oops- missed the snark in 105. Sorry 🙂
@106 “…it is pretty obvious that an explicit counterexample would reveal a hole in the proof very quickly…
Meanwhile, a giver of an alleged counterexample to Cantor is not required to take that step.”
Cantor’s argument does more than just point to specific numbers, it defines numbers by referencing the function. The difference between diagonals and other numbers are not like even and odd numbers. In order to show a bijection one must prove that all the numbers get mapped to, including the diagonals, which must have special mention. Cantor revealed the true burden of proving a bijection, and any real proof of a bijection would address Cantor. It follows from the definition of bijection and what it takes to prove bijection. This is what is “inescapable” about Cantor’s proof.
Assume Cantor’s proof is false. There is still no complex or sneaky way of proving a bijection without showing specifically what maps to the diagonal elements. Without knowledge of Cantor, a proof of a bijection would address these elements.
True but irrelevant.
I have no idea what this is supposed to me.
Yes.
Yes.
Sorry, that’s crackpot nonsense. No “must” here whatsoever.
WTF? Vorlath came back for round 2? This just keeps getting better and better…
…(and stupider and stupider)…
@william e emba. You’re quibbling. Of course a person who claims to have found a counter-example should address the proof. Cantor’s diagonalization provides an automatic counter-example to any counter-example of the fact that a one-to-one mapping from N to R does not exist. So if a person wants to show the validity of his highly controversial counter-example, he needs to show why Cantor’s diagonalization does not apply, otherwise the diagonalization automatically proves it wrong.
Not really. The statement that a crackpot must address Cantor’s proof is flat out incorrect. It’s one thing to ask a crackpot to explain where Cantor’s argument fails. It’s another to tell him he has failed to do the allegedly required logical necessity of addressing Cantor’s argument.
Since there is no such requirement, the crackpot concludes (with perfectly good reasons) those like Mark who raise this requirement are incompetent at logic 101, and then furthermore concludes (with plausible but actually incorret reasons) that he, the crackpot, is the only logical person in town.
If you want to argue with a crackpot, do not engage in clearly false logic yourself! Sheesh, this is obvious, and this is as far from a quibble as possible. It’s like “do not feed the trolls”, only much worse when you fail to heed the warning.
No “of course” about it whatsoever. That would merely be nice. It would probably be educational. But it is not a requirement. Passing it off as such is crackpot nonsense.
No kidding. But only if it’s correct! Sheesh. The crackpot’s failure is typically that he has not provided a surjection N->R, and is unaware that his map is not onto. Whether the awareness comes about by explicitly giving a missing value or by apply diagonalization is completely irrelevant. Missing is missing.
No he doesn’t! He needs to show his counter-example is in fact a counter-example. That is what he has not done.
So what? That gives people who know better absolute confidence that they can and will find a missing value. Which is a plus for us and pathos for the crackpot. But there is zero obligation to find the missing value by that particular method. As a matter of fact, there is zero obligation to find a missing value in the first place! The burden of proof is on the crackpot, and he has not delivered.
@William e emba
Let me start over. If one claims to have a bijection from the naturals to the reals, then any scrutinising person will use Cantor and prove that the mapping is not a bijection.
Your claim that proof of a bijection would not necessarily mention Cantor is only vacuously true. So is my statement that a proof would necessarily mention Cantor. You can talk about how a proof of a bijection could be independent and I could discuss how referencing diagonals is ‘clearly inescapable’ when proving a bijection, but we are both just playing together in a fantasy land where Cantor is wrong.
The point is that cranks should give Cantor proper consideration and prepare better for scrutiny bought about by Cantor. It’s silly to call Mark or me a crank over this.
If you disagree, that is fine. I just kindly invite you to prove your statement that mentioning Cantor is not necessary to prove a bijection from the naturals to the reals. That should be an easy task for someone so clearly better at logic than anyone here.
Well, er, mike, it’s impossible to prove a bijection from the naturals to the reals – we know this, because of Cantor’s proof.
But if it was possible, such a proof would not, in fact, mention Cantor’s argument. We would expect someone writing a paper claiming to have such a proof to mention Cantor, because we would expect someone with the knowledge of the field require to produce such a thing to know about Cantor and to anticipate people immediately bringing Cantor up when told about the bijection.
So when we see a proposed bijection and the author fails to mention Cantor, that’s a huge warning flag that says they probably don’t actually know what they’re doing. But if someone came up with such a Cantor-refuting bijection, a hundred years from now Cantor’s proof wouldn’t even get a line of mention in math classes.
I really shouldn’t get dragged into this, but while I think William Emba’s position is a bit of a vehement take, I do think some people are misreading him, or at least his intentions.
(Comments #10 & #101 about topoi where Cantor diagonalization fails are, while perhaps not directly relevant to the present debate, instructive to have in mind. I don’t know of the examples which are being referred to; but from my limited understanding this kind of stuff is bread and butter in categorical logic. So there are contexts in which Cantor diagonalization does not work as we’d expect.)
What is true is that a purported proof that the reals are countable *ought* — in the sense of communal norms and common sense, not necessity — to then take that proof, use it to (implicitly or explicitly define) a surjection from N to R, and finally explain why the diagonalization method fails for this mapping. If the crackpot has got this far, then this is where they would fall over.
However, I would go along with William Emba in saying that failing to do this last step is a mistake of mathematical practice, not of logic. (For instance, I know of a rather technical mathematics paper which in passing claims as a corollary some general fact about certain Banach algebras; it was then observed later that a particular class of examples fails to have that property. The article making this correction did not, and was not obliged by logic to, show where the mistake in the original paper occurred; this is frustrating, but not illogical.)
“But if it was possible [to biject N and R], such a proof would not, in fact, mention Cantor’s argument.”
… and I’m the queen of France.
In fact, if you would like to talk about fact, in fact, then you should consider the fact that you can’t prove that statement other than by saying it’s vacuously true. If one wants to discuss logic, then it’s silly to insist that a proof of a bijection does not necessarily need to mention Cantor, as if that were most logical. Maybe the fantasy world where Cantor is wrong is one where you must address Cantor to disprove Cantor. Or the fantasy world could be inconsistent and you must mention cantor and must not mention Cantor, in which case we would both be right.
Before I depart Cantor-is-wrong fantasy land, where the cranks live, I want to smash a few mailboxes. It’s not weird to think that a disproof of Cantor must address Cantor. The proof says that given ANY mapping then following from the definition of mapping… So here in fantasy land we have a mapping that disproves Cantor. Assuming this fantasy land is consistent, how could it be clear that this mapping is correct without pointing out explicitly how Cantor does not disprove it?
I think we are coming at it from different ends. William e emba thinks something along the lines of: If Andrew Wiles were wrong then there would exist three numbers which would satisfy Fermat’s Last Theorem. Similarly, if Cantor were wrong then there would exist a bijection between the Naturals and the Reals. I suppose we just took different entrances into fantasy land and it’s hard to find each other here.
Anyways, the larger point is that cranks should give Cantor proper consideration and prepare better for scrutiny bought about by Cantor.
“Our point of view is to describe the mathematical operations that can be carried out by finite beings, man’s mathematics for short.
In contrast, classical mathematics concerns itself with operations that can be carried out by God”
Everett Bishop 1985
Says it all really (potentially and actually).
True but irrelevant. Mark’s claim was that a crank had made a mistake by not using Cantor diagonalization to realize his map was not a bijection. If the crank has gotten so far as to clearly define a map N->R, then almost always mere inspection suffices to realize the map is not a bijection.
The crank’s mistake was making an unverified claim.
Your pedantry is utterly, completely, totally pointless, hence simply annoying. Yes, we are talking in a counterfactual land, but there are degrees of “vacuous truth”. Mark’s statement was criticizing the crank for not using Cantor diagonalization. He somehow managed to not criticize the crank for not using Hopf algebras, nor hypercohomology, nor Cohen-Macauley rings, nor Hewitt-Nachbin realcompactifications, nor the classification of finite simple groups, nor Grothendieck spectral sequences, nor Ehrhart polynomials, nor Banaschewski-Fomin-Shanin extensions, nor Hrushovski group configurations. And you know what? Nobody noticed.
Why? Because we all understood just what Mark was saying, vacuous truth or no vacuous truth. Meanwhile, what a crackpot has never done is provide a bijection N->R, period.
I could not care less about your deontic judgments. I am objecting to the mathematical claim that the only way to refute Cantor’s proof is by taking it apart somehow: “You can’t defeat Cantor’s proof without actually addressing it.” This statement of Mark’s is rank nonsense.
Sheesh. I gave an explicit reference (Johnstone’s book, D4.1.9) to someone doing just that.
I wrote:
Let me clarify, since I discovered a second criticism embedded in the above.
The intended meaning was the fact that Mark’s actual statement (about the crank not explaining where his supposed counterexample trips up Cantor) is vacuously true was pointlessly true: we understood what Mark meant, and going all Boolean on me but not Mark is cheating as a form of argument.
The unintended meaning is the fact that Mark could have intelligibly made several such demands of the crank! Many of the above, and thousands of other mathematical assertions, depend, at some point, on the fact that the reals are uncountable. Tons of mathematics are flat-out wrong if this isn’t so, and the crank’s alleged bijection N->R would, if worked through these various proofs, lead to an explicit identification of where tons of people went wrong, but instead, would really just show the crank where his alleged map is missing values, albeit in a convoluted fashion. Just not as point-blank trivially as Cantor diagonalization does.
To be specific: Cantor diagonalization was Cantor’s second proof. His first proof involved nested intervals on the real line. Why is the crank’s failing never been presented he that he does not explain where Cantor went wrong the first time? Quite simply, neither is his failing. Stating a claim and not verifying it (assuming he reaches that level of coherence even) is his failing.
The difficulty in envisioning the counterfactuals involved here are mostly due to the fact that no one has been able to produce a bijection from the naturals to the reals. All the examples we’ve seen thus far have either been indecipherable (e.g., Volrath) or trivially wrong (e.g., John Gabriel). In neither case was an explicit use of Cantor’s diagonalization needed.
Cantor is the reason we know such a bijection can’t exist, but we’re working with the assumption that someone could potentially produce one (for the sake of argument). This is a bit like working with the assumption that someone could potentially demonstrate the existence of married bachelors.
@121
Yes, that is a great analogy. In order to prove the existence of a married bachelor William e emba says that we must only prove that one is married and is a bachelor, whereas Mark and I argue that you need to explain the wife.
William e emba maintains that while trying to prove married bachelor one may ignore the wife because mentioning her is not necessary to the proof (though, he admits it is not the best idea to ignore a woman). With this thought William rants about how it is not necessary to mention the wife and calls Mark a crank for claiming such. I claim that it might be necessary to mention the wife in order to prove marriage or bachelorhood and that William is silly for insisting anything in our fantasy land.
Of course by “married bachelor” I mean bijective mapping between Naturals and Reals and by “the man’s wife” I mean “the subset of the Reals not in the image of the mapping (i.e. the ‘diagonals’).”
@William e emba
Maybe the compliment of the image of a claimed bijection has something more to do with a proof of a bijection than the classification of finite simple groups. This was my point when I wrote that being a diagonal is a different distinction than being even or odd, that there is an a priori connection making my ‘level of vacuity’ less.
Not quite. Sure I’m ‘going Boolean’ on you and not Mark because Mark has reasonable demands. Cranks should be informed about the realities of the topos in which Cantor was proved before setting out to prove otherwise. Also, many would not be convinced of a proof of a bijection unless someone disproves Cantor. What good is a proof that doesn’t address it’s own disproof when the disproof is so clear? Sure, William, you are right that cranks fail to prove a bijection but Mark is pointing out that not bothering to be educated about Cantor is also the crank’s failing, especially when they claim extraordinary knowledge.
@William e emba
I have a few criticisms of the way you interact with people that became clear to me with your 119 post. Frankly, I think you are condescending and proud.
I was not the first to call your statements vacuous or address the level of vacuity. When you don’t understand something in other comments like my even and odd reference, you don’t ask for clarification. Instead you call our comments pointless and become more glued to your arguments.
There is absolutely no need for analogy. We’re speaking mathematics, not poetry.
And my statement is correct. That’s all you need to do. The cranks make a statement and fail to verify it. The rest of us notice it is of course nonsense, because we are all aware of the wife.
It’s not a rant. Mark is flat-out incorrect, and to maintain it in front of clear logical arguments and numerous examples of standard mathematical practice is pure crankery.
Might. You said it! Mark said he “must” mention the wife. It’s merely a “might”.
Skip the analogy. The mathematics is clear and simple.
So what? It’s not a question of how tight the one statement (N->R is bijective) is with the other (Cantor diagonalization, or any other mathematical statement that somewhere relies on NR is bijective. In all cases, the answer is no.
This makes no sense. Mark’s demands are “reasonable”, but they are not “required” as Mark stated, as I’ve only said repeatedly. And what the hell does that have to do with “going Boolean”? You’re just playing word games.
You asked for an example. I gave one. You are objecting to the example does not live in our world? Why should it? The question is what does one do to show Cantor theorem fails. My claim is one shows there is a bijection N->R. You asked me to back up my claim. I gave a reference. (Actually, Johnstone D4.1.9 shows N^N is a subquotient of N. Close enough.) Mark’s claim is one must identify the mistake in Cantor when applied to an alleged counterexample. Johnstone does not do this.
Cranks must give a good proof, period. They don’t. Going beyond that is nice. It is highly recommended. But it is not actually mathematically required.
Well, yes, no kidding. You’re just agreeing with me loudly and clearly and vehemently saying you aren’t. Sheesh.
Mark is going beyond that. He is claiming that in order to provide a successful counterexample, they are obligated to show Cantor’s alleged mistake. This is what I’ve been objecting to. You are agreeing completely with me on this. Sheesh.
And I think you’re a crackpot, as dumb as Mark is on this issue. Considering that you’re now going out of your way to agree with me loudly and strongly, and then berate me, you’re going into extreme stupidity.
Stick to the math.
So? I said I did not understand what you were saying. Clarify as you see fit. What, exactly, is your point? I see nothing but a loser who has nothing to actually argue except insults.
No instead here. I also call pointless comments pointless, usually with a clear explanation. I am not “more” glued to my arguments. You, as I’ve pointed out, have secretly switched to agreeing with me, and then refuse to admit it and insult me.
@William e emba
Your main argument is only vacuously true, along with Mark’s statement that it is necessary to address Cantor. At best, you’re criticism is as valid as Mark’s post. I disagree that you should so stridently oppose MarkCC over such an inconsequential argument.
William, you should write about our world with our logic because everyone including the cranks are addressing that world and because your assertions are about this world.
It is great to find a blog on the very issue that has perplexed me for a long time, Cantor’s diagonalization and mapping. I’m not a crank, just an engineer who needs an answer.
If I list the natural numbers from 1 to infinity in a column and in my second column, I list their “mirror image” around the decimal point, what is to prevent me from creating a 1:1 mapping between any conceivable real decimal and a natural number? Is this one of these enumeration vs. representation fallicies? Graphing column 2 vs. column 1 is thought provoking by the way.
Example:
1 .1
2 .2
3 .3
4 .4
.
10 .01
.
14 .41
.
901 .109
.
13009 .90031
etc, etc, etc to infinity
Column 2 may be sorted by magnitude of course with column 1 following the sort.
Tell me if this is too simpleminded to be worth consideration.
@127:
It’s not too simpleminded. It’s a common misunderstanding, which gets to the heart of the problem.
The decimal representation of every natural number, by definition, has a finite length. So what your process will generate is the set of all real numbers with finite decimal representations. And any number with a finite decimal representation is, trivially, a rational number.
It’s easiest to understand what that means by asking “What natural number will produce 1/3 as its mirror image?”
No, the cranks are not addressing our world. That is completely totally obvious. They are living in some lalaland where Cantor’s theorem is invalid. And you haven’t noticed? Sheesh.
My basic assertions are about cranks, and how to respond to them.
For example, there has been the claim that since Cantor’s proof is essentially trivial but Wiles’ proof is exceedingly complicated, the putative counterexample giver to Cantor, but not to Wiles, is obligated to identify where the challenged proof went wrong. But in crankland, Cantor’s proof is unfathomably complicated, tricky, devious, and impossible to understand.
Seriously, it seems that you have never ever taught mathematics to anyone whatsoever! You are the prideful condescending know-it-all who extrapolates from your extremely high comfort level with Cantor’s proof to everybody, including the cranks. You say Cantor diagonalization is just like even-versus-odds! Well, it just doesn’t work that way. High schoolers routinely think sqrt(x+y)=sqrt(x)+sqrt(y), freshman calculus students choke on the chain rule, and a host of other trivialities they just can’t wrap their head around. Good teaching requires half-thinking in nonsense-world, half-thinking in sense-world, and walking your students from the one to the other.
Meanwhile, 100% in sense-world, there is the 100% true statement that to refute theorem X, it suffices to give a valid counterexample. There is no requirement to identify where an alleged proof of theorem X went wrong, beyond the social/psychological/etc niceties of doing mathematics in general. Since this is 100% truth, and fairly trivial to boot, those who claim otherwise repeatedly are crackpots.
This is more a theorem than a definition in most treatments of the natural numbers.
You can, of course, define the natural numbers as the set of finite decimal expansions, and define the basic operations accordingly. You have a bit of work cut out to verify induction. I vaguely recall that Abian (yes, that Abian), used this approach in his introductory textbook, and also defined the reals using decimal expansions.
You can also define decimal expansions as finite, without proving that they actually exist for all natural numbers. That’s a bit too much of a cop out to count in my book.
The reason I am quibbling is while most students sort of learn math, they never ever learn the status of the basic assertions and algorithms that constitutes grade school arithmetic. The textbooks themselves do a poor job. The worst are those claiming to prove things while merely giving a plausibility argument.
“Seriously, it seems that you have never ever taught mathematics to anyone whatsoever!” In fact, I have taught this proof to impoverished urban teenaged High School students. Most of them understood. About the cranks, I’m tempted to ask: “Are You Smarter than a 9th Grader?” Except they are not. In the cases dealt with here by Mark CC.
Anyone want a shot at this, just posted this evening? The PDF may be downloaded from the abstract page linked-to here.
http://arxiv.org/abs/1002.4433
Addressing mathematical inconsistency: Cantor and Godel refuted
Authors: J.A. Perez
(Submitted on 24 Feb 2010)
Abstract: This article critically reappraises arguments in support of Cantor’s theory of transfinite numbers. The following results are reported: i) Cantor’s proofs of nondenumerability are refuted by analyzing the logical inconsistencies in implementation of the reductio method of proof and by identifying errors. Particular attention is given to the diagonalization argument and to the interpretation of the axiom of infinity. ii) Three constructive proofs have been designed that support the denumerability of the power set of the natural numbers, P(N), thus implying the denumerability of the set of the real numbers R. These results lead to a Theorem of the Continuum that supersedes Cantor’s Continuum Hypothesis and establishes the countable nature of the real number line, suggesting that all infinite sets are denumerable. Some immediate implications of denumerability are discussed: i) Valid proofs should not include inconceivable statements, defined as statements that can be found to be false and always lead to contradiction. This is formalized in a Principle of Conceivable Proof. ii) Substantial simplification of the axiomatic principles of set theory can be achieved by excluding transfinite numbers. To facilitate the comparison of sets, infinite as well as finite, the concept of relative cardinality is introduced. iii) Proofs of incompleteness that use diagonal arguments (e.g. those used in Godel’s Theorems) are refuted. A constructive proof, based on the denumerability of P(N), is presented to demonstrate the existence of a theory of first-order arithmetic that is consistent, sound, negation-complete, decidable and (assumed p.r. adequate) able to prove its own consistency. Such a result reinstates Hilbert’s Programme and brings arithmetic completeness to the forefront of mathematics.
From your summary Mark it seems that the individual in question had a valid argument, when he says “If it were possible to reorder the rows of T in such a way that a rational antidiagonal could be defined, then we would have two contradictory results: the set Q of rational numbers would and would not be denumerable”. However, he did NOT have a sound one, because he had a false premise in that you could re-order the rows.
It seems simple enough to me. If you re-order the rows, then we have a new number produced by Cantor’s procedure. E. G. If we have
0 1 0 1…
1 0 1 0…
1 1 1 1…
0 0 1 1… as our inital table, which produces .0011… as the number not in the table, then a re-ordering which produces the table
1 0 1 0…
1 1 1 1…
0 0 1 1…
0 1 0 1… produces .1111… not in the table.
In other words, a re-ordering of a table actually produces a new table, which produces ANOTHER counterxample, which even further strengthens Cantor’s proof (psychologically speaking, not mathematically).
I just read Jonathan Vos Post’s link to http://arxiv.org/abs/1002.4433 and I found that to be really interesting — I’ll withhold comment out of fear of being labeled a crank.
@128 (Mark C. Chu-Carroll) :
You need to lay off the crank juice. You’re going off the deep end lately. Each natural does have finite decimal representation if you take a finite amount of them at a time. Take any ONE natural, and yes, it will have finite digits. Take any TWO naturals, again they will need up to X digits where X is finite and so on. But for infinite naturals, then you need infinite digits. So your objection to the progression in post 127 is flawed. The progression is fine as long as it continues infinitely.
Obviously, you don’t understand anything about infinite sets. Following on what I’ve just said, you can use these different views to have different representations. You can take finite representations or infinite representations. The infinite representation is one where you can never describe it by itself. It is always part of a bigger whole. For example, the reals from [0,1) can be viewed as its position within the infinite set. As such, you need ALL of the elements in the set to define any ONE real.
So integers can be independent of all other integers and as such can have finite representation. But reals can NEVER be independent of other reals. You always need all of them even if you only write one of them down. In essence, you are always taking infinite reals and this is why they have infinite representation just like integers have infinite digits if you take the entire set of naturals.
When you ask “What natural number will produce 1/3 as its mirror image?”, it’s clever, but ultimately demonstrates how clueless and a crackpot you are, especially considering how you berate others on the topic when you know nothing about it yourself.
Just to clarify, the part about reals being their position within the infinite set, I meant that the value can be viewed as a percentage of infinity itself.
I am hoping Jonathan Vos Post (or Mark) is still reading this post, because I would be interested in his thoughts on the paper by J.A. Perez in arxiv to which Jonathan provided a link. I can’t find the flaw in Perez’s basic argument. In a nutshell, Perez is arguing that proofs by external (or conventional) contradiction take the following format —
¬P => Q1 => Q2 => … => Qn => ( R AND ¬R )
but proofs by internal (or self-referential) contradiction take this format —
¬P => Q1 => Q2 => … => Qn => P
where some of the conditionals are possibly biconditionals, and Perez states that this makes a big difference when evaluating the syllogism.
I can’t see where Perez is wrong, but then again, I’m just a software developer and not a mathematician. I know just enough to follow along, but not enough to find the flaw.
I’d really be interested in hearing Jonathan or Mark’s thoughts on Perez’s paper. On one hand it would be pretty cool if some no name mathematician came along and refuted Cantor’s nondenumerability proofs, negated Gödel’s incompleteness theorem, provided a proof of the completeness of first-order arithmetic, and reinstated Hilbert’s Programme. However, I’m guessing this is kind of unlikely.
Perez’s arguement also seems to lead to the exclusion of transfinite numbers, which I find even more disturbing than losing Cantor’s paradise, because I kind of like pi and the roots of many higher degree algebraic expressions.
Anyway, I’m hoping one of you smart mathematician types will address this paper.
@137:
I will get around to posting something about that paper. I just haven’t had the time to do it yet.
Excellent! Thanks Mark.
@137
You’re confusing transfinite and transcendental.
Also, roots of polynomial expressions are not transcendental, but algebraic.
Anyhow, as Hilbert said, No one shall expel us from the paradise that Cantor has created for us.
You’ll be much better off if you spend your time learning the theory rather than reading cranks. Don’t assume the guy is sane just because he knows how to type a long paper in TeX that looks superficially reasonable.
Thanks Ivan, and you’re absolutely right, I was confusing transfinite and transcendental. Also I should have known that the roots of polynomial expressions are algebraic and not transcendental. At one time I did know this, but apparently had forgotten it somewhere along the line. However, there’s nothing like publicly screwing up to help remember things in the future. 🙂
As for reading the papers of cranks, I can’t help it — I find them interesting. I found Cantor’s argument pretty interesting too when I first read it, but if I can’t defend that argument the I don’t really know it. So I believe I am learning something trying to find the flaw in the crank’s logic.
For example, I’m guessing the flaw in Perez’s argument has something to do with his assumption that Cantor’s proof is self-referential when it really isn’t, but that is just my layman’s guess. A second posibility is that Perez’s limits on self-referential logic is too restrictive/non-standard. I’ll wait to hear the verdict of experts, but if my guesses are correct then, hey, I am learning something. If I’m way off base, then I’m sure I’ll still learn something as I read why others (smarter than me) think Perez is wrong.
I think you’ll find that Perez is not even wrong. Being wrong entails having a coherent logical argument in the first place.
I get that– I also find them interesting, though perhaps not in quite the same way that you do.
I suspect you’re likely to learn as much math from studying crank arguments as you would learn of a language by listening to the ravings of a mad man.
I’m a little worried that you seem to find equal amounts of logic in Cantor’s argument and Perez’s “argument”, which is why I would again gently suggest that your time is better spent learning basic theory and terminology. I suspect that if you became more comfortable with how proofs by contradiction work, you’d see how little sense Perez makes.
I stumbled across a strange thing, trying to construct a diagonal on the full infinite set of all possible combinations of zeroes and ones.
If you choose to start with elements of only zeroes, exept a single one on the place of the diagonal you will spot something strange.
1000…
0100…
0010…
0001…
…
You are already running to infinity in both directions.
No way to get out of this.
Since the “diagonal” is not dependent on the order of the data, it might not be possible to construct a diagonal this way…
cranky, but I still can’t see where I went wrong 🙂
MarkCC said…
Here’s the problem: you’re constructing a chosen rational
number. That is, you know what rational number you’re re-ordering the
rows to create. Since it’s a rational, it’s got to be in the table. And since
you know what rational it is, you’ve got to know what row in the table
it’s going to be. So go look at that row.
____________________________________________________
Mark is assuming that the rational number is going to be in the middle of the table when it could be the last.
Suppose we construct the table like this…
0.6
0.76
0.776
0.7776
…
Then our diagonal is going to be 0.666…
Then we can change all the 6’s to 7’s and we get 0.777… which is a rational number (=7/9)
When we look up 7/9 in the table we will find it. (it is the last number on the table)