The Axiom of Choice is Wrong (2007) | Hacker News Reader

The Axiom of Choice is Wrong (2007)

cornellmath.wordpress.com

68 pointsColinWright76 comments

One of the troubling aspects of the Axiom of Choice is that both affirming and denying it results in some pretty unintuitive implications (but different ones).

This MathOverflow discussion has some interesting examples of unintuitive implications of the axiom, along with a bonus answer giving examples of unintuitive implications of not having the axiom: http://mathoverflow.net/questions/20882/most-unintuitive-app...

The history of it is full of people wrestling with both sides of that, including many participants in the debate having trouble keeping their own positions consistent—the axiom of choice is equivalent to so many other things (many only discovered fairly recently) that consistently affirming or denying it has tripped up many world-class mathematicians! I am currently about 1/3 of the way through this really interesting history that tries to trace that development, Zermelo's Axiom of Choice by G.H. Moore (2013): http://www.amazon.com/gp/product/0486488411/ref=as_li_tl?ie=... (ToC: http://www.apronus.com/math/zermelos.htm)

"The axiom of choice is obviously true, the well-ordering principle obviously false, and who knows about Zorn's Lemma?" -- Jerry Bona

I particularly like the one about some vector spaces having no basis, or bases of different cardinalities (should we deny the Axiom of Choice).

That one really struck me, too. Personally, I'll take the creepy prisoner paradox if I need it to keep my vector space bases.

That's a great list! Being a grad student in mathematics, I find several of those way more upsetting than anything like Banach-Tarski or the hat problem in the linked post.

Banach-Tarski is too easily dismissed as a problem with real numbers being an intuitive model of experience, versus a problem with AC itself.

Oh, I agree. I'm totally comfortable with it, by now. I think the von-Neumann quote might apply here: "In mathematics, you don't understand things. You just get used to them."

Indeed, this is what intuition is. We often fail to notice where our childhood intuitions come from (experience), and so our adult desire to understand interferes with our ability to form new intuitions.

What's the difference? Uncountable sets does not respect out intuition about countable sets.

AC is independent from ZF, meaning it doesn't matter for any application to anything in the Universe, including physics or computing. Theory of uncountable objects is a game to play with symbols, the only thing "real" about them is that they are the firm boundary between the potentially reachable and the infinite void. The name itself conveys an important truth.

So clearly, it's the Axiom of Infinity where things really go wrong.

I find it bizarre that the author finds the use of the Axiom of Choice troubling here, but he is apparently okay with the requirement that each prisoner memorizes an infinite amount of information, and will also be able to look and see infinitely many prisoners.

Our intuition fails here only if we see this whole scenario as something plausible. But the basic requirements here are ridiculous: this puzzle has nothing to do with reality, and we have no reason to rely on our finitistic intuitions when thinking about it.

The prisoners are metaphorical. What this is really about is a mathematical (not practical) strategy whose result seems to be at odds with probability theory.

But if you remove the requirement that the algorithm be practical in any plausible Universe, there is no reason to reject it as countetintuitive.

Or hell, even correct! The result is basically a toy, metaphysically null. :)

Nothing infinite is practical or plausible in a finite universe.

It's a pet peeve of mine in general when mathematicians use imperative proofs with impossible steps, for similar reasons.

The world is indeed an "interesting" place when computation takes zero time, memory and storage are infinite, and you're allowed to give the reader step-by-step instructions that cannot be completed in any known universe.

