The Axiom of Choice is Wrong

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!

I should give credit where it is due.  I heard of both of these puzzles in Mike O’Connor’s talk, and I believe that he came up with the solution to second puzzle which is so troubling.  Also, I cannot find it anywhere, but I have heard that Chris Hardin wrote a paper on problems of this type.

First, lets review the solution the the basic problem.  The first prisoner who has to guess his hat color is out of luck; he can’t possibly have any information about his hat, so he has a 50% of being right no matter what.  However, that means he is free to use his guess to try to convey some information to the rest of the prisoners with his guess.

Hmm, he could say the color of the hat on the guy in front of him.  That guy would then guess correctly, but then the next guy would be in the same situation as the first guy.  Repeating this idea gets only 50 prisoners out guarenteed, with an average of 75 getting out.

We can do better.  Instead of just telling the guy in front of him his hat color, the first guy counts the total number of white hats.  If it is odd, he says “white”, and if it is even, he says “black”.  Then the guy in front of him can count the number of white hats he can see, and if differs from the parity the first guy counted, he knows his hat is white.  But now the next guy knows the parity of white hats the first guy saw, and whether or not the second guy had a white hat, so he can compare it to the white hats he sees, and find out if his own hat is white.  This argument repeats, and so everyone except the first guy guesses correctly.

Its interesting to notice that a larger number of hat colors poses no problem here.  For any set of hat colors $H$, the prisoners can pick an abelian group structure on $H$.  Then, the first prisoner guesses the ‘sum’ of all the hat colors he can see.  The next guy can then subtract the sum of the hat colors he sees from the hat color the first guy said to find his own hat color.  Again, this argument repeats, and so everyone except the first guy gets out.  For the case of black and white, the previous argument used black = 0 (mod 2) and white = 1 (mod 2).

This is all well and good, but it doesn’t seem to help the countably infinite prisoners in the second puzzle.  Since they can’t hear anyone else’s guess, they can’t set up a similar system for passing on information.  So what can they do?

First, instead of thinking of hat colors, they just turn white into 1 and black into 0 (like above).  Then, a possible scenario of hats on their heads is an infinite sequence of 1’s and 0’s.  Call two such sequences ‘equivalent’ if they are equal after a finite number of entries.  This is an equivalence relation, and so we can talk about equivalence classes of sequences.

Next, the prisoners invoke the Axiom of Choice to pick an element in each equivalence class, which they all agree on and memorize.  Now, when they are put in line and get a hat, they will be able to see all but a finite part of the sequence, and so they can all tell what equivalence class they are in.  Their strategy is then to guess as if they were in the pre-chosen element in that equivalence class.

How well does this work?  Well, the sequence they are actually in and the representative element they picked with the axiom of choice must be equivalent, so they are the same after a finite number of entries.  Therefore, after a finite number of incorrect guesses, each prisoner will miraculously guess his hat color correctly!

This solution is also pretty stable, in that most attempts to make the puzzle harder don’t break it.  The warden can know their plan and even know their precise choice of representative sequences.  If so, he can make sure any arbitrarily large finite number of them are wrong, but he can’t get an infinite number of them.  Also, the number of hat colors can be arbitrarily big; the same solution works identically.

This last point is pretty trippy.  In the two color case, its very reasonable for any prisoner to guess his hat color correctly, and also for arbitrarily large numbers of them to get it right in a row.  Effectively, at no finite point in the guessing do the results of the optimal strategy appear to differ from random guessing.  However, if there are uncountably many hat colors, then the probability of any prisoner randomly guessing his hat color is 0.  One can reasonably expect no prisoners to be correct for random guessing, so when eventually that first prisoner guesses correctly, the warden should be rightly shocked (though not as shocked as he will be when all but a finite number of prisoners guess correctly).

I find this solution deeply troubling to the intuitive correctness of the axiom of choice.  Sure, this is based primarily on my intuition for finite things and a naive hope that they should extend to infinities.  I think particularly troubling is in the uncountably many colors case, where any given prisoner has no chance to guess his hat color correctly, and yet almost all prisoners are correct.

Tags: ,

161 Responses to “The Axiom of Choice is Wrong”

1. John Armstrong Says:

So you mean that you consider the existence of non-Lebesgue-measurable sets the death-knell of the Axiom of Choice? Because the use of the Axiom in this strategy is essentially the same as how it’s used to pick out a non-measurable subset of the interval.

2. Charles Says:

The problem I see with the intuition is that you’re bringing in several infinities. For instance, first you have to have a countably infinite set of people, which itself poses a certain problem. The second is that each of them must have a countably infinite memory to be able to recall a countable collection of real numbers. Personally, I find the notion that these people are not merely perfect logicians, but also have such enormous memory enough to push this beyond the scope of anything I am willing to believe I have intuition for…infinitely many people I have no trouble with…but infinite memory is a much trickier thing…

3. Greg Muller Says:

Its not that the existance of a non-Lebesgue-measureable set kills the axiom of choice. I have no direct opinions on the validity of a world with or without non-measurable sets. Its that when you restate the same construction in this language, it violates how I would like probability to work, if you could generalize these probabilistic ideas to the infinite cases here.

4. Kea Says:

I never took much notice of Banach-Tarski until recently either, but having decided against AC on very pragmatic grounds (non distributivity of lattices in higher topos theory for physics) I found myself looking at it again. Now I think it always was an excellent argument against AC, especially in the context of measurement! Have you seen the cool book by Wagon?

5. Grant Says:

I agree with Charles — in the solution, people have countably infinite memories. Even if that was possible, they have to agree upon a representative element in each of a countably infinite equivalence classes. How would such an agreement happen in a finite amount of time?

6. Isabel Says:

Having not seen this post, I wrote a more humorous post about the Bananach-Tarski paradox. It must be something in the air today.

7. Aaron F. Says:

Pardon me, but isn’t the axiom of choice logically independent of the ZF axioms? If the axiom of choice and its negation are both valid extensions of ZF, why bother arguing about which one to use?

Relatedly, is there an analogue in set theory to the idea that Euclidean geometry describes flat space, while non-Euclidean geometries describe curved spaces? Are there many possible alternative versions of the axiom of choice, just as there are many possible alternative versions of the parallel postulate?

8. Terence Tao Says:

This paradox is actually very similar to Banach-Tarski, but involves a violation of additivity of probability rather than additivity of volume.

Consider the case of a finite number N of prisoners, with each hat being assigned independently at random. Your intuition in this case is correct: each prisoner has only a 50% chance of going free. If we sum this probability over all the prisoners and use Fubini’s theorem, we conclude that the expected number of prisoners that go free is N/2. So we cannot pull off a trick of the sort described above.

If we have an infinite number of prisoners, with the hats assigned randomly (thus, we are working on the Bernoulli space ${\Bbb Z}_2^{\Bbb N}$), and one uses the strategy coming from the axiom of choice, then the event $E_j$ that the j^th prisoner does not go free is not measurable, but formally has probability 1/2 in the sense that $E_j$ and its translate $E_j + e_j$ partition ${\Bbb Z}_2^{\Bbb N}$ where e_j is the j^th basis element, or in more prosaic language, if the j^th prisoner’s hat gets switched, this flips whether the prisoner gets to go free or not. The “paradox” is the fact that while the $E_j$ all seem to have probability 1/2, each element of the event space lies in only finitely many of the $E_j$. This can be seen to violate Fubini’s theorem – if the $E_j$ are all measurable. Of course, the $E_j$ are not measurable, and so one’s intuition on probability should not be trusted here.

There is a way to rephrase the paradox in which the axiom of choice is eliminated, and the difficulty is then shifted to the construction of product measure. Suppose the warden can only assign a finite number of black hats, but is otherwise unconstrained. The warden therefore picks a configuration “uniformly at random” among all the configurations with finitely many black hats (I’ll come back to this later). Then, one can again argue that each prisoner has only a 50% chance of guessing his or her own hat correctly, even if the prisoner gets to see all other hats, since both remaining configurations are possible and thus “equally likely”. But, of course, if everybody guesses white, then all but finitely many go free. Here, the difficulty is that the group $\lim_{n \to \infty} {\Bbb Z}_2^n$ is not compact and so does not support a normalised Haar measure. (The problem here is similar to the two envelopes problem, which is again caused by a lack of a normalised Haar measure.)

9. Charles Says:

Aaron, the reason that people argue about which one to use is that not everyone is a formalist. To a strict formalist, neither one is truer than the other, and so neither has an advantage (except that you can prove more theorems with AC). Some people are Platonists, in which case they believe that even independent statements are true or false, and it’s really a matter of finding the right axioms that imply the correct theorems. Personally, I fall into the latter camp and believe that the Axiom of Choice is true.

As far as your question about set theory. One way to look at the different geometries is as different models of absolute geometry (just the first four postulates), which hold in hyperbolic, euclidean and elliptic geometry. In this context, it’s just that ZF(not C) and ZFC define distinct models of ZF, and we can think of ZF as playing the same role as absolute geometry.

10. Todd Trimble Says:

As someone generally out of sympathy with Platonist philosophies of mathematics, I myself am completely agnostic on the issue of AC. As Kea points out, it holds in some universes of mathematics (read: toposes), and not in others, insofar as any of these things “exist”. In my view, an appropriate response to, “is it right, is it wrong?” might be: Mu! Wrong question!

Although I have to agree: the paradox Greg describes does show very strongly and vividly how much is really at stake with AC, if you really “believe” in these things. Excellent post.

I read somewhere (maybe in Wagon’s book? and Kea’s right, it is a nice book) that the Banach-Tarski paradox was a kind of fishes and loaves story invented for the express purpose of making AC seem ridiculous. But the plan sort of backfired — the overall reaction in the mathematical community seems to have been a kind of delight at the crazy things you can do with mathematics, and not that many took it to be all that devastating, seeing as how these funky non-measurable sets are so obviously mathematical and so obviously devoid of physical sense. I guess my reaction to this entry’s paradox is also somewhat in that vein.

11. John Armstrong Says:

Todd, I agree with your comments in re topoi wholeheartedly, but with one slight modification: I believe that along with a Real World Out There there exists a Real Topos Out There.

That is, there exists some topos whose internal logic is the logic underlying physical systems, be that classical, intuitionistic, quantum, or what-have-you. I’m ambivalent as to which topos “obtains”, but only one does. And that topos either includes AC or it doesn’t.

12. John Armstrong Says:

Oh, and that response you mention is spelled “無”. 😀

13. Todd Trimble Says:

John, I don’t believe in a Real Topos (but we can agree to disagree). I’m not a philosopher by temperament or training, but if pressed, I would not ascribe a definite internal logic to physical reality. I see logic more in terms of valid rules of inference applied to certain classes of propositions, i.e., in terms of language structure, and not as something residing in things-in-themselves.

Of course I can see that one type of logic may be more appropriate than another for theories in given domains of validity, but I don’t envision a monolithic “master logic” which would cover all domains, and so I don’t envision a master topos either. My idea would be that one day we will need a whole network of toposes with differing internal logics to adequately express physical theory (if toposes are at all the right language to use!).

14. Walt Says:

So you are agnostic on the question of whether the infinite direct product of non-empty sets is non-empty?

15. Ars Mathematica » Blog Archive » Axiom of Constructibility Says:

[…] is a discussion at the Everything Seminar about everyone’s favorite topic, the axiom of choice. The axiom of choice has various […]

16. Aaron Bergman Says:

I always thought that one was a bit of a cheat. It’s really the product of sets over an uncountable indexing set that’s the fishy thing.

17. Pierre Says:

Surely you mean uncountably infinite memories, given that they have to remember an element from ‘equivalence classes’->’representative thereof’, with the former set already being uncountable (given that each class is countable and ‘countable set’x’countable set’ is countable).

18. Z Says:

I think this is yet another example of the stark difference between our intuition and the way uncountable sets behave. I am inclined not to use the axiom of (uncountable) choice. Horst Herrlich alos has a nice book on the topic.

19. Todd Trimble Says:

Walt, certainly I’m agnostic about that. I don’t hold a fixed conception of “set”. That said, I am perfectly willing to contemplate models of ZFC (so I’m not an “atheist” 🙂 ).

(Of course, some infinite products like (Z_2)^X are obviously nonempty, since you have e.g. constant sequences or constant maps.)

20. Tom Leinster Says:

I’d go further than what Todd says (though I might not go further than what he *thinks*).

I’m not an “agnostic” or a “believer” or a “non-believer” in the Axiom of Choice. That’s because it makes no sense to me to ask whether it’s “true”. That would imply some kind of external reality in which sets – including the uncountable ones – are supposed to live.

If a physicist or astronomer could locate such a reality, then we could have a meaningful debate about whether AC is true. Otherwise, sets are a figment of our imagination – just a formal system. The analogy with the parallel postulate is a good one: it makes no sense to ask whether that’s “true”. There are models where it holds, and models where it fails. What more is there to say?

To be honest, I’m baffled by talk of a “real world” of sets. I have no idea what it means.

21. Walt Says:

I think it’s fine to have a non-fixed notion of “set”. But do toposes exist? If I said, “The effective topos clearly doesn’t exist. What are you, drunk?” you have no mathematical counterargument?

22. Oren Cheyette Says:

This problem appeared a couple of years ago on an undergrad “problem of the week list”: http://mathforum.org/wagon/fall05/p1035.html.

The issue I have with the infinite solution (which I also objected to in the Macalaster problem) is in this sentence: “Next, the prisoners invoke the Axiom of Choice to pick an element in each equivalence class, which they all agree on and memorize. ” The difficulty is that AC doesn’t provide a means to choose the elements of the equivalence classes (EC). It just says “it can be done”. It’s not a magic incantation that presents the actual EC elements. If there were an algorithm for choosing the EC elements, you wouldn’t need AC. But the prisoners need an actual algorithm.

I got a (probably warranted) dismissive reply to this objection from the list maintainer, but I still don’t see how AC provides a solution. “Assume AC” doesn’t solve the problem: the prisoners have to be able to identify the EC element, and without an algorithm they can’t do it.

Of course you can’t have an”actual” infinite set of prisoners either, so maybe this is a pointless nitpick. But the semantics of the word problem imply that one should find a method. That’s not captured by invoking AC, which amounts to saying “assume a method exists” (for choosing the EC element).

• Jean-Louis Dornstetter Says:

My take on AC is different than yours: AC *is* the “means to choose the elements …”. Of course, it is not specific on *how* to do this, else there would be no need to accept it as an additional axiom, it would be a ZF-theorem. Accepting AC, we allow ourselves to ‘actually pick’ one such beast, and share it among prisonners etc…
My favourite look at AC is that it ‘provides’ you a procedure to pick integers with uniform density: real numbers x and y are ‘equivalent’ if they differ by a rational. Use AC to pick (and memorize!) a set E of real numbers in [0,1] that contains one representative of each equivalence class. Now pick a random number u in [0,1]: u differs from exactly one member of E by the n-th rational number. Your random integer pick is n and by every reasonable argument, none of the outcome is more nor less likely than another: AC ‘provides’ a *uniform* random choice over N, which I find simpler and no less puzzling than this paradox or Banach-Tarski.

23. Todd Trimble Says:

Actually, to be clear, I’m in full agreement with Tom. The word “agnostic” is not at all what I mean, if it is interpreted as my claiming there’s a mathematical “truth” out there, but I make no claims on what it is. Rather, I think the whole question of “truth” of the axioms of ZFC, or of any piece of mathematics, doesn’t even make sense to ask, is inadmissible from the get-go. (My earlier Mu! was a too-cute way of expressing that, and I’m glad Tom expressed it more clearly.)

From this POV, it is inadmissible to ask whether a piece of mathematics is “true”, but it is however possible to be reasonably clear and certain about its deductions and calculations.

I strongly recommend Saunders Mac Lane’s book Mathematics: Form and Function, for some very clear thinking on this and other philosophical topics. In particular, the philosophical position taken here is not to be confused with a straw-man Formalism, which holds that mathematics is nothing but manipulation of symbols which have no meaning. I rather tend to an opposite conclusion, that mathematical forms (“point”, “line”, “set”) can carry a multiplicity of meanings, not fixed in advance. The example of Euclidean vs. non-Euclidean geometry provides good evidence for this.

24. Tom Leinster Says:

Todd – yup, I thought we’d probably be in agreement. (And your “mu” was perfectly clear, not too cute at all.) I guess I just wanted to ram home the point that there are many possible notions of “set”, and to make sure no one interpreted “agnostic” as meaning “I don’t know whether it’s true or false”.

Walt asks how I’d reply to “do toposes exist?”, or “does the effective topos exist?” I’d reply: it’s a meaningless question unless you say what you mean by existence. You could change “toposes” to “groups” or “circles” or “whole numbers”, and my reply would be the same.

25. Todd Trimble Says:

I’d reply roughly the same way as Tom did to whether toposes exist, and add that I would find the question “are the axioms of topos theory, or of ZFC, etc. consistent?” much more palatable. At least the consistency hypothesis is in principle falsifiable, and therefore not meaningless.

And naturally, I am perfectly prepared to act as if ZFC (or topos theory or whatnot) *is* consistent. But that doesn’t commit me to believing toposes “exist” — that sounds almost religious to me!

26. Slawekk Says:

>If the axiom of choice and its negation are both valid extensions of ZF, why bother arguing about which one to use?

One criterion may be how much useful mathematics can be done with vs. without AC. How much measure theory can be done without some form of AC?
If measured by cash flow generated by direct application, stochastic calculus is probably the most applied area of mathematics. Can we do stochastic calculus without AC?

27. Kea Says:

I believe that along with a Real World Out There there exists a Real Topos Out There.

Although mathematically I would tend to side with the category theorists, this neoplatonism is interesting, with the caveat that an ill defined ‘out there’ is a non-sensical physical notion in the physical domain to which topos theory might possibly be useful, namely quantum gravity. Nonetheless, if we try to extend this philosophy into higher-category constructive-number-theory land, where one isn’t allowed to dump Natural Number objects into Set, it makes some sense: there isn’t a Real 1-Topos but there should be a canonical heirarchy of weak n-toposes which characterises a Set (probably without the axiom of choice).

28. John Armstrong Says:

Kea, thank you for pointing out the benefits of philosophical sloganeering, namely that they’re concise at the expense of hideous accuracy.

29. Walt Says:

I think “interpretable in a standard model that we all agree is consistent” is the minimal shared meaning of mathematical existence. So I’m happy to say that a topos exists if you can show me a model in ZFC or something similar.

30. Todd Trimble Says:

“So I’m happy to say that a topos exists if you can show me a model in ZFC or something similar.”

Well, a model of ZFC would be a topos (you don’t need the C, and you don’t need the F). And there is no problem in defining other toposes relative to that model (e.g., Grothendieck toposes, realizability toposes…). I’m honestly not sure what you’re driving at here, but surely this is getting off-topic. Would you like to continue off-line?

31. Cale Gibbard Says:

Your prisoners have quite good memories. I think I might have trouble remembering the selected sequence for each of the uncountably many equivalence classes that the warden could choose.

If you only allow the prisoners a finite amount of memory, then it no longer works. I think that might have something to do with what is so intuitively troubling to you. You’re not used to running into people who can keep track of an infinite amount of information, like your prisoners can.

32. Greg Muller Says:

Wow, people had lots of strong opinions on this. I’ll take that as a good sign.

Several people mentioned the inherent difficulties in the prisoners nearly-divine capabilities: explicitly constructing the representative sequences, communicating them, memorizing them, seeing and processing countably many hats, etc. Certainly this is both impossible and a fairly legitimate reason for intuition to be inapplicable. I mean, my brain dismisses the Banach Tarski paradox as non-concerning for similar reason (“infinity can do crazy things!”). I think some arguments just hit certain people the right way. Maybe more analytically minded people can’t conscience the existance of a non-measurable set, and find that particular fact most distasteful about AC.

I’m a bit scared to wade into the discussion of whether or not there is a One True Topos, since it seems roughly as dangerous as discussing religious beliefs with a group of strangers. Still, I think that its hard to be a mathematician and not form opinions on the ‘right’ choices for various undecidable propositions:
I beleive in Countable Choice and I keep Uncountable Choice at arms-length.
I beleive that there are no infinities between the number of integers and the number of reals.
I beleive that $|2^A|=|2^B|$ implies that $|A|=|B|$.
Why do I believe these things? For no better reason than the crude generalized-intuition arguments like above. However, I also think its important to remember how baseless these beliefs are. Its like how I can root for a football team, but still remember that my allegiance is due primarily to proximity and nothing more meaningful.

33. Walt Says:

My argument, which I’m clearly butchering into incomprehensibility, is that when a mathematical object is said to “exist”, this means that it has a model in some system that everyone agrees is consistent, nothing more. So the gap between the Platonist position and your own is small.

34. Michael Smith Says:

Interesting problem. The difficulties involving a probability measure were the first to spring to mind for me, but I don’t think we have to bring that into it. What I noticed is this: the probability of *any particular* prisoner guessing correctly is 1/2, just like you would expect. The finite part that the two sequences disagree on can be arbitrarily long, so it doesn’t help out any particular prisoner. Thus the prisoners who are guaranteed to guess correctly are part of some sort of fictitious “infinite tail” of the line of prisoners; it seems like this is more a symptom of poor intuitive notions of infinity than some actual problem with the Axiom of Choice. I notice that the prisoners don’t care about *any* of the hats on finite prisoners, only the infinitely distant ones, which is somewhat nonsensical. Another interesting point is that in addition to having infinite memories, the prisoners have infinite computational power: comparing any finite number of hats against their memories doesn’t get them anywhere. Consequently, there are no halting algorithms that implement the algorithm you suggest. If we limit the prisoners to computable functions of the hats they can see, they’re screwed.

Just my two cents.

35. Plac Ebo Says:

QUOTE FROM NEAR TOP OF ARTICLE: “That guy would then guess correctly, but then the next guy would be in the same situation as the first guy. Repeating this idea gets only 25 prisoners out guarenteed, with an average of 37.5 getting out.”

This is way over my head, but fascinating none the less. Just a simple question/observation: The initial problem stated that there were 100 prisoners. Using the above quoted technique shouldn’t 50, rather than 25, be guaranteed to be set free? And, assuming the warden assigned hats randomly, wouldn’t the average be 75 set free?

36. tdbwd Says:

If all you smart folks will suffer the comments of a decided non-scientist… I think that most of the prisoners will think it’s a great joke to lie to one another about their hat colors and all but three will stay locked up. Given the recidivism rate, one of the three will be back in prison within a month and another within a year, where the story of the colored hats will circulate and grow into a legend and provide much welcome entertainment. Don’t worry, I won’t invade your discussions again, except to read them — very interesting stuff.

37. Top English WP Blogs « Hành trang 8X Says:

[…] The Axiom of Choice is Wrong When discussing the validity of the Axiom of Choice, the most common argument for not taking it as gospel is the […] […]

38. Todd Trimble Says:

Walt said:

“My argument … is that when a mathematical object is said to ‘exist’, this means that it has a model in some system that everyone agrees is consistent, nothing more. So the gap between the Platonist position and your own is small.”

(Walt, I’ll assume that your “your” generally refers to me, but it’s sometimes hard to tell, since these comments are not nested. Could be you meant Tom Leinster, for example.)

Let me take your second sentence first. I don’t agree — the traditional Platonist insists there is an *absolute truth value* for the continuum hypothesis, say. That is nowhere close to my position (it’s hard for me even to make sense of it). I interpret mathematical truth in a relative sense — relative to whatever framework we happen to be talking about.

And your first sentence suggests to me, at least in one reading, that it’s this sort of relative existence that you mean (whether syntactic: a provable consequence of a theory, or semantic: holding in a specific model of a theory). If so, then yeah, sure, I use the word “exists” that way all the time without batting an eye — that’s just ordinary language use. That’s not Platonism — not even close!

The way you put it leaves me wondering though what you really mean. “Some system that everyone agrees is consistent.” Do you mean some foundational theory, say ZFC, specified at the outset? Or do you mean just any old system of axioms that we (whoever “we” happen to be) agree to work with? [Sorry — I don’t like the formulation “everyone agrees is consistent”. “Everyone”: I believe there are excellent mathematicians, e.g., Edward Nelson, who wouldn’t agree to say ZFC is consistent. Speaking personally, if someone collared me and asked, “do you agree that ZFC is consistent?”, I’d probably splutter a bit and say “How the heck should I know? But we can take these axioms as starting point,” etc. — maybe that’s all you meant.]

Now, if you do have in mind a specific foundations like ZFC as the standard to appeal to, I’m still not 100% happy. Here’s why: imagine for example two nineteenth-century geometers, and one says to the other, “The sense in which your hyperbolic plane exists is that we can translate it in terms of a disk model construction which lives in an ambient Euclidean space, and of course we all agree that Euclidean geometry is consistent. (But those aren’t real lines, you know; they’re circular arcs.)” This would be a possible system of “government”, of course, but this privileging of one framework to which all others must appeal means that the others must inevitably undergo contortions first before they are admitted into the guild. Something like this seems to happen all the time: if you take something like non-standard analysis, the models may look horribly complicated from the standpoint of encoding them in terms of “ordinary” set theory, but from within the theory may look simple and beautiful and compelling.

Don’t get me wrong: relative consistency checks are important. But it’s a two-way (or many-way) street, and in general I would favor a more decentralized, “federated” approach — let people work with whatever axiomatic framework they want! The more pragmatic and socially adapted will build strong networks between various frameworks (transfer principles and so on), and thereby derive a lot of insight. Of course, this sort of thing goes on anyway — all I’m suggesting is let’s not be too provincial and religious in our beliefs about what is “really true”, or proper foundations, in mathematics. That wouldn’t make sense to me.

39. Richard Says:

Hasty thought while traveling.

Attempting to mix The Axiom of Choice with hypothetical undefined human conciousness in this way, and and in fact an infinite number of such, does not seem to me to be rigorous mathematics. The AOC merely asserts the existence of a choice function, and this existence has no dependency on the concept of consciousness. Moreover, as noted above, a specific choice function is unreachable by conciousness in the case of infinite collections of infinite sets. Attempting to marry the AOC with consciousness like this does not feel valid to me in any way, and leaves a taste in my mouth like a mix of milk and vinegar.

40. Walt Says:

I was arguing with you, Todd, don’t worry. 🙂 Your argument actually illuminates something to me that I never understood. I think it’s perfectly fine to translate hyperbolic geometry into a model within Euclidean geometry. I wouldn’t think that demotes hyperbolic geometry into a second-class citizen. But clearly some people would feel that way, and that explains the eagerness in some quarters to dethrone set theory as the conventional testing ground for “existence”.

41. Barak Pearlmutter Says:

Terence Tao’s comments about measurably are of course technically correct, but to my mind they miss the deep intuition here, which is the connection between the apparent paradoxes of measure theory with Godel’s incompleteness theorem and model theory.

Given this “axiom of choice” escape strategy, let us ask the following question. We know that, by definition, at “some point” the sequence we are on will agree with the “chosen” sequence forever. In other words, if
$s=(s_1, s_2, ...)$
is the sequence we are on, and
$q=(q_1, q_2, ...)$
is the “chosen” sequence, i.e., the member of the equivalence class that includes $s$ which the axiom of choice has chosen for us, then by definition

$\exists N \; \forall i, i \geq N, \qquad s_i = q_i$

Let us call that $N$ the “point of convergence”.

How big is $N$? One way of getting at this is to consider some particular value $K$ and ask whether $K. Well, it is easy to see that $K with probability at least 1/2, since $P(s_K = q_K) = 1/2$. Similarly $K with probability at least $1-1/2^2$, since

$P(s_K = q_K \& s_{K+1} = q_{K+1}) = P(s_K = q_K) P(s_{K+1} = q_{K+1}) = 1/2^2$.

In fact, for any $m$ you choose, $K < N$ with probability at least $1-1/2^m$ because
$P((s_K, s_{K+1}, \ldots, s_{K+m-1}) = (q_K, q_{K+1}, \ldots, q_{K+m-1})) = 1/2^m$

So we see that $P(K 1-\epsilon$ for any $\epsilon>0$. In other words, $K>N$ with probability zero. So for any $K$ you pick, you can be sure (with probability one) that $K. But we “know” by definition that $N$ “exists” and is therefore some integer. How can this be?

Consider the distribution $P(N)$. By symmetry, $P(N)$ is a uniform distribution. But a uniform distribution over the non-negative integers is nonstandard: $\sum_{N, yet $\sum_N P(N) = 1$.

What is really happening is that the “point of convergence” $N$ is, with probability one, not a standard integer! Using the axiom of choice we have assured that all but a “finite” number of prisoners will go free. But “finite integer” is not a concept that can be captured in an axiomatic system (Godel, model theory, etc). Instead, all but an integer number of prisoners will go free; this is all we can axiomize. But this “integer”, or “finite integer” (all integers are finite) $N$ happens to be larger than any actual integer we care to name! It is a nonstandard integer. Whether this $N$ is actually finite is, unfortunately, something we can capture in words or informal arguments (where we see that it is not) but not in an axiomatic system.

42. Petter Strandmark Says:

Why are you more troubled when the colors are uncountable? This case is possible even without the axiom of choice.

Any real number can be seen as a countable sequence of digits. The number of prisoners is countable, so the set of every prisoners’ digits are countable (by Cantors diagonal method). The first prisoner construct a real number with all these digigts and guesses that. Now every other prisoner knows his number.

Note: To make it rigouros, you would have to keep in mind that some real numbers can be represented in many ways (1.0000 vs. 0.9999) so you would have to choose one representation and stick with it.

43. Petter Strandmark Says:

Never mind, I didn’t read the problem statement carefully enough. I thought this was the same as another problem I saw.

44. James Cook Says:

Following up on Walt’s remarks, I would point out that the insistence on one point of view as “fundamental” can often itself be the stimulus of important mathematics. Take the Nash embedding theorem, for example. Apparently a part of Nash’s motivation for proving this result was a sort of contempt for the idea of an abstract Riemannian manifold, not considered as a subspace of R^n. Thanks to this “Euclidean dogma”, we now have ways of getting inverse-function-type theorems in Fréchet spaces!

As for set theory, in their eagerness to point out that we need not use one particular system as the foundation for all of mathematics, people seem to forget that it was not always clear that we could do so. (In fact, aspects of that problem are evidently still being worked on…)

45. Terence Tao Says:

Dear Barak,

Your arguments are interesting, but I am not sure I see how to make them fully rigorous. As I said above, any event which involves the axiom-of-choice-generated strategy is not measurable, and assigning probabilities to non-measurable events should be done with great caution (though one can still rigorously define an outer probability, bearing in mind that it is no longer additive, and may not behave in the expected manner with respect to Cartesian products, so that arguments involving independence may have to be reexamined). Incidentally, the concept of an event being measurable is almost the same as the concept of an event being describable to someone with at most countable memory; roughly speaking, these are the only events for which the theory of probability works as one would expect.

Furthermore, while non-standard models of, say, ZFC, certainly exist (assuming of course that ZFC is consistent 🙂 ), so do standard models, and the statement “all but finitely many prisoners go free” is also true in the standard model. So it does not seem possible to rigorously reach a conclusion that non-standard numbers exist without some additional external assumption which is not true in the standard model.

46. Barak Pearlmutter Says:

Dear Terrence,

Good point. I think that is right, and there is no way to rigorously (i.e., axiomatically) prove that the point of convergence is (with prob 1) a nonstandard integer. If there were, it seems like we would be able to use that proof to construct an axiom that rules out nonstandard integers, which is impossible.

On the other hand, I think there should be a way to push my extremely informal argument into a convincing (albeit not axiomatic) proof. What we want to show is that
$sum_{i \in \mathbb{N}^s} P(N=i) = 0$
where N is the “point of convergence” and $mathbb{\math{N}^s}$ are the (standard) natural numbers. But we know that
$sum_{i \in \mathbb{N}} P(N=i) = 1$
where $mathbb{\math{N}}$ are the natural numbers as per the axiomization which includes the axiom of choice as used here. This means we’ll need to bring in some non-axiomizable human intuition about the natural numbers. Like, that they all result from a finite chain of successor operations starting at zero. Where “finite” means, um, a natural number. A standard one, of course.

Here are two possible approaches.

(1) Use induction on K for the proposition that K is below the point of convergence with probability 1. Since induction is axiomizable, it must be that this proposition itself cannot be expressed in an axiomatic fashion. Which is where the fact that sets become unmeasurable comes back in. But that doesn’t mean we cannot use intuitive notions of probability. However it does mean, I think, that some would not consider it rigorous!

(2) Take a different limit. Let the sequences be finite, of length n, and let the equivalence classes be sequences that are identical after n/2. Now ask what is the point of convergence (defined as the point where a sequence converges to the chosen representative of its equivalence class) of a random sequence? Everything is finite here so it is easy to see that its expected value is n/2-1, by a simple sum. Now take the limit as n goes to infinity. The expected value of the point of convergence goes to infinity/2-1. Or if formulated with proper limits etc, it grows above any finite integer. This is the defining characteristic of a nonstandard natural number. QED. The same argument holds with a probability 1 kind of thing. For instance, the probability that N is above n/4 goes rapidly to 1 as n goes to infinity.

I think argument 2 can be made rigorous. It does not involve anything non-measurable, instead it uses, at any point, a finite approximation which by construction can only overestimate the probabilities of interest.

47. rbnn Says:

Barak, I do not understand your argument. How are you defining N? Is it the smallest such N? You do not seem to give a definition. And once you define it, why is P(K<N) at least 1/2 – I don’t follow your argument or definitions. For instance, why is P(s_k=q_k)=1/2 ?

48. Barak Pearlmutter Says:

: How are you defining N? Is it the smallest such N?

Yes, the smallest such N.

: Why is P(s_k = q_k) = 1/2 ?

Because the sequences s is chosen randomly, and which q it gets is independent of the value of s_k.

49. Enigman Says:

Hi y’all, thanks for the interesting read (and incidentally, also partially relevant, like the above-mentioned 2-envelope paradox, is Freiling’s argument against AC (from 1986, Journal of Symbolic Logic 51, 190-200), and maybe also that there is a forthcoming countable version of that paradox (Sorites 19, via my profile), which locates the problem with either the Axiom of Infinity, instead of AC, or the probabilities)

50. Barak Pearlmutter Says:

Dear Terrence,

Despite the obvious correctness of your points, something kept troubling me.

The random sequence can be thought of as a one-time-pad. Guessing your hat color with odds above chance can be thought of breaking a one-time-pad given information about other (irrelevant) parts of the pad. But that is impossible, even with access to ultra-fancy oracles and irrelevant infinite uncomputable information. So something is wrong. I think I’ve finally put my finger on it.

One solution to the paradox is that all but “some integer n” of the prisoners go free, but that integer n is nonstandard. That was a solution I proposed. But as you note, there does exist the usual model with only standard integers. So here is another question: does that model without nonstandard integers contain the one-time-pad sequences under consideration? There are an uncountable number of such sequences, so the relevant model theory doesn’t really speak here: it only guarantees a countable model!

Here is a model that contains no nonstandard integers: each sequence in the model is finitely specifiable in some (appropriate) language. Your “finite number of black hats” is a particular such language, except then the space of sequences wouldn’t be closed. The countable memory restriction would be another potential such language (I think that comes to computable) although again I’m not sure if it would meet closure. But we can allow the language to specify uncomputable sequences if required to meet the axioms, that is fine. In fact if we want appropriate closure properties over sequences I think the language does need to be able to do that.

The axiom of choice is no problem: given a set of sequences we can just pick out the one which can be specified with the shortest description, breaking ties by taking the lowest description lexicographically. So this is a nice model: no nonstandard integers, any sequence you can actually specify (describe) has a describable limit, axiom of choice works. But it does not contain any one time pads (all sequences so a random one can be picked) so the problem goes away.

Conjecture: any model that does incorporate both all sequences (so we can ask for a one-time-pad) and the axiom of choice (so we can set up this paradox) will also have nonstandard integers, and the “point of convergence” will then be nonstandard (thus resolving the paradox).

51. Terence Tao Says:

Dear Barak,

It seems to me that the problems are not with the model theoretic aspects, but rather with the use of probability theory in infinite settings. The finer aspects of rigorous probability theory on infinite event spaces are actually rather subtle, and when non-measurable events are concerned one should proceed with extreme caution and to carefully examine all “intuitively obvious” probabilistic statements. The long and subtle story of Lebesgue measure already illustrates these points rather well.

For instance, consider a number x chosen at random from the unit interval [0,1]. Given any specific y in [0,1], the probability that x is equal to y is 0. But one cannot simply add all these events together and conclude that the probability that x is equal to any number in [0,1] is zero, which is of course absurd. Here, the problem is that the probability measure dx is only countably additive, and is not uncountably additive.

With the axiom of choice, we can wreak havoc with countable additivity too. Let E be a subset of [0,1] which contains one representative from each translate of the rationals. Let p be the probability that x lies in E. Then by the translation invariance (mod 1) of the probability distribution of x, p is also the probability that x lies in E+q mod 1 for any rational q; summing up using countable additivity we see that $p \cdot \infty = 1$, which cannot be satisfied for any p. You may think that the solution here is to make p a nonstandard infinitesimal, but this doesn’t actually work, because the \infty becomes non-standardly infinite also. Instead, the solution is to realise that E is simply not measurable, and thus one cannot assign a meaningful probability to it. (Though one can assign an outer probability to this event, which in this case turns out to be 1.)

And of course Banach-Tarski tells us that even finite additivity can be violated when one tries to assign probabilities to non-measurable events.

The point is that once the axiom of choice is allowed to be used, and sets which require uncountable amounts of memory to describe are in play, it is not safe at all to assume that any event you care to name has a well-defined probability, and that this concept of probability obeys intuitively obvious axioms such as additivity. Since it is the axioms of probability which underlie statements such as “the one-time pad is unbreakable”, it seems that the resolution to any apparent paradoxes lies in a more careful inspection of the foundations of probability, rather than the foundations of the integers.

52. rbnn Says:

Barak,

Thank you for clarifying the unstated assumption in your post that N was the smallest such N.

Another problem here is that you are making assumptions not supported by the problem when you write P(s_k=q_k)=1/2. The problem does not make any randomness or distributional assumptions on the sequences. To the contrary, the problem suggests the warden can choose the sequence. In any case, nothing in the problem states a uniform distribution is used, so your analysis is certainly addressing a problem different from the problem stated here.

(Even if P(s_k=q_k) were equal to 1/2, in some other problem you are not defining, I don’t see how this shows that P(k=1/2, but that is another matter). The conclusion of your post is interesting and I hope you define your terms and notation so it can be to follow from explicit premises.

53. deGroot’s Problem « Rigorous Trivialities Says:

[…] Recently, a lot of blogs (incited by the Everything Seminar) have been talking about the Axiom of Choice and it’s more horrifying implications. Well, […]

54. choice is some weird shit « Electoralblog’s Weblog Says:

[…] is some weird shit Seriously. Come to think of it, I have always wondered what a well-ordering of [0, 1] looks like . . […]

I agree with the people who say that infinity in general is the problem, not the AC in particular. Tail events are creepy.

I think I find Terence Tao’s AC-free version (only a finite number have black hats and everyone says “white”) quite convincing. Apparently it’s essentially the same thing, but with a fixed equivalence class. And I think we don’t have to worry about being able to construct an appropriate product measure if we are just appealing to intuitions anyway 🙂

56. Surfaces and Spinors « The Everything Seminar Says:

[…] geometry is over-representation. Manifolds are conventionally defined via absurdly large, Zorn’s-lemma’d maximal atlases, giving an enormous sea of possible coordinates which could represent an object. […]

57. Math Bloggers - Today’s Top Blog Posts on Mathematics - Powered by SocialRank Says:

[…] The Axiom of Choice is Wrong « The Everything Seminar […]

See my web page about the negation of the axiom of choice :
http://jebara.topcities.com

59. Paul Crowley Says:

A couple of people have said that the prisoners will require a countably infinite memory to remember their agreement. I think it’s one power set worse than that, since there are uncountably many equivalence classes.

60. Peter Says:

In regards to many of the above comments, the point of this problem has nothing to do with physical prisoners or physical memories or physical hats, especially since it seems unlikely that there is even a physical infinity. The point is that the axiom of choice leads to some unintuitive consequences. For me, this is ok, because the existence of an infinite set is an axiom of ZF set theory, and it seems probable that this axiom does not coincide with the real world. If we assume one “unphysical” axiom, this probably ruins our intuition, so even if the axiom of choice seems intuitive in some choice of phrasings, it could easily lead to nonintuitive results. This is fine and interesting, and I think we shouldn’t be scared of it, as long as we realize that it shouldn’t necessarily lead to results which agree with the real world.

61. The joy of “pathology” « Mathemusicality Says:

[…] are still some people who are pissed off about Cantor’s discoveries, and who would sooner overthrow the standard axioms of mathematics than confront the “paradoxes” of the infinite. Even Hilbert, who had the good sense to […]

• Celina Says:

Wowza!!! That is COLD! I couldn't even imagine. I live in Houston and our temps are in the 70's. I love colder weather though- I'd trade places with you! loeosxox:Kri)tln

62. Gorkem Ozkaya Says:

I think, in a universe where people have countably infinite memory, the countable version of axiom of choice would no longer be an axiom, it would be a theorem. Because in their understanding of mathematics, proofs would be allowed to contain infinite lines.

63. eliza Says:

hello! ist cool …is chido me encanta de jonas brothers son fabulosos sobre todo nick jonas es un bue…esta requete bueno…

64. Set Theory and Weather Prediction « XOR’s Hammer Says:

[…] some interesting comments on this puzzle, see Greg Muller’s blog post on it here and Chris Hardin and Alan Taylor’s paper An Introduction to Infinite Hat […]

65. Guessing the result of infinitely many coin tosses « Possibly Philosophy Says:

[…] construction of the strategy is actually relatively simple (and it resembles the solution to this infinite hat problem closely.) Firstly we divide the space of all possible complete sequences of […]

66. Ron Maimon Says:

There is a much simpler contradiction from the axiom of choice and probabilistic intuition: if you are allowed to pick a real number between 0 and 1 uniformly at random, and determine whether it is in a set S or not, then you can determine the measure of an arbitrary set S.

Pick real numbers r_i uniformly at random in [0,1] and check to see if they are in S. Take the limit of the mean number that land in S and define the measure to be that. It is easy to check (intuitively! this doesn’t make sense in ZFC) that this is countably additive. But this contradicts the existence of a non-measurable set.

So you have a “choice”: allow real numbers which are random, and a mathematical universe which accords with probabilistic intuition, or allow the axiom of choice and a system which accords with nobody’s intuition. If you allow random real numbers, the ordinal properties of the real numbers are beyond reach— they are too big to be well ordered. If you allow the axiom of choice, you pretend to make statements about the ordinal size of the real numbers, and then (surprise surprise) you find this is a shifty concept which you can force around to be anything.

I think that mathematicians made a boneheaded choice, and are paying for it. So they find it difficult to construct measures on large spaces, something which should be trivial, while making proofs about the ordinal size of the reals (a concept which is so model-dependent that it should be completely counterintuitive) is easy.

67. Mark Hanlon Says:

It’s probably worth mentioning smooth infinitesimal analysis (SIA) here; a version of calculus based on intuitive logic which does not admit the Axiom of Choice (AC). Because of this, in SIA the Intermediate Value theorum is false (see A Primer of Infinitesimal Analysis, J L Bell). In The Foundations of Mathematics (Stewart and Tall) the authors assume that the Intermediate Value theorum is necessary and use that assumption to justify the development of a theory of Real numbers (as opposed to just rational numbers) which of course requires the AC. So, mathematicians not only made a boneheaded choice, they took a completely unnecessary intellectual path.

68. MaribuS Says:

I think that you are giving too much “weight” to the axiom of choice… The AC (as far as I can see) is not the only reason why these strange things happen… I say this, maybe, because I really don´t see the AC as you see it… I just don´t get the point… The infinities, the possibility of knowing all of the elements of an infinite set created at random… All those things add together in order to give us a contraintuitive result…
Take care,
😉
MaribuS.

69. Mark Hanlon Says:

‘The AC … is not the only reason why these strange things happen.’ Damn right. The real reason is impredicative reasoning. To quote from The Continuous and the Infinitesimal, J L Bell (p 211): ‘Impredicativity is a form of circularity: a definition of a term is impredicative if it contains a reference to a totality to which the term under definition belongs.’ And then this (p 224-5): ‘[Hermann] Weyl had come to believe that mathematical analysis at the beginning of the 20th century would not bear logical scrutiny, for its essential concepts and procedures involved vicious circles to such an extent that, as he says, “every cell (so to speak) of this mighty organism is permeated by contradiction.” In Das Kontinuum he tries to overcome this by providing analysis with a predicative formulation … by confining the basic principles of set formation to formulas whose variables range over just the initial given entities (numbers). Thus he restricts analysis to what can be done in terms of natural numbers with the aid of three basic logical operations, together with the operation of substitution and the process of “iteration”, i.e., primitive recursion. Weyl recognized that the effect of this restriction would be to render unprovable many of the central results of classical analysis – e.g., Dirichlet’s principle that any bounded set of real numbers has a least upper bound – but he was prepared to accept this as part of the price that must be paid for the security of mathematics.’ Bell also expains (p 211) that the Cantorian theory of sets (which originally necessitated the AC) is impredicative. So, to correct myself, the Real numbers don’t require the AC; they just require the same suspect reasoning as that which also underpins the AC.

70. Andrew Marshall Says:

I don’t understand, then, why Weyl’s “non-standard” analysis didn’t stick. We’ve matured to the point where we can have differing models of set theory, haven’t we? Why not the model where sets are required to be finitely constructible. Here every “set” $X$ of bounded reals has a supremum (since the limit of an algorithmically generated set has a finite generating algorithm). I’m happy enjoying our default system where we have linear contiunua, and randomly chosen points, and where we debate the merits of allowing the axiom of choice, but there is no reason to prefer this system, as more ontologically sound, is there? Probably less. I’ve had discussions with non-mathematical friends on why or why not $.\bar 9=1$. The only objection raised is on the grounds of intuition: “they differ by an infinitesimal!” If I can convince them that their notion of infinitesimal has no place in our number line, then how can I possibly defend our standard analysis against a sound system that refuses to allow unmeasurable sets, or Hamel Bases, or even an uncountible set.

I see, in the context of probability theory we want models where we can sample points, with uniform distribution. I suppose, too, it is simpler to understand our universe as being clean and simple, and when we need to say something about the numbers which are finitely expressible it may be simpler to understand them as belonging to a larger set of numbers. This, of course, is Cantor’s paradise Hilbert was referring to. But it is hard to accept the fact that out of the unit interval, we can ask no questions about any particular number chosen from all but a set of measure zero (the finitely expressible numbers). “take it easy, humankind! don’t bite off more than you can chew.”

71. Andrew Marshall Says:

oops.

72. Mark Hanlon Says:

Weyl’s approach and the theory of nilsquare infinitesimals did not stick because at the end of the 19th and beginning of the 20th centuries there was a debate about all of this and the wrong side won. The consequence is that all the maths textbooks are just plain wrong, all the physics textbooks are woefully incomplete, and all the academics don’t know what they’re talking about (in a very literal sense). This may sound shocking, but it’s the truth.

73. John Armstrong Says:

Michael Livshits! I barely recognized you, all calling yourself “Mark Hanlon”. Glad you ditched that overwrought “Church of Limitology” rhetoric, though.

74. Mark Hanlon Says:

I have investigated his thinking – he advocated a different form of analysis to SIA. I got the impression that he was irritated by Limit theory and contrived an alternative theory which in my opinion is inferior to SIA. This kind of thing can happen because nilsquare infinitesimals were suppressed for so long. I blame Bertrand Russell, he hated infinitesimals – and yet it turns out he was as wrong as it is possible to be. By the way, what the physics textbooks lack is a process called microadditivity (see J L Bell). I met a former student of Bell’s at a party recently, he thought Bell was a bit eccentric.

75. Peter Luthy Says:

I am only vaguely familiar with this nonstandard analysis stuff, but in nonstandard calculus (this nilsquare version, anyway), how does one get around the fact that it really only (seems) to work well with analytic functions (whose power series we know ahead of time)? Is there a formulation of nilsquare infinitesimal calculus which has smooth, compactly supported functions without just borrowing a few nice ones from standard analysis and defining the derivative properly at the strange points? Again, I am only vaguely familiar with a simplified version of nilsquare infinitesimal calculus, so maybe the answer is well-known.

76. Mark Hanley Says:

First of all, I am the same person as Mark Hanlon; I changed my name recently. Anyway, SIA only works with smoothly varying functions (such as all polynomials) because the underlying logic (constructive logic) does not admit the Axiom of Choice and consequently it is not possible to define discontinuous functions. If you did admit the AC and really wanted to fit analysis within your system you would have to invent something like Limit Theory and then suffer the consequences. I think more precise answers to your questions are contained within Bell’s books.

The address given previously doesn’t work any more.
About the negation of the axiom of choice,use :

78. 25 Potentially Controversial Opinions « Mathemusicality Says:

[…] 22. The argument about the Axiom of Choice is over. AC won. It’s one of the Official Axioms of Mathematics. If you don’t like its consequences, see a therapist. (Or: study alternative systems. But for God’s sake don’t claim that standard mathematics is “wrong”.) […]

79. Mark Hanley Says:

I AM claiming that ‘standard mathematics’ is wrong. You have not refuted any of my points. I had an argument with a ‘mathematician’ about this once and he couldn’t either. To quote Nietzsche ‘In individuals, insanity is rare; but in groups, parties, nations and epochs it is the rule.’ It took me about ten years to uncover true mathematics because of this insanity. Godel himself recognized it as such, he never recognized the least upper bound condition for the ‘Real’ numbers as valid (I can reference this if required); The LUB condition is impredicative as is the AC. And now for the Coup de Grace: according to the Banach-Tarski paradox one sphere is equal to two spheres! No more spin, no more delusions. The AC never won. It was garbage from the very beginning.

80. John Armstrong Says:

Mark, that’s a trackback. You might want to go to the blog where someone actually wrote that to argue your inanity.

As for your point, you clearly have no idea what constitutes mathematical “truth”. You seem to think it has something to do with the “real world”.

81. Todd Says:

I’m confused about “Now, when they are put in line and get a hat, they will be able to see all but a finite part of the sequence, and so they can all tell what equivalence class they are in.”

Won’t each successive prisoner believe himself to be in a different, twice-as-large equivalence class as the person behind him? If so, how do we know that at any given point the pre-selected item for that EC is the same for all subsequent ECs, which it seems like you need for the proof to work?

At the level of elementary particles, time could be stopped

The assumption is that at the level of elementary partcles,
time is the infinite set of urelements U of the set theory
with urelements.
If it can be prevented going from the urelement-time u1 to
u2, time would be stopped.
Time at the level of elementary particles is not the arrow
of time that we know at our level.

As a result of what could be happening at the level of
elementary particles, there might be disturbances of
time in an area, at our level, like slowing down.

83. Todd Trimble Says:

It’s been a while since I’ve visited this blog (bring back more math!), but I don’t think Mark Hanlon’s reply to Peter Luthy on 12-23-08 actually answered the question. Here’s an answer though: in categorical models of SIA worth their salt, the category of ordinary manifolds and smooth maps between them embeds fully and faithfully in them. There are many such models.

84. Peter Luthy Says:

Hi Todd,

Thanks for the reply — I’m hoping it’s not an April fool’s joke since compactly supported smooth functions are pretty nice!

Peter

85. David Wilson Says:

The problem in the original post lies in this sentence:

“Next, the prisoners invoke the Axiom of Choice to pick an element in each equivalence class, which they all agree on and memorize.”

AC guarantees that there exists a set containing one element from each of the (uncountable number of) equivalence classes. But it provides no mechanism to specify what that element is. Indeed, the power (and weakness) of AC is that it asserts the existence of things that ought to exist, but which we cannot even theoretically construct.

Suppose our prisoners “agree on” an AC-guaranteed choice function mapping every possible string of hats ahead of them to some representative string of hats differing only in a finite number of hats. Suppose sake of illustration, suppose that if the real string of hats is ultimately periodic (periodic except for a finite number of hats), then the choice function maps this string of hats to the unique purely periodic string differing by a finite number of hats. Whatever choice function AC grants us, we can tweak it to do this.

Now, suppose our prisoners are lucky enough to look out and see an ultimately periodic string of hats. They will then guess as if the string were purely periodic, and only a finite number will guess wrong.

But in general, the string before them will not be ultimately periodic. Indeed, with probability 1, the string of hats before them is not even computable. This means there is no algorithm to generate the true string of hats.

Now suppose the choice function maps the true string of hats to a computable string of hats. We take the algorithm for the choice string, tack on a finite amount of code flipping the color of the finite number of hats differing from the true string, and we have an algorithm for the true string. But this is a contradiction, because the true string in uncomputable. So, if the true string of hats in uncomputable, so is the finitely-differing string of hats given by the choice function.

So suppose our prisoners are unfortunate (with probability 1), and look out to see an uncomputable string of hats ahead of them. Their “agreed on and memorized” choice function will then supply them with a likewise uncomputable sequence differing by a finite number of hats.

But how do you agree on an uncomputable string of hats? At best, they can agree that the choice string exists, but they cannot specify or communicate or agree on that string. In the larger sense, they cannot agree on the choice function guaranteed by AC, since that function is undefined (or rather, necessarily ill-defined).

I think the problem lies with our gut feeling that the choice function is somehow “real” because it exists in the mathematical sense. We envision our prisoners writing a specific constant choice function in a file on a computer with aleph-1 storage, and each prisoner consulting that file to map the string of hats ahead of him to a specific constant choice string of hats from which he guesses his hat color.

But I contend that though the choice function in question may exist in the backwards E sense, it does not exist in the well-defined constant-valued continuum of information sense. One prisoner calling the choice function F and telling a second prisoner to use F to determine his hat color is singularly useless to the second prisoner unless he can know what F is, and in the context of this problem, he cannot do so even in theory. We can never exhibit or agree on such a choice function F, ergo the prisoners cannot guess their hat colors by an agreed-upon mechanism.

AC implies many things that exist but cannot be exhibited. The Banach-Tarski decomposition of the sphere is one such cryptobeast. The well-ordering of the reals is another. Likewise, the choice function that allows the prisoners to guess their hat colors exists, but cannot be exhibited, so it cannot be agreed upon and used to advantage by the prisoners.

86. Petter Says:

David Wilson, it seems that your objection is that their scheme cannot be applied in “real life”. That is quite obvious for arguments that invoke the AC.

87. babak Says:

wow! plz stop a moment.
if i see the sequence in front of me how can i understand which equivalence class our sequence belongs to?

88. Joegle » Math Says:

[…] Axiom of choice is wrong […]

89. rapidleech Says:

This post is great. thank you for sharing these helpful infos. I appreciate your work man

90. rapidleech Says:

hi,
I am very glad to thank yousharing this post.I also appreciate your work here.nice blog

The structure of the post is “since the outcome is counter intuitive, so the premises are counter intuitive as well”. To continue David Wilson’s response, let me point out that apart from Axiom of Choice it was assumed in the premises that the prisoners have continuum-size capasity in memory and computation (able to search through an uncountable list in finite time) and they have the Choice function explicitly written in their continuum-minds.

So why would we conclude that AC is the counter intuitive part, but not all the other assumptions? And in fact, the outcome is not even so counter intuitive, as Terrence Tao pointed out.

Sorry, I confused the ordering of entering my personal information.

The structure of the post is “since the outcome is counter intuitive, so the premises are counter intuitive as well”. To continue David Wilson’s response, let me point out that apart from Axiom of Choice it was assumed in the premises that the prisoners have continuum-size capasity in memory and computation (able to search through an uncountable list in finite time) and they have the Choice function explicitly written in their continuum-minds.

So why would we conclude that AC is the counter intuitive part, but not all the other assumptions? And in fact, the outcome is not even so counter intuitive, as Terrence Tao pointed out.

94. Гномики и аксиома выбора | Блог Хеллера Says:

[…] Однако оказалось, что при использовании аксиомы выбора задача все же решается. Сам я ее решить не смог, потребовав решения от задавшего задачу, и вот собственно это решение я теперь и привожу (сама задача изначально читателем как я понимаю была обнаружена в блоге «The everything seminar»). […]

95. Batton Says:

Well, this means that AC simply is WRONG

96. web sitesi Says:

web sitesi…

[…]The Axiom of Choice is Wrong « The Everything Seminar[…]…

97. Flickner9Fanti Says:

Forms of Developer Purses – What one (As well as 2 or 3) fits your needs? Google.com.br

98. CastleVille Hack Says:

CastleVille Hack…

[…]The Axiom of Choice is Wrong « The Everything Seminar[…]…

99. Online Roulette - Real Online Roulette is Very Just like Casino Roulette Says:

Hello There. I found your weblog using msn. That is a really neatly written article.
I’ll be sure to bookmark it and come back to learn extra of your useful info. Thanks for the post. I’ll certainly comeback.

100. OlgushaSunQU Says:

But, over and over all my tests revealed nothing substantial or really significant, no toxins, no poisons, nothing that made sense or was he It stimulates endorphin-release promoting a sense of well-being, and it momentarily relieves pain. It’s like taking Tylenol for headache caused by a tumor. Traditionally, psychotherapy and prescribed drugs goes along to provide treatment to the symptoms of these conditions. Yoga and meditation are excellent for taking your mind off things that seem to get to you. There are now many patients who are suffering mild depression and anxiety who are prescribed these herbs in Europe and they are very success

101. LeoSwan Says:

Sometimes this can also cause shaking or trembling. If you keep some of these points in mind and relax yourself out of your panic attack you should be fine. Hippocrates made an assessment of character closely related to present day disorders. If you have panic attacks, it is very important to seek medical care and discuss this problem with your doctor. Relaxation techniques: You can relieve stress and anxiety by meditating, doing yoga or learning muscle relaxation techniques. Consider what happens during an anxiety or a panic attack: Suddenly with little or no warning, an anxiety and panic attack sufferer’s heart

102. MrGood Says:

Encourage physical activity. Encourage your teenager to stay active. Exercise can go a long way toward relieving the symptoms of depression, so find ways to incorporate it into your teenager’s day. Something as simple as walking the dog or going on a bike ride can be beneficial. Antidepressants: Get the Facts

103. MrGood Says:

Difficulty in falling asleep A Self-Help Guide to Dealing with Depression

104. MrGood Says:

Helpguide’s Bring Your Life into Balance mindfulness toolkit can help. Norepinephrine and dopamine reuptake inhibitors (NDRIs). Bupropion (Wellbutrin) falls into this category. It’s one of the few antidepressants that doesn’t cause sexual side effects. At high doses, bupropion may increase your risk of having seizures. zoloft side effects after 1 day. or, at the most, only marginal benefit, in a fourth study. zoloft 200 mg dosage. Buy Zoloft Without a Prescription Cheap – Visit Your URL: zoloft 1996 zoloft cheap, Purchase Zoloft Without a Prescription – buy zoloft without prescription. zoloft and ibuprofen. Hypnosis for Treating Depression 25 mg zoloft pregnancy

105. Alkseniya Says:

Guys my sister takes part in the competition of the New Wave, please help. Look at this video, I will be very grateful, I hope there are still good people.

Thanks))))))))

