### Archive

Posts Tagged ‘measure theory; puzzles’

## 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 $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: Tags: