3 ms·

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

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.

consz 12y ago
I'm pretty sure the set of equivalence classes is uncountable, so it's not even enumerateable.
- fferen 12y ago
  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.
belovedeagle 12y ago
That's why this is about the https://en.wikipedia.org/wiki/Axiom_of_choice https://en.wikipedia.org/wiki/Axiom_of_choice
- couchand 12y ago
  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.
  - belovedeagle 12y ago
    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.
    - couchand 12y ago
      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.
deleted 12y ago
[deleted]
Bahamut 12y ago
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.
jdpage 12y ago
It doesn't, because of the finite number of entries. The scheme classifies sequences by an arbitrarily-large, but finite, prefix.

consz 12y ago

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

fferen 12y ago
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.

belovedeagle 12y ago

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

couchand 12y ago
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.
- belovedeagle 12y ago
  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.
  - couchand 12y ago
    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.

deleted 12y ago

[deleted]

Bahamut 12y ago

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.

jdpage 12y ago

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