Poker and Cantor’s Proof
The reals are still uncountable
Dave Patterson is a world-famous expert on computer architecture. He has won many awards, and is a member of the National Academy of Engineering and the National Academy of Sciences. He coined the term “RISC” and later the term “RAID.” He also wrote definitive textbooks on computer architecture, with John Hennessy, including the famous Computer Architecture: A Quantitative Approach..
Today I and Ken want to continue the last discussion on Georg Cantor’s Diagonal Proof. My goal is to try to answer one of the issues raised about this famous proof. I do thank all the commenters for an interesting discussion.
What does this have to do with Dave? He is not a theorist, and may know Cantor’s proof—but certainly is not excited about it. He is very practical-oriented: his most famous work is on the design of Reduced Instruction Set Computing processors.
But Dave is a poker player. When I arrived at Berkeley in the late 1970’s, I wanted to bring one tradition from Yale to Berkeley: playing a “friendly” game of cards on a regular basis. I assumed that my theory colleagues, Dick Karp and others, would be interested in playing. The game I had in mine was low stakes poker. The rules were “dealer’s choice” and modified “pot limit.” The latter means one could make a bet that was bounded by half the current pot. This method of betting was introduced to me by Albert Meyer, and it can lead to exponential increases in bets. This increase makes the game exciting—I felt—and allows for bluffing. Even through the stakes are low, the game can be quite exciting.
In any event I was sure that my theory friends at Berkeley would jump at a chance to put probability theory to a practical test. I was wrong. Every member of the theory group said: not interested, sorry. The sole possible exception was Karp, but poker requires players for much greater than to be fun. I was about to give up when I mentioned it one day to Patterson. Before I knew it all the computer architecture group—well most—had signed up, and a new course was created:
When you got the message, “CS 52 this week at X’s house,” you knew the game was on. We played for the two years that I was at Berkeley, and had a great deal of fun. I believe that they still play poker there, although the game has changed to Texas Hold ‘Em and the betting is different. I believe that it is one of my great and lasting contributions to Berkeley Computer Science Department. Perhaps they will put up a plaque that says…
Show Your Hand
In almost any version of Poker—Texas Hold ‘Em, Stud, Draw, or any other variant—there comes a time when all the bets and raises and re-raises are done. At this point, if you are the person who last bet or raised, you must show your hand, that is, must lay your cards on the table. That’s part of the meaning of saying that you have been called. Then the other players can either throw their hands away or show their cards and prove that they have a better hand. The winner takes the money.
If you are called you must show your cards. You are not allowed, if called, to say I will show my cards later; or go through the deck and change you hand. The game has come to the showdown—you must show what you have. Not anything else. Any attempt to not do this is considered cheating—do not try this in a real game.
The same principle of showing your hand applies to mathematical proofs. For instance, if you are a Count and thus believe that the reals are countable, then you must be prepared to give a listing of the reals—essentially show your cards. This is where most Counts have trouble: they want to be able to change their “hands.” Tim Gowers said it best when he wrote that he usually asks a Count to present the actual listing. Essentially Tim is calling them, and demanding that they show their hand.
Note that this requirement is standard math, and has nothing at all to do with countable sets, uncountable sets, infinities, or the reals. If you are claiming that is rational, you must be prepared to agree that there is some fixed and natural numbers, so that
You are not allowed to change the values of and during the proof. Either there is a fixed or there is not.
Another example is Euclid’s classic proof that there are an infinite number of primes. If you believed that there is a largest prime, then you must be prepared to say that is the largest prime. Then, Euclid can use this number to force you to consider
The argument then shows that is either prime or is divisible by a prime , where must be larger than .
An even simpler version of this is the “largest number game.” You name a number and then I have to name a larger one. Again if you think that there is a largest one, you must be prepared to say that the largest one is , say. Then I point out that is larger. Scott Aaronson retold here an old story based on this game:
Two noblemen vie to name the bigger number. The first, after ruminating for hours, triumphantly announces “Eighty-three!” The second, mightily impressed, replies “You win.”
Back To The Proof
If you believe the reals are countable, then you must show your hand. You must fix a listing of the reals:
This is nothing different from picking a pair to show that is rational, that there is a largest prime , or even that there is a largest number . This is the show your hand step. If you disagree with this step in Cantor’s proof, then you must also do the same in the above simple examples. You also must not play Poker by the standard rules.
Once I have seen your hand, the sequence , I can try and find a real that you missed. There are many ways that I can do this. Since I can always construct a real number based on your sequence, your hand, that is not any , I win. Your sequence does not contain all the reals.
Leading Out Versus Check-Raising
Ken on the other hand recalls he did not play a single hand of poker during 5-1/2 years at Oxford, and has picked up poker recently only because of the interest of his son. But he finds that his own angle on Cantor’s theorem, informed by his exposure to finitists at Oxford, fits in well with the poker analogy.
In poker a player whose turn to bet comes first is “under the gun” and often at a disadvantage. Assertively “leading out” with a sizable bet gives opponents more leverage to raise since more of the player’s own money is in the pot. Instead the player is allowed to check, i.e. to bet zero, and subsequent players may check until a bet is made. If an opponent bets, then the first player is in the situation of being able to raise, not just call. A raise then is called a check-raise.
The math analogy is that asserting the existence of a set that is in some sense more complex than any set previously admitted is a form of leading out. If we’ve only reached a comfort zone with countable sets, then an uncountable set represents a new level of complexity. Indeed, to a finitist, every power-set is a big step up in complexity. If you think a googolplex is a meaningless quantity, then you can only iterate for a few steps before you would pass it.
Leading out with an object on a new level of complexity takes chutzpah. But even a humble finitist may be comfortable with theorems of the form, “If you have an object then I can give you a .” This is like saying “I check”—let someone else bet . If has the same intuitive complexity level as then that is like a call. If is a step up in complexity from , but similar to how was a step up from whatever was “in the pot” already, then is a check-raise.
The “Humble” Cantor Theorem
Here is a form of Cantor’s Theorem that embodies the check-call or check-raise idea, depending on how it is applied:
Theorem 1 Given any mapping from a set into its power set , we can find a subset of that is not in the range of .
Proof: Define . We claim that is not in the range of . If it were, then there would exist a such that . But then we have:
|is in the set||by definition of|
|is not in the set||by definition of .|
Since a logical statement can never be equivalent to its negation, this contradicts being in the range of .
Note that the proof itself embodies Cantor’s diagonal argument, but makes no reference to infinite constructions or possibilities, indeed no reference to infinity at all. It is not asserting anything on its own, but reacting to someone else giving an . Since has roughly the same complexity as —both involve the power set—producing is like a call.
What this has done is bring the implied onus of the bettor to show one’s hand into the theorem statement itself. It puts the question to the Count right away. For simplicity, let’s first talk about the power set of being uncountable:
If you think that is countable, then you are giving me a function from to that is onto . You can’t give me such a function, because I can give you and it will show that you were bluffing.
With a little technical work a Count should be convinced that a bluff on is equivalent to a bluff on . Thus the Count must admit that one can never have the cards to win a showdown that the reals are countable, and by “never” itself, should come on board that they are uncountable.
One nice point about this formulation is that it carries over verbatim to prove the existence of non-r.e. sets. Just take to be the mapping from a Gödel number to the language accepted by the Turing machine , and what tumbles out is the creation of a diagonal language . Since is more complex than any in the sense of being non-r.e., we can call that a check-raise.
How widely can one replace theorems of the form “There exists a ” with “humbler” ones of the form “If you give me an , then I can build a “? Upon producing an they have the same effect. Do the latter kind show the flow of reasoning better?
Going beyond the cardinality of the reals, asserting the existence of certain Large Cardinals is a recognized way of extending ZFC set theory. Remarkably, all that have been studied are linearly ordered under the relation if ZFC + “ exists” proves the consistency of ZFC + “ exists.” That is, they are totally ordered by modulo the equivalence relation if ZFC proves the statement that “ZFC + ` exists’ is consistent ZFC + ` exists’ is consistent.” Moreover there are cases where but (if these cardinals exist at all) .
Thus the large-cardinal axioms represent progressively higher levels of complexity, in our intended intuitive sense. How high a cardinal will you bet on? Are you a SuperCompactUncount? The theorems underlying the relation can by-and-large be given the form, “If you show me a I can build a .” It is interesting to ask how illuminating this theorem structure can be for mathematics closer to home.
Do these analogies help?
Note that RISC does not mean that the instruction set is reduced in numbers, but rather than each individual instruction carries a reduced workload vis-à-vis a comparable CISC instruction. Can we organize mathematical theorems in an analogous manner? Would “humble” forms make theorems easier to understand?
Is it Texas Hold ‘Em, Texas Hold’Em, Texas HoldEm, Texas Hold Em, Texas Hold-Em, Texas Hold-‘Em, Texas Hold’ Em, Texas Hold ’em, Texas Hold’em, Texas Hold em, Texas Hold-em, Texas Hold-’em, Texas Hold’ em, Texas hold ’em, Texas hold’em, Texas hold em, Texas hold-em, Texas hold-’em, Texas hold’ em, or just Poker?