A hat puzzle

Infinitely many prisoners are assembled in a line as pictured. Each knows their place in the line. Each wears either a black or white hat, and each can only see the hats in front of them. Starting from the back of the line, each prisoner has to guess the color of their own hat. The prisoners were allowed to coordinate before the hats were assigned, but now no communication is allowed. Even the guesses must be silently submitted.

If only finitely many prisoners guess wrong, then everybody goes free. Can they succeed?

(Pause for thought.)

Amazingly, yes! Here’s the strategy: 

Label white hats as 1 and black as 0. Then an assignment of hats becomes an infinite binary sequence, i.e. an element of 2^ℕ. Define an equivalence relation called E₀ on 2^ℕ as follows: 

x E₀ y if and only if (∃n ∈ ℕ) (∀m > n) (x_m = y_m)
“x and y eventually agree”

When the prisoners meet up beforehand, they coordinate by agreeing on a choice of one representative from each class.

Once they’re in the room, every prisoner can see all but a finite number of hats. So they all know exactly which equivalence class they’re in. Now each prisoner guesses as if they were in the representative sequence from this class. Since the actual sequence and the representative sequence eventually agree, the prisoners’ guesses eventually agree with reality, and so they go free!

Making choices is hard

I talked about this puzzle a few years ago in this post. Several commenters balked at the solution and said something like: “but there are uncountably many equivalence classes, so therefore the prisoners need to be able to coordinate on uncountably many representatives. Surely this is unreasonable!”

I think that uncountably many representatives is not what’s at issue here. Consider the equivalence relation on the reals defined by:

x ~_ℤ y if and only if x – y ∈ ℤ.

Here we also have uncountably many equivalence classes, but the prisoners could easily come to an agreement on which representative to pick. They could for instance agree to choose the unique representative which lies in the interval [0,1). Here the prisoners are able to coordinate on uncountably many representatives, simply by agreeing on a function (f(x) = x mod 1) which takes each real to the representative for its class. A function f like this is called a reduction of ~_ℤ to =_ℝ, as it converts the problem of deciding x ~_ℤ y into the problem of deciding if two real numbers are equal (in particular, f(x) =_ℝ f(y)).

Now, is there a function f from 2^ℕ to 2^ℕ that takes an infinite binary sequence to the representative sequence for its class? That is, is there a reduction of E₀ to the identity relation on 2^ℕ? Sure! Each E₀-class C is non-empty, so we can “make a choice” of any element γ_C ∈ C. Then set f(x) = γ_[x], where [x] denotes the equivalence class of x.

I highlighted the key phrase in the above definition: make a choice. I said that we could choose an element from each class, but didn’t tell you how. And this is a problem for the prisoners! For them to all agree on the function’s values, they must be able to communicate how this choice is made to each other.

In the case of the equivalence relation ~_ℤ, we were able to find a precise recipe for choosing representatives, namely the definition of the function (x ↦ x mod 1). But can the prisoners find a precise recipe for choosing representatives for the E₀-classes?

That is, is there a definable function that reduces E₀ to =_ℝ? Well, what exactly is definability?

What is definability?

A major theme of descriptive set theory is the following identification, which I’d like to try to motivate:

DEFINABLE = BOREL

A definition is a syntactic thing. It’s a sentence with a free variable, like “x is the 15th digit in the decimal expansion of π” or “f is the identity function on ℝ”. To precisely state what definability is, we must specify a formal language to work in. The simplest logical language is that given by propositional logic. Here we begin with an alphabet, a countable set of basic atomic propositions, and build all other sentences through finite conjunctions, disjunctions, and negation. 

Returning to our puzzle, we were interested in describing 2^ℕ and its subsets. We want our atomic propositions to represent easily definable subsets of 2^ℕ, or equivalently, simple properties of infinite binary sequences. A natural choice for these basic atomic properties is P_nm = “x’s nth bit is m”, interpreted as defining the set {x ∈ 2^ℕ | x’s nth bit is m}. Translated back to prisoners and hats, these are sentences like “Prisoner 35 is wearing a black hat” or “Prisoner 15 is wearing a white hat”. Intuitively, everything that can be said about infinite binary sequences, should be in principle expressible just in terms of sentences like these. 

With finite conjunctions, disjunctions, and negation, we can define sets like {x ∈ 2^ℕ | x starts with 010110} and {x ∈ 2^ℕ | x’s first two bits agree}. Identifying 0 with “left” and 1 with “right”, we can draw these sets as subsets of the infinite binary tree:

How about a set like {x ∈ 2^ℕ | x contains at least one 1}?

What we want is a proposition like “x’s first bit is 0 or x’s second bit is 0 or …”, i.e. 

(P₀₀ ∨ P₁₀ ∨ P₂₀ ∨ …), or \/_n∈ℕ P_n,0

What we need is the ability to take countably infinite conjunctions and disjunctions. Ordinary propositional logic doesn’t allow this. So we graduate to countable propositional logic. In other words, we expand the syntax by closing it under countable conjunctions and disjunctions:

For any countable collection of sentences {φ_n | n ∈ ℕ},
/\_n φ_n and \/_n φ_n are also sentences

On the semantic side, our collection of definable sets is now closed under countable unions, intersections, and negations. For the measure theorist, this is a familiar object: we’ve just defined a sigma-algebra!

(Technical note: when we say “closed under countable unions and intersections”, we also include empty unions and intersections, which correspond to ∅ and X, respectively. For notational convenience, we introduce the symbols ⊥ and ⊤ into our syntax, thought of as the atomic propositions “False” and “True”.) 

In general there are many different sigma algebras you can put on a set, corresponding to different choices of the atomic propositions. But when our set is also a topological space, as in ℝ and 2^ℕ, there’s a natural choice of sigma-algebra, called the Borel sigma-algebra. Here we take our atomic propositions to define the basic (or sub-basic) open sets. Then the Borel sets are all the sets constructible through countable unions and intersections from basic opens, or equivalently,  the sets definable in countable propositional logic.

In 2^ℕ the topology is generated by sets of the form

{x ∈ 2^ℕ | x’s nth bit is m} for any n, m ∈ ℕ,

which are the same as our earlier P_mn.

How about in ℝ? Here the topology is generated by basic sets of the form 

(a,b) = {x ∈ ℝ | a < x < b}  for any a, b ∈ ℚ

So we choose our atomic propositions accordingly: for any two rationals a,b, we have an atomic proposition P_ab, which we interpret as “a < x < b”.

Let’s pause to recall how we got here. We began by trying to define “definability”, and have found that there’s a natural way to interpret countable propositional logic through Borel sigma algebras on topological spaces. We have an atomic proposition for each (sub-)basic open set, and every set is defined by some countable propositional sentence. As we vary our interpretation of the atomic propositions, we move between different topological spaces. 

The question “can the prisoners coordinate on a strategy?” has now taken on a definite form: “is there a Borel subset of 2^ℕ that picks exactly one element from each equivalence class?” And it turns out that the answer is no! For the prisoners to coordinate on a choice function, they need more syntactic resources at hand than countable propositional logic.

(To be continued…)