Do we believe the Axiom of Choice ?
Continuing on my series of posts from Israel, I’d like to share some exciting puzzle that I heard today from Omer Tamuz. I’ve learned before about the Axiom of Choice in a Measure Theory class, but never saw a so striking and counter-intuitive application of it. Ok, you might say the Banach–Tarski paradox is a pehaps better example – but since it’s proof is so complicated, it is not as striking as seeing how a simple application of it can generate un-intuitive results. First, let me present two puzzles:
Puzzle #0: There are people in a line, and each has a number on his hat. Each player can look to the numbers of the players in front of him. So, if is the number of player , then player knows . Now, from the players will say his own number. Is there a protocol such that players will get their own number right? (Notice that they hear what the players before him said).
Puzzle #1: Consider the same puzzle with an infinite number of players. I.e. there are and player knows for all . Show a protocol for all players, except the first to get the answer right?
Puzzle #2: Still the same setting, but now players don’t hear what the previous player said. Is there a protocol such that only a finite number of players get it wrong ? (notice that it needs to be finite, not bounded).
Puzzle #0 is very easy and the answer is simply parity check. Player could simply declares where stands for XOR. Now, player can for example reconstruct by . Now, player can do the same computation and figure out . Now, he can calculate and so on… When we move to an infinite number of players, however, we can’t do that anymore because taking the XOR of an infinite number of bits is not well defined. However, we can still can solve Puzzles #1 and #2 if we believe and are willing to accept the Axiom of Choice.
Axiom of Choice: Given a family of sets there is a set such that , i.e. a set that takes a representative from each element in the family.
It is used, for example to show that there is no measure that is shift invariant (say under addition modulo ) and . The proof goes the following way: define the following equivalence relation on : if . Now, consider the family of all the equivalence classes and invoke the Axiom of Choice. Let be the set obtained. Now, we can write the interval as a disjoint union:
where all operations are modulo and . Since it is an enumerable union, if such a measure existed, then: which is either if or if .
This is kinda surprising, but more surprising is how we can use the exact same technique to solve the puzzles: first, let’s solve Puzzle #2: let be the set of all infinite -strings and consider the equivalence relation on such that if the strings differ in a finite number of positions. Now, invoke the axiom of choice in the equivalence classes and let be the set of representatives. Now, if is the set of all strings with finite number of ‘s and the operation such that if . We can therefore write:
Now, a protocol the players could use is to look ahead and since they are seeing an infinite number of bits, they can figure out which equivalence class from they the entire string is. Now, they take the representative of this class and guess . Notice that will differ from the real string by at most a finite number of bits.
Now, to solve puzzle #1, the player simply looks at and figure out the equivalence class he is and let be the representative of this class. Now, since and differ by a finite number of bits, he can simply calculate XOR of and (now, since it is a finite number of them, XOR is well defined) and announce it. With this trick, it just becomes like Puzzle #0.