6. clopen vs. finitely-determined

problem

1. Prove that every clopen subset of $𝒞$ is finitely determined.
2. Give an example of a clopen set in $𝒩≔ℕ^ℕ$ that is not finitely determined.

1. Suppose $S$ is a clopen subset of $𝒞$ but $S$ is not fd.

   finitely-determined means that there exists an $n∈ℕ$ so that membership does not depend on coordinates $≥n$, i.e., for all $x$, $x∈S ⟺ (x(0),…,x(n),0,0,…)∈S.$

   therefore to say $S$ is not fd means that for all $n∈ℕ$, there exist $x_n,x'_n$ sharing common prefix up to coordinate $n$, but $x_n∈S$ and $x'_n∉S$.

   in this way define two sequences of strings, $(x_n)_(n∈ℕ)$ and $(x'_n)_(n∈ℕ)$.

   also construct a string $x$ inductively as follows. for each $i=0,1,2,…$, pick $x(i)$ so that $(x(0),x(1),…,x(i))$ occurs as a prefix of infinitely many strings in the sequence $(x_n)_(n∈ℕ)$. each step this is possible by the fact that infinitely-many candidates remain (induction hypothesis), and the pigeonhole principle (among the two choices for the next digit, at least one of them occurs infinitely many times).

   at the same time, observe that each $x_n$ and $x'_n$ share the same prefix up to index $n$, so if $(x(0),…,x(i))$ is a prefix of $x_n$ then it also is a prefix of $x'_n$.

   by construction, each (finite) prefix of $x$ occurs infinitely many times in $x_n$, so there exists a subsequence of $x_n$ converging to $x$. as in, $x$ is a limit point of ${x_n}_(n∈ℕ)$. by the same reasoning $x$ is a limit point of ${x'_n}_(n∈ℕ)$.

   the former sequence is in $S$ and the latter in $S^∁$. by the hypothesis that $S$ is clopen, both $S$ and $S^∁$ are closed, so $x∈S∩S^∁$, a contradiction.

2. For each $n≥2$ let $S_n$ denote the set of strings that begin with $(n,n,…,n)$ (repeated $n$ times), and let $S=⋃_(n∈ℕ) S_n$.

   • $S$ is open: observe that $S_n=⋂_(i=0)^n ϕ_i^(-1) ({n})$ is open, and $S$ a union of $S_n$ is also open.

   • $S$ is closed: we will show that $S^∁$ is open. Fix $x∈S^∁$, and let $n=x(0)$. Consider two cases:

     • suppose $n∈{0,1}$. by construction $S$ doesn’t contain any strings starting with $0$ or $1$, so $x∈ϕ_0^(-1)({0,1})⊂S^∁$.
     • suppose $n≥2$. since $x∉S$ we know that there exists $k<n$ such that $x(k)≠n$. furthermore any string $y$ satisfying $y(0)=n$ and $y(k)≠n$ is not in $S$. so $x∈ϕ_0^(-1)({n})∩ϕ_k^(-1)({k})⊂S^∁$. in both cases we showed that $x$ is contained in some open set $U⊂S^∁$. thus $S^∁$ is open, i.e., $S$ is closed.

   • $S$ is not fd: fix any $n∈ℕ$. define $x_n (i) = (n+1) ⋅ 1_(i≤n) = (n+1,…,n+1,0,0,…)$ (with $n+1$ leading copies of $n+1$) and observe $x_n∈S$. next define $x'_n$ by setting only the digit at index $n+1$ to zero, and agreeing with $x_n$ everywhere else. observe $x'_n∉S$.

     then $x_n,x_n'$ share a prefix of length $n$ but $x_n∈S$ and $x'_n∉S$. since this holds for all $n$ we conclude $S$ is not f.d.