7 ms·

The Axiom of Choice is Wrong (2007)

35 points by rw 17y ago

jules 17y ago
> Its interesting to notice that a larger number of hat colors poses no problem here. For any set of hat colors , the prisoners can pick an abelian group structure on . Then, the first prisoner guesses the ’sum’ of all the hat colors he can see. The next guy can then subtract the sum of the hat colors he sees from the hat color the first guy said to find his own hat color. Again, this argument repeats, and so everyone except the first guy gets out. For the case of black and white, the previous argument used black = 0 (mod 2) and white = 1 (mod 2). So the first guy says the sum, not a color? If he's allowed to say arbitrary things he can as well tell everyone their color "next guy is white, next green, etc.".
- jibiki 17y ago
  No, he translates the sum back to colors. E.g., there is a map f:colors->H with an inverse g:H->colors and he says the color g(sum(f(hat))) where the index hat ranges over all of the hats.
danbmil99 17y ago
Sounds like Bridge. I hate Bridge!
limmeau 17y ago
So this guy is against using the axiom of choice because a countably infinite number of prisoners in a row who have agreed on an infinite set of equivalence classes just between breakfast and hat game time and remember them and each of them can recognize infinitely many hat colors in finite time (takes deep breath) suddenly becomes unintuitive using the axiom of choice? I can't help him there.
bdr 17y ago
Be sure to check out the comments. Lots of good discussion in there, on both the paradox at hand and mathematical Platonism in general, by people who know what they're talking about.
Create 17y ago
If you choose not to decide, you still have made a choice. -- unsourced René Descartes
ShardPhoenix 17y ago
Looks like another example of infinity leading to nonsensical (or at least unintuitive) results.
bitdiddle 17y ago
More troubling to me has been the continuum hypothesis. The notion that you can toss a dart (whose tip is the width of a point) at the real number line and hit an integer or rational number with probability zero is very unintuitive. I can kind of grasp the continuum hypothesis, there does seem to be a distinction between countable and uncountable infinity. Continuing the game beyond that to this area of large cardinals strikes me as just a language game. Most mind blowing, IMHO, is Cantor's middle third's set[1]. Uncountable nowhere dense totally disconnected, ... it's an amazing set and so easy to construct. [1] http://en.wikipedia.org/wiki/Cantor_set http://en.wikipedia.org/wiki/Cantor_set
- stanleydrew 17y ago
  You're not talking about the continuum hypothesis. The continuum hypothesis just states that there isn't any set with cardinality larger than the natural numbers (aleph_0) but smaller than the reals (2^aleph_0). Interestingly this can't be proven or disproven within set theory if you assume the axiom of choice. Comparing the cardinality of the natural and real numbers doesn't have much to do with the continuum hypothesis. It's simply true that there are many many many more reals than rationals. It's not a hypothesis. But I do agree that the Cantor set is pretty awesome.
  - bitdiddle 17y ago
    Actually I was talking about it. My mind wanders. Sorry to be so vague (it's been years since I read this stuff). I didn't mean to imply sets of measure zero were what CH is about. The reals can be essentially equated with the powerset of the naturals. It's very intriguing that there is no set with cardinality in between that of the naturals and that of the reals. The Axiom of Choice is also independent of ZF set theory. Have you read the more modern expositions of these independence proofs based on various Topoi?
yummyfajitas 17y ago
This is still only an argument against the uncountable axiom of choice. The set of equivalence classes of infinite strings is uncountable, so using the axiom of choice here is invalid. As far as I know, the countable one is still reasonable.
jganetsk 17y ago
I feel like the axiom of choice can't be used here. Let's say we have a infinitely long bit string, b. This equivalence class has an infinite number of elements in it! That is, there is an infinite number of strings with suffix b. b, 0b, 1b, 00b, 01b, 10b, 11b, etc. Can you use the axiom of choice in this case? I think it is required that each bin has a finite number of objects, even though there are infinite bins.
- ggchappell 17y ago
  > Can you use the axiom of choice in this case? Yes, you can. > I think it is required that each bin has a finite number of objects, even though there are infinite bins. No, the axiom says only that the product of nonempty sets is nonempty. It doesn't say anything about the number of sets or their sizes. For those who don't see the connection: Each element of a product of sets consists of a choice of one item from each set. Saying the product is nonempty is saying there is a way to make such choices. For example, the product of {1,2} and {a,b} contains, among other things, the pair (1, b), which can be thought of as choosing 1 from the first set and b from the second. There are restricted versions of the Axiom of Choice (e.g., Countable Choice, Dependent Choice); however, none of these are called "the Axiom of Choice".
  - jganetsk 17y ago
    Ok. My other gripe with his argument is that these aren't equivalence classes. Let the string be 01b, where b is an infinitely long bit string. Then the string 01b belongs to equivalence class b, and also equivalence class 1b... and an element cannot belong to multiple equivalence classes at once. The only way out of this is for 1b and b to actually be the same equivalence class, that is, that of b. But, can we do that? I feel like that is wrong.
    - deleted 17y ago
      [deleted]
    - thisrod 17y ago
      It's like saying 128x and 28x, considered as finite sequences of digits followed by a letter, are in the class of sequences that end in x. Except in the infinite case, there are a lot more than 26 letters.

35 points by rw 17y ago

jules 17y ago

> Its interesting to notice that a larger number of hat colors poses no problem here. For any set of hat colors , the prisoners can pick an abelian group structure on . Then, the first prisoner guesses the ’sum’ of all the hat colors he can see. The next guy can then subtract the sum of the hat colors he sees from the hat color the first guy said to find his own hat color. Again, this argument repeats, and so everyone except the first guy gets out. For the case of black and white, the previous argument used black = 0 (mod 2) and white = 1 (mod 2). So the first guy says the sum, not a color? If he's allowed to say arbitrary things he can as well tell everyone their color "next guy is white, next green, etc.".

jibiki 17y ago
No, he translates the sum back to colors. E.g., there is a map f:colors->H with an inverse g:H->colors and he says the color g(sum(f(hat))) where the index hat ranges over all of the hats.

danbmil99 17y ago

Sounds like Bridge. I hate Bridge!

limmeau 17y ago

So this guy is against using the axiom of choice because a countably infinite number of prisoners in a row who have agreed on an infinite set of equivalence classes just between breakfast and hat game time and remember them and each of them can recognize infinitely many hat colors in finite time (takes deep breath) suddenly becomes unintuitive using the axiom of choice? I can't help him there.

bdr 17y ago

Be sure to check out the comments. Lots of good discussion in there, on both the paradox at hand and mathematical Platonism in general, by people who know what they're talking about.

Create 17y ago

If you choose not to decide, you still have made a choice. -- unsourced René Descartes

ShardPhoenix 17y ago

Looks like another example of infinity leading to nonsensical (or at least unintuitive) results.

bitdiddle 17y ago

More troubling to me has been the continuum hypothesis. The notion that you can toss a dart (whose tip is the width of a point) at the real number line and hit an integer or rational number with probability zero is very unintuitive. I can kind of grasp the continuum hypothesis, there does seem to be a distinction between countable and uncountable infinity. Continuing the game beyond that to this area of large cardinals strikes me as just a language game. Most mind blowing, IMHO, is Cantor's middle third's set[1]. Uncountable nowhere dense totally disconnected, ... it's an amazing set and so easy to construct. [1] http://en.wikipedia.org/wiki/Cantor_set http://en.wikipedia.org/wiki/Cantor_set

stanleydrew 17y ago
You're not talking about the continuum hypothesis. The continuum hypothesis just states that there isn't any set with cardinality larger than the natural numbers (aleph_0) but smaller than the reals (2^aleph_0). Interestingly this can't be proven or disproven within set theory if you assume the axiom of choice. Comparing the cardinality of the natural and real numbers doesn't have much to do with the continuum hypothesis. It's simply true that there are many many many more reals than rationals. It's not a hypothesis. But I do agree that the Cantor set is pretty awesome.
- bitdiddle 17y ago
  Actually I was talking about it. My mind wanders. Sorry to be so vague (it's been years since I read this stuff). I didn't mean to imply sets of measure zero were what CH is about. The reals can be essentially equated with the powerset of the naturals. It's very intriguing that there is no set with cardinality in between that of the naturals and that of the reals. The Axiom of Choice is also independent of ZF set theory. Have you read the more modern expositions of these independence proofs based on various Topoi?

yummyfajitas 17y ago

This is still only an argument against the uncountable axiom of choice. The set of equivalence classes of infinite strings is uncountable, so using the axiom of choice here is invalid. As far as I know, the countable one is still reasonable.

jganetsk 17y ago

I feel like the axiom of choice can't be used here. Let's say we have a infinitely long bit string, b. This equivalence class has an infinite number of elements in it! That is, there is an infinite number of strings with suffix b. b, 0b, 1b, 00b, 01b, 10b, 11b, etc. Can you use the axiom of choice in this case? I think it is required that each bin has a finite number of objects, even though there are infinite bins.

ggchappell 17y ago
> Can you use the axiom of choice in this case? Yes, you can. > I think it is required that each bin has a finite number of objects, even though there are infinite bins. No, the axiom says only that the product of nonempty sets is nonempty. It doesn't say anything about the number of sets or their sizes. For those who don't see the connection: Each element of a product of sets consists of a choice of one item from each set. Saying the product is nonempty is saying there is a way to make such choices. For example, the product of {1,2} and {a,b} contains, among other things, the pair (1, b), which can be thought of as choosing 1 from the first set and b from the second. There are restricted versions of the Axiom of Choice (e.g., Countable Choice, Dependent Choice); however, none of these are called "the Axiom of Choice".
- jganetsk 17y ago
  Ok. My other gripe with his argument is that these aren't equivalence classes. Let the string be 01b, where b is an infinitely long bit string. Then the string 01b belongs to equivalence class b, and also equivalence class 1b... and an element cannot belong to multiple equivalence classes at once. The only way out of this is for 1b and b to actually be the same equivalence class, that is, that of b. But, can we do that? I feel like that is wrong.
  - deleted 17y ago
    [deleted]
  - thisrod 17y ago
    It's like saying 128x and 28x, considered as finite sequences of digits followed by a letter, are in the class of sequences that end in x. Except in the infinite case, there are a lot more than 26 letters.