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?
Like this:
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
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.
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 …
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?
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}.
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.