Log in

No account? Create an account

Wed, Jun. 13th, 2007, 05:26 am
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.
(Deleted comment)

Wed, Jun. 13th, 2007 01:15 pm (UTC)

Yeah, I glossed over that detail. I'm just trying to describe the technique here, not formally prove it.

You can always pick a representative element of any equivalence class, especially equivalence classes you can describe. AC is necessary for the statement that they exist in all cases.
(Deleted comment)

Wed, Jun. 13th, 2007 02:40 pm (UTC)
scar3crow: Re: ooh! a maths joke!

i have a hard time relating to people when i start talking theology or serious game design - maybe i should pick up mathematics as well! friends, begone!

this was a fun read however, completely out of left field for me.

Wed, Jun. 13th, 2007 03:36 pm (UTC)

No, it doesn't mean that the axiom of choice requires there to be a finite number that isn't 1, 2, 3, etc. It's not hard to produce random variables that are always finite but have infinite expected value, without making any use of the axiom of choice. (For instance: pick n with probability proportional to 1/n2; the expected value is (a constant times) the sum of the harmonic series 1 + 1/2 + 1/3 + 1/4 + ..., which is infinite.)

The puzzle you presented is lovely, and certainly counterintuitive, but I'm not sure I'd call what it provides a strategy. After all, the axiom of choice is "nonconstructive"; you can't actually do this, even if AC is true, any more than you can actually cut a pea up and rearrange the pieces with no gaps into something the size of the earth. (That's the Banach-Tarski paradox, which I think is even more counterintuitive.)

Wed, Jun. 13th, 2007 07:16 pm (UTC)

Excellent post (says a math major). I don't really have much to add.

Fri, Jun. 15th, 2007 06:37 am (UTC)

You can't cut up a... well, great. *Now* what am I going to do with my weekend?

Wed, Jun. 13th, 2007 04:51 pm (UTC)

I'm almost certain I'm missing something, but doesn't that strategy take infinite time?
(Deleted comment)

Thu, Jun. 14th, 2007 09:00 am (UTC)

The example you present doesn't work. You don't need AC to prove Heine-Borel. All you need is the law of excluded middle (which is a whole different controversy).
(Deleted comment)

Thu, Jun. 14th, 2007 04:54 pm (UTC)

Fair points all. And no, I wouldn't get rid of AC either.

Wed, Jun. 13th, 2007 10:24 pm (UTC)

I like constructivism.

Thu, Jun. 14th, 2007 08:55 am (UTC)
clgroft: No, sorry, it's your argument that's bullshit

First off, if you ever think you've disproven AC with ordinary mathematics, you are almost certainly wrong. The only way that can happen is if set theory itself, AC or no, is inconsistent. Gödel proved that in the late 1930's.

Aside from the error that gjm11 pointed out (good job, gjm11!), the one specific mistake you made was as follows:
The probability that [the number of wrong guesses is] greater than any specific finite number is one

You present no reason to believe this. I doubt you have one, since if you did, it would indeed disprove AC.

Incidentally, judging from the similarities between this and Vitali's construction, I suspect that you have found some nonmeasurable sets, i.e., ones which don't have well-defined probabilities assigned to them. (That such beasts exist is one of the "weird" consequences of AC.) I can't prove this - at least, not at 2 AM - but it seems likely.

Thu, Jun. 14th, 2007 11:46 pm (UTC)
gjm11: Re: No, sorry, it's your argument that's bullshit

Yup, nonmeasurable sets.

Proof: for each of the countably many finite subsets A of N, consider the function fA that flips the colours of the hats of people in A. This function is obviously measurable (i.e., inverse images of measurable sets are measurable), and indeed measure-preserving and bijective. Now let S be your set of representatives. Then the fA(S), as A runs over the finite subsets of N, are disjoint, and their union is all of 2N. If any of them is measurable then they all are and all have the same measure (because fA is measure-preserving). But then by countable additivity the measure of the whole space is either 0 (if |S|=0) or infinite (if |S|>0), but in fact the measure of the whole space is 1, contradiction.

Summary of proof: consistently flipping any finite set of bits turns our set of representatives into another set that's "obviously the same size"; there are countably many of these, and they partition 2N, so whatever the probability p of having no wrong guesses, we have to have infinity * p = 1, which is impossible.

I expect this can be tweaked to yield a proof that the event "at least n errors" is non-measurable for each n -- i.e., that the probability of getting at least n errors is undefined -- but I'm too lazy to try. :-)

Thu, Jun. 14th, 2007 02:47 pm (UTC)
another_old_guy: Uh, wait a minute...

Doesn't "choosing a finite number at random" (i.e., selecting an element of the infinite set of integers, with no additional qualification) require the axiom of choice?

Thu, Jun. 14th, 2007 05:12 pm (UTC)
clgroft: Re: Uh, wait a minute...

