A bizarre riddle using the Axiom of Choice

[Jrthedawg]

I've asked many people about the incredible conclusion of this riddle, whose solution applies the axiom of choice, and have yet to find a satisfying response.

I understand the solution, but I would like to know why the axiom of choice leads to such a bizarre result, while being so compatible and useful with most of mathematics. Any insight?

 

[HallsofIvy]

I don't think we can say the result is "bizarre" without knowing why you consider it bizarre!

 

[Jrthedawg]

You're right. What I find bizarre about this result is that the axiom of choice gives the mathematicians in the riddle the ability to name a real number hidden in a box. This seems like an incredible power! Especially in light of the fact that 'most' numbers are undefinable, that is, we can't even write down a description defining them!

 

[1MileCrash]

You're right. What I find bizarre about this result is that the axiom of choice gives the mathematicians in the riddle the ability to name a real number hidden in a box. This seems like an incredible power! Especially in light of the fact that 'most' numbers are undefinable, that is, we can't even write down a description defining them!

Yeah, I don't how a solution exists at all, and the explanation of the solution is something I may understand in 10 years.

 

[1MileCrash]

OK, now I think I understand.

I don't think the axiom of choice actually allows a mathematician to actually determine a real number. I mean, no mathematician can actually carry out the strategy.

It looks like the mathematician has to open infinite boxes, and then he finds some sequence in the set of all sequences that matches his string of infinite values somewhere. Since he has infinite data, I guess I kind of buy it.

If he could only pick a finite number of boxes then he would have essentially no data, so no real human could do this.

But, I think I have a very layman and incomplete (and maybe completely wrong) understanding of just a piece of this puzzle.

 

[verty]

I don't get this at all. None of the explanations made sense to me. They are all of this sort: once you know the representative, you guess the 8th number. Huh?

 

[someGorilla]

Wow. This had me dumbfounded for a good while. It reminded me of a similar one I read some time ago, and that time I wasn't able to figure out how the heck it could work.
There's an infinite (countable) number of prisoners awaiting to be executed, standing in a queue. The hangman sets a white or black hat on each prisoner's head, so that the first one (the one at the back) can see each other prisoner's hat but not his one, the second one can see all the hats except his one and the one behind him, and so on. Then the hangman asks each one, starting with the first one, what colour his hat is. If he guesses he is freed, if not he is hanged. They are wearing headphones preventing them to hear the others' responses, so they can't communicate in any way. Still, if they are allowed to agree on a strategy beforehand, they can succeed in having only a finite number of them killed!
The solution is analogous to the boxes riddle - but simpler since only one representative is involved instead of 100. It's also more immediately generalizable to guessing an infinite number of reals instead of just one like in the boxes case: instead of white and black hats, use hats marked with a real number on their back - or an uncountably infinite number of colours. It works just as fine.

