When discussing the validity of the Axiom of Choice, the most common argument for not taking it as gospel is the Banach-Tarski paradox. Yet, this never particularly bothered me. The argument against the Axiom of Choice which really hit a chord I first heard at the Olivetti Club, our graduate colloquium. It’s an extension of a basic logic puzzle, so let’s review that one first.
100 prisoners are placed in a line, facing forward so they can see everyone in front of them in line. The warden will place either a black or white hat on each prisoner’s head, and then starting from the back of the line, he will ask each prisoner what the color of his own hat is (ie, he first asks the person who can see all other prisoners). Any prisoner who is correct may go free. Every prisoner can hear everyone else’s guesses and whether or not they were right. If all the prisoners can agree on a strategy beforehand, what is the best strategy?
The answer to this in a moment; but first, the relevant generalization.
A countable infinite number of prisoners are placed on the natural numbers, facing in the positive direction (ie, everyone can see an infinite number of prisoners). Hats will be placed and each prisoner will be asked what his hat color is. However, to complicate things, prisoners cannot hear previous guesses or whether they were correct. In this new situation, what is the best strategy?
Intuitively, strategy is impossible since no information can be conveyed from anyone who knows your hat color to you, so it would seem that everyone guessing blindly. However, all but a finite number of prisoners can go free!
I should give credit where it is due. I heard of both of these puzzles in Mike O’Connor’s talk, and I believe that he came up with the solution to second puzzle which is so troubling. Also, I cannot find it anywhere, but I have heard that Chris Hardin wrote a paper on problems of this type.
First, lets review the solution the the basic problem. The first prisoner who has to guess his hat color is out of luck; he can’t possibly have any information about his hat, so he has a 50% of being right no matter what. However, that means he is free to use his guess to try to convey some information to the rest of the prisoners with his guess.
Hmm, he could say the color of the hat on the guy in front of him. That guy would then guess correctly, but then the next guy would be in the same situation as the first guy. Repeating this idea gets only 50 prisoners out guarenteed, with an average of 75 getting out.
We can do better. Instead of just telling the guy in front of him his hat color, the first guy counts the total number of white hats. If it is odd, he says “white”, and if it is even, he says “black”. Then the guy in front of him can count the number of white hats he can see, and if differs from the parity the first guy counted, he knows his hat is white. But now the next guy knows the parity of white hats the first guy saw, and whether or not the second guy had a white hat, so he can compare it to the white hats he sees, and find out if his own hat is white. This argument repeats, and so everyone except the first guy guesses correctly.
Its interesting to notice that a larger number of hat colors poses no problem here. For any set of hat colors , the prisoners can pick an abelian group structure on . Then, the first prisoner guesses the ‘sum’ of all the hat colors he can see. The next guy can then subtract the sum of the hat colors he sees from the hat color the first guy said to find his own hat color. Again, this argument repeats, and so everyone except the first guy gets out. For the case of black and white, the previous argument used black = 0 (mod 2) and white = 1 (mod 2).
This is all well and good, but it doesn’t seem to help the countably infinite prisoners in the second puzzle. Since they can’t hear anyone else’s guess, they can’t set up a similar system for passing on information. So what can they do?
First, instead of thinking of hat colors, they just turn white into 1 and black into 0 (like above). Then, a possible scenario of hats on their heads is an infinite sequence of 1′s and 0′s. Call two such sequences ‘equivalent’ if they are equal after a finite number of entries. This is an equivalence relation, and so we can talk about equivalence classes of sequences.
Next, the prisoners invoke the Axiom of Choice to pick an element in each equivalence class, which they all agree on and memorize. Now, when they are put in line and get a hat, they will be able to see all but a finite part of the sequence, and so they can all tell what equivalence class they are in. Their strategy is then to guess as if they were in the pre-chosen element in that equivalence class.
How well does this work? Well, the sequence they are actually in and the representative element they picked with the axiom of choice must be equivalent, so they are the same after a finite number of entries. Therefore, after a finite number of incorrect guesses, each prisoner will miraculously guess his hat color correctly!
This solution is also pretty stable, in that most attempts to make the puzzle harder don’t break it. The warden can know their plan and even know their precise choice of representative sequences. If so, he can make sure any arbitrarily large finite number of them are wrong, but he can’t get an infinite number of them. Also, the number of hat colors can be arbitrarily big; the same solution works identically.
This last point is pretty trippy. In the two color case, its very reasonable for any prisoner to guess his hat color correctly, and also for arbitrarily large numbers of them to get it right in a row. Effectively, at no finite point in the guessing do the results of the optimal strategy appear to differ from random guessing. However, if there are uncountably many hat colors, then the probability of any prisoner randomly guessing his hat color is 0. One can reasonably expect no prisoners to be correct for random guessing, so when eventually that first prisoner guesses correctly, the warden should be rightly shocked (though not as shocked as he will be when all but a finite number of prisoners guess correctly).
I find this solution deeply troubling to the intuitive correctness of the axiom of choice. Sure, this is based primarily on my intuition for finite things and a naive hope that they should extend to infinities. I think particularly troubling is in the uncountably many colors case, where any given prisoner has no chance to guess his hat color correctly, and yet almost all prisoners are correct.