proof that "reasonably defined" sets in $2^\mathbb{Z}/{\sim}$ have measure $1$ or $0$

Question

I am basing this question on the slides: http://math.yorku.ca/~moliver/how.pdf

One is given the set of doubly infinite strings of $0$ and $1$ whose origin is forgotten which is the set of equivalence classes of the functions $\mathbb{Z}\rightarrow \{0,1\}$ where two strings are equivalent if one is the translation by some integer of the other. What measure $2^\mathbb{Z}$ is not completely clear but the author assumes that singletons have measure zero and given $n\in \mathbb{Z}$ the measure of the set $A^1_n =\{f:\mathbb{Z}\rightarrow \{0,1\} : f(n)=0\}$ is $1/2$ and that $A^i_n$ and $A^j_m$ where $i,j\in \{0,1\}$ and $n\neq m$ are independent.

The claim is made that if a set is "reasonably definable" and the set is closed under translation, or rather if $g\in A$ and $f\sim g$ then $f\in A$ such a set must have measure $1$ or $0$. So my question is

1. What is the natural measure on $2^\mathbb{Z}$ ?
2. What is meant by "reasonably defined"? (my guess is a set that is definable in $ZF$)
3. A proof or a reference to the fact that such sets have measure $0$ or $1$?

Answer 1

The natural measure on $\mathcal{X}=\{0,1\}^\mathbb{Z}$ is basically the (appropriately tweaked) Lebesgue measure. Precisely:

• For each finite $A\subseteq\mathbb{Z}$ and each $p:A\rightarrow\{0,1\}$, let $[p]=\{f\in \mathcal{X}: f\upharpoonright A=p\}$. The sets of the form $[p]$ for some such $p$ are the basic (cl)opens of $\mathcal{X}$.

• Say that the diameter $diam([p])$ of a basic clopen $[p]$ is just $2^{-\vert dom(p)\vert}$. Note that in case $dom(p)$ is a singleton, this agrees with what you've written in the question.

• Finally, given an arbitrary $E\subseteq\mathcal{X}$ we can define the outer measure $\mu^*(E)$ as the infimum, over all covers $\mathcal{C}$ of $E$ by basic clopens, of the sum of the diameters of the elements of $\mathcal{C}$.

A subset $E$ of $\mathcal{X}$, then, is measureable iff it satisfies Caratheodory's criterion: $$\forall A\subseteq\mathcal{X}[\mu^*(A)=\mu^*(A\cap E)+\mu^*(A\setminus E)].$$ (There are various equivalent definitions, but I like this one.)

---

Now as with Lebesgue measure in $\mathbb{R}$, there are a variety of results of the form "every 'reasonably definable' set is measurable." For example, we can show that every Borel set is measurable (note that this isn't trivial using the definition of measurability above!), and that it's relatively consistent with $\mathsf{ZF+DC+}$ "There is an inaccessible cardinal" that every subset of $\mathcal{X}$ is measurable. Your guess in part (ii) of the question is therefore pointing in the right direction (although it's not really grammatically correct - there are a lot of surprising subtleties around the idea of a theory defining a set, and it's ultimately best to abandon such language altogether in my opinion).

The theorem you ask about, then, is really a combination of the previous paragraph (which is admittedly a bit vague) and the following result:

$(*)\quad$ Every measurable translation-invariant subset $E$ of $\mathcal{X}$ has $\mu^*(E)\in\{0,1\}$.

That is, the definability is really only relevant insofar as it gives us measurability. If you're willing to restrict attention to measurable sets at the outset, you don't need to mention definability at all; conversely, if you're willing to blackbox some logic, you can get away assuming this zero-one law without thinking about measure theory at all.

Proving $(*)$ is a good exercise. Here's a hint (which I'll phrase in terms of $\mathbb{R}$ rather than $\mathcal{X}$ for clarity): if $E$ is measurable and has intermediate measure, we can find a pair of intervals $U,V$ such that $E$ is "big" everywhere in $U$ and $E^c$ is "big" everywhere in $V$. Now what happens when I translate $\mathbb{R}$ so that $U$ overlaps with $V$?