Now, this is the conclusion I reached, and I'd like to know what you think of it:
What makes it paradoxical is just the way it's told. It's the dramatization. Because the mathematical truth by itself is nothing weird: if you group sequences of hat colours so and so, and pick representatives so and so, then there exists the representative of the actual sequence of hats on the prisoners' heads. Oh well. It's so obvious that it's almost a tautology (if you admit the axiom of choice, that is).
What makes is strange is setting it in such an almost-daily fictional depiction that it appeals to your daily intuition. You can kind of imagine the queue of hatted people, you can imagine being one of them, and so on. So it seems like a "real" situation and it seems the paradoxical statement says something about what can be done in reality.
Except that... there's an infinite number of people and hats, people are able to see infinitely far in the distance, but above all:
- each one of the prisoner has an infinite memory. Uncountably infinite, in order to remember the representative for each group (and there's uncountably many of those).
- no algorithm exists to pick a representative for each group (if there were one, there would be no need for the axiom of choice to even exist!)
- the groups can't be named with a symbol that is less than infinite
- each prisoner needs infinite computing power

«If the prisoners are allowed to find a common strategy...» is a cheat: they can't agree on it because no such strategy actually exists. And if we remove the strategy detail, and with it the need for a working algorithm, it becomes nothing more that an immediate corollary of the axiom of choice.

So, to put it short I'll rephrase the paradox statement: «If there were infinite prisoners with uncountably infinite memories and the ability to process uncountably infinite information in a finite time, and if they were able to agree in a finite time on an algorithm that does not exist, then...» Then strange things might follow.

Over here in Tuscany there's an old traditional reply to far-fetched counterfactuals: Yes, and if my grandma had wheels she'd be a chariot.

 

[verty]

I've now read the countable hats solution on wikipedia and still am not fully understanding how this representative idea works. Here is the problem. Imagine prisoners in line, each can see those in front of him, and each hat has a digit from 0 to 9 on the back.

Suppose prisoner #6 knows that he is the 6th prisoner. In front of him he sees 2,7,3,5, and so on. He has a representative in mind for sequences that end 2,7,3,5... to infinity, matching what he sees in front of him. The representative had a 1 in the 6th position: 1,2,7,3,..., so he announces that his hat is labeled 1. Now prisoner #7 knows he is prisoner 7, and he sees the sequence 7,3,5, and so on. We know his hat is number 2. He has a representative in mind for sequences that, from the 8th position onwards, are 7,3,5,... etc. But his representative could have any digit in this 7th position. There are 10 possibilities. He has a 1 in 10 chance of guessing which hat he has. This extends to any prisoner.

Wikipedia claims that, by knowing the representative, only finite prisoners will be killed. After finitely many prisoners, they will all be safe because they will be choosing from the representative of the class of the actual sequence. I don't see this. Pick any finite number N, prisoner N has a representative for sequences that, from the N+1'st position, are what he sees in front of him, but it doesn't help because his hat could be any 1 of 10.

 

[someGorilla]

Suppose prisoner #6 … has a representative in mind … The representative had a 1 in the 6th position. … prisoner #7 … has a representative in mind

No. They must all use the same representative. That's why they need to concoct a strategy before the game starts. They must agree that for all sequences of a certain group the representative is, for example, 4, 6, 0, 0, 9, 8, 4, 7, 3, 5... In your case, with this representative all prisoners from #8 on guess right. But they must have agreed beforehand on the representative to use for ALL possible sequence groups.

 

[1MileCrash]

So it sounds like they have to make an infinite number of decisions.

 

[verty]

I've been thinking about this a bit, I think I now understand the idea about letting the prisoners have the same set of representatives for matching-at-finite-distance infinite sequences. It occurs to me that the prisoners don't all need to have the same set of representatives; as long as there are only finitely many sets of representatives shared by all the prisoners, all is fine.

I also wondered how many representatives are needed. Each equivalence class is countable (order the members by the finite distance that each differs from the representative), so there do need to be uncountably many representatives.

 

[someGorilla]

the prisoners don't all need to have the same set of representatives; as long as there are only finitely many sets of representatives shared by all the prisoners, all is fine.

I don't get what you mean... what are finitely many sets of representatives? What is a set of representatives?

I also wondered how many representatives are needed. Each equivalence class is countable

True, but this has no importance. There's one representative per class anyways.

… so there do need to be uncountably many representatives.

Since there are uncountably many equivalence classes...

 

[someGorilla]

Oh, by the way, why cling to this wimpy version of the paradox? Instead of real numbers, you might have anything inside the boxes. Box #3 might contain π^{2}, #5 might contain a Mexican sombrero, #200 might contain Borges' library, and #201 a complete copy of the whole set of boxes. And still cofinitely many players will guess right.

 

[someGorilla]

I've been thinking about this a bit, I think I now understand the idea about letting the prisoners have the same set of representatives for matching-at-finite-distance infinite sequences. It occurs to me that the prisoners don't all need to have the same set of representatives; as long as there are only finitely many sets of representatives shared by all the prisoners, all is fine.

I also wondered how many representatives are needed. Each equivalence class is countable (order the members by the finite distance that each differs from the representative), so there do need to be uncountably many representatives.

Oh, now I see. You're right. Still, you need uncountably many representatives because you have uncountably many equivalence classes, no shortcut around that.