106. JessieAlbaClub Says:

They are guaranteed to work and give you your life back. Again the short-coming to these drugs are that they are not permanent solutions but only stop gaps. Applying pressure to the chest also makes the pain worsen. What should be understood about anxiety and panic is that the symptoms are not the same for everyone. It will likely be one sentence, similar to the examples earlier. Be mentally sound at all times and there is never a need to be anxious.

107. JessieAlbaClub Says:

But remember that medication does not solve your anxiety symptoms nor is it an anxiety treatment which you can use for long periods. Your heart starts to beat rapidly and you turn off the nearest ramp. If anxiety has invaded your office, it may be time to deal with its causes. It has both psychological and physiological benefits. The most common treatment for anxiety in women is therapy, though there can be various approaches. Anxiety is a natural human feature of behavior and is an inherent part of our species.

What’s up friends, how is all, and what you want to say about this paragraph, in my view its actually amazing in favor of me.

109. Anika Says:

Hello everyone, today I found a very interesting video backdoor teen mom , she really is very sexy?

110. Farrah Says:

Hello everyone, today I found a very interesting video teen mom tape , she really is very sexy?

111. AaHelsseksbog Says:

Let us show your photos here

112. Play minecraft free Says:

Great article.

113. Decomlbasync Says:

Looking for a man for intimate relationships.
Price 2500 rubles \ hour
My telephone number is :
79312159614
My photo:

