Borel and Analytic Sets, Perfect Sets, and Determinacy: Examples and Counterexamples

Every closed subset $F$ of $\mathbb{R}$ is a countable intersection of open sets: if $F\mathrm{\ne }\mathrm{\varnothing }$, use $O_j={\bigcup }_{a\in F}(a-1\mathrm{/}(j+1),a+1\mathrm{/}(j+1))$. Points of $F$ belong to every $O_j$; a point outside $F$ has an interval disjoint from $F$, and hence misses $O_j$ for sufficiently large $j$. For $F=\mathrm{\varnothing }$ use the constant empty sequence. Consequently any countable intersection of open and closed sets is a countable intersection of open sets: replace each closed factor by this explicit sequence, leave an open factor as its constant sequence, and enumerate pairs of indices by finite diagonals. Such a set is ${\mathrm{\Pi }}_2^0$, since its complement is a countable union of closed sets. Therefore every set in the claimed class is ${\mathrm{\Sigma }}_3^0$.

The map $j$ in L3 constructs a Cantor copy in the real line. Put $K=j[\mathcal{C}]$ with its subspace topology. The real line is Hausdorff: two distinct reals $s,t$ have disjoint open intervals of radius $\mathrm{\mid }s-t\mathrm{\mid }\mathrm{/}3$ around them. The subspace $K$ is therefore also Hausdorff, by intersecting these separating intervals with $K$. As a map onto $K$, $j$ is a continuous bijection: for open $O$ in $\mathbb{R}$, the preimage of $K\cap O$ is $j^{-1}[O]$. L3 gives compactness of its domain, so L4 gives a homeomorphism $\mathcal{C}\to K$. L4 also makes $K$ compact and closed in $\mathbb{R}$. Thus this explicit ternary-series map supplies the required homeomorphic Cantor subset without choice.

By L2 and step 1.2 the hypotheses of L1 hold for $\mathbb{R}$, so choose $D\in {\mathrm{\Pi }}_3^0(\mathbb{R})\setminus {\mathrm{\Sigma }}_3^0(\mathbb{R})$. This is a Borel set: the first three ranks are obtained from opens by complements and countable unions, operations preserving the Borel sigma-algebra. Suppose the statement were true. It would place $D$ in the displayed class and thus, by step 1.1, in ${\mathrm{\Sigma }}_3^0$, contradicting its choice. Hence the statement is false. The only choice input is L1; the conversion in step 1.1 makes no simultaneous choices of representations.

Every putative branch of $\mathrm{\varnothing }$ would have to satisfy $y\upharpoonright 0=\mathrm{\varnothing }\in \mathrm{\varnothing }$, which is false. Hence $[\mathrm{\varnothing }]=\mathrm{\varnothing }$, a closed set.

Restricting $x\upharpoonright n$ to $m\le n$ gives $x\upharpoonright m\in T_x$, so $T_x$ is a tree. The point $x$ lies in its body. If $y\in [T_x]$, its prefix of length $k+1$ equals the unique member $x\upharpoonright (k+1)$ of $T_x$ of that length. Consequently $y(k)=x(k)$ for every $k$, giving $[T_x]=\{x\}$.

For $z(n)=0$, step 1.2 gives $y(k)=0$ at every coordinate, the claimed concrete calculation. If $y\mathrm{\ne }x$, choose one differing coordinate $k$; its cylinder of length $k+1$ excludes $x$. Thus the complement of $\{x\}$ is open, establishing the closedness assertion. QED.

Every $s^{⌢}0$ belongs to the full tree, so $\sigma$ is a legal strategy, including at $s=\mathrm{\varnothing }$. We have $A=N_{(0)}$ and $\mathcal{N}\setminus A={\bigcup }_{k\ge 1}{N}_{(k)}$, both open by F2. Hence $A$ is clopen.

Every branch consistent with $\sigma$ satisfies $x(0)=\sigma (\mathrm{\varnothing })=0$, so belongs to $A$. For example, if II always plays $1$, the unique compatible branch is $(0,1,0,1,\dots )$ and its first coordinate is $0$. The same first-coordinate calculation holds for every sequence of II moves, proving that $\sigma$ wins. QED.

Prefixes of $(1{)}^{⌢}{0}^n$ are the root or words $(1{)}^{⌢}{0}^m$ with $m\le n$, all listed in $T$. The only other nonempty word is $(0)$, whose sole proper prefix is the root. Thus $T$ is a nonempty tree. The node $(0)$ is terminal and every node on the other ray has the unique child obtained by appending $0$, verifying the asserted terminal partition.

At the root I can choose $0$ and reach the II taboo immediately. Below the child $(1)$ every legal continuation is forced and the only maximal continuation is the infinite sequence $(1,0,0,\dots )$. No continuation from that child reaches a terminal node. Neither player can therefore force an opponent terminal taboo there, although I can do so at its parent.

The proposed deletion removes the root by step 2.1 and retains $(1)$ by the same step. A set retaining $(1)$ but omitting its empty prefix is not a tree. This is the required witness against both the child assertion and the resulting deletion rule. QED.

F1 with A1 supplies A and F2 supplies e. Suppose e[A] were Borel in $\mathbb{R}$. By continuity of e, F3 with A1 would make $e^{-1}[e[A]]$ Borel in Baire space. This preimage equals A: if e(x)=e(a) for some a in A, injectivity gives x=a; conversely each a in A maps into e[A].

Then F4 with A1 would give a winning strategy for one player for payoff A, contradicting its defining property from F1. Hence e[A] is not Borel and is the required subset of the real line witnessing the failed assertion. QED.

Let $T_1=\{\mathrm{\varnothing }\}$ with root label leaf$(n)$. It is valid since it has no child and its empty relation is well-founded. F2 gives $E_1(\mathrm{\varnothing })=U_n$. For $T_2=\{\mathrm{\varnothing },(0)\}$ label the root complement and $(0)$ leaf$(n)$. Then $E_2((0))=U_n$ and $E_2(\mathrm{\varnothing })=X\setminus U_n$, which is closed because $U_n$ is open.

On $T_3=\{\mathrm{\varnothing }\}$ put a union label; then $E_3(\mathrm{\varnothing })=\bigcup \mathrm{\varnothing }=\mathrm{\varnothing }$. On $T_4=\{\mathrm{\varnothing },(0)\}$ put a complement at the root and a union at $(0)$. Then $E_4((0))=\mathrm{\varnothing }$ and $E_4(\mathrm{\varnothing })=X\setminus \mathrm{\varnothing }=X$.

In each two-node tree the sole child is terminal; any subset containing it has it as a minimal element, and a remaining nonempty subset is the singleton root. Thus the child relation is well-founded, and the complement nodes have exactly child zero as required. All four codes are valid even when $X=\mathrm{\varnothing }$ or $U_n$ is empty or all of $X$. The empty underlying tree is not one of these codes, because F1 requires a root. QED.