Are The Reals Really Uncountable?
A discussion of Cantor’s famous diagonal method
Georg Cantor discovered his famous diagonal proof method, which he used to give his second proof that the real numbers are uncountable. In an earlier discussion I have given the first proof that Cantor discovered years earlier.
Today I want to talk about what I plan to cover this week in my complexity class: the diagonal method of Cantor.
In my teaching experience, students find it hard to believe Cantor’s diagonal method. Perhaps it is my fault, but I have talked to others who teach the same result, and I hear the same comments. The diagonal method is elegant, simple, and is deep. Students usually follow the method line by line, but I am sure that many really fail to get it. Perhaps that it is a proof by contradiction makes it hard to follow? But, they seem to get other proofs by contradiction. Or is the key problem that it is about infinities?
Here is an interesting quote by the logician Wilfrid Hodges:
I dedicate this essay to the two-dozen-odd people whose refutations of Cantor’s diagonal argument have come to me either as referee or as editor in the last twenty years or so. Sadly these submissions were all quite unpublishable; I sent them back with what I hope were helpful comments. A few years ago it occurred to me to wonder why so many people devote so much energy to refuting this harmless little argument — what had it done to make them angry with it? So I started to keep notes of these papers, in the hope that some pattern would emerge. These pages report the results.
You might enjoy his essay—it is a careful treatment of some of the issues that people have in following Cantor’s famous argument.
Let’s turn to prove the famous result.
Proofs
I will give two different proofs that the reals are not countable. Actually, I will prove the statement that no countable list of infinite sequences of 
This is enough because of two observations. First, it is enough to show that the interval ![{[0,1]}](https://s0.wp.com/latex.php?latex=%7B%5B0%2C1%5D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
The first proof is essentially the famous diagonal proof, with a slight—very slight—twist. The second, is a proof based on probability theory.
Consider the following triangular array of bits that has an infinite number of rows:
 |
||
 |
 |
|
 |
 |
 |
 |
row is 
where each 
Our plan is to construct an infinite sequence 
The absence of alternatives clears the mind marvelously.
Thanks to our friends at Brainy Quote.
Next we must make 
But, we must be prepared for the worst case. So we set 
Look at the triangular array again and we see that
 |
||
| |
 |
|
| |
|
 |
| |
This is why we call it the diagonal method. What does this have to do with the reals being uncountable? Suppose that now we have an array where each row is infinite too:
 |
 |
 |
| |
|
 |
| |
|
 |
| |
We want to construct a
| |
||
| |
|
|
| |
|
|
| |
But, we just constructed a
In this proof we use the probabilistic method. We just pick a random 
Let 
Clearly,
![\displaystyle \mathsf{Prob}[ E_{n,i} ] = 2^{-n}.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathsf%7BProb%7D%5B+E_%7Bn%2Ci%7D+%5D+%3D+2%5E%7B-n%7D.+&bg=ffffff&fg=000000&s=0&c=20201002)
The key is the event 
The probability of
![\displaystyle \mathsf{Prob}[ E_{2,1} ] + \mathsf{Prob}[ E_{3,2} ] + \dots](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathsf%7BProb%7D%5B+E_%7B2%2C1%7D+%5D+%2B+%5Cmathsf%7BProb%7D%5B+E_%7B3%2C2%7D+%5D+%2B+%5Cdots+&bg=ffffff&fg=000000&s=0&c=20201002)
which is equal to
Thus, the probability of the complement event 
But, 
for any 
Even though the methods look different, if you look closely you would
notice that they both have Cantor’s diagonal method at their heart.
Open Problems
There are many other papers on alternative approaches to proving the reals are uncountable. Matt Baker has a great explanation in his paper: definitely take a look at his version. It is closer to the first proof that Cantor found.
Did you always believe the classic proof that the reals are uncountable? Or did this discussion help? I hope it increased your understanding, rather than decreased it.
Trackbacks
- Some concepts « Qleafriver's Blog
- Some concepts « Qleafriver's Blog
- Tweets that mention Are The Reals Really Uncountable? « Gödel’s Lost Letter and P=NP -- Topsy.com
- uberVU - social comments
- Biweekly Links – 01-25-2010 « God, Your Book Is Great !!
- Does Cantor’s Diagonalization Proof Cheat? « Gödel’s Lost Letter and P=NP
- What If Cantor’s Proof Is Wrong? « Gödel’s Lost Letter and P=NP
- Thanks For Sharing « Gödel’s Lost Letter and P=NP
- Diagonalization Without Sets | Gödel's Lost Letter and P=NP
I head the simple diagonal proof first at a short fast lecture for High School students, and immediately believed it. Next time I heard it was in a lecture in the course Introduction to Discrete Math, where I heard no complaints by the students (this could be because of lack of interest by the students).
To a student it may simply seem as though the proof by contradiction shows that a particular choice of enumeration fails, and it may be difficult to internalize that the proof does not depend on the choice of enumeration, i.e. every enumeration fails. It’s certainly a very large set to quantify over.
Here’s a “proof” using description complexity: Consider any enumeration of infinite binary sequences. Then the first N bits of any sequence in the list can be described using O(1) + log(N) bits for any N, while it is easy to see that for any description system, there is an infinite sequence whose prefixes require N – log(N) bits to describe infinitely often.
@Rahul: It seems like the first N bits of an arbitrary sequence in the enumeration are likely to require N + O(1) bits to describe, not log(N) + O(1)…unless you are assuming that the enumeration is a computable enumeration? Or am I missing something?
I was thinking of a description system of the following type: you’re allowed to describe substrings by tuples of the following form: (c, i,j), which means the substring between the i’th and j’th bits of the c’th string in the enumeration. As long as 0’s and 1’s are present in the enumeration, you can describe any string in this way, and just as with Kolmogorov complexity, a counting argument shows there are strings that are hard to describe.
I guess my point is that computability is a side-issue, this sort of argument can be applied with any description system…
When I first learned this proof I knew that it was correct but it didn’t feel “solid” like the simpler proofs of simpler theorems I’d seen thus far.
In the interest of improving pedagogy I’ve tried to elaborate in detail my reactions when I first saw this proof; it’s hard with a couple decades’ time to get it 100% accurate (and it is all embarassingly “wrong” to my eyes now) but here goes.
From what I recall of my thoughts at the time I think the stumbling block was that I didn’t really understand the full import of what the assumption of the set of sequences S being a “full enumeration” really meant.
So in stepping through the proof the diagonalization procedure clearly worked: given a countable set S of 0-1 sequences you could clearly construct an s NOT in S by diagonalization.
I understood this meant S wasn’t actually a complete enumeration of sequences.
If you really get what it would mean to be a “complete enumeration” this is enough.
If you don’t quite get it the following reasoning is pretty “obvious” and attractive:
Treat S as a “candidate” complete enumeration, and rename it S(0).
Clearly given S(0) we can use diagonalization to get an s(0) not in S(0); so S(0) is actually a “defective” enumeration.
Create S(1) = S(0) U { s(0) }. This is a new, “better” candidate enumeration. But, diagonalization yields s(1) not in S(1), so now we go to S(2), etc.
We can clearly do this ad infinitum, so let us write S’ = lim n->infinity S(n).
By this point we already can prove (easily) that if lim n -> infinity S(n) exists it is the U n = 0…infinity S(n) , which is a countable union of countable sets and thus also countable.
I don’t think at the time I ever sat down and worked through my “objections” in this much detail.
I do remember that much of my feeling that the result wasn’t really “solid” came from feeling like you could patch up “S” to be a complete enumeration; it took a long time to really settle in that when you make assumptions you actually need to take them completely literally.
What’s interesting now is how pernicious the above line of thought is. If you don’t really accept the contradiction of the completeness assumption as proving the difference in cardinality you’re powerless, I think, to go further.
On the one hand S’ is clearly not complete, either; you can diagonalize on S’, and go through more rounds of taking the limit of S'(n), S”(n), etc.. This is about where you ought to get discouraged, and start to understand the full import of the completeness assumption.
On the other hand if you don’t take as given that | N | < | R | you can't really convince yourself by iteratively adding elements to S (to try and "patch" it); all of the operations you'd try seem to increase the size of S by either finite or countable amounts, which leaves the size of S countable. Without taking for granted that you're trying to shove uncountably many items into a countable set it's hard to see how you'd wind up with more than a countable set.
I can see particularly bright cranks inventing entire theories of recursive limit-taking (essentially reinventing the cardinality theories they're trying to disprove): you'd define a 1-limit as a single limit of one of the S(n) sequence, a 2-limit as the limit of a countable iteration of 1-limit-taking, a 3-limit as the limit of a countable iteration of 2-limit-taking, etc.; that way lies madness.
So to Qiaochu: in my case my initial discomfort wasn't so much "choice of enumeration" as it was not quite fully getting what "enumeration" meant, which feels different.
The key observation is trivial: if {t} differs from the start of a row, it certainly is different from the whole row.
Except that is not true if you are thinking of the rows as a simple binary representation of the reals…
What if the first row is 0.10000… and your constructed t were 0.011111… ? These are the same real number, even though they differ in every digit. (This is also a bug in the Cantor proof as it is usually presented; in base 10, 0.1 is equal to 0.099999… Just because two reals differ in one place in their representation, it does not mean they are different reals.)
This flaw is reparable, of course, but it is takes at least as much verbiage as the original proof. Put another way, it is not self-evident that “the reals in the interval have the same cardinality as the set of all of infinite {0}-{1} sequences”. You have to prove that as a lemma.
Was only thinking of them as strings. I thought that was clear. Good point.
I find it’s much more intuitive to show the diagonal proof that there is no bijection from P(A) to A for any set A. Note that this fact holds even when A is finite.
Since the set of all real numbers has cardinality |P(N)|, it obviously follows that |N| < |P(N)|.
Is it obvious that the set of real numbers has cardinality |P(N)| ?
It is a true statement, of course. But my claim is that the shortest proof you will find is at least as long and complex as the diagonalization argument itself… And this subtlety is almost always glossed over when people discuss “simple” proofs that the reals are uncountable.
Frankly, the real numbers are just annoying. Definitely the “work of man”, as it were.
The set of real numbers has the same cardinality as the set of continued fractions that don’t end in 1. But this is a proof that requires “work.” For a proof that doesn’t require work you should just appeal to Cantor-Schroeder-Bernstein.
one of the main reasons that i think that budding logicians might have difficulty understanding cantor’s proof is that it smudges several things together that aren’t understood very well at the undergraduate level unless they’ve been treated properly:
* what a proof by contradiction actually contradicts, and why one should believe a proof by contradiction.
* the construction of the reals
* the equivalence class construction that places the reals in correspondence with decimal representations.
without seeing (for instance) dedekind cuts and defining the relevant equivalence classes, all the usual diagonalization does is show that there is some string outside of any countable set of strings over the same alphabet. which is neat regardless.
s.
I never claim my suggestion is the shortest proof. Instead it is the longer one. However, when proving that |A|<|P(A)| for any every set A, we can focus on the correctness of the diagonal proof. This is to clarify that the diagonal proof technique has nothing to do P(A) is uncoutable (i.e., "the work of man") or not. The key is that the set A is always strictly "smaller" than P(A). See Terry Tao's post below for more interesting examples in mathematics.
And showing that |P(N)| has the same cardinality as |R| is just as hard as showing that we can use infinite binary sequences to represent the real numbers. Don't we have to assume this "fact" also in the original proof? Of course, everything can be shown formally and nicely using set theory, but again that might be again argued to be the "work of man". But if one keeps denying the existence of "uncountable" or even "infinite" sets, he loses a big part of modern mathematics.
The easiest way I know to avoid the 0.1111… problem is to work in at least base 3. When building your missing element, map 0 to 1 and anything else to 0. That gives you a missing element which has a unique base-n representation.
That probability-based proof can actually be done concretely, to provide CS people without abstract math background more intuition about why diagonalization “works.” This is a teaching trick I learned from Jack Lutz.
Put a handful of boolean functions on the board, and then have students literally flip coins, to generate a random bit string. Show that the bit string differs from the diagonal of the matrix of the boolean functions. Encourage the students to “fix” this, by changing the functions, or moving them around, so the bit string does not diagonalize the functions. Then show how easy it is to diagonalize the “fixed” functions.
It’s not a big leap to see that if you can diagonalize against four or five functions so easily, you can diagonalize against countably many. It’s a way of making an abstract argument hands-on.
I was thinking if I had to teach the diagonal method and one of my students did not understand it, I would have no idea what to do. Because I don’t understand at all what is difficult to understand here; I guess I should read the article you linked to.
I’ve always ‘understood’ the proof, but never quite accepted it. My main issue is generally with all logic formulas with infinite number of elements. As far as I can remember, 1st order logic has a grammar for formulas of arbitrary length, but semantics and proofs are defined for finite length formulas.
I don’t know from the “fundamentals of math” point of view what the latest position regarding proving infinitely long formulas is…
So I’ve always raised an eyebrow when someone wanted me to imagine an infinitely long row, an infinite sum, etc. as sub-formulas of a proof.
I might not be the best person to guess what is with this proof that people find disquietening; but given that I was once among the category of disbelievers, I think I can probably guess where do these troubles arise from. I should not say guess though, I should say I know (but to be on a safer side let me use the word guess [:)])
I would say that it is because it is very hard to believe (or let go) of your childhood notions that there is some “absolute” infinite. Our conception of infinity (because of our assumption about infinite “size” of the universe, could be our conceptions of “God” and other things) fix in our mind an impression of infinity.
When people like these encounter Cantor’s Proof for the first time – which is so easy to understand – we think that its crazy!
We share the opinion of Leopold Kronecker’s and Hermann Weyl’s. Infinity greater than infinity looks like a child’s attempt in a game of who can name a bigger number wherein some child says something meaningless like “infinity raised to infinity”.
Therefore, people like me, being dense, insist that Cantor’s proof though not as bad in look appears like as though it were echoing the meaningless utterances of a child. We think we know better.
But then, sinks in Hilbert’s statement – “No one shall drive us out of the paradise that Cantor created for us”. It is not (and should not) because an eminent mathematicain said it – it should be because we come across some other examples saying the same thing in a rather easy to understand setting – things like this post or maybe something like a measure theroetic proof.
Then there is a ladder full of things like Surreal Numbers, Halting Problem etc which help reaffirm these notions.
Finally I would point out that there are some other reasons for believing this – like the too abstract nature of infinity which drives us crazy. Also there are some slight errors in some well known science popularizations like one in George Gamow’s one two three..infinity (I do not remeber exactly where – it was something related to Cantor’s work; or could be I am wrong here) which can confuse people.
Just my thoughts
-Akash
“Infinity greater than infinity looks like a child’s attempt in a game of who can name a bigger number wherein some child says something meaningless like “infinity raised to infinity”.”
To the contrary, in my view, this is a mature point of view. The “childish” – that is unreflective – point of view is that “infinity raised to infinity” is meaningless.
As Poincare emphasized (even though he detested set theory) … “to a reflective mind …”
I’ve wondered whether the diagonal argument or the $latex|\mathcal{P}(A)| > |A|$ argument (ala. Russell’s paradox) is easier to understand. The second seems cleaner as a final argument for someone to remember. (that is, I think it is the “book” proof for the uncountability of the reals. Especially since it has such strong and direct connections to Russell’s paradox and the halting problem) However, it seems remiss not to also present Cantor’s diagonalization argument, if for no other reason than the historical context of why the $latex|\mathcal{P}(A)| > |A|$ argument is called a diagonalization argument.
Cantor’s theorem is part of a general family of results that show that the class of all “potential” solutions to some problem is far larger than the class of “explicitly describable” or “actually solvable” solutions, e.g.
0. The set of real numbers is significantly larger than the set of rationals; most reals cannot be expressed as the ratio of two integers. (Obvious now; a shock to the ancient Greeks.)
1. The set of algebraic numbers is significantly larger than the set of numbers solvable by radicals; in particular, the general quintic cannot be solved by radicals. (Again, a shock when Galois showed this.)
2. Most real numbers are not constructible, or even enumerable by a fixed enumeration. (Cantor’s shock.)
3. Most statements that are true in arithmetic, are not provable in arithmetic. (Godel’s shock.)
4. Most sets of natural numbers are not decidable, or even recursively enumerable. (Turing’s shock.)
5. Most PDE and ODE are not explicitly solvable, and in fact can be quite chaotic. (Not sure who to attribute this principle to: Poincare’s shock, perhaps?)
6. “Most” Diophantine equations are undecidable. (Matiyasevich’s shock.) Similarly for the word problem in groups, etc., etc.
7. Most problems whose solutions can be verified in polynomial time, (conjecturally) cannot be solved in polynomial time (not so shocking now, I guess because the novelty has worn off :-).
Once one appreciates this type of distinction, I think a lot of the philosophical resistance to Cantor begins to fade away. But it is quite possible not to be aware of this distinction for quite a long time. Note for instance that undergraduate maths education largely focuses on problems with explicit solutions and constructibly enumerable answers; the realisation that most problems are unsolvable explicitly and not enumerable explicitly tends to come rather late.
My impression is that, after having gone through a typical calculus sequence, students believe the following things:
1. Most equations have solutions which can be expressed in terms of elementary functions.
3. Most series have closed forms.
2. Most integrals have closed forms.
For some students “most” may even be “all”! So I think it’s extremely important to rid students of these illusions before we even talk about any of these other far more fundamental results.
To what extent can we overcome all the important negative results cited by Tao if we introduce suitable concepts of approximately true as in all reals can be approximated by rationals to arbitrary accuracy, and/or probable truth, as in random 3-sat or random verification? Are there other methods of bypassing these negative results, at the price of accepting an occasional falsehood? I am thinking of physical contexts such as numerical mathematics as practiced in numerical relativity for example. Many more examples could be cited, but I am asking if there are any general theorems or summary statements that apply here, other than 1=0 implies everything, or GIGO.
In the more restrictive context cited by Yuan, i. e. elementary calculus, numerical techniques come close to providing a universal solution for most practical problems.
But I am more interested in something like random Q-sat which attacks the problem of truth or falsehood in a reasonably comprehensive formal language.
I can’t really say too much about the reals, but i like my proof that the integers (counting numbers) are uncountable. As shown by experts, every integer can be expressed as a porduct of primes. So just consider the primes—and experts have shown they are an infinite set. So, write down the set of primes, and construct the power set. By Cantor’s theorem (or method) we know these can’t be counted. So, putting the subsets of the power set of primes in 1-1 correspodnace with the integers, we show the integers are uncountable. (of course, there’s a flaw in the proof, but i like it).
That’s pretty clever. I think what they’ll mention as the flaw is that no natural number uses infinitely many primes. So it isn’t really the power set. However, I don’t think that argument holds water. Infinitely many numbers will indeed use infinitely many primes.
It comes down to nothing more than a battle of definitions. As long as they push for a 1-1 (finite) correspondence, you’ll have to use an intermediate step where you map multiple naturals to a single real. This is because you need something to get around the finite digits of naturals. A surjection to the power set is what you need. I think your proof can do this.
Nice work Terry. This post really puts the things in perspective.
A few quick questions though.
I have never come across Post’s Model in my undergraduate studies. I just studied in Feynman’s Lectures on Computation someplace that it is also a very robust model.
But why neglect Post’s Model? Is Turing’s Model really easy to understand as opposed to his Model? Or is it because Turing’s Model got catapulted to fame maybe because it was published earlier than Post’s Work.
I don’t really know much about these things, but I think Theoretical Computer Science does not lay much stress on the Computability Part. Is it just me or is it because the field has been more or less “throughly” investigated? Or is there some other reason?
In case you (or anybody else) finds time I would really love to see these questions answered.
Thanks
-Akash
Maybe antoher reason for people not to understand or accept this proof. I felt once embarassed about this proof (even though I already accpeted it before) because of the following: Why cannot you use the same argument with decidable sets? You enumerate all the decidable sets (of integers) as binary string (the i-th bit of the string telling you whether the integer (i-1) belongs to the set). Then the set A is defined by the diagonal method. Why is this set decidable: simply because to decide whether i belongs to A, you test whether i belongs to the i-th set of the eumeration and you are done.
This example is here not because everybody may have it in mind when one is taught the diagonal argument, but because it illustrates to my mind a problem people can face. To correct my “proof”, you need to be more precise on the concepts you are using. In the same way, I think it may be a good idea, for student to really understand how and why it works, toask them to formalize the proof with the actual definition of being countable.
To do that, you suppose that infinite binary strings are a countable set, that is you have a bijection s between the natural numbers and those strings. Then, if you denote by s(i)_j the j-th bit of the image of i by this bijection, you can consider the string w defined by w_k = 1- s(k)_k for every k. The string w is a binary string, so it should have a pre-image by s. Let denote by i its pre-image. Then w_i=1-s(i)_i, but at the same time w=s(i), so w_i=s(i)_i: contradiction.
Of course it is the same proof, but I think it can help students who do not accept or understand the proof, and for whom the the notion of enumeration of all the strings is not easy. It is a good idea of course to show the argument by writing some strings and physically show the diagonal. That way people really see what we are doing, and then give the proof as I wrote it above to show there is no flaw in it.
On the other hand, I agree with Nemo that it can sometimes be hard to explain students that there are as many reals in [0,1] as infinite binary strings.
I see two problems for understanding the diagonalisation argument.
I think both might be caused by the actual infinity interpretation.
A)The first problem is based in an argument which is surelly flawed but might appear naturaly in starters.
1.Diagonalisation argument is based on an analogy with countability proofs.
2.Countability proofs are of the type:
–i give you a rule for generating a hamiltonian path in an infinite digraph, the naturals (start with the unit and add one at each iteration).
–i give you a rule for constructing a hamiltonian path in the set i want to count (that is necessary and might be the hard part of the proof),
–i give you a bijection”.
Nothing weird. No one has problem to understand this.
3.With this in mind you start explaining the diagonalisation argument:
–i give you a rule for the hamiltonian path of the naturals, N. Ok.
–i give you the set of all the posible strings, S (but not a rule for constructing the hamiltonian path on it !). Mmmh…¿ok.?
–then I suppose there is an N to S bijection and by constructing a second bijection (within the supposed hamiltonian path in S represented by the diagonal and bottom string) i extract a contradiction. Ok.
But the problem is not in the contradiction, but in what it is presuposed for extracting it, due to the analogy: am i not using an object (the hamiltonian path trough the set of all posible strings) without having even prooved it could exist ?
So even if this argument is flawed, at least we must recognise that the diagonalisation argument is not as clean as the one with which the analogy is built !
B) Now assuming above argument is flawed, the second problem might appear, is that with the actual infinity interpretation, it is not obvious that the bottom string will not appear in the hidden part (the etc… part) of the list of all possible infinite strings.
IMO it is better to think about it as a neverending process and rephrase it as follows:
“As well as until now (after a finite number of iterations of the process) the finite bottom string is different from all the others in the list as you can see, by the rule of construction, won´t it be different in the next interation ?. and in the next ? and so on….
What about the probabilistic proof? Does that seem more intuitive or less?
To my mind, the probabilistic proof do not show why the result is true. For me, it appears as somehow magical. But it is hard to find any “flaw” in the proof (of course there is not any!), even an invented one.
A good point of this discussion for me is that it gives several proofs and several ways to present some of the proofs (for example, I find Cantor’s original proof very interesting). So one can teach this result with a proof, and depending on the problems the students have to understand it, one can try to give them other proofs. Maybe you can increase the number of satisfied students doing so!
I see a possible problem with the probabilistic proof. First, what is meant by E_2,1? Based on your notation, I take that to mean the event that t = s for the second row which has 2 elements. This agrees with Prob[E_2,1] = 1/4. But what about the first row? It has probability 1/2, which makes the total probability 1, and the complement, 0, suggesting that t = s for some row.
Drewby Scoot
Thanks for the comment. I think the point is that we are just trying to show that a random string is different. The big or of many events is the probably it is different. So need only look at the second row, does that help.
I read about Cantor’s proof in George Gamow’s wonderful “One, Two, Three … Infinity” and I guess I understood it at the time (high school). Before that I had somehow decided intuitively that there were more reals than integers, but also more pairs of integers than integers.
These days though I’m not so persuaded that there’s an uncountable set of reals. The diagonal proof presupposes that 0.{d1,d2,d3,… d_infinity} actually exists as a real number. Is there a completed infinity? Cantor’s assertion that there is one is, in some ways, much more revolutionary than the diagonal proof. After all, the diagonal proof holds even for finite sets, e.g. it works in ZFC without the axiom of infinity.
Do you know about predicative arithmetic? It’s a system in which even Peano arithmetic is considered bogus. Those crazy enormous numbers that can only be written symbolically (like with Knuth’s up-arrow notation): they are fictitious entities, they don’t really exist, the “proofs” that certain Turing machines halt after that many steps are bogus (because they rely on impredicative axoms) and those Turing machines don’t actually halt at all. Predicative arithmetic is even weaker than primitive recursive arithmetic, but despite this, most practical mathematics can be proved in it (maybe not the Knuth-Bendix algorithm, hmm).
You can read about it on Edward Nelson’s homepage, and there is also a downloadable book there: http://www.math.princeton.edu/~Nelson/papers.html
The slides for “Hilbert’s mistake” are a good place to start: http://www.math.princeton.edu/~Nelson/papers/hm.pdf
Where you write “Thus, the probability of the complement event \bar{E} is 1/2” I think you mean that “Thus, the probability of the complement event \bar{E} is at least 1/2”.
Also, I’ve found that the diagonal argument can be much harder for beginners to accept when the argument shows that the halting problem is undecidable. Most people don’t try to enumerate the real numbers in their spare time, so being told that this is not possible may not be as shocking as being told that there are computational problems that are inherently unsolvable.
If E has prob 1/2 then its complement has prob 1/2.
Yes, I think that is what is meant. All we need for the probabilistic method to work is to show that we have a non zero probability, so probability of \bar{E} being greater than half is enough for us.
I actually take DTML’s approach, but stated positively like this:
For every mapping f from a set A into its powerset P(A), we can construct a subset D of A that is not in the range of f.
Namely D = {x in A: x is not in the set f(x)}.
If D were in the range, then there would be an element e such that D = f(e). But then e \notin D e \notin f(e) e \in D, so we have a statement that is equivalent to its negation. That can never happen—if it did the Universe would vanish in a thunderclap, or not exist to begin with. (Proof by cosmogony rather than contradiction.)
When A is finite, we can see D emerge with our own eyes. But actually, nothing about this cares whether A is finite. The notation for D is equally constructive regardless of what the given A is. Hence it works when A = N. Thus P(N) is uncountable.
Then I go on to relate P(N), or equivalently P({0,1}*), to the set of languages over {0,1}, and to the set of branches of the infinite binary tree. If I mention the real numbers at all, I handle the technicality noted by Nemo by saying that the duplication applies only to (dyadic) rationals and those can be counted separately. I don’t have to say “cardinality” or draw an infinite square grid and its diagonal. The final dividend is that when e comes from the enumeration of Turing machines M_e, and f(e) is the language L(M_e), the same D pops out as the prototypical non-r.e. language.
Oops, my equivalence arrows got eaten as HTML codes. Using the syntax for embedding LaTeX in comments which I gave here, the contradiciton-line is:
Oops, my equivalence arrows got eaten as HTML codes. Using the syntax for embedding LaTeX in comments which I gave here, the contradiciton-line is:
The general theme of “mathematical shocks and how students get over them”, which very often manifests itself as “the answers to some mathematical questions aren’t explicitly and efficiently constructible” is a an ongoing theme of Dick’s blog; going back in time we have in recent months the December 14, 2009 The Descriptive Complexity of Solutions; the November 25 2009 What Are Proofs For Anyway?; the October 22, 2009 Helping Wall Street Cheat With Theory; and July 13 200 SAT Solvers: Is SAT Hard or Easy? … and there are many more.
So this post is mainly fan mail … this class of problems won’t soon be exhausted, and so I hope the columns upon this theme keep coming!
Here are three more daunting problems that broadly belong to this class.
1. Forward error-correction codes that approach the Shannon limit (like turbo codes and LDPC codes) formally are NP-hard to optimally decode … and yet in practice, these decoders work fine. Why is this?
2. Quantum state-spaces formally are exponentially large, yet in practice, compressed tensor network representations of them suffice for practical simulation; thus quantum simulation formally is NP-hard, but in practice often requires only polynomial resources. Why is this?
3. Biological dynamical systems are “Avogadro”-large and on the molecular scale their dynamics are generically chaotic and/or quantum mechanical. Yet in practice homeostatic dynamics prevails (e.g., ova successfully grow to be embryos, then infants, then children, then adults). Why is this? How can we describe it efficiently? And how can we apply these insights in healing?
So, please keep these columns coming … their wonderfully pleasing unity-of-theme points always both to wonderful mathematics *and* to practical avenues for addressing what Thomas Jefferson called “the enormities of the times”.
There is a distinction that people miss here. The ontological status of the “reals” described in Cantor’s proof is quite different from the ontological status of everyday numbers like 1, e, pi, sqrt(2) and such.
There are some numbers which are constructable: ultimately you can write down some method of constructing them, and that method has to have a finite length. The set of methods you can write down is countable, so the number of constructable numbers (integer, real, transcendental, rational, whatever) is countable.
Almost all of cantor’s real numbers are unconstructable: you know that they’re in some set like (0,1), but you’ll never be able to talk about the set that has just that one number in it… Pretty funny, huh?
Paul Houle, the number busybeaver(1000) is supposedly an ordinary integer, but it is just as unconstructable as Cantor’s unconstructable reals. There is no recipe for writing it down explicitly.
Yes, there is! Check all Turing machines with less than 1000 states and find the one which runs the longest. That is a recipe, and it is explicit.
When people say that the busy beaver function is not computable, they don’t mean it is impossible to compute any particular value. It is perfectly possible to do this in principle (though whether it’s possible in practice is another matter entirely). There exists a Turing machine which prints out any fixed finite set of integers. What “computable” means is that there does not exist a single algorithm that will compute the entire sequence uniformly.
You can’t test all TM’s with less than n states as some may not halt and you can’t necessarily prove that they won’t and move on to testing the next TM. (there are proofs for very small n.)
So busybeaver(n) is not computable as it is based on another uncomputable predicate; namely Halts(tm). So, there’s no “recipe”.
Fair enough. But it is still true that any particular integer is computable in the sense that I understand it.
I dont know if someone uses this name in teaching a mathematically rigorous course – it is something which author Ian Stewart calls Holmes Principle (Yes, Sherlock Holmes).
The principle is the famous one line utterance of the character “If you have eliminated the impossible, whatever remains, however improbable, must be the truth.”
I dont know how appealing students might find a mention of this principle while studying Cantor Diagonalization but I am sure this principle is worth a good laugh.
“I dedicate this essay to the two-dozen-odd people whose refutations of Cantor’s diagonal argument have come to me either as referee or as editor in the last twenty years or so. Sadly these submissions were all quite unpublishable; I sent them back with what I hope were helpful comments. A few years ago it occurred to me to wonder why so many people devote so much energy to refuting this harmless little argument — what had it done to make them angry with it? So I started to keep notes of these papers, in the hope that some pattern would emerge. These pages report the results.”
Truthfully, you are simply not intelligent enough to understand that you don’t have a clue what you are talking about.
No one shall remove Cantor’s followers from the fools paradise he created for them. – John Gabriel
Sadly, Lipton, you are one of those fools.
The Greeks created the integers. All else is the work of fools. – John Gabriel
You mean if someone is not a Greek, he’s a fool? I feel either your comment is quite racist or “you don’t have a clue what you are talking about.”
“Before you speak, ask yourself: is it kind, is it necessary, is it true, does it improve on the silence?” — Sai Baba
Cantor’s proof is of course sound line by line.
Yet the result jars with students intuitive idea about what could be done to repair the attempt to construct a list of the reals. Which doesn’t mean they’re blockheads – their reaction actually contains an important truth.
(And don’t get me started on why freshmen react to the ‘explanation’ of calculus the way they do.)
There are only a countable number of rationals but way way more reals, and yet the existence of these many reals is demonstrated by producing just one element not in the much smaller countable set.
And the way any normal human being reacts to this is to point out that if this extra element was added to the countable set of things you have constructed in your list you’d still obviously have a countable list.
Which is all true.
The problem is that though you can construct each of the things in your list, the set of all of them isn’t a constructible notion. In the constructible/countable world you don’t have ‘the set of everything on the list’ to hand in order to add the extra element to it and keep everything constructible/countable/listable.
Hope that helped. I have a great natural insight into misunderstanding in maths.
Out of curiosity, what’s wrong with this counterproof?
1. Consider the list of rationals in binary (other bases work just as well).
2. In Cantor’s argument, the diagonal must be different from each row and therefore one digit in each row is changed. This is a clear one to one mapping between the digits and the rows. This is necessary to ensure that there is at least 1 digit different in each row from the newly created number.
3. Back to the list of rationals, there are numbers that have a single digit set to 1 (everything else set to 0). This subset of rows matches one to one with each of the digits. In fact, you can order them so that the diagonal is all 1’s and everything else all 0’s. For each row, the digit that is a 1 indicates what digit that row is mapped to. These rows are all rationals by definition since each single digit must represent a fraction.
4. By the same argument used by Cantor in constructing his diagonal to show how all rows are different by at least one digit, I must now find a digit that is NOT used in order to add other rows of rationals so that this digit can be added to Cantor’s diagonal. But there are no digits that aren’t already mapped. Examples of other rationals are 0.11 and 0.
5. By Cantor’s logic, this means that |Q|>|N|.
But we know that |Q|=|N|. Contradiction.
QED.
My quick thought is that you are not including all the rationals properly. If you do the new number is not rational.
I don’t think you understand what I’m getting at. If there are string that have a single digit set to one, then there will be one of these strings for each digit. So any other string you want to include in your list, you will need to find a free digit to include in Cantor’s diagonal, but there are none.
The new number that you speak of is bogus because it cannot be different than all rows since some rows are not included in the diagonal.
Said another way, tell me which digit will be inserted into Cantor’s diagonal for the number zero (or any other rational that has more than a single digit set to one). Whatever digit you select, I know that there is already a string in existence where that digit is set to one and is already in the diagonal. So it’s impossible for the diagonal to include digits from all rows.
i hesitate to respond because this feels like a troll.
pick the set that you want to diagonalize against and which is countable.
note that the diagonal method works, and will generate a new number not in the list.
done.
if you want to declare the order of your countable set, that order needs to be well-defined. if you don’t, then it’s easy to see that the diagonal method will generate a new number. if you do, don’t then suggest that the method isn’t working against some different set that isn’t the one that you initially started to describe.
s.
I assure you I’m not a troll.
I’ve proven that the diagonal cannot be constructed. You cannot simply say that the diagonal works.
The order does not matter. However, using a specific order makes my counterproof clearer to understand, but is not critical for the validity of the counterproof.
Simply consider all strings that have a single digit set to one. There will be one of these for each and every digit. Order them so that the digit set to one is found along the diagonal. Now consider the string for zero. You need to find a digit to include in the diagonal. But no matter what digit you select, there is already a corresponding string that has that digit set to one and is already in the diagonal. So the zero string will not be in the diagonal.
Simply give me the index of the digit in the zero string that you want to include in the diagonal. That’s the flaw. You can’t do it.
Also, the 1’s don’t need to be in the diagonal. I simply need to show that there is at least one row per digit and I’ve done that (since this is exactly the same process used by Cantor) leaving no extra digits to be included in the diagonal for other rationals. You may order the rows any way you wish. You may even swap the zero string for one of the other strings. It changes nothing as the zero string will now use the vacated digit leaving no digit free for the remaining string for use in the diagonal.
OK, here is what you proved (and it is true!): consider the set of all rationals that are written with exactly one “1” in binary. Then zero does not belong to this set.
I don’t see how you conclude that |Q|>|N|…
The big difference of your “proof” and Cantor’s is that in Cantor’s one does the following: enumerate all infinite binary strings, then there is another but diagonalization. And ONE CAN REPEAT THE PROCESS, which is obviously not the case in your proof. Once you’ve said that zero does not belong to your set, you cannot say “OK I add zero to my set and continue my argument” as zero has not the same form as the other elements.
You’re not making sense. I am constructing my list. I can add whatever I want to it. Are you saying that zero is not a real? You can’t seriously be arguing that I can’t use zero!
The list I am trying to construct is that of ALL reals. I’m only asking you to consider that the subset of strings that have a single digit set to one will map one to one with all digits leaving none for the other reals to be included in the diagonal.
you need to be more careful — the order does matter. this might be part of the reason that you don’t understand the original proof.
in particular, your list should have a first number.
s.
My counterproof doesn’t care about the order because I use all reals. I’m simply pointing out that within that list, there will always be one real with a single 1 for each digit. This is how Cantor builds his diagonal. But there’s a problem. There are more reals.
In fact, Cantor says that ANY MAPPING will work with his argument. Clearly, you disagree with Cantor’s argument.
I don’t usually reply to posts but I will in this case, great info…I will add a backlink and bookmark your site. Keep up the good work!
I’m slightly anxious about the probabilistic proof, though my anxiety could go away if I thought harder. What worries me is that it seems to rely heavily on the countable additivity of probability. And that, it seems to me, relies on the uncountability of the reals (since you can cover a countable set of reals with intervals of total length as small as you like).
To put it another way, suppose I imagine a strange alternative universe in which the reals are countable. Then I don’t see how to justify the countable additivity step. So how can I be persuaded that that alternative universe isn’t the actual universe?
I threw that proof out to see what people think. I have never seen that exact argument before, perhaps I am wrong.
Can we argue like this. Restrict yourself to the case of the first N strings. Then, when you pick the diagonal string of length N it clearly is very unlikely to be equal to any of the first N strings: I did it so only checked some of the bits, but could look at all. So clearly the probability it is equal is very small. Now as N tends to infinity seems that should work?
I think the key is that we do not need countable additivity, but really use a much weaker property. I will try and work out the details.
Thanks for the comment—I wondered why no one asked anything about this argument.
I can see how to prove that
(for every n) (with high probability) random number does not equal any of first n numbers in sequence
but I don’t see how to reverse the quantifiers.
I dedicate this comment to the countless number of mathematics professors
who have tried in vain to persuade students and others of Cantor’s non-mathematical nonsense.
“A few years ago it occurred to me to wonder why so many people devote so much energy to refuting this harmless little argument — what had it done to make them angry with it?”
Answer: It has resulted in morons like you Lipton! One of you is already too much.
http://knol.google.com/k/are-real-numbers-uncountable
Though it is clear that one can extract from the diagonal argument a proof of the uncountability of the real line, I could find no place where Cantor himself explicitly notes this possibility.
The stated objective of the paper (see here and click your way to page 75) is to prove the existence of infinite sets that cannot be mapped bijectively onto the set of natural numbers without using the theory of irrational numbers.
I’d be grateful for any pointers to places where Cantor wrote explicitly that the diagonal method can be used to prove R uncountable.
Cantor used the proof to prove that there are lots of transcendental numbers. He published in 1874 “On a Property of the Collection of All Real Algebraic Numbers.” Cantor used it to prove that the transcendental numbers where dense. This result had been proved earlier by Liouville in a constructive manner. Cantor did this to avoid some attacks that he felt he might get to the main results of the paper.
A great book to look at is: Georg Cantor by Joseph Warren Dauben. It explains quite a bit about the resistance that Cantor faced with his new theories. By the way the proof of 1874 was not the famous diagonal proof.
I read Cantor’s collected works and I read Dauben’s biography some time ago already, so I’m certainly familiar with the 1874 proof. However, what all this reading failed to turn up was any explicit mention by Cantor himself that a diagonal-argument-proof of the uncountability of the real line is possible, not even in the Beiträge, where there would have been ample opportunity, e.g., after the proof that continuum equals 2-to-the-aleph0.
This leaves me flummoxed: (almost) everybody talks about “Cantor’s second proof” but I can’t find it in his own writings.
A link to a long discussion about this subject in another blog:
http://scienceblogs.com/goodmath/2010/02/_so_remember_back_in.php
Well, Set Theory can, of course, conclude from Cantor’s diagonal argument that there can be no 1-1 correspondence between the set of `natural numbers’ and the set of `reals’ as defined in ZF.
However, Computability Theory can only conclude from Turing’s Halting argument that there is no enumeration of the reals by a deterministic Turing-machine.
In other words, given a putative 1-1 correspondence as above – always possible in ZF – Cantor’s argument does well-define a real number in ZF; however, such a conclusion is vacuously true in a number theory outside ZF since the 1-1 correspondence cannot be made algorithmically as needed for the diagonal `construction’ to yield a real number not in the correspondence.
This is a limitation on algorithmic definability in number theory that – like G\”{o}del’s definition of his `undecidable’ arithmetical proposition and Turing’s definition of his algorithmically uncomputable Halting function – has more to do with self-reference than any `uncountable’, only Platonically interpretable, cardinality defined in ZF!
Of course this objection would not survive if ZF could be shown to be consistent!
The need for always maintaining an appropriate perspective when viewing such 1-1 correspondences is emphasised by Skolem in his paper, `Some remarks on axiomatized set theory’, delivered in Helsinki before the Fifth Congress of Scandinavian Mathematicians on 4-7 August 1922 (reproduced on p.25 of Jean van Heijenoort’s `From Frege to G\”{o}del: A source book in Mathematical Logic’).
Whilst discussing the seemingly-paradoxical nature of his (downwards) L\”{o}wenheim-Skolem Theorem, Skolem notes the:
`… peculiar and apparently paradoxical state of affairs. By virtue of the axioms we can prove the existence of higher cardinalities, of higher number classes, and so forth. How can it be, then, that the entire domain B can already be enumerated by means of the finite positive integers? The explanation is not difficult to find. In the axiomatization, `set’ does not mean an arbitrarily defined collection; the sets are nothing but objects that are connected with one another through certain relations expressed by the axioms. Hence there is no contradiction at all if a set M of the domain B is non-denumerable in the sense of the axiomatization; for this means merely that within B there occurs no one-to-one mapping \Phi of M onto Z_{0} (Zermelo’s number sequence). Nevertheless there exists the possibility of numbering all objects in B , and therefore also the elements of M, by means of the positive integers; of course such an enumeration too is a collection of certain pairs, but this collection is not a `set’ (that is, it does not occur in the domain B).’
Cantor and much of metamathematics is a bunch of Bourbakist non-sense and smart people know it. Only left-hemispheric idiots believe Cantor really proved anything. The whole metamathematical games rests on nonsense.
Logic of Actual Infinity and G. Cantor’s Diagonal Proof of the Uncountability of the Continuum
A. A. Zenkin. Source: Rev. Mod. Log. Volume 9, Number 3-4 (2004), 27-82.
http://projecteuclid.org/euclid.rml/1203431978
Cantor’s Diagonal Argument: New Apsect (On the Power Set Argument)
http://alexzen.by.ru/papers/CANTOR-2003/Zenkin%20BSL-2.pdf
Completed infinity and completed infinite sets in extension are contradictory and untenable. That is what we should have learned in the twentieth century after laboring so long under such irrationality.
“Following up this kind of argument, we can, I think, convince ourselves that all the remarkable problems and discoveries of the Foundations of Mathematics, the paradoxes of the theory of aggregates, Russell’s theory of types, with its axiom of reducibility, Cantor’s arithmetic of transfinite numbers, with its insoluble problems such as the “continuum problem “, the problems connected with functions in extension and the multiplicative axiom – all these merely express in one way or another the well-known difficulties which arise when we attempt to treat an infinite process as completed.”
Mathematics and Its Foundations
Author(s): A. G. D. Watson
Source: Mind, New Series, Vol. 47, No. 188 (Oct., 1938), pp. 440-451
Published by: Oxford University Press on behalf of the Mind Association
Stable URL: http://www.jstor.org/stable/2250384
Doron Zeilberger Opinion 68
http://www.math.rutgers.edu/~zeilberg/Opinion68.html
Views of Professor N J Wildberger
http://web.maths.unsw.edu.au/~norman/views.htm
(I like his comment about people in academia taking too much pride in thinking they understood high school math. Quantity is not quality folks!)
Nikolai Nikolaevich Luzin wrote about an interesting objection to Cantor’s proofs involving “effective enumeration”. See: Naming Infinity by Graham and Kantor (p. 206).
“A. Cantor’s Diagonal Method
Starting early in 1910, while thinking about the famous argument of Cantor, Luzin meditates on what the existence of a real number means. Luzin says that Cantor’s argument only shows that the reals are not “effectively enumerable” (meaning defined without the Axiom of Choice). But it still could be the case that the reals are “countable” but not “effectively enumerable” (an expression of Borel). These topics were still discussed later, of course, in connection with recursivity theory, and also with Gödel’s and Cohen’s results (see [2]).”
http://www.amazon.com/Naming-Infinity-Religious-Mathematical-Creativity/dp/0674032934
Actual or completed infinity is self-contradictory but was explicitly used by Cantor. Cantor replaced “infinitum actu non datur” with “omnia seu finita seu infinita definita sunt et excepto Deo ab intellectu determinari possunt”. (Page 14 of Michael Hallet’s “Cantorian Set Theory and Limitations of Size”)
http://www.amazon.com/Cantorian-Theory-Limitation-Oxford-Guides/dp/0198532830/ref=sr_1_1?s=books&ie=UTF8&qid=1289410858&sr=1-1
And just for the real analysis cretins and The Church of Limitology:
“We examine the evolution of the lost calculus from its beginnings in the work of Descartes and its subsequent development by Hudde, and end with the intriguing possibility that nearly every problem of calculus, including the problems of tangents, optimization, curvature, and quadrature, could have been solved using algorithms entirely free from the limit concept.”
The Lost Calculus (1637-1670): Tangency and Optimization without Limits
Author(s): Jeff SuzukiSource: Mathematics Magazine, Vol. 78, No. 5 (Dec., 2005), pp. 339-353Published by: Mathematical Association of AmericaStable URL: http://www.jstor.org/stable/30044190
“Real” Analysis is a Degenerate Case of Discrete Analysis [Appeared in the book “New Progress in Difference Equations”(Proc. ICDEA 2001), edited by Bernd Aulbach, Saber Elaydi, and Gerry Ladas, and publisher by Taylor & Francis, London, 2004.]
http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/real.html
Just for a fun exercise of distinguishing the map from the territory, let me quickly explain a classic paradox. Mathematical solutions to Zeno’s paradox do miss the point, according to Grimaldi [1]. But let’s just think about how a mathematician models the problem. Planet Math has a simple presentation of the argument using convergence. Now, a simple system of equations makes the problem much more sensible and easy:
D[A] = 10T
D[T] = T + 10.
Substitute D and solve for T and you get T = 10/9 (rational!).
In other words, a bad modeling of the problem says nothing about accomplishing some feat of non-enumerable complexity. In other words, we should actually reject the paradoxical idea of the continuum except as a shortcut group of estimation hacks (limit concept etc…).
It seems like we are assuming stupid things, and instead of questioning our basic assumptions we come up with equally stupid things to get around the ridiculous problems they create.
1. Papa-Grimaldi, Alba (1996). “Why Mathematical Solutions of Zeno’s Paradoxes Miss the Point: Zeno’s One and Many Relation and Parmenides’ Prohibition”. The Review of Metaphysics.
The probability proof above makes me laugh. Talk about confusing the map with the territory!
All of this probability obsession reminds me of the cranky anti-realist physics that is so common today. The original 1935 EPR paper showed that without a real physical nonlocal action at a distance the Heisenberg principle would be violated. Recently a similar result was suggested by Oppenheim and Wehner. See: “The uncertainty principle determines the non-locality of quantum mechanics.” In Science, vol. 330, no 7006, pp. 1072-1074.
Of course, Platonism is seen to be fine. Philosopher kings and fascist love it. Only when we talk about the real world does everyone agree to deny it. Irrational numbers? NO PROBLEM! That rock over there? Well, that’s certainly not real!
I just tell them to hold their judgment until I drop the rock on their heads! It’s a bunch of new post-modern, abstract non-sense. Lately, I’m beginning to erupt like a Feynman volcano! (http://www.textbookleague.org/103feyn.htm) We have more information than every but more stupidity than ever.
“Cantor’s argument has no deductive content at all” ~Ludwig Wittgenstein
By the way, Turings and Godel’s reasoning is not simply about self-reference. It is an extension of Cantor’s reasoning in different ways.
On Godel
BTW, the reason people don’t like Cantor’s diagonal is this.
Cantor did not prove that the reals are uncountable. He proved that the relationship between the rows of any infinite set and the digits required to enumerate that set is a surjection. He proved it for reals. The same is true of naturals. If X is the digits and Y is the rows, then there is a surjection from Y to X. But only when X is the digits used to represent Y. None of this has any effect on remapping of X and Y once that relationship is broken.
Said simply, Cantor defines a non-square matrix, then assumed the matrix was square and finally proved it was not. He jumped the gun in his conclusion. What he actually proved is that the infinite matrix where one axis is the digits (in binary or higher) is never square. It is a surjection from the rows to digits in this ONE specific case. It says nothing of the general case where you use arbitrary sets on each axis (ie. one set representing the naturals does not represent the digits of the rows).
The funny thing is mathematicians saying this non-square relationship is true of all sets of reals. Unfortunately, one axis is not arbitrary. It is always the digits used to represent the rows. And only if the rows are represented in binary or higher. If you substitute the axis of the digits for an arbitrary infinite set, Cantor’s proof no longer holds water.
For mathematicians, let me explain it this way. There exists a proof that shows in any enumeration of the naturals that the digits will always be a proper subset of the rows. That for the digits, we only need a proper subset of N to enumerate N. IOW, what Cantor proved for reals is also true of the naturals.
Now, such a proof would not indicate that the reals are countable, though I know they are. But it would mean that Cantor’s conclusion was flawed.
So it’s not about the proof per se, but the technique used to accomplished the “jump-the-shark” conclusion. People don’t like the technique because of the bogus conclusion, not the other way around. The technique is fine, just not for what you want to use it for. And it’s so obvious that it requires one to check their brain at the door to not see it. For everyone that does see it, here’s what we see:
1. Set up a grid that is by definition not square. aka trivially non-square at the outset.
2. Assume it’s square.
3. Prove it’s not square (ie. surjection).
DUH!
A bijection is a possibility, not a necessity. Why “counts” don’t understand this, I’ll never know. Cantor defined a surjection at the start and then proved this surjection. Surjections can happen with naturals. Just because we know we can remap them doesn’t remove the surjection from existence. The relationship between an infinite set and its digits is always a surjection regardless if it’s naturals or reals.
We shouldn’t be looking for a proof that maps N to R. We should be looking for a proof that you only need a proper subset of N digits to enumerate N (in binary or higher). Everyone that doesn’t agree with Cantor sees this as trivially true though.