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 
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.
The Everything Seminar 
September 13, 2007 at 3:00 pm |
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.
September 13, 2007 at 3:23 pm |
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…
September 13, 2007 at 5:06 pm |
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.
March 25, 2017 at 3:55 pm |
I want to send you an award for most helpful inrnteet writer.
August 29, 2017 at 12:36 pm |
Evet evet bol 'ssss' kullanmamak gerek zira 3'lü yaşlara girdim 18. doğumgünümü nasıl heyecanla beklediğimi daha dün gibi hatırlıyorum. Zaman nasıl bu kadar çabuk geçiyor bir bilsem (
September 13, 2007 at 5:55 pm |
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?
September 13, 2007 at 9:05 pm |
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?
September 13, 2007 at 9:23 pm |
Having not seen this post, I wrote a more humorous post about the Bananach-Tarski paradox. It must be something in the air today.
September 13, 2007 at 9:51 pm |
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?
September 13, 2007 at 9:58 pm |
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
), and one uses the strategy coming from the axiom of choice, then the event 
that the j^th prisoner does not go free is not measurable, but formally has probability 1/2 in the sense that 
and its translate 
partition 
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 
all seem to have probability 1/2, each element of the event space lies in only finitely many of the 
. This can be seen to violate Fubini’s theorem – if the 
are all measurable. Of course, the 
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
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.)
November 3, 2019 at 4:20 pm |
Actually, the $E_j$ are all measurable; in fact, every singleton of $\mathbb Z_2^\mathbb N$ is measurable. The problem is that one does not only use Fubini’s theorem, but also the independence of the events $E_j$. And if we assume that this independence equation holds for infinite products, we may observe our integral to become zero in a blink.
September 13, 2007 at 10:29 pm |
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.
September 13, 2007 at 10:36 pm |
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.
September 13, 2007 at 10:54 pm |
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.
September 13, 2007 at 10:55 pm |
Oh, and that response you mention is spelled “無”. 😀
September 13, 2007 at 11:28 pm |
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!).
September 14, 2007 at 1:39 am |
So you are agnostic on the question of whether the infinite direct product of non-empty sets is non-empty?
September 14, 2007 at 1:40 am |
[…] is a discussion at the Everything Seminar about everyone’s favorite topic, the axiom of choice. The axiom of choice has various […]
September 14, 2007 at 1:44 am |
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.
September 14, 2007 at 7:27 am |
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).
September 14, 2007 at 8:37 am |
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.
September 14, 2007 at 8:50 am |
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.)
September 14, 2007 at 11:05 am |
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.
September 14, 2007 at 1:40 pm |
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?
September 14, 2007 at 1:49 pm |
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).
October 15, 2011 at 10:16 am |
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.
September 14, 2007 at 2:32 pm |
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.
September 14, 2007 at 2:47 pm |
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.
September 14, 2007 at 4:07 pm |
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!
September 14, 2007 at 4:28 pm |
>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?
September 14, 2007 at 5:24 pm |
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).
September 14, 2007 at 5:53 pm |
Kea, thank you for pointing out the benefits of philosophical sloganeering, namely that they’re concise at the expense of hideous accuracy.
September 14, 2007 at 11:34 pm |
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.
September 15, 2007 at 12:42 am |
“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?
September 15, 2007 at 4:35 pm |
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.
September 15, 2007 at 5:09 pm |
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:
implies that 
.
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
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.
September 15, 2007 at 6:21 pm |
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.
September 15, 2007 at 6:39 pm |
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.
September 15, 2007 at 7:02 pm |
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?
February 24, 2016 at 4:51 pm |
yes 50 guaranteed freedom the other 50 have a a 50% chance so 25 of them would survive giving a total of 75 saved on average.
September 15, 2007 at 7:15 pm |
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.
September 15, 2007 at 8:26 pm |
[…] 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 […] […]
September 16, 2007 at 1:30 pm |
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.
September 16, 2007 at 10:36 pm |
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.
September 17, 2007 at 12:44 am |
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”.
September 18, 2007 at 5:35 am |
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
which the axiom of choice has chosen for us, then by definition
is the sequence we are on, and
is the “chosen” sequence, i.e., the member of the equivalence class that includes
Let us call that
the “point of convergence”.
How big is
? One way of getting at this is to consider some particular value 
and ask whether 
. Well, it is easy to see that 
with probability at least 1/2, since 
. Similarly 
with probability at least 
, since
In fact, for any
you choose, 
with probability at least 
because
So we see that
for any 
. In other words, 
with probability zero. So for any 
you pick, you can be sure (with probability one) that 
. But we “know” by definition that 
“exists” and is therefore some integer. How can this be?
Consider the distribution
. By symmetry, 
is a uniform distribution. But a uniform distribution over the non-negative integers is nonstandard: 
, yet 
.
What is really happening is that the “point of convergence”
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) 
happens to be larger than any actual integer we care to name! It is a nonstandard integer. Whether this 
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.
September 18, 2007 at 11:57 am |
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.
September 18, 2007 at 12:00 pm |
Never mind, I didn’t read the problem statement carefully enough. I thought this was the same as another problem I saw.
September 18, 2007 at 6:42 pm |
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…)
September 19, 2007 at 1:45 am |
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.
September 19, 2007 at 7:06 am |
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
are the (standard) natural numbers. But we know that
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.
where N is the “point of convergence” and
where
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.
September 19, 2007 at 8:44 am |
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 ?
September 19, 2007 at 9:35 am |
: 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.
September 20, 2007 at 9:36 am |
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)
September 20, 2007 at 9:52 am |
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).
September 20, 2007 at 12:42 pm |
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
, 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.
September 21, 2007 at 8:46 pm |
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.
September 24, 2007 at 12:18 am |
[…] 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, […]
September 27, 2007 at 8:14 pm |
[…] is some weird shit Seriously. Come to think of it, I have always wondered what a well-ordering of [0, 1] looks like . . […]
September 27, 2007 at 9:25 pm |
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 🙂
September 28, 2007 at 2:18 pm |
[…] 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. […]
October 1, 2007 at 5:45 am |
[…] The Axiom of Choice is Wrong « The Everything Seminar […]
October 18, 2007 at 5:44 am |
See my web page about the negation of the axiom of choice :
http://jebara.topcities.com
Adib Ben Jebara.
November 19, 2007 at 6:25 am |
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.
November 21, 2007 at 5:23 am |
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.
April 12, 2008 at 4:46 pm |
[…] 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 […]
March 25, 2017 at 8:58 pm |
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
April 30, 2008 at 10:58 am |
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.
June 7, 2008 at 5:46 pm |
hello! ist cool …is chido me encanta de jonas brothers son fabulosos sobre todo nick jonas es un bue…esta requete bueno…
August 23, 2008 at 7:17 pm |
[…] 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 […]
September 22, 2008 at 5:05 pm |
[…] 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 […]
September 29, 2008 at 4:30 pm |
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.
October 1, 2008 at 8:07 am |
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.
October 6, 2008 at 1:24 am |
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.
October 6, 2008 at 11:03 am |
‘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.
October 19, 2008 at 11:49 pm |
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”
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 
. 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.”
October 19, 2008 at 11:50 pm |
oops.
November 12, 2008 at 6:52 pm |
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.
November 12, 2008 at 9:23 pm |
Michael Livshits! I barely recognized you, all calling yourself “Mark Hanlon”. Glad you ditched that overwrought “Church of Limitology” rhetoric, though.
November 28, 2008 at 11:15 am |
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.
December 18, 2008 at 12:16 am |
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.
December 23, 2008 at 8:04 am |
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.
December 29, 2008 at 11:16 pm |
The address given previously doesn’t work any more.
About the negation of the axiom of choice,use :
http://www.freewebs.com/adibbenjebara
Adib Ben Jebara.
February 15, 2009 at 6:31 pm |
[…] 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”.) […]
February 17, 2009 at 9:34 am |
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.
February 17, 2009 at 12:51 pm |
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”.
March 18, 2009 at 1:54 pm |
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?
March 30, 2009 at 11:56 pm |
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.
Adib Ben Jebara.
April 1, 2009 at 3:39 am |
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.
April 5, 2009 at 3:53 pm |
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
May 28, 2009 at 9:41 pm |
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.
November 12, 2009 at 9:42 am |
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.
February 22, 2010 at 3:05 am |
wow! plz stop a moment.
could you please give me an answer
if i see the sequence in front of me how can i understand which equivalence class our sequence belongs to?
May 4, 2010 at 12:26 am |
[…] Axiom of choice is wrong […]
January 15, 2011 at 5:42 am |
This post is great. thank you for sharing these helpful infos. I appreciate your work man
January 15, 2011 at 9:07 am |
hi,
I am very glad to thank yousharing this post.I also appreciate your work here.nice blog
March 3, 2011 at 4:53 pm |
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.
March 3, 2011 at 4:56 pm |
Sorry, I confused the ordering of entering my personal information.
March 3, 2011 at 4:57 pm |
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.
August 5, 2011 at 4:24 am |
[…] Однако оказалось, что при использовании аксиомы выбора задача все же решается. Сам я ее решить не смог, потребовав решения от задавшего задачу, и вот собственно это решение я теперь и привожу (сама задача изначально читателем как я понимаю была обнаружена в блоге «The everything seminar»). […]
September 21, 2011 at 11:37 am |
Well, this means that AC simply is WRONG
November 12, 2011 at 1:07 pm |
web sitesi…
[…]The Axiom of Choice is Wrong « The Everything Seminar[…]…
November 30, 2011 at 9:22 pm |
Forms of Developer Purses – What one (As well as 2 or 3) fits your needs? Google.com.br
December 14, 2011 at 2:14 am |
CastleVille Hack…
[…]The Axiom of Choice is Wrong « The Everything Seminar[…]…
December 13, 2012 at 6:41 pm |
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.
March 5, 2013 at 7:40 pm |
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
March 10, 2013 at 7:46 am |
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
March 12, 2013 at 4:51 pm |
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
March 13, 2013 at 9:54 am |
Difficulty in falling asleep A Self-Help Guide to Dealing with Depression
March 19, 2013 at 6:48 pm |
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
March 22, 2013 at 4:44 am |
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))))))))
April 9, 2013 at 6:16 pm |
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.
April 9, 2013 at 8:00 pm |
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.
April 24, 2013 at 5:09 pm |
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.
May 7, 2013 at 10:35 am |
Hello everyone, today I found a very interesting video backdoor teen mom , she really is very sexy?
May 7, 2013 at 12:48 pm |
Hello everyone, today I found a very interesting video teen mom tape , she really is very sexy?
July 1, 2013 at 1:04 pm |
Let us show your photos here
September 8, 2013 at 10:17 am |
Great article.
December 23, 2013 at 7:45 am |
Looking for a man for intimate relationships.
Price 2500 rubles \ hour
My telephone number is :
79312159614
My photo:
Waiting for your call !
January 8, 2014 at 3:42 pm |
[…] 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 […]
March 18, 2014 at 2:19 am |
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
May 13, 2014 at 2:20 pm |
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.
March 25, 2017 at 9:12 pm |
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
May 15, 2014 at 8:58 pm |
Sam, there are also alternative set theories (not to mention systems of logic).
May 15, 2014 at 9:50 pm |
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.
May 24, 2014 at 1:38 pm |
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
July 5, 2014 at 11:26 am |
[…] Source: hacker news […]
July 5, 2014 at 11:50 am |
[…] The Axiom of Choice is Wrong (2007) […]
July 5, 2014 at 5:54 pm |
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.
July 7, 2014 at 11:40 pm |
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.
July 23, 2014 at 2:39 am |
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.
August 3, 2014 at 10:10 am |
what an interesting article with so many enlightening responses!
August 4, 2014 at 1:43 pm |
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.
March 25, 2017 at 6:42 pm |
Hahhaaha. I’m not too bright today. Great post!
August 10, 2014 at 9:34 am |
” 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.
August 11, 2014 at 11:08 am |
“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.
August 11, 2014 at 11:20 am |
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
August 11, 2014 at 12:07 pm
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.
August 11, 2014 at 12:27 pm
“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).
August 11, 2014 at 12:34 pm
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.
August 12, 2014 at 10:45 pm |
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?
August 15, 2014 at 2:41 am |
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.
What am I missing? Please help…
(Btw Stan I love the link you posted on May 24!)
December 23, 2014 at 4:37 pm |
click here for the best roofers available
January 17, 2015 at 4:12 pm |
[…] 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 […]
January 29, 2015 at 4:43 am |
Reblogged this on Pathological Handwaving and commented:
The 8th comment down is a great refutation of the situation proposed in the post.
February 25, 2015 at 11:38 am |
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.
April 24, 2015 at 11:26 pm |
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.
May 13, 2015 at 10:14 pm |
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.
June 19, 2015 at 1:47 pm |
@ 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!!
August 3, 2015 at 3:19 pm |
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.
December 10, 2015 at 3:32 am |
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
February 9, 2016 at 3:42 am |
[…] From: https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/ […]
February 16, 2016 at 7:28 am |
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
February 16, 2016 at 6:26 pm |
“… 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.
February 22, 2016 at 3:52 am
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.
February 22, 2016 at 6:02 pm
“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.
February 23, 2016 at 2:08 pm
Unfortunate for my previous argument, [s1, s2, s3, s4, …] is not unique. Well then.
August 17, 2016 at 4:42 am |
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)
January 3, 2017 at 8:21 pm |
[…] 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 […]
February 5, 2017 at 3:27 am |
[…] 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 […]
February 5, 2017 at 8:05 am |
[…] Read Full Story […]
February 5, 2017 at 3:36 pm |
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.
March 18, 2017 at 4:43 am |
[…] The Axiom of Choice is Wrong […]
September 2, 2017 at 2:46 pm |
هيئة المهندسين التجمعيين – corps des ingenieurs du parti du RNI
corps des ingenieurs du parti du RNI
October 9, 2017 at 10:33 am |
In case you have outside kittens and cats, be sure to discourage pests like coyotes, possums and raccoons by taking cat food in the house at nighttime. Give your pet cats first thing in the morning, and ensure there is absolutely no food items remaining at nightfall. This may keep your cats safe from strike and sickness.
October 9, 2017 at 10:54 am |
The preceding ranks as the most bizarre comment about the Axiom of Choice I have seen.
October 29, 2017 at 1:37 am |
The real issue here is not the axiom of choice but the law of excluded middle. In intuitionistic logic, the axiom of choice is a theorem, while the law of excluded middle is not true (it’s just unfalsifiable). Intuitionistic = computable = continuous.
November 22, 2017 at 2:46 pm |
Aliso canyon ride
The Axiom of Choice is Wrong | The Everything Seminar
December 1, 2017 at 3:11 pm |
To clarify my earlier comment, my favored theory for how the world works is something along the lines of HoTT. In this:
(a) the law of excluded middle is not quite provably false, but it is possible to prove (in ZF) that the only model of HoTT+LEM is trivial;
(b) the axiom of choice is a theorem, because the most natural wording of “nonempty set” is “pointed type”, for which AC obviously holds.
Then the argument fails to go through, because all functions are continuous, and any function from $S^Z$ to itself that sends equivalent elements (equal at infinitely many points) to the same element is heavily discontinuous under the product topology, as long as $S$ is disconnected.
There is actually a nice proof that all but the first prisoner (who cannot do better than by guessing) can survive:
Simply assign a group structure to the set of colors (there are arbitrarily large groups by Löwenheim-Skolem and the existence of $\Bbb Z$), select an element $E(C)$ of each equivalence class,
then prisoner $n$ computes $Q_n=\prod_{i=n+1}^\infty (C_iE(C)_i^{-1})$. This exists because all but finitely many factors are trivial.
Then set $A_0=Q_0$, $A_{n+1}=A_nQ_{n+1}^{-1}E_{n+1}$,
where prisoner $n$ can compute $A_n$ and announce it after hearing $A_{n-1}$, and $A_n=C_n$ if $n>0$ by simple computation.
December 1, 2017 at 3:18 pm |
And my second-favorite set theory is a variation on NBG. Take the language of ZF plus a unary function $u$,
let the axioms be those of NBG relativized to $u(x)$, where we replace “$y$ is a set” by “$y\in u(x)$” and “$y$ is a class” by “$y\in u(u(x))\wedge \forall z\in y. z\in u(x)$”, except for the axiom of infinity (which we won’t need, because $u(\emptyset)$ contains all the hereditarily finite sets anyway).
April 4, 2018 at 8:36 am |
[…] I stumbled upon an interesting article about a ‘paradoxical’ appeareance of the axiom of choice in a generalization of the […]
November 12, 2018 at 7:51 pm |
You made some decent points there. I regarded on the internet for the difficulty and found most individuals will go together with together with your website.
December 11, 2018 at 9:15 pm |
Been following your site for a while now. Visit mine, I write tips on a blog for earning some extra cash online. https://deepwebsites.org
December 22, 2018 at 8:00 pm |
Great info. Lucky me I came across your blog by chance (stumbleupon).
I have saved it for later!
May 2, 2019 at 3:21 am |
I found your blog site on google and check a few of your early posts. Proceed to keep up the very good operate. I just extra up your RSS feed to my MSN Information Reader. Looking for forward to reading more from you later on!…
May 13, 2020 at 5:41 pm |
Hey guys,
I stumbled upon this problem a few days ago and found a proof that the solution is wrong. Even with accepting the existence of AC, the solution does not work.
I got a proof written in plain text on my forum, though it is in german:
https://abenteuer-universum.de/bb/viewtopic.php?f=15&t=4328&p=68317#p68317
Its got to do with the signature of the equivalence classes, which I derived from a well-order. Even with viewing ALL hats and knowing all preremembered elements of each class, it is impossible to determine the equivalence class they are in (even when trying to apply AC).
kindly regards
Halim Paracki aka Skeltek
July 29, 2020 at 9:05 am |
Personal Struggle
The Axiom of Choice is Wrong | The Everything Seminar
September 1, 2020 at 11:43 pm |
http://Www.Londonchinese.Org
The Axiom of Choice is Wrong | The Everything Seminar
September 19, 2020 at 6:35 am |
Has anybody ever shopped at Discount Vape Connection Vapor Store in 203 Santa Ana Ave #B?
October 10, 2020 at 6:31 pm |
you think ashton
November 12, 2020 at 1:14 am |
thank you zindagi
November 21, 2020 at 4:22 am |
Life changes
The Axiom of Choice is Wrong | The Everything Seminar
May 9, 2023 at 12:54 pm |
ratu 311
The Axiom of Choice is Wrong | The Everything Seminar