Does Cantor’s Diagonalization Proof Cheat?
Alice and Bob play some set theory games
Raymond Smullyan is a great writer of popular books on logic—especially books on various forms of the liar paradox. He is also a first rate logician whose book on set theory with Melvin Fitting was just republished by Dover. This book gives a very readable approach to set theory, especially the independence results of Kurt Gödel and Paul Cohen.
Today I would like to use an example from their book to explain Georg Cantor’s famous diagonal argument. I have an idea why some people have difficulty with Cantor’s beautiful proof. If you know it well, you may wish to read on anyway; if you do not know it or do not believe it, then please read on and see if I have something to say. I have discussed the argument before, but still feel there is something to add to the discussion.
I have never had the pleasure of meeting Smullyan, but have heard a number of stories about him. One concerns the etiquette at Yale University, where I had my first job in the Computer Science department. One day I wrote a letter and gave it to a secretary to type up on our CS letterhead. My letter started
Dear Dr. X:
I am sending you my referee report on
The letter came back slightly changed
Dear Mr. X:
I am sending you my referee report on
I immediately asked why the change from “Dr.” to “Mr.”? The answer was: “This is Yale, we assume that all professionals have doctorates and call them `Mr.’ or `Ms.’ and so we never use any formal titles.” Okay I was new, I was young, so the letter went out as changed.
Later on I heard a story about Smullyan, who had given a talk at Yale, in the 50’s, before he had his Ph.D. After his talk there was tea in his honor, and his host introduced Smullyan around to all.
Mr. Blue, Mr. Green, Ms. Red, Mr. Yellow
Note, the introduction was to “Smullyan” not “Mr. Smullyan.” I do not know first hand if the story is true or not, but I like it very much.
Let’s turn to the classic argument of Cantor that proves the reals are uncountable. Somehow his argument is subtle, and many do not “get it.” There are some who are puzzled when they first see the proof, there are others who never understand it, and there are some who do not believe it at all. I would like to use Alice and Bob to help explain what the roadblock may be to understanding Cantor.
Alice and Bob Play Some Games
Consider the following simple game that Alice challenges Bob to play. Alice picks a natural number 
Eventually he will say
She then challenges Bob to another game. This time Alice picks a secret
They both agree that he wins again.
So far the games have been pretty easy, and Bob is feeling pretty good. Then Alice says she will pick a pair 
and then switch to the pairs
The problem is that if Alice picked 
Alice has many games like this, but here is the last one she decides to ask Bob. She said now my secret is a finite set of natural numbers 
Alice gives up, for now, since Bob has handled all her challenges so well.
Let’s Look at Bob’s Strategies
In set theory terminology Alice’s games prove:
- The natural numbers are countable.
- The integers are countable.
- The pairs of natural numbers are countable.
- The finite sets of natural numbers are countable.
The third game can be viewed as proving the rational numbers are countable.
Note there was something very special about Bob’s strategies. He did not need to keep them secret. Even if Alice knew his strategy for the second game, for example, she still would lose. No matter what number she selected, positive or negative, he would eventually guess the number. This is true of all of Bob’s strategies. They win whether or not Alice knows them or not.
This is a very special situation in playing games, even playing infinite games. Since Bob’s strategies are so powerful, I believe there should be no argument with the conclusions. For example, the pairs of natural numbers are countable. You agree?
Is Diagonalization Cheating?
Alice now challenges Bob to another game. Now Alice selects an infinite set of natural numbers
Bob wins if, as before, one of his sets 
The classic proof of Cantor shows the following: if Bob selects a strategy and Alice knows his strategy, then Alice can produce an 
Perhaps the point that many find unfair is Alice gets to see Bob’s strategy. This seems like a huge advantage. In the previous games, Bob’s strategies were so strong that he could allow her to see his strategies. Now Alice can only be sure of winning if she knows exactly what Bob’s strategy is. If Alice does not know his sequence of sets
then she cannot guarantee that she will always win. Whatever she picks for 
Can We Fix This?
Cantor’s theorem is correct, there are more infinite sets of natural numbers than natural numbers. But there is no strategy for Alice that always wins the game without “cheating”—without her seeing exactly what Bob’s strategy is.
This seems unfair, it seems like Alice is cheating. Is this the reason you might have been puzzled the first time you saw Cantor’s proof, or is this the reason you still are worried there is something wrong with it?
Alice has a fix. She tells Bob that she will let him keep his strategy secret, but she will now use a mixed strategy. That is Alice will pick her secret set 
so Bob always wins. She further argues that this means the set of all sets of natural numbers is not countable. If it was, then Bob would have a winning strategy.
Bob thinks about this last statement. In all the previous games he won because the sets were countable, he agrees that if she can win even some of the time, then Alice is right. Alice says here is how she picks 
The claim, from Alice, is that the probability 
Alice thus wins with probability
Open Problems
This discussion is related directly to a previous discussion I had on various proofs that the reals are uncountable. There was strong discussion before whether or not the random proof is valid. I think the point here is that the randomization is needed to make the game between Alice and Bob “fair.” What do you think?
Trackbacks
- Does Cantor’s Diagonalization Proof Cheat? » Proof, Cheat, Diagonalization, Cantors, Original, Does » Adjoozey
- Does Cantor’s Diagonalization Proof Cheat? » Proof, Cheat, Diagonalization, Cantors, View, Does » Adjoozey
- Biweekly Links – 07-05-2010 « God, Your Book Is Great !!
- Guides to Expressions of Quantity / Countable and Uncountable Nouns « El Weblog de First Studio Institute
- This Statement Does Not Refer To Itself « Gödel’s Lost Letter and P=NP
- The Tang Effect and Theorems « Gödel’s Lost Letter and P=NP
- What If Cantor’s Proof Is Wrong? « Gödel’s Lost Letter and P=NP
- A few links | Miles Shang
- Making Choices | Gödel's Lost Letter and P=NP
- Diagonalization Without Sets | Gödel's Lost Letter and P=NP
- A Proof Of The Halting Theorem | Gödel's Lost Letter and P=NP
- Why Study Logic? | Gödel's Lost Letter and P=NP
Let me start by saying that I DO believe Cantor’s proof (and think it is quite elegant), but I interpret its consequences differently than most people.
To me, it shows that our usual notion of the reals is incoherent.
Your game explains why: if Alice is randomly generating her set in an infinite number of steps, how can we say that this set “exists”? At every step, she has at most a finite amount portion of it, and if Bob is allowed to guess at each step, he will guess that portion using his normal strategies.
In a sense Alice never really finishes choosing her set and the game never really gets started.
An important result, but a different one if you allow yourself to question our usual notion of the reals. What does it mean to “have” an uncomputable real when the only way to say anything about it is to have some way to partially compute it?
I feel uncomfortable with your first games, when the set are countable. You allow (or Alice does!) Bob to make an infinite number of guesses. But correct me if I am wrong, aren’t a finite number of guesses sufficient? Unbounded number of course, but finite!
For instance, for the natural numbers, Bob’s strategy only needs K guesses if Alice chooses the integer K.
here’s another way of phrasing it (or maybe a different idea):
assume that bob’s strategy is a finitely described algorithm that does not employ randomness.
alice chooses the lexicographically least max-komolgorov complexity binary string of each length, concatenating them together as she goes [wrt some universal turing machine].
bob can’t guess this string with any finitely described algorithm.
this description semi-cheatingly uses the fact that the number of turing machines is countable, whereas the number of languages over {0,1} is not. moreover, it seems to assume the church-turing thesis.
s.
PS: the story about smullyan is awesome.
You’re asking for a layman point-of-view? Well here’s mine:
“Alice gets to see Bob’s strategy (…) Is this the reason you might have been puzzled the first time you saw Cantor’s proof, or is this the reason you still are worried there is something wrong with it?”
No I’ve no problem with that. To me it’s a straightforward way of saying Bob can’t always win, which is enough for assessing Cantor’s theorem correctness. However one thing is far more puzzling to me:
“She looks at each of his sets in turn and decides (…)”
How could she looks at all Bob’s sets? It seems that we could have said the same for the very first game involving one natural number only: Alice looks at each of the natural number Bob produced and decides…
This is the one thing I think puzzling in the demonstration. Maybe it could help if you explicitly say how Alice chooses her strategy once knowing Bob’s one.
” the randomization is needed to make the game between Alice and Bob “fair.” What do you think?”
To me it’s fair. Moreover, it adds something interesting even if I was ok with Alice seeing Bob’s strategy. Indeed, first demo indicates Bob’s chance to win is lower that one. Now I know it’s zero. That’s better. 🙂
Nice discussion. Basically, Alice can always win (or win with probability 1), but only if she has access to more computational resources than Bob (in particular, the ability to enumerate all of Bob’s strategic output and then diagonalise). If she has equal or lesser computational resources, then Bob can steal Alice’s strategy to win.
The random number generator that Alice uses to build her example is a powerful computational resource, that allows her to easily defeat Bob… unless Bob also has access to exactly the same generator (with the same seed), then Bob can win again.
The Skolem paradox shows that even if the reals are not internally countable, they can be externally countable; this is analogous to the above discussion, because an external Bob has more computational power available to internal Bob. For instance, in a model where the reals are only the “constructible” reals, then an internal Bob (who does not have the ability to solve the halting problem) cannot actually enumerate all these reals, whereas an external Bob (who can solve the (internal) halting problem) can do so easily.
Slight correction: if Alice and Bob have equal computational resources, then Bob can only win if he knows Alice’s strategy. If Bob has significantly greater computational resources than Alice, then Bob can enumerate all of Alice’s strategies and win even if he does not know Alice’s strategy in advance.
Incidentally I discuss similar adaptive interpretations of set theory in
http://terrytao.wordpress.com/2010/03/19/a-computational-perspective-on-set-theory/
Terrence,
Thanks for the comments on the complexity issues involved.
quote:
The random number generator that Alice uses to build her example is a powerful computational resource, that allows her to easily defeat Bob… unless Bob also has access to exactly the same generator (with the same seed), then Bob can win again.
Wrong. Suppose the device of generating the numbers is so:
K=0
loop
Kth +1 number. how many persons pass over the street X today between the hours …
kth+2 number. how many degree there are outside now
k+3. number : how many photons touch a surface at a given time.
k+4. the spatial position of an electron of an atom inside a box .
k+=4
repeat loop
Even if Bob knows the algorithm, he cannot use it, as he cannot reproduce the experiment.
1. Suppose Alice chooses a Diophantine equation (in say 3 unknowns), tells it to Bob and ask for a solution (she can construct equations with arbitrary large solutions)?
2. Suppose (regardless of P vs NP) Bob has NP-oracle, will this help him for {1.}?
In order for Alice to “pick” X and Bob to try to guess with Y and Alice to decide X=?Y so that she can tell Bob whether he won, X & Y have to be computable.
Alice cannot pick an infinite set that is not computable. Essentially Alice can only pick programs. Unfortunately she can’t even always decide whether Bob’s Y =? X, either.
Cantor’s proof is troubling because it constructs just more computable reals from computable reals, but somehow taking this to acknowledging the existence of uncomputable reals.
No, in this perspective it only shows that there is no counting program. I.e., the counting function is not computable. It doesn’t say anything about the existence -whatever that means- of uncomputable reals.
What you’re talking about is a consequence of the sets having different cardinalities. It’s not specific to the integers and the reals.
For example, suppose Bob may choose 9 out of 10 possible numbers. Once again, Alice can win 100% of the time only if she is privy to Bob’s choices. Once again, even if Alice is not privy to the choices, Bob can’t win 100% of the time.
I would recast the game in terms of sets rather than their elements. By this I mean Alice’s challenge to Bob should not be for him to discover which secret element Alice has chosen from a given infinite set (either countable or not countable) but rather for Bob to be given the infinite set itself and be challenged to come up with a strategy which _exhuasts_ all the elements of the set. For this to work Bob’s strategy must formulated as a sort of iteration by assigning to each numbered iteration the element of the set his strategy choses next (i.e. he sets up a bijection between the canonical infinite set of natural numbers and another infinite set). In order for Alice to win she must then show that Bob’s strategy isn’t exhaustive and the only way she can do that is to exhibit an element in the given set that Bob’s strategy cannot exhaust. You will see that this game is identical in it’s essentials to the first four given in your blog post but in the case of the last the key difference is that Alice choses her counter-example _after_ Bob has chosen his strategy. It doesn’t matter if Alice happens to chose beforehand an element of the set that Bob’s strategy finds because this doesn’t mean that there aren’t other elements that the strategy misses and the issue of whether or not Bob’s disclosing his strategy is fair is avoided entirely because the burden of (a posteriori) proof rest with Alice not Bob. Furthermore Alice can prove, in the case of the reals (i.e. your example of sets of infinite sets of natural numbers) that _whatever_ strategy Bob might come up with she can _always_ find a real number that his strategy does not find and thus, because Bob cannot demonstrate a bijection from the natural number, the reals must in some sense form a ‘larger’ set.
A Smullyan story I like is from Smullyan’s preface to “To Mock a Mockingbird.” A lady had written to him with a solution to a puzzle from his previous book and signed off saying “Love”. He says that he was impressed by the solution. He had no idea if she was single but wrote back asking to use her solution in the next edition of the book and suggesting that she major in mathematics. She replied granting permission to use her solution and said that university was not on her mind because she was nine years old.
IMHO, the perspective from games is not a good one for *teaching* diagonalization. I would start by a 4×4 matrix of zeros and ones and show that if we take the diagonal and invert it, it would be different from all the rows in the matrix.
It seems to me that “the power set of A is larger than A” is completely intuitive, and unless one has problems with the notion of an infinite set or a real number or the power set, there shouldn’t be any problems with the fact that there are more reals than integers.
I have the same problem with the randomness argument that I had last time: it seems circular. After all, if the reals are countable, then it clearly fails. So why should one believe it? Of course, one can construct Lebesgue measure, but one cannot do that without basically proving (a strengthening of) the statement that one can create a nested sequence of closed intervals whose intersection avoids any given countable set.
On the subject of why people don’t like the diagonal argument, I think part of the reason is that they get distracted by the ordering on the natural numbers. The proof that there is no bijection from a set to its power set is harder to object to because the function is given all in one go, so to speak.
I see that I have inadvertently repeated a point made in the previous comment …
Another vein of confusion is that a matrix is typically is made of “same nature” elements. In Cantor, the columns are digits (the way we represent numbers), and the rows are the numbers themselves. Since each number has an infinite number of elements, and since there are infinite reals, then Cantor just draws from a set to that is infinite in both directions and the fires “So you tell me this list exhausts the reals?” and then proves there’s an element missing in the list, contradicting the premise through the diagonalization concept.
What many don’t like is that that number of columns, if the list is to be complete, requires there to be N^(base number) rows. If there were equal number of rows and columns, the list would obviously be incomplete. This just follows from the natural observation that decimals (or binary or any other) representation is just a compact way of writing the numbers of elements (or a quantity). So how can he claim to have a complete list in the assumptions and then just because there is an infinite number of elements in every direction, assume hi can exhaust the number of elements and at the end of that process come up with a number not in the list? If he could do so, his thought experiment would just show him that every time he moves to find out the next “digit” of his magical element, that he is actually creating SUM(“j”)^(base number) rows, and that he’d increasingly find his “diagonal number” represent a smaller fraction of whatever was on above: his hypothetical square matrix.
I believe reals represent a larger infinity that naturals or rationals, while Cantor’s diagonal isn’t its proof.
Made a few immaterial errors, eg.
>every time he moves to find out the next “digit” of his magical element, that he is actually creating SUM(“j”)^(base number) rows
Base^(j-) – Base^(j-1) where j = current column
It doesn’t matter. The matrix needs Base^(columns) rows, which means you increasingly need fewer columns as you grow the number of rows. The diagonal argument just states that if one could create the impossible square matrix with rows as elements and columns as digits, that that list would be missing “rows”.
To use his diagonal as proof that the reals are larger than naturals, Cantor would have needed to show that we’d expect the matrix to be square, and then go on to show (the part we are on) that he is arriving at a contradictory position. What he did is create a matrix that can’t be square, and then showed that it isn’t square: it’s missing at least one element.
Anyway…I just wanted to point out that many don’t believe in Cantor’s diagonal as proof, but believe that the reals are “larger”.
Hmmm. This realm of all these infinite integers, irrationals and their ordering did confuse me when I made those comments later in this post. I just now read this comment by @gowers and anonymous above and it made me think better about it. If we dont bother about some the set of integers but only bother about sets and powersets and their powersets we would be better off. Cantor’s proof that a surjection doesnt exist from set S to power set S is a start.
Cantor proves it using contradiction. He assumes a surjection exist and then sets up a particular set in such a manner that a particular element both belongs and doesnt belong to the set he has set up which is not admissible and hence our assumption of surjection is wrong.
The question one needs to ponder is whether proof by contradiction or the assumption that an element either belongs or doesnt belong to a set is valid in case of infinite sets.There is some how a leap of logic an human mind takes here to reach this judgement while if you let a computer work on this, it would go through the whole list to make the determination which is impossible to do and hence we will be left with a state of ‘unanswer’.
Ofcourse one needs to prove that there is no surjection from the set of natural numbers to the set of irrational numbers. Cantor’s diagonal routine helps in it and my doubts which I had posted later are still valid. Infact if we do manage to prove that without a sleight of hand, we still dont know whether there is a surjection from the set of irrational numbers to the powerset of natural numbers. Is there a different kind of infinity between an infinite set and its infinite power set.
I’m perfectly happy with the original Cantor argument – actually less so with this version.
To me, it feels as though you are trying to provide a proof which is somehow ‘constructive’, which I think isn’t possible. As has already been said, this infinite sequence of random choices argument does nothing but sneak a non-constructive proof through the back door: why can Bob not simply claim he has enumerated over all Alice’s possible random choices?
Perhaps one way to look at this is to ask who verifies claims. Someone has to: otherwise Alice will claim that none of Bob’s numbers was hers, and Bob will claim that he enumerated the reals and therefore must have hit Alice’s number. So this leads to: what do you count as verification?
The Cantor argument is essentially what you get if verification consists of a sequence of back-and-forth questions between Alice and Bob, with Alice not being allowed to contradict herself and the burden of proof placed on Bob (i.e. he must eventually guess Alice’s number, which presumably Alice makes up as she goes along).
If you insist both players play algorithms (i.e. Alice chooses an algorithm and is thereafter stuck with the number it generates) then you get into this computational power question; if you don’t limit Bob, then he will win in finite time (he will guess Alice’s algorithm). If you cease to insist that Alice’s algorithm must be stuck to, then Alice can always keep finding algorithms which don’t contradict any previous answer and permit her to claim that Bob’s guess is wrong. This is really no different to the standard diagonalisation argument: it just amounts to diagonalising over Kolmogorov complexity instead of over finite-length strings.
If you insist Alice make a decision and stick to it, perhaps an interesting choice for Alice is: The [0,1] real whose k-th binary digit is the parity of the number of halting programs of length k. This is of course boring if Bob has access to an oracle which can decide the halting problem: so let’s assume not. To be fair, let’s assume the same of Alice. Then, here is a hard question: does Alice win?
Bob’s problem here is obvious – but Alice also has a problem. Bob can simply ask in succession whether each digit is 1. Presumably whenever Bob asks a question, Alice must reply within some ‘sensible time’ – say, a time limit function (of the question-and-answer history). Now the halting problem is easy on very short programs. Alice must presumably try to guess (compute?) where the halting problem becomes hard, compute correct parities up to this point, and thereafter assume that Bob cannot ever catch her out in a lie about a single digit. But Bob has an arbitrarily long time to check every digit: he can try to run to halting state and prove non-halting of each program of length k, dovetailing, while asking questions of Alice. If Bob is allowed to ask arbitrary questions, it is likely he can force Alice into a contradiction by simply asking questions to which Alice cannot compute the answer within the time limit, so let us restrict Bob to guessing algorithms whose output is some specified digits (perhaps only one, or perhaps all) of Alice’s number, and Alice to answering ‘yes’ or ‘no’ as to whether these digits are correct. It’s not clear whether Alice can expect to win, or how much difference the choice of time limit function makes…
Your probabilistic proof of the uncountability of the reals relies crucially on the following two facts:
i. For any real x, the probability that a real number picked uniformly at random from [0,1] happens to be equal to x is zero.
ii. The probability of a countable union of events of probability zero is always zero.
These facts (plus the axiom that the probability of the sample space is 1) trivially imply the uncountability of the reals without any need to complicate the argument with games.
Fact (i) can be argued for intuitively pretty easily, whereas fact (ii) is not intuitive. (An _uncountable_ union of null events can yield the whole sample space, so why not a _countable_ union?)
In contrast fact (ii) is easy to prove formally (it’s a corollary of an axiom of probability theory) but proving fact (i) requires proving that the uniform distribution over [0,1] exists, which is non-trivial.
—–
The set of numbers with finite descriptions is countable, so proving the uncountability of the reals inevitably requires a non-constructive proof technique. I wonder if rejection of non-constructive proofs contributes to some people not liking Cantor’s proof?
>I wonder if rejection of non-constructive proofs contributes to some people not liking Cantor’s proof?
Yes in my case. Cantor constructs a matrix that can’t be square if constructed, and since the elements are infinite in both directions, he just assumes that that doesn’t matter. And one is expected to find the conclusion that there’s an element not in the matrix actually “news” only because the elements are infinite. Is trying to prove that a matrix of infinite rows and columns can’t be square (ie. there will be additional rows?). There are 10^ROWS number of COLUMNS, which is why it can’t be news -much less prove anything- one does obviously know beforehand that one will find more rows than columns, and thus constructing a number with the diagonal starting at 1,1 reiterates the obviousness of the premises with emphatic meaninglessness.
Absolutely right. The diagonally constructed number, during construction, can never catch up with the lower rows of the list at the same stage of construction – i.e. there are numbers on the list of which it cannot be true that a diagonally constructed niumber differs at some digit.
@logicophilosophicus: Yes, that’s exactly my objection to the diagonal argument. There are always rows that the diagonal will never catch up to. The matrix is one that is by definition not square. The result of the diagonal proof says as much (it finds its own assumption). IOW, the mapping is not one to one and then goes one to say it isn’t. DUH! Natural sets CAN BE one to one. They don’t have to be. There can be a surjection between two natural sets and that’s what’s happening in Cantor’s matrix where he tries to form a diagonal.
does every proof of the uncountability of [0,1] depend on a contrapositive?
Actually, you do not use the contrapositive when proving a negative statement. The statement here is: there is no bijection from N to P(N) (or R, or [0,1]). To prove this negative statement you assume that the statement is true and then try to show a contradiction. No contrapositive there!
In fact the whole proof is valid in constructive foundational theories. The result can intuitively be understood as: there is no computable (within the system) function from the set of natural numbers to the set of computable functions (within the system) from N to {0,1}.
Croux,
This may sound far too simplistic, but please don’t dismiss the question as students ask this all the time:
If you are attempting to prove that there is no bijection from the N to the R
and you attempt to prove it by contradiction – so you assume there is
a bijection from the N to the R, and then via Cantor’s Diagonal Proof show
that assumption leads to a contradiction, therefore there can be no bijection, how do you know you should not assume that the R are dense/complete/continuous and that it is that assumption that leads to the contradiction and not the bijection ?
I know the question may show a lack of Logical Understanding but this type of question comes up again and again in my classes.
Thank You
I think that an even more central “problem” with the diagonalization argument arises as soon as we say: “Now Alice selects an infinite set of natural numbers…” How does Alice do this? Are infinite sets of natural numbers available in black boxes? If not, and if one presumes that Alice must have some notion of the infinite set that she has chosen, then this would seem to require that Alice have some sort of a (finite) definition or description of that infinite set – perhaps an algorithm that could generate it. But then, assuming that Alice and Bob share the same language, and that this language uses only finitely (or even countably) many symbols, then Bob does indeed have a winning strategy for guessing Alice’s set. Bob has only to enumerate all possible definitions in that language (similar to the fourth game in your examples), and he will eventually arrive at the definition of Alice’s infinite set.
Of course, this is an “artifact” of the presentation of the diagonalization argument as a game between two (finite) human beings, but I think that it points very nicely to the essentially nonconstructive nature of the argument itself. Really, the diagonalization argument only makes sense if one believes that real numbers and infinite sets are in some sense “Platonic objects” that are just “there”. Of course, if one is not a Platonist, then one can always accept the diagonalization argument itself on formal grounds, in which case it is more of a curiosity regarding definitions than anything with “real” content (no pun intended).
Great blog, by the way, and a great topic – thanks for the effort it must take to keep it up!
i wonder if there’s a proof in terms of filtrations — ie if one ‘player’ has to live in a world where he does have knowledge of the future (and therefore has countably many moves) and the other does not (he therefore has uncountably many moves)
There’s a flaw in Cantor’s diagonal if the list I produce uses the same technique that Cantor uses. Cantor decides whether or not to use i depending if it’s in each of Bob’s set or not. At the end, Alice’s set is different from each of Bob’s sets. That’s the theory. But there’s a flaw because Bob can do the same thing and show a proof by contradiction.
I’ll use the normal diagonal where you flip the bit in binary strings so that the resulting string is different than every number in the list. Now, my list of random numbers I’ll call M. However, for each one, I will also associate the binary natural number from 1 increasing forever.
So each element has both a real number and a natural number, both represented in binary.
However, I want to re-order the natural number representations for each elements. Note that the element order stays the same. I’m only going to move around the natural number representations associated with each element.
What I do is that I exchange the first natural with the natural that has only a single 1 in the number, but where it is last. So it is the number 1. I then swap the second natural with the number 2 (that’s in decimal). The third natural number, I swap with the number 4 (again shown here in decimal). If I keep going, the list of reals remains the same, but the naturals will produce a diagonal.
The problem is that even if I keep doing this infintely, I will both never run out of single 1 digit numbers on the diagonal while I will also have infinitely many numbers that have several 1’s in them because those have never been removed from the list. So when Cantor creates his diagonal, he can only ever get a subset of N. He can never get the whole set. He can’t even make sure that all of N are accounted for.
Now here’s the kicker. If you find a flaw in what I did, then that flaw exists in Cantor’s proof as well because I’m using the EXACT same technique, but from the other side. If Cantor’s proof succeeds, it must fail. It is a self-defeating proof.
Mr. X,
Could you demonstrate your insight via a small diagram ?
I’m using proof by contradiction from the conclusion of Cantor’s proof. So if my list is countable, then no problem associating countable naturals to the countable list of reals that Cantor has proven must be countable.
5, r1
12, r2
3, r3
2, r4
1, r5
4, r6
6, r7
8, r8
7, r9
(list continues on…)
Now, I’m going to show the natural numbers in binary.
0101, r1
1100, r2
0011, r3
0010, r4
0001, r5
0100, r6
0110, r7
1000, r8
0111, r9
I’m now going to swap the assigned natural (shown in binary) so that the top most numbers have a single 1 digit in it starting at the right most location. That would be the natural associated with r5. So the naturals associated with r1 and r5 get swapped.
0001, r1
1100, r2
0011, r3
0010, r4
0101, r5
0100, r6
0110, r7
1000, r8
0111, r9
I then see that r4 has the next natural fitting my description. So I swap it with the natural associated with r2.
0001, r1
0010, r2
0011, r3
1100, r4
0101, r5
0100, r6
0110, r7
1000, r8
0111, r9
Next is r6, then r8
0001, r1
0010, r2
0100, r3
1000, r4
0101, r5
0011, r6
0110, r7
1100, r8
0111, r9
I’ve only gotten to r4, but “eventually”, I’ll get this:
000000001, r1
000000010, r2
000000100, r3
000001000, r4
000010000, r5
000100000, r6
001000000, r7
010000000, r8
100000000, r9
(this list continues)
Where did all my reals associated with naturals with more than a single 1 digit go?
This is what happens when Cantor creates his diagonal. He intentionally selected a subset of any list that he is given, EVEN COUNTABLE ONES. That’s how the Cantor grid is set up.
All Cantor did was prove that the digits are always a proper subset of the rows they represent for any infinite set X (this includes N and R). Cantor proved there were “more” rows than digits when it comes to R. It’s also true for N (the example above proves it since it shows that the digits map to a subset of the rows only a la Cantor). The problem is that outside of this grid (when the digits are no longer coupled/describing the rows), you can map one set of N to another set of N no problem. Yet we’re led to believe that the rules suddenly change for R??? Circular reasoning. If R maps to N, then R = N and you can map N to N. Otherwise, you can’t. So Cantor’s proof doesn’t impress me much with this kind of circular reasoning.
Take the infinite binary tree. The rows are a subset of the nodes since a row consists of many nodes. This will always be true within this tree. Yet both are countable. So this technique of mapping one axis to another when one is used to define the other is not valid for proving differences of cardinality. Hence, Cantor’s diagonal is not a valid proof.
Let me chew on what you wrote.
I see the strength of your points but when dealing with infinity
it is hard, at least for me, to make sure there are not any assumptions
I should not have made.
Thank you for what you wrote.
Note too that the construction of the diagonal is simply to show that the diagonal itself is only a subset of my countable set. As to Cantor’s proof, how I created the diagonal is irrelevant once we accept that such a diagonal can only map one to one with a subset of a countable set. And once this is accepted, then Cantor’s proof falls apart since the requirement that it map the entire list given no longer holds true.
I think in case of counting integers as well as rational numbers you created a scheme with which you were able to come up with a next number in a sequence which hasnt yet appeared in the sequence. Now for a moment assume if you didnt have such a counting through the diagonals scheme for rational numbers or even a next number counting scheme for natural numbers. Now let us in the case of natural numbers, use the same contradiction proof which we used for real numbers for proving that we can come up with a number which is not in some predefined real number list. Assume you have a infinite list of natural numbers and you dont have any clue what those numbers are or how it has been constructed like you are assuming in the case of real numbers. Then I can come up with an argument saying add all those numbers in your list and the resulting number would not be in your list. This is similar to the argument you are giving for proving that there cant be such a list in case of real numbers – in real numbers the scheme is not addition but digit replacement using the diagonal. In both cases, you are doing an infinite computation across all numbers in the list. But in the case of natural numbers even if you are able to come up with a number not in the list, you KNOW you have a counting scheme, and similarly such a counting scheme could be possible for real numbers also and possibly we havent found it. So what I am saying is just proving by contradiction through using infinite computation logic is not good enough to prove that the infinities are different.
In first case, apriori you are assuming that you can come up with a next number which is not already in the sequence. You assume an infallible counting scheme. But if for a moment forget those things you write are numbers, what you are coming up with is a counting scheme to list a set of non repeating strings which has an order property. So the question boils down to – given a real number string, can you come up with the next number string? If the real numbers are ordered, then implicitly you are assuming that there is a next number – just that we dont know how to write it. The fact is between any two rational numbers, there can be infinite rational numbers – but we found a scheme. Why can we find in the case of irrationals? If we dont accept cantor’s proof for uncountabilty of reals based on the line of argument I suggested in the previous para, nothing prevents us of thinking of a scheme to order reals. I do not really buy the replace the diagonal digits argument as it is based on infinite computation over an infinite list! Something is quite fishy there.
I agree, dealing with Infinity requires very, very special care.
Suppose I create a numbering scheme for natural numbers in the form of a tree. I start with root nodes – 1,2..9. Then child nodes for each of those root nodes are say 0,1,2..9. Then so on and on. Then each of those nodes in the trees would cover all natural numbers. Then our counting scheme is from the root level, you go from left to right and then the next level you go from left to right and so you will be able to enumerate all natural numbers. This is an infinite tree and if you see – there are many infinite paths of infinite length from the root to the leaf node which is pretty much at infinity. If you were to imagine the leaves of this infinite tree, they contain natural numbers with never ending digits and many with never repeating digits. Suppose in each of these infinitely lengthy natural numbers or base 10 digit strings add a ‘.’ / dot in front of it, you get most of the irrational numbers between 0 and 1 (we left out Zero as root node, which skips some numbers but lets say we skipped 1/10th of such numbers but we have remaining 9/10th of the numbers). Wouldnt that make irrational numbers between 0 and 1, contained in the set of natural numbers? If we can include these leaf nodes in the infinite rational tree in our natural numbers counting scheme and still say we have a good counting scheme – cant we just adopt the same counting scheme for irrational numbers between 0 and 1, as it is only a part of the tree? In this counting scheme, isnt all irrational numbers between 0 and 1 covered atleast 9/10th? I have an one-one correspondence between the leaf nodes of this tree and the list of 9/10 th of the irrational numbers between 0 and 1. Why are the leaf nodes of a countable tree in itself is called uncountable? If Alice thinks of any irrational number between 0 and 1 which doesnt start with zero, it will be in the rational tree – Bob needs to draw up the rational tree and then enumerate the leaf nodes one by one and he will reach that number at some point. That is the strategy for guessing Alice’s number. Bob will disclose his rational tree which is his list, Alice cant come up with a number not in that list, as all numbers will be there. So what am I missing here? – Is this something like a paradox?
So the crux of the argument is :
What is the difference between these two infinite lists – both derived from the leaf nodes of the natural numbers tree. I should correct the above comment from rational tree to natural numbers tree as that tree contains only natural numbers.
n1 = l11l12l13l14..
n2 = l22l22l23l24…
…
n infinity
ir1 = .l11l12l13l14…
ir2 = .l21l22l23l24..
…
ir infinity
where letter/digit lij belongs to the alphabet [1,2..9].
Seems like both are same except for the dot in front – the first list is part of the list of natural numbers and if a part of natural numbers can be mapped 1-1 with irrational numbers then how come irrational numbers are bigger than natural numbers.
Ask a mathematician how many digits it takes to represent all naturals and they’ll balk. They’ll change the subject or flat out refuse to answer. It’s because it’s an area that has been completely hand waved away without any justification.
The seeming contradiction is something they don’t want to talk about. Any single natural has finite digits. But infinitely many of them will require infinite digits. This last one is proven by the very diagonal in Cantor’s proof. Any single row has a single 1 in it at a finite position indicating where we flip the digit. But taken all together, there are infinitely many digits.
So when they say to your comment that the two lists are different because naturals cannot have infinitely many digits. Yet they can if taken together. Infinitely many naturals require infinitely many digits. So the “finite digits” argument doesn’t really hold water.
The fact that mathematicians balk at this is my favourite part of this entire argument. The only answer I’ve heard from them is to say it’s “unbounded” as if that is different than infinite. It is not. If a set is unbounded, then it is infinite by definition. Yet mathematicians balk at this. The funny thing is that the infinite identity matrix represents the naturals quite fine. And the digits map one to one with the rows. Yet the digits are “unbounded” but the rows are infinite. Truly amazing how that works. If the digits are infinite, then the excuse that naturals are finite becomes irrelevant because you can take infinitely many naturals and map them to irrationals.
Any fixed natural number n needs only finitely many digits to represent it. We all agree about that. So if you reflect a natural number about the decimal point you get a real number with only finitely many digits after the decimal point. In particular, you don’t get the real number 0.333333333….
You disagree? OK, what’s the natural number that reflects to give the number 0.333333333…? It certainly isn’t something like …3333333333, since, as you yourself admit, no single natural number has infinitely many digits. If you want to put together an infinite collection of natural numbers to make an infinite sequence of 3s, then go ahead. But now you are not counting natural numbers — you are counting things you can make by putting together infinite collections of natural numbers. The set of all such things is not the same as the set of natural numbers. In particular, it is uncountable.
@gowers –
My bad. I didnt recognize the fact that all natural numbers have finite number of digits. Now I understand that if I pick any particular natural number from the set of natural numbers it will have a finite number of digits but an irrational number like even root of 2 will have infinite number of digits after the decimal point. Point taken.
Now lets forget irrationals. What about the power set of the set of natural numbers? If we take any element in that power set of natural numbers and concatenate the numbers in the elements in that set along with the braces and comma and create a string of it. What I am doing is I am stringizing a set. Instead of looking at {1,2,3} as a set lets us a look at it as a string ‘{1,2,3}’, Then if we do that for all the elements in the power set we would have created a set of such strings. Lets called stringized power set. Then that set will have the same cardinality as power set as it will have the same number of elements as the power set and no duplicates. Now replace the braces { and } and comma with A, B and C resply. Now after replacements, this modified stringized powerset can be interpreted as a set of natural numbers (infact a subset) where natural numbers are written in Base 13.
Am I right in that or am I goofing up somewhere?
If I am not then I have a power set of an infinite set of natural numbers which can be mapped 1-1 with the infinite set of natural numbers itself. The power set and the set will have same cardinality.
What am i missing?
@gowers: What about the set of numbers that have a single 3 in it and 0’s everywhere else? Each number is a natural, but collectively have infinitely many digits.
“The set of all such things is not the same as the set of natural numbers. In particular, it is uncountable.”
BS. You’re handwaving without a paddle. Next, you’ll tell me that the even numbers don’t map to N. That’s what you’re implying. Or that the even positions of the even numbers don’t map to N, etc.
@sridharmahadevan: The powerset has elements that has infinitely many “characters”. A single natural doesn’t have infinitely many digits.
This is really the sticking point. As others here have shown, the “uncounts” don’t want to let you do a mapping just because they want you to stick to finite length numbers regardless if the mapping is valid or not. All the proofs revolve around the finite length property of a natural as if all mappings from naturals must also create sets with elements of finite lengths.
Also, the “uncounts” handwave away mappings that are not one to one. Just because A and B can have a bijection doesn’t mean that a non-bijective mapping can’t exist. Yet, Cantor’s diagonal is predicated on this with its square infinite matrix.
I thought further about the finiteness of the number of digits of natural number. If I make a choice in the set, our mind converges to a finite number and digits are finite. That means if all natural numbers are finite, then the set should be finite but it is not.
One way of evading that is all numbers though are finite but you can keep going on and on and on and create ever larger finite numbers hence that possibility of the fact that it can go and on and on is given a term called infinity. Infinity is some kind of a limit to the series and so it cant have a real form.
But lets do this thought experiment. If we create a ever expanding natural tree like I suggested before, then natural numbers are expanding in various paths generating leaf nodes corresponding to infinities starting with 1, starting with 2…etc. There are possibilities of natural numbers converging into different type of an infinite numbers. An infinity which starts with 1 and another which starts with 2 depending on the path you take in the natural number tree. So that means that there are multiple possibilities for the infinity.
Now let me bring the process of creating irrational number – say root of 2. I can keep calculating the decimal digits of root of 2 with increasing accuracy and generate digits and it would generate more and more digits tending to infinite digits.
Now assume that I use the same process and traverse through the Natural tree and choose my nodes and path based on the decimal digits of root of 2. For instance I traverse to next child node in the natural number tree based on the next decimal digit I get in calculating root of 2. As I am traversing this natural tree I see like how calculating the root of 2 process doesnt end – this traversal doesnt end. Then I have tied a process of generating a string with a process of generating the decimal digits of root of 2. Both are processes, generating never ending strings – One I know is root of 2 and the other I am naming it now and say that it is the natural number generated with the above mentioned process and I call it the natural path of root of 2. There is a critical difference between this process and the previous method where I just removed the digit or reflected a natural number or irrational number. Here I am defining a number like say Chaitin defined his number – that number which is reached when I traverse the tree like the way I mentioned before. The fact is like how you define the irrational number root of 2 through a mathematical operation, this number or the string of digits also is defined through the tree traversal process I mentioned which is tied to the definition of root of 2.
So what is that string? It looks like a natural number but it definitely has infinite digits like the root of 2’s decimal digits as it is directly tied to it.
Simply put – if I subtract 1 from root of 2 and then in the resulting string I remove the decimal dot, then I see a number. What is it? Is it a natural number? or is it not a number at all? Or should I say it is a “natural number like” representation of actually an irrational number – ([root of 2] -1)?
I am really confused or there is lacunae here. May be the string I get above cannot be called a natural number as a natural number is finite and this is by definition infinite. But if it is not a natural number, what is this thing/string called in mathematics? Or is mathematics not bothered about it?
Ok infact the crux of the question is this. Lets keep it simple. I have a string which is 1 followed infinite number of zeros. It is a string which I can visualize in my mind. It seems like a number to me but it is not a natural number as it has infinite digits. So what is it? Is it a rational number or an irrational number or complex number? Or is that string not a number at all?
As per what rule does this string violates the concept of a number? What number litmus test does it fail?
That is the key question. If we can answer that, then we are fine. Lets call them unnatural numbers.
Commutative law: a+b = b+a.
If suppose (root of 2 -1) and (root of 3 -1) are commutative we can use the same principles of addition. Take any of these unnatural numbers and I define addition as add a dot in front and then do addition like you do addition for normal irrational numbers and then remove the dot. The resulting unnatural number will be the same if you add the other way around and so these numbers pass the commutative law.
So if I have a number 1 followed by infinite zeros, and add it with 2 followed by infinite zeros then we get 3 followed by infinite zeros. The same thing will happen if you add other way around – so it is commutative.
I believe I am properly adding these strings/numbers and not evading the principle of addition. Similarly we can prove other laws of arithmetic like associative and distributive laws applicable for these unnatural numbers for addition and multiplication.
Am I stretching the idea of addition or multiplication operations to include this string of 1 followed by infinite zeros into the realm of numbers and arithmetic?
What is a number?
@sridharmahadevan I’m afraid I don’t understand your construction well enough to be able to say whether you have goofed or if so where.
@MrX If you can give me a natural number that reflects to 0.33333… then maybe I’ll sit up and take notice.
Consider the following statement: if you take infinitely many natural numbers and put them together then you get a natural number. I say that that statement is false. You say that what I say is BS. Unfortunately for you, it’s not BS at all: it is a very straightforward truth. If you don’t accept it, it simply means that you are using a nonstandard definition of “natural number”. That’s your prerogative, but Cantor’s diagonal argument is about standardly defined natural numbers and not nonstandardly defined natural numbers.
To put this as diplomatically as I know how, let us agree to disagree. I prefer the standard definition of natural numbers, according to which if you put together infinitely many natural numbers you don’t get a natural number. Adopting the standard definition, there is no 1-1 correspondence between natural numbers and reals. You prefer a nonstandard definition where you can put together infinitely many natural numbers and get a natural number. Adopting this definition, there is a 1-1 correspondence between natural numbers and reals. Would you be happy with that as a conclusion?
@gowers
Thanks for the response.
I will try to explain my constructions more clearer and simpler.
Two constructions:
Construction 1:
Three strings:
1 followed by infinite zeros
3 followed by infinite 3s (the one you said you will take notice)
Remove the dot in root of 2
These three are strings made of alphabets from 0 to 9 each a different type of an infinite string. You might say that these strings have infinite letters and arent natural numbers according to you. But are these strings numbers at all? If not what are these? Just infinite strings or “things” which has no role to play in the language of arithmetic?
Construction 2:
The power set say of S- {1,2} is PS – {{1},{2}, {1,2}, {}}.
I take each element in the PS and stringize it and replace with A,B,C the letters { and } and comma and we get:
Stringized and converted SCPS – { A1B, A2B, A1C2B, AB} – This SCPS will have 1-1 correspondence with PS and there wont be any duplicates.
But SCPS can be interpreted as a set of certain natural numbers in base 13.
Specifically the Base 13 elements in set SCPS can be looked at in Base 10 as
SCPSBase10 – {1714,1727,289872,141}
If we extrapolate this construction for the whole set of natural numbers N, then wouldnt the stringized converted power set of N will be again another set of natural numbers in Base 13? Then that stringized converted power set has 1-1 correspondence with both the power set of natural numbers and the set of natural numbers N.
If that happens, can we not say there is a 1-1 correspondence between Power set of natural numbers and natural numbers?
Please note in constructing the stringized power set of natural numbers we arent concatenating infinite number of natural numbers as if we pick any element in the power set of N to stringize, I feel that element will be a set which has a finite number of elements (from the set of natural numbers) and each element in that set will have a finite number of base 10 letters. Except for one element in the power set of N which is the set of all natural numbers itself all will be finite sets. The set of all natural numbers in power set of N can be mapped to number infinity in the set of natural numbers. Thus we can achieve 1-1 mapping. I am trying to stress this point because if you say the infinite letter string constructions in the Construction 1 are not natural numbers, I wanted to emphasize stringized elements obtained in the Construction 2 are unlike the infinite letter strings in Construction 1 and so that cant be an argument.
Hope this clarifies both constructions. Looking forward to your reply as to what I am missing?
@gowers: You’re being contentious. There is absolutely no reason to claim I’m using non-standard descriptions of naturals. You’re the one who is hand waving about infinite subsets of N. You’re saying I can’t use a surjection. Tough. Surjections exist.
“You prefer a nonstandard definition where you can put together infinitely many natural numbers and get a natural number.”
There is no requirement for me to get a natural number and there is no requirement to produce a 1-1 mapping. The only requirement is a surjection from N to R.
See, my claim is exactly right. The “counts” never want to leave behind the notion of finite digits. It’s only required for the naturals. It’s not required for any intermediate mapping. If I map N->X->R, the elements of X need not be finite in length despite your consternations.
I should end the conversation right here, but let me try one more iteration. I agree that if you want to construct a surjection from N to R as a composition of maps from N to X and X to R, then the elements of X do not have to be finite in length. They can be whatever you want them to be. But you do have to prove that the composition is a surjection. The most obvious way of doing that is to prove that you have a surjection from N to X composed with a surjection from X to R. If X is a set of objects that have infinitely long descriptions, then it is likely that getting a surjection from X to R will be the easy part and a surjection from N to X will be the hard part. It depends on exactly how you define X, of course.
So let me ask this. What exactly is your intermediate set X? What is your surjection from X to R? And what is your surjection from N to X?
If I don’t get satisfactory answers to all three questions, then this is my final contribution to this discussion.
@ gowers –
I see you are having an heated conversation with Mr X. Would request you to if possible to respond and if you have time, and please clarify my questions on the two constructions I had posted before.
In the stringized power set construction, I am mapping the elements of power set of set of natural numbers in base 10 to the set of naturals in base 13.
There is also a numerical relationship. Limit of 2 power n/n will tend to infinity when n tends to infinity. Similarly limit of 13 power n/ 10 power n will tend to infinity when n tends to infinity. The second limit is the (number of natural numbers which can be generated with n digits in base 13) / (number of natural numbers which can be generated with n digits in base 10).
Just by changing the representation of natural numbers, I am able to generate so much more natural numbers that the limit of the division between the numbers in these two sets is tending to infinity when number of digits tend to infinity.
I feel this is an observation which challenges the concept of higher cardinality for power set. Infact the power set limit of (2 power n/n) arises through the same construction. That is if we start with binary and unary representation of natural numbers which are the most basic number representations.
With unary representation of natural numbers, with n digits we can represent, n natural numbers.
With binary representation of numbers , with n digits we can represent , 2 power n natural numbers.
The ratio of the two is 2 power n/n. This is exactly the ratio of :
the number of elements in the power set / elements in a set from which the power set was constructed,
This train of thought disproves the higher cardinality of powerset of natural numbers. I think this is an important train of thought which needs to be considered.
Infact I did give you an intermediate set X in the process:
The surjection chain is as below.
N represented in base 10 -> N represented in base 13 -> Power set of N represented in base 10 -> R
N represented in base 13 is your intermediate set X.
If you read my stringization proceedure I have given you:
1. Surjection from N -> X which is quite obvious as both represent natural numbers. Infact it is a bijection.
2. I have also provided surjection from X -> Power set of N through stringization of the power set of N.
3. Power set of N has surjection with R – this you know as both are of same cardinality.
QED.
@ gowers – It would be great if you can comment on the same.
@ gowers –
Infact my stringization of power set technique and then treating each element in the power set as a natural number in base 13 is kind of similar to how godel arrived at a number for each formulae or expression through godel numbering scheme. But mine is simpler as I am just substituting 3 letters – the two braces and comma to A,B,C which are letters for 10,11,12 in the base 13 numbering scheme. Infact I should call it not stringization but numbering of the elements of the power set of Nbase10. But the only trick I do which Godel didnt do in his numbering scheme is I shift the base from 10 to 13 which is the key trick in proving Power Set of natural numbers is of the same cardinality of Natural Numbers. I am just encoding the elements (subsets) in the power set and encoding each element (subset) as a natural number in base 13. Whats wrong with that?
@ Gowers and @ Mr X
I think the whole argument has arisen due to the ability to distinguish one number from another. I will explain this and I feel this will definitely throw light to this discussion.
If it is a natural number we are fine with the unary representatation.
1 – 1
2 – 11
3 – 111
..
infinity – 11111….
But if it is a irrational number then unary representation becomes insufficient. Lets us look at unary representation :
Root of 2 = 1.1111…
Root of 3 = 1.1111…
All look the same but they have different limits and tend towards different numbers.
To bring out the difference necessitates Binary representation.
In binary representation we have:
Root of 2 = 1.0110101000001001111…
Root of 3 = 1.10111011011001111010111010000101…..
The compression in length which is bought by going from unary to binary is 2 power n.
In case of natural numbers we can make do with unary representation. In case of irrational numbers we have no choice but to go with binary representation at the minimum and so the higher cardinality of 2 power n.
But this is because of the simple assumption we made in rational numbers that rational numbers have finite digits and hence we dont need to differentiate between the two numbers
1 followed by infinite zeros and 2 followed by infinite zeros.
These are two different numbers and if they are admitted into natural numbers realm then even natural numbers would need a minimum a binary representation to represent all numbers uniquely. Then even that set would have a cardinality of 2 power n.
So how to arrive at cardinality- look at a set – see what is the minimum representation you need to uniquely encode all the elements of the set – is it unary, binary or tertiary… based on that you can determine the cardinality – whether it is n or 2 power of n or 3 power of n… and so on.
I think this clarifies my doubts and possibly your argument. Please let me know if my reasoning is wrong.
@srinharmahadevan For the sake of Richard Lipton and Ken Regan I should wrap up this discussion too, but let me quickly point out what appears to be your mistake. Obviously there’s a surjection from natural numbers represented in base 10 to natural number represented in base 13. (Just send each number to itself.)
Now let’s write the digits in base 13 as 0,1,2,…,9,{,}, and a comma. Then some numbers will, when written out, give you expressions that can be read as subsets of N, such as {23,425,11,45627,4}. In fact, every finite subset of N will be the image of some number written out in base 13 in this way.
Where you have gone wrong is in thinking that this gives us the power set of N. It doesn’t. The power set consists of all subsets of N, whereas this technique only gives us the finite subsets of N.
If you try to put that right by taking “numbers” with infinitely many digits in base 13, then you are no longer talking about natural numbers, so if you manage to find a surjection to R, it doesn’t tell you that there is a surjection from the natural numbers to R. (It might tell you that there is a surjection from some more general set of “natural numbers with infinitely many digits” to R, but the existence of such a surjection does not contradict the statement that there is no surjection from the set of normal natural numbers — that is, ones with finitely many digits — to R.)
In fact, let me put a question to MrX. Do you agree that if we define N to be the set of all natural numbers that can be represented with finitely many digits, then there is no surjection from N to the real numbers? If you agree with that, then we agree about the mathematics, and the only remaining question is a terminological one.
@gowers
Thanks for your patience 🙂 This discussion is very important to my peace of mind as this issue has been gnawing me for years and I have gotten good clarity during this discussion and quite indebted to this blog and your comments for that. I understood where I faltered in constructing the power set. A subset could be all natural numbers except 1. That would have infinite digits (if I accept that there are infinite natural numbers) and wont correspond to any specific finite natural number and so the surjection wont hold good.
So it boils down to the definitions of natural number and the set of all natural numbers:
1. “All” natural numbers have finite digits and hence it follows all natural numbers are finite in value
2. There are infinite natural numbers in the set of “all” natural numbers
Some may think these two statements contradict each other and some might think they can coexist. That I feel is the source of contention.
One line of thought could be:
If we order the numbers in the set of all natural numbers in the ascending order and as there is only a difference of 1 between one element and the other, we can say the largest number is the size of the set. But then there is no largest number in the set of all natural numbers as given a largest number, we can always generate another number by adding 1. So the largest number is indefinite and hence the size of the set is indefinite and NOT infinity.
While on the other hand, the number of digits to represent an irrational number is truly infinite and not indefinite.
In that line of thought, one could say that Cantor’s theorem is comparing apples and oranges.
But then that’s just a thought. Thanks for the comments and replies!!
To clarify, it is possible for a finite but unbounded space to exist. However, none of those situations apply to naturals.
@ gowers –
I see you are having an heated conversation with Mr X. Would request you to if possible to respond and if you have time, and please clarify my questions on the two constructions I had posted before.
In the stringized power set construction, I am mapping the elements of power set of set of natural numbers in base 10 to the set of naturals in base 13. There is also a numerical relationship. Limit of 2 power n/n will tend to infinity when n tends to infinity. Similarly limit of 13 power n/ 10 power n will tend to infinity when n tends to infinity. The second limit is the (number of natural numbers which can be generated with n digits in base 13) / (number of natural numbers which can be generated with n digits in base 13).
Just by changing the representation of natural numbers, I am able to generate so much more natural numbers that the limit of the division between the numbers in these two sets is tending to infinity when number of digits tend to infinity.
I feel this is an observation which challenges the concept of higher cardinality for power set. Infact the power set limit of (2 power n/n) arises through the same construction. That is if we start with binary and unary representation of natural numbers which are the most basic number representations.
With unary representation of natural numbers, with n digits we can represent, n natural numbers.
With binary representation of numbers , with n digits we can represent , 2 power n natural numbers.
The ratio of the two is 2 power n/n. This is exactly the ratio of :
the number of elements in the power set / elements in a set from which the power set was constructed,
This train of thought disproves the higher cardinality of powerset of natural numbers. I think this is an important train of thought which needs to be considered.
@ gowers – It would be great if you can comment on the same.
@ gowers – Please ignore the above reply as I had posted the same and even expanded it in a different reply chain where you have asked the three questions. I have replied to your three questions around intermediate set X and surjection you had asked Mr X just below your comment in the previous reply chain. Infact those are three questions I have been answering all along in my comments through my constructions. Thanks.
“In fact, let me put a question to MrX. Do you agree that if we define N to be the set of all natural numbers that can be represented with finitely many digits, then there is no surjection from N to the real numbers?”
When you say “with finitely many digits”, are you saying that the aggregate number of digits of all elements of N is finite and thus implies N has finite elements? I can’t see this being what you’re getting. Yet the alternative makes “with finitely many digits” redundant and doesn’t alter the definition of N.
Whatever the case, I believe that there is indeed a surjection from N to R. I believe that what Cantor found is a relationship between rows and digits of any infinite set. IOW, he found a surjection from R to N. I believe that if N constitutes the rows, then there is also a surjection from N to D where D is the digits of N. So because we already know that there exists a bijection between N and D, then this means the same possibility exists for R and N.
The missing part in this is proving that in order to represent all of N, you only need a subset of N for the digits. This part is actually trivially true, but because non-bijections between N and subsets of N are handwaved away, mathematicians refuse to look at the implications. In fact, when people try to explain the flaw in Cantor’s grid, it’s that there is a non-bijection in the grid and the “counts” say “Yes, this is exactly what Cantor is proving” completely missing the point.
Going to repeat mkatkov’s setup:
Consider doubly infinite table X_{k,m} , where index k \in \mathbb{N} enumerates rows, and index m \in \mathbb{N} enumerates columns. Each element X_{k,m} is independent binary random variable with equally probable possible states 0 and 1.
As said, the inverted diagonal means that it’s different from all other rows. The reason stated why this doesn’t apply to N is because this diagonal number is not a natural since it has infinitely many digits. I contend that there is a yet unknown proof that shows the same thing for naturals as it does for reals. But we’ve already defined the rows as N, so it wouldn’t work, right? Except that it would. It would simply mean that the digits D are a proper subset of N. When this unknown proof is applied to a D by D infinite matrix, finding a new element is just fine because D is a proper subset of N. And since |D| = |N|, everything works out.
Just looking at the inverted diagonal always being 1111… with naturals should be a clue that what I’m describing is true. There is always a surjection from rows to digits when listing N in binary (or other higher base).
I think the “counts” have jumped the gun wrt to uncountability. I submit that what Cantor actually found is a property of the digits of any infinite set (which applies to N and R alike).
Ultimately, if it can be proven that we only need a subset of N digits to represent all of N rows, then Cantor’s conclusion was wrong. The proof is still valid, but the interpretation of it would need to be updated to simply mean that the relation between the elements of an infinite set and its digits is always a surjection. IOW, this is a very specific mapping that is non-bijective, nothing more.
@gowers Tim, since you holding discussion, this is the argument – in the typical universe reals are countable, only in the small number of universes (of measure 0) reals are uncountable.
Consider doubly infinite table
, where index 
enumerates rows, and index 
enumerates columns. Each element 
is independent binary random variable with equally probable possible states 
and 
. Suppose 
is a realization of random variables. We are going to fix it for the rest.
Cantor diagonal argument Let row
. Since, 
is different from every row in at lest one place it is not in the table. Using induction we can check the next row diagonal element, and will get proof by induction.
Theorem There are countably many rows equal to any
in the table with probability 1.
) where the first column has value 
: 
. Since 
is a realization of independent random variable, there are infinite number of rows in 
with probability one. Moreover, viewing 
as a table one can see that 
, and 
is a realization of equi-probable binary random variable.
Proof
Initialization. Select the subset of rows (
Induction step. Suppose there is a set of countable many rows
such that 
. We select from the table 
a subset of rows that have 
. The set 
consists of countable infinite number of rows with probability 1. Moreover, the table 
divided into 2 parts. The left part- columns from 1 to 
– all rows coincide with 
. The right part – all columns starting from 
are realization of independent random variable.
Therefore, by induction, there is set “
that is countably infinite with probability 1, and each member consists of rows 
. QED.
You seem to misunderstand induction. It doesn’t give you a statement about what happens “at infinity”. It just tells you what happens at each finite n. Have a look at the statement of the axiom of mathematical induction on Wikipedia. Infinity is not mentioned.
For an example that illustrates why it has to be this way, consider the sequence
of subsets of 
where 
consists of all multiples of 
. Then each 
is an infinite subset of 
. But the intersection of all the 
is empty: there is no positive integer that is a multiple of every single power of 2. So there is no way of extending the sequence of sets to an infinite set 
that is a subset of all of them.
Can you prove that intersection is empty? without Cantor diagonal argument?
In other words, at what k
becomes empty? if I say will take intersection consecutively.
For every k the intersection up to k is non-empty, so there is no k of the kind you ask for. Nevertheless the intersection of all the sets is empty.
There is no paradox here. A very simple example of a collection of sets exhibiting this phenomenon is given by
That is,
consists of all positive integers from 
onwards. The intersection of the first 
of these sets is just 
. But the intersection of all of them is empty, since no positive integer is greater than every single 
.
In the case of your sets, your theorem is false. A quick proof is as follows (but it requires some knowledge of measure theory). Let us fix a y and look at the probability that the jth row of your table belongs to every single
. The probability that it belongs to 
is 
. Therefore, the probability that it belongs to every 
is smaller than 
for every 
. In other words, it is zero. So each row has a zero probability of belonging to all the 
. Since there are countably many rows, it follows that the probability that there exists a row that belongs to all the 
is zero.
You might object to this argument on the grounds that I have used the statement that a countable union of sets of measure zero has measure zero, which immediately implies that the reals are uncountable. But if your argument depends on rejecting a basic statement in probability, then you must explain why you reject it, which puts you more or less back where you started.
First, you certainly right, by definition. Second,
example seems to be true by definition, e.g. an axiom. I do not see why it has to be empty, except that it coincides with intuition – I think it is cheating about infinity- this statement about human brain – if you could not provide an example it does not mean it is empty. Measure 0 does not mean the set is empty. And finally, you counting probability top-down and getting 0, if you count probabilities left-to-right the probability is one. There is something wrong with infinity- there are more than one truth. But again I do not insist, you are right by definition.
20 years ago I was pretty sure reals are uncountable. Now after your argument I’m not sure why 0.9(9) = 1.(0) and why those argument does not apply to the numbers in random table.
There’s a visual reference to Cantor’s diagonalization argument in the trailer for my new independent film “Digital Physics”. Please check it out, fellow nerds:) The debate on Infinity(ies) gets to the heart of what the movie is all about.