114. Universal countable Borel equivalence relations with an eye toward finitely generated groups | jaywillmath Says:

[…] eventual equality of infinite binary sequences (known as , which you may have seen in a hat problem), isomorphism of finitely generated groups, or orbit equivalence relations arising from Borel […]

115. MintWit AUK Says:

The axiom of choice is wrong

Someone just sent me a link to this. “The Axiom of Choice is Wrong”, by Greg Muller It’s a well written account of a very accessible example of the application of the axiom of choice to bring a “rabbit out of a hat”, except that when you look in the

116. Sam Says:

The statement that the axiom of choice is wrong has been PROVEN false. The axiom of choice is independent of the other axioms of ZF. To say that we have to choose between ZF, ZFC, and ZF with the negation of the axiom of choice is like to say that we have to choose between the rational and real numbers. We don’t, and all of these sets are useful and self-consistent (assuming, of course, the consistency of ZF). The idea that there even IS a two sided debate about the axiom of choice is represents one of the greatest mainstream misunderstandings of math by mathematicians today. Do you want all of your sets to have measure? Then don’t use the axiom of choice. Do you want a larger, more powerful system than ZF? Then consider the possibility of adding the axiom of choice. You wouldn’t tell me that I have to choose between the rational and real numbers, so don’t tell me that I have to choose the axiom of choice or not.

• Jayne Says:

Th3#ey&9;re all super good reasons – PLUS you look amazing and special in your finds (this trousersuit is a gem). The world needs more uniqueness, for sure! xoxo

117. Carl Says:

Sam, there are also alternative set theories (not to mention systems of logic).

118. Sam Says:

Carl, but that’s exactly my point. The axiom of choice isn’t true or false, it’s consistent or inconsistent with a system. Perhaps my analogy with the rationals and reals was misleading. The axiom of choice is a property of a system, like commutativity. Some systems have it, others don’t. Maybe you don’t like working in systems with noncommutative operations. That’s OK, but you wouldn’t reject all such systems as not existing just because they have properties that you don’t like. Calling the axiom of choice false is equally ridiculous.

119. Stan Wagon Says:

Nice to see my book getting a mention here. It is now 30 years on and, with Greg. Tomkowicz, I am working on a second edition (which will include a complete discussion of the circle-squaring solution in the plane; Tarski’s problem, as solved by Laczkovich).

The last chapter of my book discusses the role of AC in measure-theoretic issues in some detail. A really important point, in my opinion, is that some sort of AC (say, DC, the axiom of dependent choice) is needed to get the countable additivity of Lebesgue measure. Lebesgue and Borel, who argued strenuously against AC, were unaware of this. So for a decent theory of measure one needs some nonconstructive choice. Esthetics then demands what we accept all of AC.

Stan Wagon, author of The Banach-Tarski Paradox

PS: These hat problems are fascinating though! A new one is now making the rounds. See

http://mathforum.org/wagon/fall13/p1179.html

120. The Axiom of Choice is Wrong | ADSTRK Says:

[…] Source: hacker news […]

121. The Axiom of Choice is Wrong (2007) | Blog Says:

[…] The Axiom of Choice is Wrong (2007) […]

122. David Pokorny Says:

You assume that if a particular real number x exists, then it is possible for the prisoners to compute, for any given “n”, the nth bit of x IN FINITE TIME. This is clearly not true for any r.e. nonrecursive x (i.e. a real number whose binary representation corresponds to a r.e. subset of the natural numbers, a 1 meaning presence in the set / the Turing machine halts, a 0 meaning absence, the Turing machine runs forever). For example a Chaitin constant. We only “know” that such a number exists because ZFC says it exists. The actual values of the bits can only be computed IN THEORY by running a process for an infinite amount of time. The term “strategy” implies getting a result in finite time.

If you were to actually operationalize this in the context of the problem, then what you would find is that for all of the halting Turing machines, prisoner “n” (starting from the first one who must call out a color) would have to say, “my Turing machine halts”. The first prisoner who corresponds to a non-halting Turing machine will attempt to simulate, in his head, a Turing machine that runs forever, and he won’t be able to call out a color until the simulation in his head finishes. It won’t finish, and the warden and all prisoners will die before he calls out a color.

[Nonsense warning] If “w” = Omega, then worst case we have to wait “w*w” time for the prisoners to give answers, assuming we go in sequence and (patiently) wait possibly an infinite amount of time for each one to answer. I’m not an expert on hyper-computation, but my understanding is that computable power can be indexed by ordinals.

I’m assuming here for simplicity that (1) a particular Chaitin constant has been selected and (2) by chance, the hats of ALL of the prisoners (not just all but finitely many) are identical with the true binary representation of this number. So if only they had the time, they could ALL go free.

123. elliptical trainer reviews Says:

Hi to all, how is everything, I think every one is getting more from
this web site, and your views are pleasant for new people.

124. smaudet Says:

So I probably missed this in the above comments somewhere, but:

A) Very interesting, informative, I feel a tad smarter. 😛
B) The people talking about time are confusing math and reality. Math at this level exists outside of the known physical constructs we encounter – this is where the ‘1 true topos’ argument comes from, which is interesting in that if there is no ‘true’ topos, what, exactly, is physicality? At any rate it should be fairly obvious that this whole question of time and memory is bogus and a limit of your imagination. We think time at any rate is a by-product of physical space, memory or information is probably also (we think) a by-product of space, not something inherent to math.

C) Viewed from the concept of an information problem, I think this is also very interesting. I don’t fully understand the Axiom of Choice, but at least from what some people were saying about probabilty, I think I may have spotted a fallacy. They are presuming each guess is independent – they are dead wrong.

It is true that each prisoner’s guess isn’t dependent in reverse, on the previous choice, but they have visibility of ‘all but a finite set’. They have infinite dependency upon future elements.

So, basically, we have an infinite track tape and the warden is choosing some finite part of that track tape to screw up, and afterwards at some point in the future the assertion is that seeing infinity allows infinite numbers of correct choices on that track tape.

I’ll admit, I don’t understand how that works, and that may be that I don’t understand the equivalence classes very well but:

Are we asserting that all infinite equivalence classes are the same?

Why can’t the warden make infinitely many choices? The prisoners are choosing infinitely many times, I see no reason presented the warden cannot.

So, I’m highly tempted to say the problem presented is bogus, not the Axiom of Choice.

125. sam chen Says:

what an interesting article with so many enlightening responses!

126. Dylan Stephano-Shachter Says:

I agree that there are some points in this strategy that are quite hard to accept. Those difficulties do not arise, however, from the axiom of choice.

The part that is so hard to wrap your head around is that the prisoner can look out upon an infinite sequence and tell which equivalence class it comes from. This would obviously be impossible in the real world but in the world of perfectly intelligent prisoners, it is fine. Not only is it fine but it does not use the axiom of choice at all.

The axiom of choice comes in just to make it possible that there is a representative sequence for the equivalence class. I don’t think anyone would find it far fetched that you can choose a representative from a bunch of sets.

127. Anonymous Says:

” I don’t think anyone would find it far fetched that you can choose a representative from a bunch of sets.”

lots of mathematicians do, actually. And this is not just a “bunch” of sets, it’s uncountably many of them, and there is no algorithm at all that can tell you which representative you should take (and by that i mean that it’s impossible to create an algorithme to do that, it can’t exist one) and yet, by the axiom of choice, you get to choose a representative from every set.

128. Dylan Stephano-Shachter Says:

“and there is no algorithm at all that can tell you which representative you should take”

The thing is, is doesn’t matter which one you take. Your algorithm could be “Pick a random one, move on to the next set”. Of course one might ask “How does one pick a random element?” I would argue that while I can not explicitly say how, it is clear that that is possible in the same way that I can pick a random pebble out of the ocean.

• Stan Wagon Says:

I note a lot of comments here about “picking”, “how to pick”, etc. But AC says nothing about algorithms or “picking” elements. It simply says that a set with a certain property EXISTS. Just like the Axiom of Replacement of ZF says the same thing: a set of a certain sort “exists”. The concept of “picking” seems irrelevant.

Stan Wagon

• Dylan Stephano-Shachter Says:

Yes you are completely correct about that but you can’t ignore the fact that we are talking about a specific problem where people do have to find the set even if it already exists.

And of course these are not real people but abstract math “people” but it still remains that the point of the problem is to find a precedure.

• Stan Wagon Says:

“is to find a procedure.” I disagree. See the recent book by Hardin and Taylor on these sorts of infinite hat problems.

The theorems are all of the form “a strategy exists”, as opposed to: “the prisoners can formulate some sort of strategy telling them how to behave depending on the hats that they see”. A strategy is a certain set-theoretic object. ZFC asserts ONLY that this object exists as a set (not that it can be “found” or used as an actual algorithm procedure).

• Dylan Stephano-Shachter Says:

I agree with you that ZFC only asserts the existance of such a set and not the ability to find it. Furthermore I would never say that the answer is wrong. That being said, it is still important when we say “a strategy exists” to think about how we should define a strategy.

129. Jeff Says:

Isn’t possible that different prisoner’s think they belong to different equivalent classes because of their position in line?

For instance

101001000… may appear to be equivalent to 010010001…
for the first person but not to the second person

I am not sure if this changes anything but it is another weird aspect to this.

Also, one thing that isn’t clear is if the prisoner’s no their position in line. When guessing are they do as if they are in the first position or in the same corresponding position that they actually are in?

Lastly, isn’t each person’s guess irrelevant? Since any person who can see an infinite part of the sequence in front of them must be in the finite part? Or do these finite difference not necessarily occur at the beginning?

130. Cedric Says:

Disclaimer: I am a newbie to all this.

What I don’t get is that for each and every sequence, there exists an identical sequence with a different starting hat. So you can never know which EC you’re in, only which EC everyone in front of you is in. So you can never know what to say.

(Btw Stan I love the link you posted on May 24!)

131. qrlornp@gmail.com Says:

132. Spooky inference and the axiom of choice | Matt Baker's Math Blog Says:

[…] and the counterintuitive conclusions of infinite hat puzzles in the comments section of this blog post.  Among other things, Tao points out that one of the issues here is that the direct limit as […]

133. Emi Says:

