Bram Cohen (bramcohen) wrote,
Bram Cohen

The Axiom of Choice is Bullshit

The axiom of choice is presented as 'obviously' true, an axiom which can be simply thrown on the pile in the interests of convenience, without raising any notable philosophical hackles.

Bullshit. The standard statement of the axiom of choice is heavily spun to be obviously true of finite quantities, which is the only thing most people have intuition for. Digging into the details turns up the seedy underbelly...

Let's say that there are a countably infinite number of people (that's plain old infinite to those of you who haven't studied such things) and that each of them has a hat on their heads, either red or blue. Each of them can see the color of the hats on everybody else's heads, but not the color of their own hat. Each of them must write down a guess as to the color of their own hat, with no ability whatsoever to communicate with anybody else. Can you devise a strategy for hat color guessing such that there's guaranteed to only be a finite number of people who guess their own hat color wrong?

Obviously no, but I wouldn't have asked the question if the answer wasn't yes. I'll start with the reason why not.

What is the expected number of hats which are guessed wrong? Well, each person has a 1/2 chance of getting their own hat color wrong, so the expected total number is 1/2 + 1/2 + 1/2 + ... which happens to sum to infinity, which can't be finite. What's wrong with this reasoning? Not anything really, I'll get back to that in a moment.

So what is the strategy? Well, first let's define two assignments of all hats as being 'almost' the same if they only differ in a finite number of hat assignments. Note that if assignments A and B are 'almost' the same, and assignments B and C are 'almost' the same, then assignments A and C must be 'almost' the same. Likewise, if A and B are 'almost' the same, and B and C aren't 'almost' the same, then A and C can't be 'almost' the same. So 'almostness' forms an equivalence class of assignments. By the axiom of choice we can pick a canonical representative of each set of 'almost' identical assigments.

Each person then simply observes what assignment is on everyone else's hats, uses that to figure out what element of the equivalence class they're in (which they can by using either hat assignment for themselves, because it changes at most one hat) then guesses the color on their own hat by picking the one in the canonical representative. By construction, the number of wrong guesses must be finite, so we have our strategy.

What was wrong with the argument that the expected number of wrong guesses is infinite? Nothing whatsoever. The number of wrong guesses is a 'random finite number'. The probability that it's greater than any specific finite number is one, and its expected value is infinite. Does this mean that the statement that there isn't a 'finite' number which isn't in the set 1, 2, 3, etc. conflicts with the axiom of choice? I think it does, but would appreciate it if someone more well versed than I in the foundations of mathematics chimes in.

In answer to the question of the definition of 'finite', a finite set is one for which it's impossible to form a one-to-one mapping between a proper subset of its elements and all of its elements.

Thanks to Lance Fortnow for linking me to this craziness.
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded