Posts Tagged ‘math.LO’

The Axiom of Choice is Wrong

September 13, 2007

    When discussing the validity of the Axiom of Choice, the most common argument for not taking it as gospel is the Banach-Tarski paradox.  Yet, this never particularly bothered me.  The argument against the Axiom of Choice which really hit a chord I first heard at the Olivetti Club, our graduate colloquium.  It’s an extension of a basic logic puzzle, so let’s review that one first.

100 prisoners are placed in a line, facing forward so they can see everyone in front of them in line.  The warden will place either a black or white hat on each prisoner’s head, and then starting from the back of the line, he will ask each prisoner what the color of his own hat is (ie, he first asks the person who can see all other prisoners).  Any prisoner who is correct may go free.  Every prisoner can hear everyone else’s guesses and whether or not they were right.  If all the prisoners can agree on a strategy beforehand, what is the best strategy?

The answer to this in a moment; but first, the relevant generalization.

A countable infinite number of prisoners are placed on the natural numbers, facing in the positive direction (ie, everyone can see an infinite number of prisoners).  Hats will be placed and each prisoner will be asked what his hat color is.  However, to complicate things, prisoners cannot hear previous guesses or whether they were correct.  In this new situation, what is the best strategy?

Intuitively, strategy is impossible since no information can be conveyed from anyone who knows your hat color to you, so it would seem that everyone guessing blindly.  However, all but a finite number of prisoners can go free!