Reblogged this on Pathological Handwaving and commented:
The 8th comment down is a great refutation of the situation proposed in the post.

134. Zombie Joe Says:

Depends on what you mean by “a strategy exists”. If we want to accept the solution presented here then it means:

A function f exists that maps from other people’s hat colors and the prisoner’s own ID to a color guess, such that the application of this function will only result in finite failures, independent of the particular hat coloring.

But just because the strategy “is out there”, it doesn’t mean that the prisoners can utilize it or even know whether they are utilizing it. The book on the cure of cancer is out there in the Library of Babel (all possible 1000 page books), the actual hard part is to tell it apart from all other similar books.

It boils down to the ‘invent vs discover’ problem or the ‘create vs choose’ problem. Every creation is basically choice out of a sufficiently large set of possibilities. When you invent something you discover that particular construction from the set of all possible constructions. Whenever you write a poem or novel you basically choose one from Library of Babel. I wouldn’t say that the Mona Lisa existed before Da Vinci painted it, even though that configuration of pixels already ‘existed’ before (or configuration of the quantum states of elementary particles).

The platonic existence concept only describes potentials, things that might as well happen that way but nobody can make them actually happen. It’s like hitting Chaitin’s omega number over the number line by throwing a dart. It’s not impossible to hit it, since “the number exists”, but you cannot aim for it because you don’t even know it precisely in the real world. If you could invoke hypercomputation then you could hit it.

For me any existence claim is inherently coupled with a (potentially infinite or otherwise weird) construction process, and the existence is only valid to the same extent that I accept the construction ‘story’ as valid.

The only (but huge) difference is that the prisoners don’t need to be intelligent or creative. They just need to be able to make an infinite amount of agreements and then remember the agreements. They may do it in some way where they spend 1 second on it in total and they make a decision at each real number seconds or something along these lines. But the have to remember an infinitely complex agreement (with such memory they could even hold the ‘halting function’ in their head).

I have no problem to accept the solution. If they have the means to go through an infinity of arbitrary decisions and have infinite memories, then sure they can win at this game.

In practice however, the guards wouldn’t notice a thing. The prisoners would look like random players and neither the prisoners nor the guards could know an upper bound on when the block of infinite correct guesses will begin. It will “at some point”, but it’s an unfalsifiable claim. Any finite sequence of guesses that looks random is totally compatible with the prisoner’s claim that they have this great strategy.

135. Matthew Schallenkamp Says:

So if the axiom of choice is that a set exists that has one member of each set from a set, why can you not simply construct all sets that contain one element of each set within the set and then choose one from them?

So say you have set a that contains a countable infinite number of sets of countable infinities, creating the set of all sets that have one member of each of those is possible, right?

I can see a possible difficulty as you get to higher ordinals, but intuition tells me that if you can solve it for the first few ordinals, the rest would come inductively.

136. gaurav sinha Says:

Infinite number of persons toss coins. Everyone can see all outcomes except his own. Then the strategy allows all except finite number to guess their outcome correctly.

Furthermore instead of coin toss It could be a random element generator from any set. For example each person could Have a ordinal number.

137. Maidenhair Says:

@ The guy from many years ago we said AC is wrong because its impredicative, it sounds as if you are a crazed loon! Why would you tar “the tallest person in the room” with the same brush as the Banach-Tarski?

To the guy from many years ago who said the infinite product of nonempty sets is nonempty, yes you can restate the AC that way. Doesn’t make it obvious.

Personally I despise even countable choice. Look at the proof of finite choice. You have a choice sequence of cardinality 1. Now if we are assuming (n-1)-choice is true, we can form the n-choice sequence by invoking the existence of (n-1)-choice to get an (n-1)-choice sequence for the first (n-1) sets, and then choose 1 more to get an n-choice sequence. So its an inductive proof of n-choice.

If we are to believe that the AC is obvious, then we are supposed to believe that the above proof was a complete waste of time. It doesn’t feel that way, it feels like the above proof was a full proper proof of a full proper theorem. So I absolutely refuse to accept as obvious a *generalisation* of it!!

138. damian Says:

Does the strategy really need AC? It seems to me that the prisoners only need to agree on a representative sequence for their equivalence class. Each prisoner needs to remember the set of all equivalence classes and pick the correct equivalence class of their observed hat sequence. As far as I can tell, AC is not necessary for this and they will all pick the same equivalence class from what they observe. Furthermore, the strategy might tell the prisoners to take the first sequence from this equivalence class with respect to some order. A lexical order should do it after they have agreed on a total order over the set of all colors.

139. Jay Says:

I agree with Damien. Why is AC needed? As your representative member of the equivalence class, choose the one with all black hats before the infinite sequence that determines the equivalence class starts.

The non-intuition is from the infinity, not AC

140. 2 – The Axiom of Choice Is Wrong (2007) Says:
141. Fezvez Says:

In response to the last 2 commenters, you need AC. “Each prisoner needs to remember the set of all equivalence classes and pick the correct equivalence class of their observed hat sequence”. No, they need to pick the representative of that equivalent class. And picking such an element of the class requires AC

• Damian Says:

“… they need to pick the representative of that equivalent class. And picking such an element of the class requires AC.”

No. You need AC if you want a set of representatives of all equivalence classes. You can use this set to get a representative of a given equivalence class, I agree. But I do not agree that it is the only way.
1) Take the set of all equivalence classes E.
2) Take the desired equivalence class e in E (the one you are interested in)
3) Take a representative r in e.

• Ben R Says:

Some equivalence classes are simple: for example there’s the class of sequences that end in white hats forever, those that end in alternating white and black forever, and so on. For those you can pick “simplest” representatives. But the overwhelming majority of sequences (all but countably many) have no structure: they are just random colors out to infinity. How will you pick a representative? Your method must yield the same result for any two sequences that differ in any finite number of positions; this means that it can’t depend on the color of the hat in any particular position, as there are members of the class where that hat has the opposite color.

• Damian Says:

“But the overwhelming majority of sequences (all but countably many) have no structure: they are just random colors out to infinity. How will you pick a representative?”

Let [x0, x1, x2, x3, x4, …] be an infinite sequence.
Let
suff(0, [x0, x1, x2, x3, x4, …] = [x0, x1, x2, x3, x4, …]
suff(1, [x0, x1, x2, x3, x4, …] = [x1, x2, x3, x4, …]
suff(2, [x0, x1, x2, x3, x4, …] = [x2, x3, x4, …]
suff(3, [x0, x1, x2, x3, x4, …] = [x3, x4, …]
etc.
Let “+” be the operator for sequence concatenation.
Let w^n be a word of length n.

Then for any equivalence class E, there is a fixed infinite sequence [s0, s1, s2, s3, s4, …] such that every sequence in E has the form w^n + suff(n, [s0, s1, s2, s3, s4, …])
With n=0, [s0, s1, s2, s3, s4, …] itself is in E, so take it as a representative.

• Damian Says:

Unfortunate for my previous argument, [s1, s2, s3, s4, …] is not unique. Well then.

142. Soeren Wolfers Says:

The paradox persists in the following variation that does not need AC!

Let’s say the prison guard must pick a sequence from a single equivalence class. Then, the prison guard still has infinitely many choices, and knowing the tails doesn’t tell anything about the heads. Therefore, intuition still says that each prisoner has only a 50% chance to know about his own hat color. However, the now obvious strategy to just agree on one representative, which now does not require AC, still works with the same result.

Some might object that the prisoners are given too easy a problem in my variation for the outcome to be surprising, but in my opinion the paradox in both cases is that we turn 50% “felt” individual chance of infinitely many prisoners into finite failure guarantees (Note that in my variation we still have intuitive independence of the individual chances: the probability that two given prisoners survive is intuitively 25%)

In both cases the 50% are not rigorous, and I think this supports previously stated opinions that the problem is not with AC but with our intuition about chances, which cannot be made rigorous in this problem. In particular, I think that the strategies in both cases require “aligning” the choices of the prisoners in a way that prevents measurability. In the original problem, this aligning happens dependent on the actual pick of the sequence (and leads to non-measurability of the survival-events), in my variation it is built into the problem (and leads to problems even defining the prison guards probability measure)

143. A Countable Hat Game and the Kolmogorov 0-1 Law – Random Walks in the Dark Says:

[…] is somewhat well-known that in this game and similar ones, the players can always win if they make use of the Axiom of Choice. (It seems to me that this […]

144. The Axiom of Choice is Wrong Says:

[…] 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 … – Read full story at Hacker News […]

145. The Axiom of Choice is Wrong | ExtendTree Says:

146. Greg Magarshak Says:

The axiom of choice is used to demonstrate the *existence* of something, in this case a perfect strategy.

However, if said strategy’s implementation requires actual infinities, eg each prisoner having an infinite memory, then that is why you find it intuitively objectionable.

It is useful here to think of computer algorithms and not just math. While mathematical arguments have no problem supposing infinite amounts of actors, the next question is whether each actor can have infinite memory.

In mathematics, infinity can be thought of as a property of a *set*. It can also be thought of as some limit of an infinite sequence of operations on sets, which is a statement that is simultaneously true about each member of that sequence.

This is useful because it can tie constructions we observe in the real world into patterns that approximate and converge to the limit of this infinite sequence. And then the question is how the computational complexity grows.

So in your example here, each FINITE set of prisoners can’t coordinate a strategy. So there is no “approaching a limit” – the thing only starts working with an infinite set of prisoners, each of whom has infinite memory etc. And that is why you get your intuition alarm bells go off 🙂

But it is even more than that. Your construction requires each prisoner to *use the axiom of choice in order to take an action based on the NAME of the chosen member* which is used to demonstrate the existence of a sequence of *actions* that satisfies a certain property. However, when the axiom of choice is used normally, it is not used to actually NAME the chosen element, but merely work with it like a black box. By NAME, I mean an id that distinguishes it from all other elementa, and lets you pick it out and examine is properties THAT ARE DIFFERENT than all other elements in that set.

In other words, Sure, you can assume that the chosen “representative” sequence has the same property as any other in the equivalence class — namely that all but finitely many terma are equal. BUT the part where you “cheat” is having the prisoner “find out” more than that about the representative sequence, in particular its initial values up to an arbitrary depth.

147. Articles/Links I liked. | mEssy bYtes Says:

[…] The Axiom of Choice is Wrong […]