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?
 A: 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.
A: 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.
A: 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.
