13 ms·

The Axiom of Choice Is Wrong (2007)

110 points by jaybosamiya 10y ago

Arnavion 10y ago
Mathologer recently did a video on the puzzles mentioned in this article: https://www.youtube.com/watch?v=aDOP0XynAzA https://www.youtube.com/watch?v=aDOP0XynAzA
CJefferson 10y ago
As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Other's view may differ. Here is an interesting thing I've never seen anyone write down (I should do it myself) -- we don't need uncountable infinities. * How many natural numbers are there? Countable * How many rational numbers are there? Countable * How many numbers are solution to a polynomial? Countable * How many numbers are the output of any turing machine (including programs that run forever, producing an infinite decimal)? Countable * How many numbers are the answer to any maths problem anyone can write down (where the problem has at most a countable number of answers)? Countable. If the set of all numbers any can express in any sensible way, and the solution to any problem any could ever have, is countable, why do we need the other uncountables?
- kirrent 10y ago
  How many real numbers are there?
  - chriswarbo 10y ago
    > How many real numbers are there? 2^ℵ₀ Which I just managed to encode using a finite number of symbols :)
- baddox 10y ago
  This is discussed heavily in topics around constructing the reals and constructivism. Wikipedia has a short section about using the computables instead of the reals: https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number It is pretty fascinating to think about: that almost all real numbers are not computable ("almost all" of course meaning "all but a countable set"). And yet you almost certainly will never run into a noncomputable real except in computer science when you're specifically defining one to illustrate something about computability (like Chaitin's constant).
  - IsaacL 10y ago
    Are there any good books on this topic?
    - andybak 10y ago
      Yes. An uncountable number are in the Library of Babel. (actually - I'm guessing there's actually a countable number in the Library of Babel but it didn't read quite so amusingly that way. In any case - all the ones I flicked through were trash.) Edit - The Library of Babel is actually finite isn't it? Fixed alphabet and fixed book length? It's a while since I read it.
      - disconcision 10y ago
        the number of possible distinct books is finite but it's unknown if the library itself is finite. iirc it ended with the narrator speculating that, although the books themselves are devoid of meaning, perhaps the overall structure of the library is ordered, i.e. the same finite pattern of books repeats endlessly in infinite space.
      - sn41 10y ago
        The Library of Babel is finite if the books are unique. Interestingly, Borges does mention that one of the books in the library must be an index of the other books. This is similar to the notion of a universal computably enumerable language. However, I doubt that Borges' claim is accurate. If the set of programs is finite, then I think there cannot be a comprehensive index of all programs. A finite set is a regular language, and there is no universal regular language in the set of regular languages.
    - philipov 10y ago
      I recommend Gregory Chaitin's book intended for a popular audience. It is short, and a good introduction to algorithmic information theory for non-mathematicians. Chaitin's Constant (Omega) is a non-computable number that is equivalent to the halting problem. [0]: https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/1400077974 https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/14...
- im3w1l 10y ago
  > As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Is a hammer true or false? I don't know, but it's good for hitting nails.
  - kmm 10y ago
    Yeah, a hammer is definitely useful, but I think the point he's trying to make is that the notion of uncountable sets isn't very useful outside of things like set theory.
- zodiac 10y ago
  How many sets of natural numbers are there? An uncountable number. Of course, you could throw out some axioms so that you create an axiom system in which I can't define such a thing as "a subset of the natural numbers", but such a world doesn't feel "real" (in a platonic sense) to me.
  - pherq 10y ago
    In this case, what you "throw out" are uncomputable (or non-recursive, depending on terminology you like) sets; i.e. sets for which the membership function is not decidable. Yes, there are an uncountable number of these sets, but they can't be defined in any useful way.
    - baddox 10y ago
      Indeed, if you consider a real number to just be a decimal representation formed by concatenating all the natural numbers in a set (not at all a rigourous construction of the reals, but hopefully sufficient for this argument), the equivalence is clear.
      - zodiac 10y ago
        I've always found dedekinds construction (where sqrt 2 is represented by the set of rationals {x in Q : x^2 < 2}) to be a nice natural place where powersets of countable infinite sets come up (in addition to being a great way to construct R)
      - pherq 10y ago
        I tend to prefer considering the sets to encode bitstrings (encode a set as sum(2 ^ -x for x in X)), but yes the equivalence between computable sets and computable numbers is straightforward.
    - zodiac 10y ago
      For sure - as I understand it in most formulations you throw out lots of sets but keep all the finite sets of natural numbers, the set of even numbers, the set of prime numbers etc One thing I never found satisfactory is that any axiom system like this has to define things in terms of decidability etc, so it's "more verbose" (or less axiomlike) than ZFC
- rw 10y ago
  You could have answered all of your questions with "finitely many", because, after all, we can each only perform a finite number of actions in the world. In general, the infinite hierarchy of infinite sets "exists" because we can define it.
- sn41 10y ago
  One of the great theorems in logic is the Lowenheim-Skolem theorem [1], which says that if a countable first-order model has an infinite model, then there is a countably infinite model. For example, there is a countably infinite model for the theory of reals. I have heard that Skolem [2] used this theorem as a basis for his belief that uncountable sets can be avoided, and countably infinite sets suffice. [1] https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_... [2] http://www-gap.dcs.st-and.ac.uk/history/Biographies/Skolem.html http://www-gap.dcs.st-and.ac.uk/history/Biographies/Skolem.h...
- joatmon-snoo 10y ago
  the solution to any problem any could ever have That's a pretty tall claim to make. Once upon a time people thought irrationals and transcendentals like pi and e didn't even exist. It wasn't until the past century that people realized abstract algebra and its ilk had practical applications. The same goes for chaos theory and fractals as well. Admittedly it's hard for me to envision a world where notions of countability will ever have real-world uses, but I also consider calling it "a fun maths game" rather reductionist, and frankly, poor taste (especially if you're going to say something like "intrinsic truth or falsity"). Give him three pence, since he must make gain out of what he learns.
  - CJefferson 10y ago
    The reason I say "the solution to any problem anyone could ever make" is a maths argument! If you can write down a problem as a finite string, then the set of all problems must be countable.
- heinrichhartman 10y ago
  Good luck developing analysis with only countable infinities. Limits will take you out of the realm of countable spaces. Most of your derivatives and integrals won't exists, if you force them to take values in countable sets.
  - CJefferson 10y ago
    Why not, can you give an example. Most of the "common" derivatives and integrals I can think of would work just fine, unless I'm missing something obvious?
    - kutkloon7 10y ago
      No, for example the integral sqrt(1 - x^2) from x = 0 to x = 1. Or any other integral over a circle/sphere for that matter.
      - CJefferson 10y ago
        Nothing wrong with that, it's still a computable number -- I'm not suggesting doing away with all real numbers, just the non-computable ones. I don't claim to have thought through every detail, but having now gone and done some reading, this seems fine in the world of constructivism, which only requires computable numbers (and therefore only countable infinities of numbers)
    - twic 10y ago
      Are the computable numbers continuous? If not, is that a problem for analysis? If so, can you construct some computable analogue of continuity which is sufficient?
    - heinrichhartman 10y ago
      - Every real number can be represented as a limit of rational numbers, which are uncountable. - So for every countable subset you can find a (Cauchy) sequence of rationals that does not converge. Hence, you loose one of the most important tools in Analyisis (Cauchy criterium for convergence). You can still work with the remaining set, but formulating and proving theorems, is going to be much harder. - If integrals over f and g exists, then the integral over f * g does not need to exists. - E.g. Integrals over bounded regions will not always exists. - Theorem of Montonic convergence fails - Function spaces will not be complete (L2). A nice theory of constructible "periods" has been developed by Kontsevich and Zagier (http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf) but it relies heavily on the existing body of Analysis being available.
- heinrichhartman 10y ago
  Are you aware of the concept of periods ? This is a quite fascinating, countable, ring of numbers, that captures all of the above: Kontsevich and Zagier introduce and develop this concept quite far: http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf
  - CJefferson 10y ago
    No, but this looks interesting. Thanks for the reference!
  - wolfgke 10y ago
    Just to give a little bit more attention to this link: Wikipedia link to one of the authors: > https://en.wikipedia.org/wiki/Maxim_Kontsevich https://en.wikipedia.org/wiki/Maxim_Kontsevich Proof that one of the authors really is no other "M. Kontsevich" (I openly admit that I wanted to be sure since I associate Maxim Kontsevich mostly with other mathematical areas): > http://www.ihes.fr/~maxim/publicationsanglais.html http://www.ihes.fr/~maxim/publicationsanglais.html
- ArkyBeagle 10y ago
  Euler held that infinities in general were nothing more than a way of reasoning about limits.
- yequalsx 10y ago
  The are uncountably many polynomial over the reals. There are uncountably many functions from N to N. The premise of your question is incorrect.
  - waqf 10y ago
    OP never claimed there were countably many functions from N to N, only that there are countably many Turing machines which is true. By "polynomials" OP doesn't mean polynomials over the reals but over, for example, the rationals – the point is that there's a countable subset of R that's algebraically closed.
    - yequalsx 10y ago
      I know those things. OP does not claim that the set of functions from N to N is uncountable. One gives up things if only countable things are considered. For instance those things that I mentioned.
      - waqf 10y ago
        Oh, I see, you're addressing the "we don't need uncountable sets" statement by giving examples of intuitively obvious things which are uncountable. But I think OP's claim is that we don't "need" those things because we could do mathematics with the set of Turing machines instead of the set of functions, etc.
        yequalsx 10y ago
        Yes, but can Turing machines do enough mathematics? The second order Peano Axioms are categorical and the first order axioms are not. The Incompleteness Theorem tells us that there are statements that are true in the standard model of N that are not provable by a Turing Machine.
- lmm 10y ago
  No mathematical object exists exactly in the real world. E.g. you will never see a physically perfect square. The whole point of mathematics is that it's a simplified model of reality that's easier to work with for some purposes, and that's as true of uncountable infinities as it is of anything else in maths.
- imh 10y ago
  Better yet, just consider all deduction as "a fun language game," rather than having any intrinsic truth or falsity. If you assume a whole bunch of stuff and the axiom of choice, you can get these interesting things over here. If you assume that same bunch of stuff but not the axiom of choice, you get this other interesting stuff over there. Which assumptions to use at any given time just depend on what you're trying to do. If I'm trying to count my sheep, I just need enough axioms to get me addition of natural numbers. If I'm trying to model some mechanical trajectory, maybe I ought to grab some reals. Got circles? Adding imaginary numbers to the reals makes that easy, even though imaginary numbers are totally "fake." Using sentences that might not make sense? Maybe avoiding the excluded middle is a good idea.
- paulddraper 10y ago
  > If the set of all numbers any can express in any sensible way, and the solution to any problem any could ever have is countable This is trivially true, since there are only countable (finite) expressions and problems. > why do we need the other uncountables? You can't do calculus without reals. http://math.stackexchange.com/questions/1880741/why-cant-calculus-be-done-on-the-rational-numbers http://math.stackexchange.com/questions/1880741/why-cant-cal... And calculus is pretty important (e.g. for any branch of physics ever).
im3w1l 10y ago
I'd assume that even if in every case the number of incorrect guesses is finite, the expected number of people that fail to guess their color is infinite. Am I right about this?
- baddox 10y ago
  Im not sure what you mean by "expected number." Do you mean if you try to guess how many inmates the warden has managed to guarantee will fail? Per the article, the warden can guarantee that an "arbitrarily large finite number of them" will fail. But it's still always finite despite being unbounded. If you want to predict a lower bound on the number of failures the warden has guaranteed, you just have to guess a larger natural number than the warden. :)
  - im3w1l 10y ago
    I mean if the warden picks a sequence randomly.
- daxfohl 10y ago
  Interesting observation! Yes, I think reduced to its essence, it boils down to: the expected value of "a finite number" is infinity. Which is strange in itself. So you end up with a sequence that converges to 100%, but that convergence never starts, but it certainly happens eventually. I guess a similar, less verbose thing would be "pick a random rational in (0, 1)". In decimal representation it'll repeat after "a finite number" of random digits, but "a finite number" again is expected to be infinity. So is a random rational really rational? Someone more educated on set theory will have to comment.
- waqf 10y ago
  If you take any finite subset of N prisoners, it's easy to see that they won't do better than chance, so the expectation is for N/2 of them to guess wrongly. Since N can be arbitrarily large, your intuition is correct.
mrob 10y ago
Infinities aren't real, so you shouldn't be surprised if unrealistic things happen when you invoke infinities. That you can duplicate a sphere by cutting it into a finite number of pieces and reassembling it is a "fact" in the same sense as "Luke Skywalker destroyed the Death Star". It might be interesting and culturally important, but it's talking about fictional entities. Both spheres and arbitrarily detailed pieces of spheres only exist in the imaginations of mathematicians. The Axiom of Choice is obviously true, and the fact that it lets you invent weird sounding stories from weird components is no evidence against it. Don't confuse mathematical tools with reality.
- zodiac 10y ago
  There are a small number of people who think it's obviously false! (I'm not one of them). And a larger number who think it's not obviously true nor obviously false.
  - pherq 10y ago
    There's the old joke that the axiom of choice is obviously true, the well-ordering theorem is obviously false, and Zorn's lemma is too complicated to say.
- llamaz 10y ago
  Mathematics is formalised is to avoid this sort of philosophizing. I used to think, for example, that the dirac delta function was mathematical fiction - a mathematical "hack". But then in an engineering control systems class, we did an experiment where we used a step function to approximate a dirac delta function. I could see the results both on the computer screen and in physical reality through a mass-spring-damper system. From that moment on I saw the dirac delta function in the same way that I see cosine/sine: The reason it works in math is because it has a basis in physical reality. The lesson to be learned here, is that you don't know in advance whether something is obvious or not. To me, it doesn't make sense to decide whether the axiom of choice can be justified by looking at the axiom itself. You have to look at where it's used and required, and whether the proofs convey something that matches your physical intuition.
fmap 10y ago
The problem solution in the article uses the axiom of choice to construct a "nonprincipal ultrafilter" on the natural numbers. This is actually weaker than the full axiom of choice, but you can still show that no such object is computable. It's a nice exercise to show that with the same assumptions as in the article you can decide the halting problem. (hint: consider the boolean sequence where the nth element is true iff the Turing machine halts within n steps) As for the axiom of choice, the real problem is trying to claim that it is right or wrong in the first place. Mathematics as a whole has never quite recovered from the failure of Hilbert's program... The bottom line is that there is no complete and consistent notion of "truth". There is no objective mathematical reality, because it cannot include a statements about its own consistency (and it's easy to translate this into "statements about certain hard problems", by exactly the same process we use to show that some problems are NP complete by reduction from another NP complete problem). On the other hand, this is not actually detrimental to mathematical practice. It only means that you have a lot more freedom in modeling your problem domain. For instance, it turns out that set theory with the axiom of choice is a horrible place to do probability theory in (non-measurable sets and functions are a direct consequence, and you have to go to a lot of trouble to exclude them everywhere). If ZFC was part of some objective mathematical reality, then this would in some sense be unavoidable, since ultimately you want to make statements describing reality. On the other hand, once we realize that this assumption is just plainly false, we can start looking for more refined models.
- cygx 10y ago
  There is no objective mathematical reality, because it cannot include a statements about its own consistency I'm assuming we're talking about Gödel's incompleteness theorems? Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized?
  - candiodari 10y ago
    > Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized? No they don't. Real space doesn't appear to be infinite, and Zn is not subject to Godel's incompleteness theorem. If you drop the requirement of infinite numbers and "recursive" infinites (e.g. real numbers), as reality appears to do, there is no problem.
Ceezy 10y ago
YOUR MATH ARE WRONG If prisonners follow the last strategy, the dude number 0 as a probability of finding his hat of 50% and the dude number 1 000 000 50%. Why? because nobody knows how many times they will lose. Those who are sure to win are those close to infinity... This have nothing to do with Axiom of Choice. But only because almost all the mass of your distribution is near infinty. With or without Axiom of Choice this things exist.
twic 10y ago
The axiom of choice always seemed intuitively wrong to me. You can't just take a set and arbitrarily pick something out of it! Making a choice requires information, and you can't pluck information out of thin air at whim; applying the axiom amounts to creating information out of nothing. I suppose this is because i'm not a mathematician, but have a natural sciences background. In the physical universe, memorably, "the law that entropy always increases holds, I think, the supreme position among the laws of Nature" [1], and so we do not accept the mathematicians' fake information. More specifically related to choice from a set, Curie's principle that "when certain causes produce certain effects, it is the elements of symmetry of the causes that may be found in the effects produced" [2] forbids something uniform from becoming arbitrarily non-uniform; whenever that appears to happen, there must be some hidden cause which already carries that non-uniformity. [1] https://en.wikipedia.org/wiki/Second_law_of_thermodynamics https://en.wikipedia.org/wiki/Second_law_of_thermodynamics [2] https://hal.archives-ouvertes.fr/jpa-00239814 https://hal.archives-ouvertes.fr/jpa-00239814 - "Enfin, lorsque certaines causes produisent certains effets, les éléments de symétrie des causes doivent se retrouver dans les effets produits."; please excuse the not-so-literal translation
- hackinthebochs 10y ago
  > You can't just take a set and arbitrarily pick something out of it! Making a choice requires information True, but how can you "have a set", i.e. reference a set in any way, without having information about that set? There seems to be a requirement of some bare minimum of information enough to specify the set, and so enough to pick out a member of the set.
  - twic 10y ago
    Having enough information to specify the set isn't enough to pick out one particular member. For example, if i say "the colours teal, maroon, and taupe", you have enough information to know what's in the set, but no extra information that would let you pick one element out of it.
    - mcphage 10y ago
rtpg 10y ago
I have a vague understanding of the Axiom of Choice, but I've always had trouble with some of the analogies people use to explain it. Two things that have bugged me for a while: - why is it usually talked about only in the context of infinite sets? Is there a general trick to building a choice function if all you have are finite sets? - There's a saying like "you can choose from an infinite set of shoes, but not from an infinite set of socks without AC". Why exactly?
- petteris 10y ago
  The axiom of choice is about making an infinite number of arbitrary choices simultaneously. If you can specify some rule, this rule is just one choice. Finitely many choices are always fine and don't need the axiom of choice. If you have a finite set, you can number its elements and make rules by saying "let's take the element with the smallest number having this or that property", so you don't need the axiom of choice when dealing with finite sets. The point of Russell's shoes versus socks analogy is that shoes are distinguishable while socks aren't: To choose one shoe from each of an infinite set of pairs of shoes, you can always choose the left shoe, or specify some pattern (so you don't need the axiom of choice), whereas when choosing socks, you have to make an arbitrary choice to select one from each pair (so you do need the axiom of choice).
- kmill 10y ago
  The main problem is taking a statement about a set ("for every A in X, A is nonempty") to the existence of a set ("there is a function f [which in ZFC is considered to be a set] such that for all A in X, f(A) is in A"). If you are able to create a statement P(A,a) that for every A in X is true for exactly one a in A, then it follows from the axiom of replacement that there is such a choice function. The axiom of choice seems to say that it suffices to make a statement P(A,a) that for every A in X is true for at least one a in A. The axiom of replacement helps actually construct such a choice function, whereas the axiom of choice just asserts one ought to exist since "at least one" seems good enough. To use the axiom of replacement, you have to use some structure for A. For instance, with the finite set example, it might be that each A is not just a set, but a set which is in bijective correspondence with a natural number, where there is a distinguished bijection. Then, you could just say that P(A,a) is true exactly when a is the image of 0 under the bijection.
ramblenode 10y ago
What an interesting thought experiment. Lying in bed last night, the best I could come up with (before seeing the optimal solution this morning) was an average of 83 with a minimum of 66. The prisoners agree that every third prisoner, beginning with the first, uses "white" to convey that the subsequent two prisoners are wearing the same color and "black" to convey different colors. Since the second prisoner in each triple knows the color of the third, he can deduce his own color, leaving the third prisoner to also deduce his own color. And of course there's a 50/50 chance the sacrificial first prisoner in the triple still gets out. I suppose this could be improved upon by later prisoners having a longer memory, but I've already seen the optimal solution. ;) Interested to hear others' attempts.
eru 10y ago
You can generalize their prisoner example to using a countable number of colours, not just two or finite.
Grue3 10y ago
There are many problems with this puzzle that go against the intuition. - the number of prisoners is infinite, so they will never finish answering the question. At any point in time, only a finite number of prisoners will be freed. - a single prisoner must process an infinite amount of information to reach the decision. In fact, by observing only a finite number of hats he cannot possibly choose the answer. - the number of equivalence classes is uncountable. Not even a countably infinite number of prisoners can possibly have enough time to pick out a single element from every equivalence class.
- Tloewald 10y ago
  As soon as you start treating the axiom of choice as a superpower for a conscious being you are in conceptual la la land. How do I guess the color of my hat if there's an uncountable number of possible colors? Doesn't that mean that communicating the value of that color involves transmitting an infinite amount of informtion?
  - waqf 10y ago
    Quick, tell me your favourite number between 0 and 1. How did you do that? Weren't there an uncountable number of possible numbers? Ah, you may say, but I obviously wasn't going to choose one with an infinite information content, so all but countably many possible numbers had probability 0. Which is true. But in fact it's true that whenever you have a probability measure on an uncountable space then all but countably many elements have probability 0, so that escape clause applies equally well to the hat colours.
    - TheCoelacanth 10y ago
      But the axiom of choice applies to all sets, not just ones that you can easily choose a number from. For instance, what is your favorite non-computable number between 0 and 1?
      - red75prime 10y ago
        Inverse of Kolmogorov complexity of thirteenth bit-string with uncomputable Kolmogorov complexity, of course.
pron 10y ago
So what bothered the author was the axiom of choice and not the part where a prisoner with a finite brain needs to memorize an infinite amount of information and then perform a computation on infinite information to compute the equivalence class? For this strategy to work you must assume that the prisoners are capable of carrying out noncomputable computations, too. That's the more problematic assumption.
bananabiscuit 10y ago
This problem has exactly the wrong setup for using th the axiom of choice: First, the axiom of choice requires that you have a countable number of sets that you are choosing elements from, but there are undoubtably many of the equivalence classes that he described [0]. So the author is using something stronger than the axiom of choice to arrive at his paradox. Second, if you actually are in a situation where you have to choose from a countably infinite number of sets, you only need the axiom of choice if there is no selection rule for choosing an element available. In this case there is a rule you can use, namely: select the sequence in which the "finite prefix" is all zeros. [0]: the number of equivalence classes is uncountable because there is a 1:1 relation between the equivelance class and an the infinite sequence that is common to all the sequences in the equivalence class once theirs uncommon prefixes have been truncated.
- n4r9 10y ago
  > the axiom of choice requires that you have a countable number of sets that you are choosing elements from You're referring to the "axiom of countable choice", which is a different axiom. The Wikipedia entry for the axiom of choice makes it clear that the number of sets can be uncountable. > select the sequence in which the "finite prefix" is all zeros This doesn't really make sense as a selection rule. The size of the prefix can vary between pairs of members from the same equivalence class.
- yequalsx 10y ago
  The axiom of choice applies to index sets of arbitrary size. Indeed there is an axiom of countable choice for those who don't like the axiom of choice.
- TimonKnigge 10y ago
  > First, the axiom of voice requires that you have a countable number of sets that you are choosing elements from, but there are undoubtably many of the equivalence classes that he described [0]. No it does not? The axiom of countable choice [0] is a strictly weaker axiom. [0] https://en.wikipedia.org/wiki/Axiom_of_countable_choice https://en.wikipedia.org/wiki/Axiom_of_countable_choice
wolfgke 10y ago
An interesting alternative to the axiom of choice (AC) is the axiom of determinacy (AD): https://en.wikipedia.org/w/index.php?title=Axiom_of_determinacy&oldid=738341699 https://en.wikipedia.org/w/index.php?title=Axiom_of_determin...
jiiam 10y ago
In the comments to the linked article there's a nice explanation by Terry Tao of why this is not so spectacular, in the sense that our intuition with probabilities here relies on Fubini's theorem, which in this case do not apply due to measure theoretic obstacles. But, again, our intuition of probability fails with much easier examples. Here follows Terence Tao's comment (refer to the original to have proper rendering of math symbols): "This paradox is actually very similar to Banach-Tarski, but involves a violation of additivity of probability rather than additivity of volume. Consider the case of a finite number N of prisoners, with each hat being assigned independently at random. Your intuition in this case is correct: each prisoner has only a 50% chance of going free. If we sum this probability over all the prisoners and use Fubini’s theorem, we conclude that the expected number of prisoners that go free is N/2. So we cannot pull off a trick of the sort described above. If we have an infinite number of prisoners, with the hats assigned randomly (thus, we are working on the Bernoulli space {\Bbb Z}_2^{\Bbb N}), and one uses the strategy coming from the axiom of choice, then the event E_j that the j^th prisoner does not go free is not measurable, but formally has probability 1/2 in the sense that E_j and its translate E_j + e_j partition {\Bbb Z}_2^{\Bbb N} where e_j is the j^th basis element, or in more prosaic language, if the j^th prisoner’s hat gets switched, this flips whether the prisoner gets to go free or not. The “paradox” is the fact that while the E_j all seem to have probability 1/2, each element of the event space lies in only finitely many of the E_j. This can be seen to violate Fubini’s theorem – if the E_j are all measurable. Of course, the E_j are not measurable, and so one’s intuition on probability should not be trusted here. There is a way to rephrase the paradox in which the axiom of choice is eliminated, and the difficulty is then shifted to the construction of product measure. Suppose the warden can only assign a finite number of black hats, but is otherwise unconstrained. The warden therefore picks a configuration “uniformly at random” among all the configurations with finitely many black hats (I’ll come back to this later). Then, one can again argue that each prisoner has only a 50% chance of guessing his or her own hat correctly, even if the prisoner gets to see all other hats, since both remaining configurations are possible and thus “equally likely”. But, of course, if everybody guesses white, then all but finitely many go free. Here, the difficulty is that the group \lim_{n \to \infty} {\Bbb Z}_2^n is not compact and so does not support a normalised Haar measure. (The problem here is similar to the two envelopes problem, which is again caused by a lack of a normalised Haar measure.)"
EGreg 10y ago
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 terms 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.
IshKebab 10y ago
How can an axiom be 'wrong'?
- thethirdone 10y ago
  Suppose, I choose "This sentence is false" as an axiom. having it as an axiom allows me to reason from its content that it is false and thus I have a contradiction. In this way at least, that axiom is "wrong".
  - monochromatic 10y ago
    But the Axiom of Choice doesn't lead to contradictions (unless Zermelo Fraenkel set theory itself contains contradictions). The Axiom of Choice just leads to some non-intuitive results.
- dvt 10y ago
  An axiom is simply a statement that is defined as being true. Often times on grounds of being self-evident. For example, one of Euler's axioms is "Things that are equal to the same thing are also equal to one another". Whereas Euler's may seem pretty tame, the Axiom of Choice is not. That's why some people think it might be wrong.
  - IshKebab 10y ago
    Exactly, so unless it leads to contradictions it may be weird and unintuitive but it's not wrong.
deleted 10y ago
[deleted]
alsadi 10y ago
> Sure, this is based primarily on my intuition for finite things and a naive hope that they should extend to infinities. but it's known that it does not extend!
DigitalPhysics 10y ago
If you're interested in the Axiom of Choice, Godel, finitism, pseudo-randomness, complexity, information, and other foundational topics, check out the indie film "Digital Physics" on iTunes, Amazon, or Vimeo. Free packs of trading cards (with gum!) are available too! Check the website.

110 points by jaybosamiya 10y ago

Mathologer recently did a video on the puzzles mentioned in this article: https://www.youtube.com/watch?v=aDOP0XynAzA https://www.youtube.com/watch?v=aDOP0XynAzA

CJefferson 10y ago

As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Other's view may differ. Here is an interesting thing I've never seen anyone write down (I should do it myself) -- we don't need uncountable infinities. * How many natural numbers are there? Countable * How many rational numbers are there? Countable * How many numbers are solution to a polynomial? Countable * How many numbers are the output of any turing machine (including programs that run forever, producing an infinite decimal)? Countable * How many numbers are the answer to any maths problem anyone can write down (where the problem has at most a countable number of answers)? Countable. If the set of all numbers any can express in any sensible way, and the solution to any problem any could ever have, is countable, why do we need the other uncountables?

kirrent 10y ago
How many real numbers are there?
- chriswarbo 10y ago
  > How many real numbers are there? 2^ℵ₀ Which I just managed to encode using a finite number of symbols :)