But yeah, if you're willing to accept all that, CHECK OUT WHAT I'VE PROVED!!1!!! (And hand me that Nobel—I've earned it.)

This was a well-written and thought-provoking post. But to say that the axiom of choice is wrong (and to give no mathematical explanation!) is a bit silly. Reading through the comments, Terry Tao gives a very nice explanation about why the author's intuition for additivity of probabilities doesn't extend to non-measurable scenarios like this one.

[1]: http://cornellmath.wordpress.com/2007/09/13/the-axiom-of-cho...

For the author to say "The Axiom of Choice is Wrong" is simply shorthand for:

    We make choices as to what we use as axioms in
    mathematics.  Having made the choices, we then
    work to see what consequences we are forced to
    accept.  In the case of the Axiom of Choice, I
    find some of the consequences unacceptable. As
    a result I decide to believe that the Axiom of
    Choice is not true.

I think it's more arbitrary than that, quoting his comment:

> 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.

I think that on average people who deny the axiom of choice are the people who approach set theory and probability theory with intuition, and then rather than discard their intuition as being incorrect, they discard the axiom of choice as not lining up with their intuition (and then go on to do great math in other fields). But seeing as the author is an algebraic geometer, and published this post early in graduate school, I'm willing to bet he switched his ideology. I don't think AoC is something you can deny while actively working in his field, since you need to make tons of assumptions about algebraic closures to even get started.

So if you are willing to go full Grothendieck from the get-go you can dodge the need to have algebraic closures. Even making an algebraic closure doesn't require the axiom of choice, as you can adjoin the roots of all polynomials with coefficients in your field without invoking it.

The problem is that a lot of categorical constructions involve sets that get big. This isn't too much of a problem, but if you want to show that they are nonempty, choice comes in in a big way. Even worse, ZFC isn't enough: you need to play tricks to formalize category theory inside of set theory (or use proper classes instead).

If a mathematician would throw away his mathematical understandings in order to prove more results, I worry for his soul. A theorem in ZFC-but-not-ZF is much less interesting than a theorem in ZF, except as a topic in model theory.

Mathematical understanding quite often contradicts intuition. Part of becoming a mathematician is learning when to trust your intuition, and when you start your mathematical career your intuition is pretty unreliable. The thing about AoC and measure theory is that it's notorious for challenging your intuition after you think you've built up a lot of good intuition.

Also, from my experience the vast majority of mathematicians don't care whether their theorems are ZF-compliant or need ZFC, unless it's marketed to logicians or specifically deals with AoC in a certain field.

That's not true. Set theory is based on a lot of assumptions and it only consistent if you assume all of them are true.

I could argue if you start at infinity and count down you never reach zero as there are uncountable many infinite numbers. Worse there are uncountable many digits in an infinite number so any operation based on an infinite sequence never finishes. Making that argument and much of set theory meaningless.

PS: There are many Axioms which are chosen simply because it makes math more interesting. One of the more fun ones is to do set theory but allow for some undefined relationships. Aka x is in set A but it's undefined if it's in set B. Now quick draw a venn diagram.

Since you've edited your comment, I've deleted my reply, and here's a replacement ...

  > That's not true. Set theory is based on a lot of
  > assumptions and it only consistent if you assume
  > all of them are true.

All of mathematics is based on the idea of taking some axioms, and then seeing what follows. We usually use axioms that somehow align with our intuition or experience, and then see if things develop as we expect. Consistency is nothing to do with "Truth".

  > I could argue if you start at infinity and count
  > down you never reach zero as there are uncountable
  > many infinite numbers.

This doesn't make sense. To "start at infinity," what does it mean to count down at all? Certainly I can't interpret what you are saying in any meaningful way. Perhaps you could restate it in a more precise way.

  > Worse there are uncountable many digits in an
  > infinite number ...

There is no such thing as "an infinite number."

  > ... so any operation based on an infinite sequence
  > never finishes.

With care, operations on infinite sequences can be defined precisely and shown to be well-defined, so it's not clear what you're trying to say here.

  > Making that argument and much of set theory
  > meaningless.

  > PS: There are many Axioms which are chosen simply
  > because it makes math more interesting. One of the
  > more fun ones is to do set theory but allow for
  > some undefined relationships.

So you are creating a completely different math? Good, but not relevant here.

  > Aka ...

I don't think you mean "aka" - that means "Also known as ...". I suspect you mean something more like "For example" which is "E.g."

  > ... x is in set A but it's undefined if it's in
  > set B. Now quick draw a Venn diagram.

You haven't defined any of your terms, and you're doing something completely different from standard set theory. Sure, it might be fun, but it's more likely a toy problem in a toy theory. Can you give more precise definitions for what you're doing? Perhaps you should write it up and submit a link.

It's not that I am creating a different Math. Just point out that branches of math are not just exploring different topics, they often use different Axioms.

With care, operations on infinite sequences can be defined precisely

Sure, but let's suppose your describing a finite state machines. Now, they can't generally deal with infinity.

The Venn diagram bit is actually part of an old CS joke. "Everything is working perfectly, and the database returns NULL."

Edit: Bringing back to my first post, the "Axiom of Choice" is not the only place you can disagree.

The comment section on this blog post is spectacular. Many of the comments are by very accomplished mathematicians.

As with Banach-Tarski, I think the axiom of choice is being unfairly blamed for being a minor but easily identified (and therefore scapegoated) component of the paradox.

In this case as I understand it (someone correct me if I'm wrong) the solution is a nonstandard use of the word 'finite'. That is, if you ask just how many prisoners can get the answer wrong before the rest get it right, and whether the number is smaller or larger than a googol, a googolplex, BusyBeaver(googolplex) etc., the answer is always 'larger'. In other words it's a nonstandard integer, which is infinite for all purposes except arcane mathematical ones.

It's the mathematical equivalent of saying prisoners will start getting out when hell freezes over (which was intended to mean never) and then writing a future history whose starting point is 'The day hell froze over' (without saying this will happen at any finite time in our future).

Well, first of all, nothing rules out the first prisoner getting free--look more carefully at how the sequences work.

But your other objection is confused too. It's a theorem that the sum of any finite number of numbers is a finite number. But of course that sum might be bigger than a googleplex or any particular busy beaver number.

Thinking more: it seems like you've confused the claims: "there is a finite number n such that any sequence of prisoners can guarantee that they will only have n prisoners remaining" (false) with "for each sequence of prisoners, there is a finite number n such that they will only have n prisoners remaining" ( true).

> Well, first of all, nothing rules out the first prisoner getting free--look more carefully at how the sequences work.

Except that in the infinite colors case it's infinitely improbable.

> Thinking more: it seems like you've confused the claims: "there is a finite number n such that any sequence of prisoners can guarantee that they will only have n prisoners remaining" (false) with "for each sequence of prisoners, there is a finite number n such that they will only have n prisoners remaining" ( true).

The latter is the claim that I understood to be effectively false. Can you actually present an example sequence of prisoners for which there is a finite standard integer n? If so, what is the value of n in the example?

The first of the two claims I stated implies the second, but not vice versa.

I don't really understand what you mean by choosing an example sequence. Here's one: all prisoners have black hats. They all guess black. They all go home. Nothing in the problem rules that out, though nothing guarantees that the prisoners' strategy will get them this result. I believe there are actually an uncountable infinity of strategies that the prisoners could choose, with an infinite number of distinct choices that the prisoners could make for any given sequence that they get arranged in.

What the strategy guarantees is that starting with the first prisoner, some (zero or more) go home, and some (zero or more) remain captives, and then after some (finite, standard) number of prisoners, all the rest go home.

Right, that's a valid example case with n=0, though such cases are of measure zero in the same way the rational numbers are of measure zero in the real numbers.

Here's a counterexample: give all the prisoners white hats. Now the same strategy produces no prisoners going home.

In fact, if the population of hat distributions is restricted to {all black, all white}, this still suffices to show that there is no strategy that guarantees all prisoners will go home after some finite standard number.

  > ... if the population of hat distributions is
  > restricted to {all black, all white}, this still
  > suffices to show that there is no strategy that
  > guarantees all prisoners will go home ...

The strategy given in the submitted article is such that if all prisoners are given the same color hat then they will all go home, so I'm not sure what you're saying here.

I'm saying the strategy in the article does not actually do this at all, and it's easy to prove this by noting that a strategy that has them all going home with black hats has none of them going home with white hats.

I've worked through the strategy, and what you say seems simply to be false. As I work through the strategy I find that if they all have black hats the strategy has them all saying "Black", and if they all have white hats then the strategy has them all saying "White." I don't understand why you claim otherwise.

You're confused about what the strategies are. A strategy is not "all say black" or so on. The prisoners will make different choices depending on the infinite sequence of hats they see in front of them.

The thought experiment with infinite hats is interesting.

It sounds funny to ever say "the AoC is wrong," though, because axioms are things you get to choose as true or false. They are essentially subjective, and in practice are as "socially true" as they are commonly used. I guess the author is arguing that the more intuitively satisfying set of axioms excludes AoC.

I personally disagree, although I admit there's still room for debate because of compelling arguments on either side (most of which are appeals to intuition by the nature of the problem).

Here's a small counter-argument: Since we're appealing to intuition, consider that we're asking a countably infinite number of people to (a) see and reason based on seeing an infinite sequence in front of them; and (b) all memorize a specific function which is essentially from all the reals in [0,1] to a subset of [0,1], which we may think of as binary numbers with infinite expansions. (The intuitive point is clear without having to worry about 0.01111... being the same value as 0.1). This function is insanely weird and hard to describe succinctly; basically, it must be memorized. My intuition tells me that as soon as we expect agents to perform these feats, they are no longer humans and no longer Turing machines. Since this memorized function is so weird, they are even beyond some kind of infinite-time Turing machines with finite memories (or infinite-memory TMs with finite time). I think they are even beyond infinite-time Turing machines with countably-infinite memories, although I haven't proven this carefully.

In the long run, I suspect an alternative axiomitization (or possibly an elegant classification of set theory statements) will shed light on these problems, somewhat analogous to the way we now consider non-Euclidean geometry as interesting and "true" in its own universe that we mentally separate from the Euclidean plane.

[ps Not all comments about axioms are appeals to intuition. E.g., you can prove some are independent or dependent. But arguments along the lines of this post are appeals to intuition when used for/against AoC.]

What these expressions of formalism usually miss is that provably inconsistent/dependent/independant and all that mess actually are mathematical claims, and you're saying they're true or false. There are real attempts to get around that problem, but things get complicated here (http://plato.stanford.edu/entries/formalism-mathematics/).

Actually, that is where the argument goes wrong. You cannot have a function that maps the infinite numbers in [0,1] to a finite subset (which is the 'finite initial sequence'. So the argument collapses to the conclusion: after an infinite number of or incorrect guesses, everyone guesses correctly. Which is to say there is no such point where everyone starts to guess correctly.

Well, "wrong" itself can be subjective, if not interpreted in the "provably inconsistent" sense, and more in the "to take it as an axiom leads to problematic mathematical models".

It seems to me that in the paradox, although the Axiom of Choice plays a role, the bigger issue is how probability behaves in non-measurable sets. His intuition about how the laws of probability should work is not correct in this scenario.

Conceptually, it's not so different from the garden variety probability 101 issues taught in measurable sets - one can make a countably infinite number of picks from a segment in the real line, and the probability of picking any given number from that segment is still zero, despite an 'infinite' number of picks from a finite-measure segment.

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.

I'm no mathematician, but wouldn't this imply an infinite number of equivalence classes? Perhaps I'm missing something critical about the infinity of it, but I don't see how the prisoners could possibly enumerate every equivalence class.

There is a difference between countably and uncountably infinite. Countably infinite is when you have a one-to-one correspondance with the natural numbers. Uncountably infinite is when you have even more.

Note that one can come up with a proof that the number of equivalence classes should be uncountably infinite using the method of the Candor diagonalization argument.

I'm pretty sure the set of equivalence classes is uncountable, so it's not even enumerateable.

This is what I was thinking. Since there are only a countably infinite number of prisoners, you can't assign each one an equivalence class.

That's why this is about the https://en.wikipedia.org/wiki/Axiom_of_choice

I'm not clear on how the Axiom of Choice helps here. So you want a choice function, and you want it without enumerating every set. Great, the AoC gives you that. Now, you want to execute that choice function on every equivalence class. The AoC says nothing about that - you still need to be able to enumerate every set you would like to choose from.

Giving all the prisoners the choice function is by itself useless: once they observe the sequence, they can tell which equivalence class they're in. That's a tautology. For the suggested strategy to work, the prisoners need not only the choice function (which they get by the AoC), but an actual element from every set. It doesn't seem like the Axiom of Choice is relevant for that part.

I'm still not clear on what the issue is. Like you said, the prisoners observe the sequence and thus know which equivalence class they're in. The choice function (thanks to AC) gives them an "actual element" from that set.

I'm saying it's incorrect to suggest they can enumerate a representative example of every equivalence class simply because they have a choice function. Of course they can pick an element from any of the equivalence classes in bounded time (by the Axiom of Choice) but that says nothing about picking an element from every one of those sets in bounded time.

It doesn't, because of the finite number of entries. The scheme classifies sequences by an arbitrarily-large, but finite, prefix.

> I find this solution deeply troubling to the intuitive correctness of the axiom of choice.

There are so many unintuitive things about infinite sets that it's strange that it is the only the axiom of choice that the author finds unintuitive in this scenario. In order to use this "unintuitively" successful strategy, each prisoner has to memorize an uncountable[1] set of (countably) infinite sequences.

[1]: The set of all infinite binary sequences is uncountable, but the size of each equivalence class is only countable because the set of all finite binary sequences is countable. Hence there are an uncountable number of equivalence classes.

"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?" — Jerry Bona

I wonder if there's a 'Godwin's Law'-analogue for this quote [1]. It's one of the first things that I thought when I saw the article, and we're not the only ones: emilion thought of it, too (https://news.ycombinator.com/item?id=7992318).

[1] To be fair, Godwin's Law is not quite the right comparison: unlike references to Nazis, I think that this quote actually does contribute something to the discussion, by succinctly describing an interesting consequence of trying to decide if axioms are 'really true' (obvious / intuitive / whatever).

A mathematical axiom cannot be wrong, since by definition an axiom is always true. More accurately, a system of axioms can be vacuous, in the sense that it leads to conclusions that are logically impossible.

To ask "Is the axiom of choice true" requires that we agree on the meaning of 'truth', which is of course a very complicated philosophical question.

The author tries to make an appeal to our intuition by describing an example that (supposedly) takes place in the real world, but the real world is the realm of physics. In physics, truth derives from the result of experiments; whereas in mathematics, true statements are derived from a set of axioms.

Considering that an axiom is a rule that is made up by a person, and that there are an infinite number of consistent axiom systems, the question of the "truth" of a set of axioms has no meaning, unless we are actually asking, is a given axiom necessary for an accurate description of nature.

As far as I am aware there is no part of physics in which the axiom of choice plays any direct role.

A lot of people who talk about math on the internet seem to phrase it as this cold austere thing where it doesn't matter what anyone thinks because theorems are theorems and it's all just axioms in the end. And while we all sort of work with that understanding (somewhere, deep down there), in our waking hours "experiments" are the most efficient and insightful way to check our work and intuition. If we come up with some great beautiful theory and, assuming all the work was done correctly, we find a simple example for which our results contradict something we know to be true (or hold dear) then we have to look more closely at the starting assumptions, potentially rejecting them entirely.

These kinds of mathematical experiments definitely do not "take place" in the real world. Having an infinite number of people who can see infinitely far in front of them should have been a clue to that. It's just a way to expand mathematical jargon into an idea that is easy to keep in your head.

No, your argument is wrong.

The infinite number of prisoners find that it is impossible to express the sequence of all of the hat colors in their native language in a finite amount of time, which is a fundamental limit of formal languages. The language lacks the forms to express the state of reality.

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

Not possible. AC is invoked when you can't write down a rule, the purpose of the rule being to "consistently make an infinite number of choices in an unambiguous way, in a representation format that is equivalent to a Turing machine". So if you invoke AC, then you have to give something up, but you haven't given anything up. You're pretending you're in the representable, computable world.

Any prior choice of representation system can be thwarted by the actual reality. The information contained in the infinite sequence of hat colors can be so great that representations of it simply don't exist. Proof follows.

Let R be the set of real numbers. The equivalence classes described in the article can be extended to binary representations of real numbers, but this doesn't concern us and is a distraction. In this way, each real number would correspond to a different configuration of hat colors according to the values of the binary digits. If a number (like 1) has two binary representations, "0.1111..." and "1.0", then we pick the one that ends after finitely many places (1.0). All we care about is whether certain real numbers exist.

Let F be a formal proof system that corresponds with "your intuitive notion of a legitimate existence proof" (Here we take F to be the system of representation the prisoners are using to communicate, so the must all agree beforehand that F is the test that will be used to determine whether or not /a supposed existence and uniqueness proof of a particular real number/ is valid. These are prisoners after all: they might try to convince each other that certain things exist when they really don't exist). Because R is uncountable, and because there can only be countably many valid proofs in F, there exist elements of R whose existence and uniqueness cannot be proven by F.

Therefore F "is wrong" and the prisoners lack the ability to express the "state of the world" in which they find themselves.

You are importing misleading assumptions about what a strategy is, in this sort of mathematical game (basically, you're thinking of a strategy as a thing that concrete humans beings communicate to each other, rather than as a sort of mathematical object).

Of course, given that fact, I don't actually care about this particular thought experiment. Who cares that this abstract object exists? The hats and such are just a way of dramatizing the actual claim about the existence of a particular abstract object.

"Who cares that this abstract object exists?"

The form of this question is "Who cares about X?" so I would put this back to you, "who cares about answers to questions of the form, 'who cares about X?'?"

"The hats and such are just a way of dramatizing the actual claim about the existence of a particular abstract object."

The hats are about binary representations, and calling out the hat colors is about being able to compute binary representations. I don't know how to interpret the word "strategy" without implying "algorithm". The setup is that an interrogator sequentially queries the prisoners, and the prisoners have to come up with answers.

If you're criticizing the idea that computability should be injected into talk of what a "strategy" is, then we have to get to the heart of the problem: are the prisoners different people or are they all "manifestations of the same underlying strategy"? (I'm saying that the ability to make a prior agreement about an infinite amount of information is tantamount to the prisoners losing their individuality and being "merged" into a kind of consciousness that speaks for all of the prisoners simultaneously). If they are different people, then we have to be able to formalize somehow the concept that information available to one is not available to another.

So I turn the question around: how do you propose to model the fact that the prisoners do not have insight into the "raw visual sense data" of the other prisoners, yet the "raw auditory sense data" is shared?

Now, back to the original problem: the hats are an attempt to hide under the rug the very difficult concept of being able to evaluate/compute the binary digits of a particular real number given some mathematical description of it. The key word is "agree". The prisoners have to "agree" on something, and in this context, we aren't sure what that means, but I'm taking it to mean that there is a finite alphabet they're using to communicate, they can only communicate finite sentences, and other similar practical assumptions...

Since there are uncountably many real numbers and only countably many computable numbers, there are (in ZFC) plenty of real numbers whose existence and uniqueness have been proven, but which are not computable. This is going to turn out to be an insurmountable operational obstacle for the prisoners.

For example any Chaitin constant will do. I've added a comment to the original blog post explaining the details.

Neither computability nor sense data have any relevance. The prisoners are a literary device. As far as formalizing the lack of information, the elements of each equivalence class chosen need not depend on the particular arrangement of the prisoners--that is more than enough.

Again, you're thinking of this far too literally.

I'm claiming that there is a very serious flaw in the argument, and these remarks do not address the flaw I have brought up.

Would it help if I pointed out that the original poster and most of the commentators here are well aware that no human, or indeed, no finite thinking being, could do what the prisoners do? Because you're not telling us things we don't know.

I take another thing from the Banarch and Tarsky paradox and the prisoner story: infinite sets don't exist in reality and have some features that thus seem strange

I'd put it slightly differently: Any theorem that required the axiom of choice for proof has no relevance for physical reality.

So you're saying it's not constructive to talk about theorems that require the axiom of choice for proof? (ducks)

All joking aside, I liked your definition. Thanks!

Colin, is this submitted for disagreement, or because you think the author is really on to something?

It's submitted because it's interesting. My point of view is that AC is neither "True" nor "False" - maths at this level isn't really about "Truth".

There are choices to make, and we make choices that are convenient and useful. The question with AC is that to make the choice that it's "true" is to allow things that seem intuitively wrong, but similarly, making the choice that AC is "false" is to prevent things that intuitively seem like they should be allowed.

This article is explaining clearly one of the consequences of choosing to accept the AC, and pointing out that, in the opinion of the author, the consequences are just too much to permit.

The axiom of choice is very interesting. It’s independent of the other (more intuitive axioms), so you can do math with it and with it’s negation. It’s useful to prove some “intuitive” results and some “paradox”, so it’s polemic.

The canonical “paradox” is the Banach–Tarski paradox, but it’s a very strange result and it can be “ignored” as a weird corner case.

I didn’t know this “paradox”. This “paradox” looks more innocent. It’s easy to explain. Most of the steps are easy and intuitive. I have to read this five times to be sure that this has no obvious error, and I’m a mathematician.

This is not a ground braking result that will change math forever, it’s just another example of the polemic state of the axiom of choice. But the article is interesting and I’ll remember this example because it can be useful to discuss the topic with the students.

ColinWright, you know a lot about math, but this article is misleading and confused. Why did you post it? HN has a history of confused discussions of infinity; I would request that experts share illuminating articles, not confusing ones.

judk,

In what way is it misleading? This is a well-known puzzle in some circles, the solution is accepted by those I work with, and this is the clearest write-up I've seen. Can you clarify why you think the article is "confused". To me it seems perfectly clear.

It's not wrong, but it would surprise me if anyone ever had to appeal to it when reasoning about a useful model of a specific real-world situation.

I would say it is 'wrong' in the sense that there is a very different kind of 'reality' of the countable number of mathematical objects which people can name with a countable number of symbols, vs the 'real' numbers which can only be specified in the aggregate. The 'real' numbers ought to be called the 'phony' numbers or something like that.

Terence Tao's comment is very much worth reading. He addresses "is wrong". (It's not that simple.) Our intuition about probability fails us because it involves non-measurable sets, for which probabilities can't be properly assigned. Then, the intuition that "each prisoner has a 50% chance of being right" (based on a "rigid motion" argument in (Z_2)^N, or the space of sequences of {0, 1}) fails us because we don't have a meaningful probability. (We're conditioning on an equivalence class that is similar to a Vitali set; it can neither be assigned a zero nor positive measure, so it's non-measurable.)

The no information is passing argument in the infinite case is wrong. After all, they all agree on a strategy, which is information they share.

The author means: they do not communicate after the game begins (except in people seeing the hats of those after them in line).

I know what the author means. He is basing his intuition on this. Which is wrong, because they DO share information, as strategy is played out DURING the game, although it has been agreed upon beforehand.

If they "pass" information, then that means that if player B is after player A in line, then player B somehow gets information about the color of player A's hat. But this is demonstrably false, for the two equivalence classes are the same regardless of whether player A's hat changes colors.

I.e. information is not passed during the game from one player to another. This is different than sharing information ahead of time, and is unrelated to the author's intuition (which is confounded by the fact that the strategy is not measurable).

But that kind of information isn't information about that particular configuration of prisoners. That's the kind of information the author is talking about.

Reply on news.ycombinator.com