# Why does the infinite prisoners and hats puzzle require the axiom of choice?

Infinite prisoners puzzle.

The link to Wikipedia describes the puzzle, and the solution. The axiom of choice is used to pick a sequence from each equivalence class, which the prisoners memorize beforehand.

However, the answer says "When they are put into their line, each prisoner can see what equivalence class the actual sequence of hats belongs to."

Why not wait until the prisoners see which equivalence class they are in. Then, pick a sequence from this equivalence class? This would avoid having to use the axiom of choice, or am I mistaken?

If each prisoner individually picks an arbitrary representative of the equivalence class of the actual sequence of hat colors, and guesses their own hat color according to this arbitrarily selected one, then it is possible that every single prisoner guesses their hat color wrong. There is no limit.

They need to coordinate and agree on one representative for every single equivalence class and stick to the chosen representative, because then only finitely many of them can be wrong instead of arbitrarily many of them.

• My knee jerk reaction is that since all sequences in the same class are equal after a finite number of entries, even if each prisoner pick a different representative, there are only a finite number of wrong guesses. Is this wrong because there might not be a upper bound to the number of these finite entries? – Legendre Mar 25 '13 at 15:38
• @Legendre: Suppose the actual sequence is (0,0,0,...) and each prisoner picks the representative with a 1 on their own hat color and 0 for every other coordinate. Your reasoning is wrong: there can be at most finitely many errors between the actual sequence and each representative, but if each prisoner picks their own representative separately and there are an infinite number of prisoners then there can be an infinite number of errors in total - only finitely many per prisoner. – anon Mar 25 '13 at 15:41
• Alternatively, each prisoner picks the representative that is 1 up to their own hat, and 0 for every other coordinate. Each of these sequences have finite number of differing entries. But all the prisoners would be wrong too. Ah thanks for putting my thoughts together. Puzzles involving infinities always confuses me! (but they're still fun) – Legendre Mar 25 '13 at 15:46

They aren't allowed to discuss things once they are in line, so it might be that each prisoner picks a different representative for the equivalence class. They need to pick a representative beforehand to avoid this problem, and if they pick beforehand they need to pick a representative for every equivalence class because they don't know which one they will be in yet.

In addition to the fact that the prisoners are not allowed to communicate between them after they are given the hats, it should be added that not every infinitely many choices require the axiom of choice, however this particular choice does.

It is consistent that there is no choice function from the set of equivalence classes of binary sequences modulo finite differences. In such universe the prisoners are doomed to fail.