No, selecting one element from a nonempty set is considered valid, no matter how big the set is. In mathematical arguments, one often sees "There exists x where A(x); let k be such an object", or words to that effect, and it's not considered a problem. Once you can make one choice, as here, then you can make two, or three, etc.

The problem arises when you have an infinite family of nonempty sets, and have to make a choice simultaneously for all of them. It's the number of choices that matters, not the number of options for each choice.

Don't feel too bad. Paul Cohen, the man who proved that AC is not provable from ordinary set theory, thought the same thing early on. If it can confuse him...

Thu, Jun. 14th, 2007 05:39 pm (UTC)
another_old_guy: Re: Uh, wait a minute...

Thanks. I wish I could make such an edifying mistake every day...

Thu, Jun. 14th, 2007 08:39 pm (UTC)
brian_jaress: strategy

Okay, the strategy gives you fewer wrong guesses than 1/2 + 1/2 + 1/2 . . ., but does that prove anything except that the strategy works?

Better than random != impossible.

Fri, Jun. 22nd, 2007 03:33 am (UTC)
clgroft: Re: strategy

I think the intuition is that it shouldn't be possible to do better than random, because seeing everybody else's hats doesn't tell any one person anything about the person's own hat.

The intuition goes awry because, in fact, each person knows more than the other people's hat colors -- they all know everybody else's strategies as well. It's not clear that this helps, but it's also not clear that it doesn't; and in the presence of AC, it does.

Tue, Jun. 19th, 2007 02:27 pm (UTC)
says_sara: Missing the point of axioms

Hi all. My brother James forwarded me this post. As a quick background, I have undergraduate degrees in mathematics, philosophy, and history and philosophy of science. My undergraduate history/philo specialty was mathematical logic and foundations of math. I'm currently working on a phd in math (analysis & analytic topology). Sorry for the big "math cock" waving around. I just wanted to introduce where I'm coming from. I would like the make a number of points, first about axiomatic mathematics is general, then more specifically about the development of the ZFC (Zermelo-Frankel with Choice) axiom set that most professional mathematicians use. I will then explain the error in the above reasoning about hats.

1) Mathematics, in a very real and powerful way, is completely unlike science. The goal of science is to observe the world and come to know what is true about thw world. In mathematics we "arbitrarily" decide what we shall consider (axioms) to be true and DEDUCE what further truths follow from them (theorems).

2) The study of foundations of mathemtics and axiomatic set theory (which basically have to do with determining which axioms we need to assume to get the strongest, most robust system) is a matter of deciding what sort of explanatory and computational powers we would like mathemtics to have, and then deducing the best axioms needed to get there. Whether or not the axioms are "obvious" is unimportant (and to some extent highly sugestive, as long term exposure to theoretical math radically changes ones intuitions). I will catagorically state that anyone who told you the axiom of choice was "obvious" was either 1)lying 2)had NO grasp of real mathematics or 3)a VERY bad teacher. In point of fact, for most ofthe last century , the inclusion of the axiom of choice in the "standard" model was a point of great debate among the intellectual giants of the day.

3) For this reason, mathematics can be done with any number of choices of axioms. The most famous (well, you know, among mathematicians and out (woefully few) groupies) is called the Zermelo Frankel set and comes in two flavors, with and without the axiom of choice. (see http://en.wikipedia.org/wiki/ZFC). Nearly all modern mathematicians work with ZFC (ie, include choice) becasue without it, our power to work with continuous sets (like the real numbers) become sadly limited, and the entire field of analysis (which is both beautiful and useful) becomes difficult.

4)The hat problem: "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."

I have no reason to believe that "almostness" is countably transitive. That is to say, A~B & B~C implies A~C (where ~ means "almost equivalent) works just fine for any FINITE number of steps, but once you need an infinite number of intermediary B steps in between A & C, it simply doesn't work anymore. Example, Imagine the following series:
where Sn is the series of n ones followed by countably many zeros.
Clearly, each Sn is "almost everywhere" zero. However, it is also clear that Sn converges to the sequence of all 1s, which is certainly not almst everywhere zero.

Hope that helps. Let me know if there are questions.


Thu, Jun. 21st, 2007 06:32 am (UTC)

I have a question: Can infinity only be understood mathematically meaning there is only one definition of infinity?

Wed, Jun. 27th, 2007 05:01 am (UTC)

Back in the day I used to be into AC, and did some work in Nonstandard Analysis. OK if I add you?

Sun, Jan. 27th, 2008 08:22 am (UTC)
adib46: Negation of the axiom of choice

The negation of the axiom of choice is true.
See :

Sun, Jul. 13th, 2008 03:55 am (UTC)
adib46: Re: Negation of the axiom of choice

My previous site became inaccessible after an attack
Adib Ben Jebara