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

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.