The prima facie hole in the argument is here: "During their consultations the night before, prisoners have agreed on a CHOICE function: For each equivalence class, they have assigned a particular representative sequence."

The Axiom of Choice guarantees that such a choice function *exists*; it doesn't guarantee that prisoners can *all agree on one*. In general there will be infinitely many choice functions for a prisoner to choose from among. By what mechanism will the prisoners be able to pick out one from all the possibilities and ensure that they're all going to use the same choice function when it comes to deciding what color to say their hats are?

Is this objection to the mathematical abstraction, or to "real-world" limitations? For example, instead of an infinite number of prisoners, could we postulate a Hydra-like creature with a single brain to come up with the choice function, but that had to use his infinitely-many fire-walled brainlets during the guessing phase?

Or maybe you've hit on the fundamental flaw (or elusiveness) in the Axiom of Choice: It's one thing to say "There exists a choice function" and another thing to actually hold that function in your hands, or be able to write it down.

Having more things between any two things isn't what makes a set uncountable. Between any two rational numbers there are more rationals; for instance (A + B) / 2 is in between A and B. But the rational numbers are a countable infinity.

The rationals are proven to be countable if they can be mapped one-to-one to a subset of the natural numbers. An inelegant brute-force way is to map each a/b to (2

^{a}3

^{b}). (Multiply this by 5 to represent -a/b.) Insist that a/b be in lowest terms to avoid duplication.

I think that a similar approach can be used to show that each of the equivalence classes I introduced upthread is countable (though this demonstration uses AC at the outset). If 'a' is in the class whose chosen representative is 'b' then 'a' has a finite number of "misguesses" (m

_{1}. m

_{2} ...) each of the form (i,j) where i and j are natural numbers: — 'i' is the location of the misguess, 'j' is the wrong guess.

(i,j) can be represented with the integer (m = 2

^{i}3

^{j}). 'b' itself can be denoted (given knowledge of its class's representative) by

2^{m1}3^{m2}5^{m3}7^{m4} ...
That is, the k'th misguess is encoded as the exponent of the k'th prime.

If this is correct — and by now I'm giving myself at best a 30% chance — then it means we are using only a weak form of the Axiom of Choice in the proof upthread: We are imposing a choice function on an (uncountable) collection of COUNTABLE sets.