baddox 10y ago
This is discussed heavily in topics around constructing the reals and constructivism. Wikipedia has a short section about using the computables instead of the reals: https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number It is pretty fascinating to think about: that almost all real numbers are not computable ("almost all" of course meaning "all but a countable set"). And yet you almost certainly will never run into a noncomputable real except in computer science when you're specifically defining one to illustrate something about computability (like Chaitin's constant).
- IsaacL 10y ago
  Are there any good books on this topic?
  - andybak 10y ago
    Yes. An uncountable number are in the Library of Babel. (actually - I'm guessing there's actually a countable number in the Library of Babel but it didn't read quite so amusingly that way. In any case - all the ones I flicked through were trash.) Edit - The Library of Babel is actually finite isn't it? Fixed alphabet and fixed book length? It's a while since I read it.
    - disconcision 10y ago
      the number of possible distinct books is finite but it's unknown if the library itself is finite. iirc it ended with the narrator speculating that, although the books themselves are devoid of meaning, perhaps the overall structure of the library is ordered, i.e. the same finite pattern of books repeats endlessly in infinite space.
    - sn41 10y ago
      The Library of Babel is finite if the books are unique. Interestingly, Borges does mention that one of the books in the library must be an index of the other books. This is similar to the notion of a universal computably enumerable language. However, I doubt that Borges' claim is accurate. If the set of programs is finite, then I think there cannot be a comprehensive index of all programs. A finite set is a regular language, and there is no universal regular language in the set of regular languages.
  - philipov 10y ago
    I recommend Gregory Chaitin's book intended for a popular audience. It is short, and a good introduction to algorithmic information theory for non-mathematicians. Chaitin's Constant (Omega) is a non-computable number that is equivalent to the halting problem. [0]: https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/1400077974 https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/14...
im3w1l 10y ago
> As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Is a hammer true or false? I don't know, but it's good for hitting nails.
- kmm 10y ago
  Yeah, a hammer is definitely useful, but I think the point he's trying to make is that the notion of uncountable sets isn't very useful outside of things like set theory.
zodiac 10y ago
How many sets of natural numbers are there? An uncountable number. Of course, you could throw out some axioms so that you create an axiom system in which I can't define such a thing as "a subset of the natural numbers", but such a world doesn't feel "real" (in a platonic sense) to me.
- pherq 10y ago
  In this case, what you "throw out" are uncomputable (or non-recursive, depending on terminology you like) sets; i.e. sets for which the membership function is not decidable. Yes, there are an uncountable number of these sets, but they can't be defined in any useful way.
  - baddox 10y ago
    Indeed, if you consider a real number to just be a decimal representation formed by concatenating all the natural numbers in a set (not at all a rigourous construction of the reals, but hopefully sufficient for this argument), the equivalence is clear.
    - zodiac 10y ago
      I've always found dedekinds construction (where sqrt 2 is represented by the set of rationals {x in Q : x^2 < 2}) to be a nice natural place where powersets of countable infinite sets come up (in addition to being a great way to construct R)
    - pherq 10y ago
      I tend to prefer considering the sets to encode bitstrings (encode a set as sum(2 ^ -x for x in X)), but yes the equivalence between computable sets and computable numbers is straightforward.
  - zodiac 10y ago
    For sure - as I understand it in most formulations you throw out lots of sets but keep all the finite sets of natural numbers, the set of even numbers, the set of prime numbers etc One thing I never found satisfactory is that any axiom system like this has to define things in terms of decidability etc, so it's "more verbose" (or less axiomlike) than ZFC
rw 10y ago
You could have answered all of your questions with "finitely many", because, after all, we can each only perform a finite number of actions in the world. In general, the infinite hierarchy of infinite sets "exists" because we can define it.
sn41 10y ago
One of the great theorems in logic is the Lowenheim-Skolem theorem [1], which says that if a countable first-order model has an infinite model, then there is a countably infinite model. For example, there is a countably infinite model for the theory of reals. I have heard that Skolem [2] used this theorem as a basis for his belief that uncountable sets can be avoided, and countably infinite sets suffice. [1] https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_... [2] http://www-gap.dcs.st-and.ac.uk/history/Biographies/Skolem.html http://www-gap.dcs.st-and.ac.uk/history/Biographies/Skolem.h...
joatmon-snoo 10y ago
the solution to any problem any could ever have That's a pretty tall claim to make. Once upon a time people thought irrationals and transcendentals like pi and e didn't even exist. It wasn't until the past century that people realized abstract algebra and its ilk had practical applications. The same goes for chaos theory and fractals as well. Admittedly it's hard for me to envision a world where notions of countability will ever have real-world uses, but I also consider calling it "a fun maths game" rather reductionist, and frankly, poor taste (especially if you're going to say something like "intrinsic truth or falsity"). Give him three pence, since he must make gain out of what he learns.
- CJefferson 10y ago
  The reason I say "the solution to any problem anyone could ever make" is a maths argument! If you can write down a problem as a finite string, then the set of all problems must be countable.
heinrichhartman 10y ago
Good luck developing analysis with only countable infinities. Limits will take you out of the realm of countable spaces. Most of your derivatives and integrals won't exists, if you force them to take values in countable sets.
- CJefferson 10y ago
  Why not, can you give an example. Most of the "common" derivatives and integrals I can think of would work just fine, unless I'm missing something obvious?
  - kutkloon7 10y ago
    No, for example the integral sqrt(1 - x^2) from x = 0 to x = 1. Or any other integral over a circle/sphere for that matter.
    - CJefferson 10y ago
      Nothing wrong with that, it's still a computable number -- I'm not suggesting doing away with all real numbers, just the non-computable ones. I don't claim to have thought through every detail, but having now gone and done some reading, this seems fine in the world of constructivism, which only requires computable numbers (and therefore only countable infinities of numbers)
  - twic 10y ago
    Are the computable numbers continuous? If not, is that a problem for analysis? If so, can you construct some computable analogue of continuity which is sufficient?
  - heinrichhartman 10y ago
    - Every real number can be represented as a limit of rational numbers, which are uncountable. - So for every countable subset you can find a (Cauchy) sequence of rationals that does not converge. Hence, you loose one of the most important tools in Analyisis (Cauchy criterium for convergence). You can still work with the remaining set, but formulating and proving theorems, is going to be much harder. - If integrals over f and g exists, then the integral over f * g does not need to exists. - E.g. Integrals over bounded regions will not always exists. - Theorem of Montonic convergence fails - Function spaces will not be complete (L2). A nice theory of constructible "periods" has been developed by Kontsevich and Zagier (http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf) but it relies heavily on the existing body of Analysis being available.
heinrichhartman 10y ago
Are you aware of the concept of periods ? This is a quite fascinating, countable, ring of numbers, that captures all of the above: Kontsevich and Zagier introduce and develop this concept quite far: http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf
- CJefferson 10y ago
  No, but this looks interesting. Thanks for the reference!
- wolfgke 10y ago
  Just to give a little bit more attention to this link: Wikipedia link to one of the authors: > https://en.wikipedia.org/wiki/Maxim_Kontsevich https://en.wikipedia.org/wiki/Maxim_Kontsevich Proof that one of the authors really is no other "M. Kontsevich" (I openly admit that I wanted to be sure since I associate Maxim Kontsevich mostly with other mathematical areas): > http://www.ihes.fr/~maxim/publicationsanglais.html http://www.ihes.fr/~maxim/publicationsanglais.html
ArkyBeagle 10y ago
Euler held that infinities in general were nothing more than a way of reasoning about limits.
yequalsx 10y ago
The are uncountably many polynomial over the reals. There are uncountably many functions from N to N. The premise of your question is incorrect.
- waqf 10y ago
  OP never claimed there were countably many functions from N to N, only that there are countably many Turing machines which is true. By "polynomials" OP doesn't mean polynomials over the reals but over, for example, the rationals – the point is that there's a countable subset of R that's algebraically closed.
  - yequalsx 10y ago
    I know those things. OP does not claim that the set of functions from N to N is uncountable. One gives up things if only countable things are considered. For instance those things that I mentioned.
    - waqf 10y ago
      Oh, I see, you're addressing the "we don't need uncountable sets" statement by giving examples of intuitively obvious things which are uncountable. But I think OP's claim is that we don't "need" those things because we could do mathematics with the set of Turing machines instead of the set of functions, etc.
      - yequalsx 10y ago
        Yes, but can Turing machines do enough mathematics? The second order Peano Axioms are categorical and the first order axioms are not. The Incompleteness Theorem tells us that there are statements that are true in the standard model of N that are not provable by a Turing Machine.
lmm 10y ago
No mathematical object exists exactly in the real world. E.g. you will never see a physically perfect square. The whole point of mathematics is that it's a simplified model of reality that's easier to work with for some purposes, and that's as true of uncountable infinities as it is of anything else in maths.
imh 10y ago
Better yet, just consider all deduction as "a fun language game," rather than having any intrinsic truth or falsity. If you assume a whole bunch of stuff and the axiom of choice, you can get these interesting things over here. If you assume that same bunch of stuff but not the axiom of choice, you get this other interesting stuff over there. Which assumptions to use at any given time just depend on what you're trying to do. If I'm trying to count my sheep, I just need enough axioms to get me addition of natural numbers. If I'm trying to model some mechanical trajectory, maybe I ought to grab some reals. Got circles? Adding imaginary numbers to the reals makes that easy, even though imaginary numbers are totally "fake." Using sentences that might not make sense? Maybe avoiding the excluded middle is a good idea.
paulddraper 10y ago
> If the set of all numbers any can express in any sensible way, and the solution to any problem any could ever have is countable This is trivially true, since there are only countable (finite) expressions and problems. > why do we need the other uncountables? You can't do calculus without reals. http://math.stackexchange.com/questions/1880741/why-cant-calculus-be-done-on-the-rational-numbers http://math.stackexchange.com/questions/1880741/why-cant-cal... And calculus is pretty important (e.g. for any branch of physics ever).

im3w1l 10y ago

I'd assume that even if in every case the number of incorrect guesses is finite, the expected number of people that fail to guess their color is infinite. Am I right about this?

baddox 10y ago
Im not sure what you mean by "expected number." Do you mean if you try to guess how many inmates the warden has managed to guarantee will fail? Per the article, the warden can guarantee that an "arbitrarily large finite number of them" will fail. But it's still always finite despite being unbounded. If you want to predict a lower bound on the number of failures the warden has guaranteed, you just have to guess a larger natural number than the warden. :)
- im3w1l 10y ago
  I mean if the warden picks a sequence randomly.
daxfohl 10y ago
Interesting observation! Yes, I think reduced to its essence, it boils down to: the expected value of "a finite number" is infinity. Which is strange in itself. So you end up with a sequence that converges to 100%, but that convergence never starts, but it certainly happens eventually. I guess a similar, less verbose thing would be "pick a random rational in (0, 1)". In decimal representation it'll repeat after "a finite number" of random digits, but "a finite number" again is expected to be infinity. So is a random rational really rational? Someone more educated on set theory will have to comment.
waqf 10y ago
If you take any finite subset of N prisoners, it's easy to see that they won't do better than chance, so the expectation is for N/2 of them to guess wrongly. Since N can be arbitrarily large, your intuition is correct.

mrob 10y ago

Infinities aren't real, so you shouldn't be surprised if unrealistic things happen when you invoke infinities. That you can duplicate a sphere by cutting it into a finite number of pieces and reassembling it is a "fact" in the same sense as "Luke Skywalker destroyed the Death Star". It might be interesting and culturally important, but it's talking about fictional entities. Both spheres and arbitrarily detailed pieces of spheres only exist in the imaginations of mathematicians. The Axiom of Choice is obviously true, and the fact that it lets you invent weird sounding stories from weird components is no evidence against it. Don't confuse mathematical tools with reality.

zodiac 10y ago
There are a small number of people who think it's obviously false! (I'm not one of them). And a larger number who think it's not obviously true nor obviously false.
- pherq 10y ago
  There's the old joke that the axiom of choice is obviously true, the well-ordering theorem is obviously false, and Zorn's lemma is too complicated to say.
llamaz 10y ago
Mathematics is formalised is to avoid this sort of philosophizing. I used to think, for example, that the dirac delta function was mathematical fiction - a mathematical "hack". But then in an engineering control systems class, we did an experiment where we used a step function to approximate a dirac delta function. I could see the results both on the computer screen and in physical reality through a mass-spring-damper system. From that moment on I saw the dirac delta function in the same way that I see cosine/sine: The reason it works in math is because it has a basis in physical reality. The lesson to be learned here, is that you don't know in advance whether something is obvious or not. To me, it doesn't make sense to decide whether the axiom of choice can be justified by looking at the axiom itself. You have to look at where it's used and required, and whether the proofs convey something that matches your physical intuition.

fmap 10y ago

The problem solution in the article uses the axiom of choice to construct a "nonprincipal ultrafilter" on the natural numbers. This is actually weaker than the full axiom of choice, but you can still show that no such object is computable. It's a nice exercise to show that with the same assumptions as in the article you can decide the halting problem. (hint: consider the boolean sequence where the nth element is true iff the Turing machine halts within n steps) As for the axiom of choice, the real problem is trying to claim that it is right or wrong in the first place. Mathematics as a whole has never quite recovered from the failure of Hilbert's program... The bottom line is that there is no complete and consistent notion of "truth". There is no objective mathematical reality, because it cannot include a statements about its own consistency (and it's easy to translate this into "statements about certain hard problems", by exactly the same process we use to show that some problems are NP complete by reduction from another NP complete problem). On the other hand, this is not actually detrimental to mathematical practice. It only means that you have a lot more freedom in modeling your problem domain. For instance, it turns out that set theory with the axiom of choice is a horrible place to do probability theory in (non-measurable sets and functions are a direct consequence, and you have to go to a lot of trouble to exclude them everywhere). If ZFC was part of some objective mathematical reality, then this would in some sense be unavoidable, since ultimately you want to make statements describing reality. On the other hand, once we realize that this assumption is just plainly false, we can start looking for more refined models.

cygx 10y ago
There is no objective mathematical reality, because it cannot include a statements about its own consistency I'm assuming we're talking about Gödel's incompleteness theorems? Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized?
- candiodari 10y ago
  > Don't they just say that if there's such a thing as objective mathematical reality, it can't be effectively axiomatized? No they don't. Real space doesn't appear to be infinite, and Zn is not subject to Godel's incompleteness theorem. If you drop the requirement of infinite numbers and "recursive" infinites (e.g. real numbers), as reality appears to do, there is no problem.

Ceezy 10y ago

YOUR MATH ARE WRONG If prisonners follow the last strategy, the dude number 0 as a probability of finding his hat of 50% and the dude number 1 000 000 50%. Why? because nobody knows how many times they will lose. Those who are sure to win are those close to infinity... This have nothing to do with Axiom of Choice. But only because almost all the mass of your distribution is near infinty. With or without Axiom of Choice this things exist.

twic 10y ago

The axiom of choice always seemed intuitively wrong to me. You can't just take a set and arbitrarily pick something out of it! Making a choice requires information, and you can't pluck information out of thin air at whim; applying the axiom amounts to creating information out of nothing. I suppose this is because i'm not a mathematician, but have a natural sciences background. In the physical universe, memorably, "the law that entropy always increases holds, I think, the supreme position among the laws of Nature" [1], and so we do not accept the mathematicians' fake information. More specifically related to choice from a set, Curie's principle that "when certain causes produce certain effects, it is the elements of symmetry of the causes that may be found in the effects produced" [2] forbids something uniform from becoming arbitrarily non-uniform; whenever that appears to happen, there must be some hidden cause which already carries that non-uniformity. [1] https://en.wikipedia.org/wiki/Second_law_of_thermodynamics https://en.wikipedia.org/wiki/Second_law_of_thermodynamics [2] https://hal.archives-ouvertes.fr/jpa-00239814 https://hal.archives-ouvertes.fr/jpa-00239814 - "Enfin, lorsque certaines causes produisent certains effets, les éléments de symétrie des causes doivent se retrouver dans les effets produits."; please excuse the not-so-literal translation

hackinthebochs 10y ago
> You can't just take a set and arbitrarily pick something out of it! Making a choice requires information True, but how can you "have a set", i.e. reference a set in any way, without having information about that set? There seems to be a requirement of some bare minimum of information enough to specify the set, and so enough to pick out a member of the set.
- twic 10y ago
  Having enough information to specify the set isn't enough to pick out one particular member. For example, if i say "the colours teal, maroon, and taupe", you have enough information to know what's in the set, but no extra information that would let you pick one element out of it.
  - mcphage 10y ago

rtpg 10y ago

I have a vague understanding of the Axiom of Choice, but I've always had trouble with some of the analogies people use to explain it. Two things that have bugged me for a while: - why is it usually talked about only in the context of infinite sets? Is there a general trick to building a choice function if all you have are finite sets? - There's a saying like "you can choose from an infinite set of shoes, but not from an infinite set of socks without AC". Why exactly?

petteris 10y ago
The axiom of choice is about making an infinite number of arbitrary choices simultaneously. If you can specify some rule, this rule is just one choice. Finitely many choices are always fine and don't need the axiom of choice. If you have a finite set, you can number its elements and make rules by saying "let's take the element with the smallest number having this or that property", so you don't need the axiom of choice when dealing with finite sets. The point of Russell's shoes versus socks analogy is that shoes are distinguishable while socks aren't: To choose one shoe from each of an infinite set of pairs of shoes, you can always choose the left shoe, or specify some pattern (so you don't need the axiom of choice), whereas when choosing socks, you have to make an arbitrary choice to select one from each pair (so you do need the axiom of choice).
kmill 10y ago
The main problem is taking a statement about a set ("for every A in X, A is nonempty") to the existence of a set ("there is a function f [which in ZFC is considered to be a set] such that for all A in X, f(A) is in A"). If you are able to create a statement P(A,a) that for every A in X is true for exactly one a in A, then it follows from the axiom of replacement that there is such a choice function. The axiom of choice seems to say that it suffices to make a statement P(A,a) that for every A in X is true for at least one a in A. The axiom of replacement helps actually construct such a choice function, whereas the axiom of choice just asserts one ought to exist since "at least one" seems good enough. To use the axiom of replacement, you have to use some structure for A. For instance, with the finite set example, it might be that each A is not just a set, but a set which is in bijective correspondence with a natural number, where there is a distinguished bijection. Then, you could just say that P(A,a) is true exactly when a is the image of 0 under the bijection.

ramblenode 10y ago

What an interesting thought experiment. Lying in bed last night, the best I could come up with (before seeing the optimal solution this morning) was an average of 83 with a minimum of 66. The prisoners agree that every third prisoner, beginning with the first, uses "white" to convey that the subsequent two prisoners are wearing the same color and "black" to convey different colors. Since the second prisoner in each triple knows the color of the third, he can deduce his own color, leaving the third prisoner to also deduce his own color. And of course there's a 50/50 chance the sacrificial first prisoner in the triple still gets out. I suppose this could be improved upon by later prisoners having a longer memory, but I've already seen the optimal solution. ;) Interested to hear others' attempts.

eru 10y ago

You can generalize their prisoner example to using a countable number of colours, not just two or finite.

Grue3 10y ago

There are many problems with this puzzle that go against the intuition. - the number of prisoners is infinite, so they will never finish answering the question. At any point in time, only a finite number of prisoners will be freed. - a single prisoner must process an infinite amount of information to reach the decision. In fact, by observing only a finite number of hats he cannot possibly choose the answer. - the number of equivalence classes is uncountable. Not even a countably infinite number of prisoners can possibly have enough time to pick out a single element from every equivalence class.

Tloewald 10y ago
As soon as you start treating the axiom of choice as a superpower for a conscious being you are in conceptual la la land. How do I guess the color of my hat if there's an uncountable number of possible colors? Doesn't that mean that communicating the value of that color involves transmitting an infinite amount of informtion?
- waqf 10y ago
  Quick, tell me your favourite number between 0 and 1. How did you do that? Weren't there an uncountable number of possible numbers? Ah, you may say, but I obviously wasn't going to choose one with an infinite information content, so all but countably many possible numbers had probability 0. Which is true. But in fact it's true that whenever you have a probability measure on an uncountable space then all but countably many elements have probability 0, so that escape clause applies equally well to the hat colours.
  - TheCoelacanth 10y ago
    But the axiom of choice applies to all sets, not just ones that you can easily choose a number from. For instance, what is your favorite non-computable number between 0 and 1?
    - red75prime 10y ago
      Inverse of Kolmogorov complexity of thirteenth bit-string with uncomputable Kolmogorov complexity, of course.

pron 10y ago

So what bothered the author was the axiom of choice and not the part where a prisoner with a finite brain needs to memorize an infinite amount of information and then perform a computation on infinite information to compute the equivalence class? For this strategy to work you must assume that the prisoners are capable of carrying out noncomputable computations, too. That's the more problematic assumption.

bananabiscuit 10y ago

This problem has exactly the wrong setup for using th the axiom of choice: First, the axiom of choice requires that you have a countable number of sets that you are choosing elements from, but there are undoubtably many of the equivalence classes that he described [0]. So the author is using something stronger than the axiom of choice to arrive at his paradox. Second, if you actually are in a situation where you have to choose from a countably infinite number of sets, you only need the axiom of choice if there is no selection rule for choosing an element available. In this case there is a rule you can use, namely: select the sequence in which the "finite prefix" is all zeros. [0]: the number of equivalence classes is uncountable because there is a 1:1 relation between the equivelance class and an the infinite sequence that is common to all the sequences in the equivalence class once theirs uncommon prefixes have been truncated.

n4r9 10y ago
> the axiom of choice requires that you have a countable number of sets that you are choosing elements from You're referring to the "axiom of countable choice", which is a different axiom. The Wikipedia entry for the axiom of choice makes it clear that the number of sets can be uncountable. > select the sequence in which the "finite prefix" is all zeros This doesn't really make sense as a selection rule. The size of the prefix can vary between pairs of members from the same equivalence class.
yequalsx 10y ago
The axiom of choice applies to index sets of arbitrary size. Indeed there is an axiom of countable choice for those who don't like the axiom of choice.
TimonKnigge 10y ago
> First, the axiom of voice requires that you have a countable number of sets that you are choosing elements from, but there are undoubtably many of the equivalence classes that he described [0]. No it does not? The axiom of countable choice [0] is a strictly weaker axiom. [0] https://en.wikipedia.org/wiki/Axiom_of_countable_choice https://en.wikipedia.org/wiki/Axiom_of_countable_choice

wolfgke 10y ago

An interesting alternative to the axiom of choice (AC) is the axiom of determinacy (AD): https://en.wikipedia.org/w/index.php?title=Axiom_of_determinacy&oldid=738341699 https://en.wikipedia.org/w/index.php?title=Axiom_of_determin...

jiiam 10y ago

In the comments to the linked article there's a nice explanation by Terry Tao of why this is not so spectacular, in the sense that our intuition with probabilities here relies on Fubini's theorem, which in this case do not apply due to measure theoretic obstacles. But, again, our intuition of probability fails with much easier examples. Here follows Terence Tao's comment (refer to the original to have proper rendering of math symbols): "This paradox is actually very similar to Banach-Tarski, but involves a violation of additivity of probability rather than additivity of volume. Consider the case of a finite number N of prisoners, with each hat being assigned independently at random. Your intuition in this case is correct: each prisoner has only a 50% chance of going free. If we sum this probability over all the prisoners and use Fubini’s theorem, we conclude that the expected number of prisoners that go free is N/2. So we cannot pull off a trick of the sort described above. If we have an infinite number of prisoners, with the hats assigned randomly (thus, we are working on the Bernoulli space {\Bbb Z}_2^{\Bbb N}), and one uses the strategy coming from the axiom of choice, then the event E_j that the j^th prisoner does not go free is not measurable, but formally has probability 1/2 in the sense that E_j and its translate E_j + e_j partition {\Bbb Z}_2^{\Bbb N} where e_j is the j^th basis element, or in more prosaic language, if the j^th prisoner’s hat gets switched, this flips whether the prisoner gets to go free or not. The “paradox” is the fact that while the E_j all seem to have probability 1/2, each element of the event space lies in only finitely many of the E_j. This can be seen to violate Fubini’s theorem – if the E_j are all measurable. Of course, the E_j are not measurable, and so one’s intuition on probability should not be trusted here. There is a way to rephrase the paradox in which the axiom of choice is eliminated, and the difficulty is then shifted to the construction of product measure. Suppose the warden can only assign a finite number of black hats, but is otherwise unconstrained. The warden therefore picks a configuration “uniformly at random” among all the configurations with finitely many black hats (I’ll come back to this later). Then, one can again argue that each prisoner has only a 50% chance of guessing his or her own hat correctly, even if the prisoner gets to see all other hats, since both remaining configurations are possible and thus “equally likely”. But, of course, if everybody guesses white, then all but finitely many go free. Here, the difficulty is that the group \lim_{n \to \infty} {\Bbb Z}_2^n is not compact and so does not support a normalised Haar measure. (The problem here is similar to the two envelopes problem, which is again caused by a lack of a normalised Haar measure.)"

EGreg 10y ago

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

IshKebab 10y ago

How can an axiom be 'wrong'?

thethirdone 10y ago
Suppose, I choose "This sentence is false" as an axiom. having it as an axiom allows me to reason from its content that it is false and thus I have a contradiction. In this way at least, that axiom is "wrong".
- monochromatic 10y ago
  But the Axiom of Choice doesn't lead to contradictions (unless Zermelo Fraenkel set theory itself contains contradictions). The Axiom of Choice just leads to some non-intuitive results.
dvt 10y ago
An axiom is simply a statement that is defined as being true. Often times on grounds of being self-evident. For example, one of Euler's axioms is "Things that are equal to the same thing are also equal to one another". Whereas Euler's may seem pretty tame, the Axiom of Choice is not. That's why some people think it might be wrong.
- IshKebab 10y ago
  Exactly, so unless it leads to contradictions it may be weird and unintuitive but it's not wrong.

deleted 10y ago

[deleted]

alsadi 10y ago

> Sure, this is based primarily on my intuition for finite things and a naive hope that they should extend to infinities. but it's known that it does not extend!

DigitalPhysics 10y ago

If you're interested in the Axiom of Choice, Godel, finitism, pseudo-randomness, complexity, information, and other foundational topics, check out the indie film "Digital Physics" on iTunes, Amazon, or Vimeo. Free packs of trading cards (with gum!) are available too! Check the website.