# An infinite hat puzzle variation—if we don't know our place, can we still be almost all correct?

An evil demon is holding uncountably many set theorists captive. He explains to us how he will presently arrange us into a well ordered sequence, with everyone facing the same direction upward in the order. On the back of everyone's head he intends to inscribe an ordinal, visible only to those behind (or, we can imagine it as a hat color). All the ordinals will be less than a certain private ordinal $$\theta$$ that he is thinking about, but he won't tell us what it is. And then, at the designated time, we must all shout out simultaneously an ordinal that we predict is the ordinal on the back of our head. These ordinals must all be less than $$\theta$$, or we shall all be put immediately to death. Otherwise, if all the predictions are correct except for at most finitely many errors, then we shall be released. We have a few moments to plan before all this will happen. Will we be able to succeed?

Initial answer. If we are able to observe the order type $$\gamma$$ into which we are arranged, as well as our place in it, then the answer is yes, using the global choice principle. Namely, by global choice we agree upon a fixed well order $$\lhd$$ of all well-ordered sequences of ordinals. Then, when we are arranged, we observe the order type $$\gamma$$ of our sequence, and we know our place in this sequence. Everyone looks ahead to the pattern of ordinals they observe, and we find the $$\lhd$$-least pattern of $$\gamma$$-sequences of ordinals that agrees with that observation data. We then announce our value in that pattern, provided this ordinal is not larger than every ordinal we see, in which case we say $$0$$ (this saves us from death by the $$\theta$$ rule). I claim this strategy will have only finitely many errors. The reason is that first of all, those ahead in the line observe less data, and so any pattern that is consistent with someone's observed data behind will also be consistent with the later person's observed data. So the $$\lhd$$-least pattern in agreement will descend with respect to $$\lhd$$ as one proceeds in the line or stay the same. Since this is a well order, it can go down only finitely often. Any time someone's predicted ordinal disagrees with the actual value, it does strictly down, and so this occurs only finitely often. But also, only finitely many people are affected by the provisional rule about not exceeding observed values, since every well-ordered sequence of ordinals has only finitely many instances where an ordinal exceeds all later ordinals, since these descend as one proceeds. So we have altogether only finitely many errors.

This solution is described in my recent essay Infinitary hat puzzles and the Aftermath. The solution is a modest generalization of the method of Hardin and Taylor (2008), which describes the case with 2 colors and fixed order type $$\omega_1$$.

My question is the following:

Question. What if the prisoners cannot observe $$\gamma$$ and their place in it? Is there still a solution by which all but finitely many will be correct?

I don't expect so, but I don't know how to prove there is no such strategy. The question admits some special cases:

• Assume the order type $$\gamma$$ of the prisoners is known, but one's place in the sequence is not known (for example, if $$\gamma$$ is an infinite cardinal then one can't tell one's place by looking forward). Is there still a winning strategy for all but finitely to be correct?

• Is this possible even when the order type is known to be $$\omega_1$$? Or known to be $$\omega$$?

• Easiest version. Forget all the $$\theta$$ stuff and assume that there are only 2 colors and we are in an $$\omega$$ sequence, but we don't know our place in the sequence. Can we still achieve the only-finitely-many-wrong solution?

• Same but for $$\omega_1$$, or some other definite ordinal, or for finitely many colors, or $$\omega$$ many colors, and so forth.

The question is whether we can still achieve the all-but-finite solution when people don't know their place in the order. The situation I am imagining is that everyone thinks: perhaps I am the first person, or the 7th person, or the $$\alpha$$th person for some ordinal $$\alpha$$. They just don't know their position, and this seems to break the main argument.

