Hacker News Reader

Comment by couchand | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com