Home > puzzles, theory > Do we believe the Axiom of Choice ?

Do we believe the Axiom of Choice ?

April 10th, 2011 Leave a comment Go to comments

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 n+1 people in a line, and each has a 0/1 number on his hat. Each player can look to the numbers of the players in front of him. So, if x_i is the number of player i, then player i knows x_{i+1},\hdots,x_n. Now, from i = 0 \hdots n the players will say his own number. Is there a protocol such that players 1,\hdots,n 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 x_i; i \in \mathbb{Z}_+ and player i knows x_j for all j > i. 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 0 could  simply declares y = x_1 \otimes\hdots \otimes x_n where \otimes stands for XOR. Now, player 1 can for example reconstruct x_1 by y \otimes x_2 \otimes \hdots \otimes x_n. Now, player 2 can do the same computation and figure out x_1. Now, he can calculate x_2 = y \otimes x_1 \otimes x_2 \otimes \hdots \otimes x_n 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 \{ S_i \}_{i \in I} there is a set \{x_i; i \in I\} such that x_i \in S_i, 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 \mu : 2^{[0,1)} \rightarrow \mathbb{R} that is shift invariant (say under addition modulo 1) and \mu([0,1)) = 1. The proof goes the following way: define the following equivalence relation on [0,1): x \sim y if x - y \in \mathbb{Q}. Now, consider the family of all the equivalence classes and invoke the Axiom of Choice. Let K be the set obtained. Now, we can write the interval as a disjoint union:

[0,1) = \cup_{x \in \mathbb{Q}} (K+x)

where all operations are modulo 1 and K+x = \{y+x; y \in K\}. Since it is an enumerable union, if such a measure existed, then: \mu([0,1)) = \sum_{x \in \mathbb{Q}} \mu(K+x) = \sum_{x \in \mathbb{Q}} \mu(K) which is either 0 if \mu(K) = 0 or \infty if \mu(K) >0.

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 S be the set of all infinite \{0,1\}-strings and consider the equivalence relation on S such that x \sim y if the strings differ in a finite number of positions. Now, invoke the axiom of choice in the equivalence classes and let S_0 be the set of representatives. Now, if F is the set of all strings with finite number of 1‘s and \otimes the operation such that z = x \otimes z if z_i = x_i \otimes y_i. We can therefore write:

S = \cup_{x \in F} (S_o \otimes x)

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 S/\sim they the entire string is. Now, they take y \in S_0 the representative of this class and guess y_i. Notice that y will differ from the real string by at most a finite number of bits.

Now, to solve puzzle #1, the player 0 simply looks at x = x_1 x_2 \hdots and figure out the equivalence class he is and let y \in S_0 be the representative of this class. Now, since x and y differ by a finite number of bits, he can simply calculate XOR of x and y (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.

Categories: puzzles, theory Tags:
  1. No comments yet.
  1. No trackbacks yet.