• Consider the equivalence relation on sequences defined by $\exists N,M \forall i, a_{N+i} = b_{M+i}$, and choose a representative from each congruence class. All people view sequences in the same class, so from some point their sequence must be a suffix of representative. Now I think everyone can find the first appearance of what they see as a suffix of the representative, and say what appears before it. However, I'm not sure if looking at the first appearance is correct Commented Jul 31 at 2:57
• I think it is correct, because if two different suffixes agree then the sequence is eventually periodic, and that can just be handled separately Commented Jul 31 at 3:01
• Perhaps everyone is $0$, but the representative of the eventually zero sequence has a big string of $1$s initially. Why can't it be using your method that everyone guesses $1$? Commented Jul 31 at 3:07
• I think the version with hidden $\theta$ is also solved by this by finding an upper bound for all ordinals you see, then considering the representative amongst the sequences with ordinals up to it Commented Jul 31 at 3:09
• The "easiest case" (unknown place in an $\omega$ sequence) but with an arbitrary set of colors was American Mathematical Monthly Problem 5348. I recall that they published a faulty solution (not the proposer's) but later published a correct one. The original statement (from memory) was something like this: "Prove that there is a function $f$ such that, for every infinite sequence $\{x_n\}$, we have $x_n=f(x_{n+1},x_{n+2},x_{n+3},\dots)$ for all but finitely many $n$."
– bof
Commented Jul 31 at 3:19

The prisoners cannot win for $$\gamma = \omega^2$$ even if there are only 2 colours and they know the entire sequence in advance! Assign colour $$0$$ to anyone whose position is a limit ordinal, and $$1$$ to everyone else. Now everyone sees the exact same sequence ahead of them, but if they all guess $$0$$ or all guess $$1$$, there will be infinitely many errors either way.

If $$\gamma = \omega \cdot n + m$$ for finite $$n,m$$, then this case is easily solvable iff $$\gamma = \omega$$ is; the $$m$$ set theorists at the end can all guess $$0$$, and everyone else only has to look at the $$\omega$$ people ahead of them, because finitely many errors $$n$$ times is still finite. So this reduces the problem to just the $$\gamma = \omega$$ case, which is solved in bof's answer.

• It is specified that there are an uncountabel set of prisoners. However, your construction still works for $\gamma=\omega_1$. Commented Jul 31 at 8:56
• @Lucenaposition But the solution for $\omega^2$ also works for any ordinal $\gamma\ge\omega^2$, right? Assign arbitrary colors to all hats after the first $\omega^2$, color them all black, whatever, there are sure to be infinitely many errors among the first $\omega^2$ prisoners.
– bof
Commented Jul 31 at 11:46
• Possible objection: there was no requirement that they all follow the same strategy. Reply: all but finitely many must, since otherwise we can swap them around and make them wrong that way. Commented Aug 1 at 1:19

This solution, for an unknown position in an $$\omega$$-sequence with an arbitrary palette of colors for the hats, is apparently due to F. Galvin, American Mathematical Monthly Problem 5348, 1965.

Theorem. For any set $$E$$ there is a function $$f:E^\omega\to E$$ such that, for every infinite sequence $$(x_1,x_2,x_3,\dots)\in E^\omega$$, we have $$x_n=f(x_{n+1},x_{n+2},x_{n+3},\dots)$$ for all but finitely many $$n$$.

Proof. Define an equivalence relation in $$E^\omega$$ by calling two sequences $$x,y\in E^\omega$$ equivalent if they have a common final segment, i.e., if $$(x_m,x_{m+1},x_{m+2},\dots)=(y_n,y_{n+1},y_{n+2},\dots)$$ for some $$m,n$$. Choose an element from each equivalence class; if there are periodic sequences in the class, be sure to choose one of those. Let $$C$$ be the set of sequences so chosen.

Given an infinite sequence $$x=(x_1,x_2,x_3,\dots)\in E^\omega$$, define $$f(x)=x_0$$ so that, if possible, $$(x_0,x_1,x_2,x_3,\dots)$$ is a final segment of an element of $$C$$; if such a choice is not possible, let $$x_0=x_1$$. It is easy to see that this function $$f$$ has the desired property.

• Problem 5348 was indeed posed by Fred Galvin, who had a solution, although the published solution is attributed to D. L. Silverman. But then in this addendum, it says that Silverman withdrew his solution, and a solution by B. L. D. Thorpe is offered instead. Commented Jul 31 at 10:35
• Thanks for this answer. I think you haven't quite defined $f$ correctly, however, since one must allow that perhaps the chosen representative places more than one extra item in front of the observed sequence, so you should say $f(x)=x_0$, if some member of $C$ has $(x_0,x_1,x_2,x_3,\ldots)$ as a final segment. Commented Jul 31 at 14:52
• @JoelDavidHamkins Oops, thanks for the correction. Hope I've got it right now.
– bof
Commented Jul 31 at 17:18