Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Can the well known blue eyed islanders puzzle be extended to an infinite number of islanders?

In that puzzle, a set of $k$ islanders, each with either blue eyes or non-blue eyes, each knows the color of every other islander's eyes but not his own. At time $t=0,1,...$ an islander who knows the color of his eyes raises his hand. Each islander can see which other islanders raised their hands at earlier times and nothing else. At time $t=0$ a visitor tells the islanders that at least one of them has blue eyes. All of the above is common knowledge among the islanders.

Suppose $k$ is finite, as in the initial version of the puzzle. Then, if all the islanders have blue eyes, they will all raise their hands at time $t=k$.

If $k$ is infinite, will they ever raise their hands?

I think it is best to assume here $t$ is an ordinal, and that each islander knows who raised his hand at any lower ordinal.

Certainly, if initially only a finite number of islanders have blue eyes, then after a finite time everyone will know his color. Thus, if initially they all have blue eyes, then after time $t=\omega$, it will be common knowledge that there are an infinite number of islanders with blue eyes. Unfortunately, that gets us nothing because I think this fact was already common knowledge at time $t=0$. I also considered maybe having the islanders collaborate on a strategy somehow - so long as they all know the others are using the strategy, and so long as it is still the case each only raises his hand when he knows his own eye color - but made no headway.

More speculatively, is there some kind of variant of this puzzle that could usefully distinguish between knowledge at transfinite times? I played around with different kinds of finite knowledge - maybe each islander can only see a subset of his fellows - but got nowhere.

share|improve this question
1  
I doubt that this is possible, because transfinite ordinals differ from transfinite cardinals. The finite puzzle works because from each islander's perspective, the other islanders map naturally to an ordinal (the days), allowing the induction to proceed. But with a countably infinite population, there's no natural way for an islander to map the other islanders to a particular countable ordinal. You might be able to do something by putting the islanders into some kind of hierarchy, but then that breaks the symmetry that is such a pleasing feature of the original problem. –  Timothy Chow Jan 2 at 3:25
1  
To paraphrase @Timothy in his comment, the original riddle and its solution make use of the fact that the ordinal number of days is also the cardinal number of islanders. But once you enter the transfinite domain, not every ordinal is a cardinal. –  Asaf Karagila Jan 2 at 15:54
    
I suppose that is true, although perhaps a formal proof, to the extent possible, that no matter what the islanders agree beforehand noone will ever raise his hand, would be useful. Note that by time $\omega$ the islanders have solved the halting problem, and by higher ordinals they have solved much more. –  user44653 Jan 3 at 2:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.