Borel and Analytic Sets, Perfect Sets, and Determinacy

For any tree $T$ and $x\mathrm{\notin }[T]$, F2 gives $n$ with $x\upharpoonright n\mathrm{\notin }T$. If $y\in N_{x\upharpoonright n}$, it has that same excluded prefix, so $y\mathrm{\notin }[T]$. Thus each point of the complement has a basic neighbourhood in the complement, which proves $[T]$ closed. This includes $n=0$ and $T=\mathrm{\varnothing }$.

Suppose $F$ is closed. If $s\in T_F$, one witness $y\in F$ extending $s$ also extends every restriction of $s$. Thus $T_F$ is a tree. Each $y\in F$ has all its prefixes in $T_F$, so $F\subseteq [T_F]$.

Let $x\in [T_F]$. If $x\mathrm{\notin }F$, closedness and F1 give a cylinder $N_{x\upharpoonright n}$ disjoint from $F$. But $x\upharpoonright n\in T_F$ has an extending witness $y\in F$, a contradiction to this disjointness. Therefore $[T_F]\subseteq F$, and equality follows.

If $F=\mathrm{\varnothing }$, no prefix has a witness and $T_F=\mathrm{\varnothing }$. If $F\mathrm{\ne }\mathrm{\varnothing }$, its empty prefix belongs to $T_F$. For each individual $s\in T_F$, a witness $y$ extends it to $y\upharpoonright (\mathrm{\mid }s\mathrm{\mid }+1)\in T_F$, proving pruning. These are separate existential deductions at each node, not a simultaneous choice of witnesses. Together with the closed-body implication this establishes both directions and all additional claims. QED.

A basic neighbourhood of $(x,y)$ contains $N_{x\upharpoonright k}\times N_{y\upharpoonright l}$ for some $k,l$. Setting $n=\max (k,l)$ gives a contained product of equal-length cylinders. If $(x,y)\mathrm{\notin }[T]$, some paired prefix of length $n$ is absent; every point of that product cylinder has the same absent prefix. The complement of $[T]$ is therefore open, precisely as in the argument for F3.

Conversely, for closed $F\subseteq \mathcal{N}\times \mathcal{N}$, put $T=\{(x\upharpoonright n,y\upharpoonright n):(x,y)\in F,n\in \mathbb{N}\}$. Restrictions of witnessed pairs have the same witness, so $T$ is a synchronous tree and $F\subseteq [T]$. A point of $[T]\setminus F$ would have an equal-length product cylinder disjoint from $F$ by step 1.1's neighbourhood observation, but its paired prefix in $T$ supplies a point of $F$ in that cylinder. Thus $[T]=F$. For $F=\mathrm{\varnothing }$ the constructed tree is empty.

If $A$ is analytic, choose its one closed witness $F$ and apply step 2.1 to obtain $A=p[T]$. Conversely, if $A=p[T]$, step 1.1 makes $[T]$ a closed witness for analyticity. These choices concern one asserted witness and do not require AC.

For each fixed $x$, restricting a pair in $T$ proves prefix closure of $T_x$. For any $y$, the assertions $y\upharpoonright n\in T_x$ for all $n$ and $(x\upharpoonright n,y\upharpoonright n)\in T$ for all $n$ are identical. Existence of such $y$ is exactly $x\in p[T]=A$, proving the section equivalence. QED.

For open $U$ put $F_n=\{x:(\mathrm{\forall }y\mathrm{\notin }U)d(x,y)\ge 1\mathrm{/}(n+1)\}$. Each $F_n$ is closed: if $d(x,y)<1\mathrm{/}(n+1)$ for one $y\mathrm{\notin }U$, every point within $1\mathrm{/}(n+1)-d(x,y)$ of $x$ has the same strict inequality, by the triangle inequality. Also $F_n\subseteq U$, since $x\mathrm{\notin }U$ permits $y=x$. If $x\in U$, some ball of radius $r>0$ about $x$ lies in $U$; take $n$ with $1\mathrm{/}(n+1)\le r$ to get $x\in F_n$. Hence $U={\bigcup }_n{F}_n$. For $U=X$ the universal condition is vacuous and $F_n=X$; for $U=\mathrm{\varnothing }$ every $F_n$ is empty.

We prove the operations by F3, simultaneously at each positive rank. At rank one, opens are closed under arbitrary unions and finite intersections, and closed sets have the dual operations. Suppose the assertion holds below $\alpha >1$. Given $A_i\in {\mathrm{\Sigma }}_{\alpha }^0$, A1 chooses sequences $B_{ij}\in {\mathrm{\Pi }}_{{\beta }_{ij}}^0$, $1\le {\beta }_{ij}<\alpha$, with $A_i={\bigcup }_j{B}_{ij}$. The explicit diagonal enumeration of ${\mathbb{N}}^2$ turns ${\bigcup }_i{A}_i={\bigcup }_{i,j}{B}_{ij}$ into an allowed representation, proving countable-union closure.

We first prove the inclusions directly. If $1<\alpha <\beta$, every lower-$\mathrm{\Pi }$ representation allowed for ${\mathrm{\Sigma }}_{\alpha }^0$ is allowed for ${\mathrm{\Sigma }}_{\beta }^0$. For $\alpha =1<\beta$, step 1.1 supplies a representation using ${\mathrm{\Pi }}_1^0$, so the same inclusion holds. Complementing gives ${\mathrm{\Pi }}_{\alpha }^0\subseteq {\mathrm{\Pi }}_{\beta }^0$. A constant sequence represents every ${\mathrm{\Pi }}_{\alpha }^0$ set as a ${\mathrm{\Sigma }}_{\beta }^0$ set. Complementing that inclusion gives ${\mathrm{\Sigma }}_{\alpha }^0\subseteq {\mathrm{\Pi }}_{\beta }^0$. Together these are the displayed inclusion in ${\mathrm{\Delta }}_{\beta }^0$.

For two such sets, $A_0\cap A_1={\bigcup }_{i,j}(B_{0i}\cap B_{1j})$. Put $\gamma =\max ({\beta }_{0i},{\beta }_{1j})<\alpha$. Step 2.1 raises both sets to ${\mathrm{\Pi }}_{\gamma }^0$, and the earlier-rank assertion gives their intersection in ${\mathrm{\Pi }}_{\gamma }^0$ (repeat either set to view the intersection as countable). Thus the displayed union belongs to ${\mathrm{\Sigma }}_{\alpha }^0$. Iteration proves finite intersections. The empty intersection is $X$, which is in every class by F1.

De Morgan's identities transfer the two $\mathrm{\Sigma }$ closure assertions to the two $\mathrm{\Pi }$ assertions at the same rank, completing the progressive step of F3. A finite union or intersection of sets in both classes remains in both, by these assertions; complement interchanges their two memberships. The empty finite union is $\mathrm{\varnothing }$ and the empty finite intersection is $X$. This proves all claims, including empty $X$, at every positive countable rank. QED.

On any function $h$ on the children of $s$, replace values not in $\mathcal{P}(X)$ by $\mathrm{\varnothing }$, then apply the operation specified by the label at $s$. This is a definable, single-valued, total rule returning a subset of $X$. The child relation is well-founded by F1 and setlike because $T$ is a set. F2 therefore supplies a set function $E$ on $T$ satisfying the rule. Every value is a subset of $X$, so no replacement of an actual value occurs, and the displayed equations hold.

If $E^{\mathrm{\prime }}$ is another evaluation agreeing with $E$ at the children of $s$, the relevant union, complement, or fixed leaf value is identical, so $E^{\mathrm{\prime }}(s)=E(s)$. This property is progressive, and F3 proves equality at all nodes. For Borelness, leaves are basis opens, a complement of a Borel set is Borel, and a union node uses the sequence indexed by $k\in \mathbb{N}$, filling absent children by $\mathrm{\varnothing }$. Borelness is therefore progressive too; F3 proves it at every node.

Let $\mathcal{H}$ be the set of root values of valid codes. A single leaf codes each $U_n$. For any open $V$, give a union root one child $(n)$ labelled leaf$(n)$ for each $n$ such that $U_n\subseteq V$. Its evaluation is $\bigcup \{U_n:U_n\subseteq V\}=V$ by the basis property. This includes $V=\mathrm{\varnothing }$ and an empty union. The tree has height at most one and hence is well-founded: a nonempty subset containing a child has that child minimal; otherwise its root is minimal.

From a code $(T,l)$ for $B$, form $T^{\mathrm{\prime }}=\{\mathrm{\varnothing }\}\cup \{(0{)}^{⌢}s:s\in T\}$, put a complement label at its root and copy all other labels. It codes $X\setminus B$. For a sequence $(B_n)$ in $\mathcal{H}$, the sets of codes for the respective $B_n$ are nonempty subsets of the one set of all labelled trees. A1 selects $(T_n,l_n)$ for all $n$. The tree $T^{\mathrm{\prime }\mathrm{\prime }}=\{\mathrm{\varnothing }\}\cup \{(n{)}^{⌢}s:n\in \mathbb{N},s\in T_n\}$, with union root and inherited labels, codes ${\bigcup }_n{B}_n$.

Both graftings in step 2.3 are well-founded. Given a nonempty subset meeting a tagged constituent subtree, take a minimal element of its intersection with that one subtree. Every child of that element is still in that subtree, so it is minimal in the whole subset. If no constituent subtree is met, the subset consists of the root. Thus the graftings are valid codes. By steps 2.2–2.3, $\mathcal{H}$ contains all opens and is closed under complement and countable union; it therefore contains $\mathcal{B}(X)$. Step 2.1 gives the reverse inclusion. This proves the converse under AC and completes the claims, including $X=\mathrm{\varnothing }$. QED.

Symmetry and separation of $d$ follow from the first differing coordinate. If $x,y$ and $y,z$ both agree through the first $n$ coordinates, so do $x,z$. Consequently $d(x,z)\le \max (d(x,y),d(y,z))\le d(x,y)+d(y,z)$, proving the metric law. For $n\ge 1$, $N_{x\upharpoonright n}=\{y:d(x,y)<2^{-n}\}$, so the metric induces precisely the cylinders. A Cauchy sequence has each coordinate eventually constant: use the Cauchy bound $2^{-k-1}$ for coordinate $k$. Define $x(k)$ to be that unique eventual value. The Cauchy bound at $2^{-n}$ shows all sufficiently late terms agree with $x$ on the first $n$ coordinates, hence converge to $x$. In the binary case each value remains binary.

Let $\mathcal{U}$ be an open cover of $\mathcal{C}$. If no finite subfamily covers it, the root cylinder is not finitely covered. Whenever $N_s$ is not finitely covered, at least one of $N_{s^{⌢}0},N_{s^{⌢}1}$ is not finitely covered: otherwise combine their two finite covers. Recursively take the least such bit. The resulting $x$ lies in some $U\in \mathcal{U}$, and openness gives $N_{x\upharpoonright n}\subseteq U$ for some $n$, contradicting the construction. Hence every cover has a finite subcover, as F3 requires. Only least choices from two bits were used.

The displayed pairing is a bijection ${\mathbb{N}}^2\to \mathbb{N}$: on diagonal $i+j=r$ its values are the consecutive integers from $r(r+1)\mathrm{/}2$ to $(r+1)(r+2)\mathrm{/}2-1$, and the diagonals partition $\mathbb{N}$. Define $H(x{)}_i(j)=x(⟨i,j⟩)$. Its inverse assigns $x(⟨i,j⟩)=z_i(j)$, so both compositions are identities coordinate by coordinate. A finite restriction on either side constrains finitely many coordinates on the other; at each point a long enough initial cylinder fixes all those coordinates. Thus both directions are continuous by F4, in the binary case as well.

Each block in $h$ ends in $1$ and has positive length, so $h(x)\in D$. Conversely for $z\in D$, let $p_n$ be the position of its $n$th $1$, indexed starting at zero, obtained by successive least search. Put $x(0)=p_0$ and $x(n+1)=p_{n+1}-p_n-1$. These are natural numbers and the block concatenation reconstructs $z$. Reading block lengths from $h(x)$ returns $x$, giving a two-sided inverse. Fixing enough input coordinates to finish the first $k$ output bits proves continuity of $h$; fixing through the $k$th separator proves continuity of its inverse on $D$.

Finite words admit an explicit natural-number coding: encode a finite word by its length and recursively pair its entries, using $⟨i,j⟩=(i+j)(i+j+1)\mathrm{/}2+j$. Appending infinitely many zeros gives a countable family meeting every cylinder in either space. Thus they are separable; combined with step 1.1 this proves Polishness. Given any binary cylinder containing $x$, change the next unrestricted bit of $x$ and keep all other bits. The resulting different point is in the same cylinder, so no point is isolated.

If $z\mathrm{\notin }D$, it has only finitely many $1$s. Associate the integer $c(z)={\sum }_{j:z(j)=1}{2}^j$. Distinct finite binary supports give distinct sums: at their largest differing index $r$, the term $2^r$ exceeds the sum ${\sum }_{j<r}{2}^j=2^r-1$. Thus $c$ is an injection into $\mathbb{N}$, with the zero sequence mapped to zero. This proves the countability assertion and completes all constructions. QED.

By F5, every rank lies in $\mathcal{B}(X)$: rank one consists of opens; the progressive step takes complements and countable unions of earlier Borel sets. Write $H$ for the union in the statement. If $A\in {\mathrm{\Sigma }}_{\alpha }^0$, then $X\setminus A\in {\mathrm{\Pi }}_{\alpha }^0\subseteq {\mathrm{\Sigma }}_{\alpha +1}^0$, the latter inclusion using a constant sequence. Thus $H$ is closed under complements.

Let $f:X\to Z$ be continuous. For open $U\subseteq Z$, every point of $f^{-1}[U]$ has an open neighbourhood inside that preimage by F3; their union proves it open. Induct on the rank by F5. For a represented union $A={\bigcup }_n{B}_n$, $f^{-1}[A]={\bigcup }_n{f}^{-1}[B_n]$, and the induction hypotheses place each preimage in its original lower $\mathrm{\Pi }$ rank. Also $f^{-1}[Z\setminus A]=X\setminus f^{-1}[A]$. These identities prove both classes at the next rank. Membership in both gives the $\mathrm{\Delta }$ assertion, without selecting any representations simultaneously.

Given $A_n\in H$, let ${\alpha }_n$ be its least positive $\mathrm{\Sigma }$ rank. The preceding complement argument applied twice gives $A_n\in {\mathrm{\Pi }}_{{\alpha }_n+1}^0$. By F2 and A1, $\delta ={\sup }_n({\alpha }_n+2)<{\omega }_1$, and each ${\alpha }_n+1<\delta$. Hence ${\bigcup }_n{A}_n\in {\mathrm{\Sigma }}_{\delta }^0$. The empty union is $\mathrm{\varnothing }\in {\mathrm{\Sigma }}_1^0$. Thus $H$ is a sigma-algebra containing the opens and so contains $\mathcal{B}(X)$ by its leastness; step 1.1 gives equality.

For the inclusion $i:Y\to X$, $i^{-1}[U]=Y\cap U$ is open by F4, so $i$ is continuous and step 1.2 gives one trace inclusion. Conversely induct by F5. Opens lift by F4. If $B={\bigcup }_n{B}_n\in {\mathrm{\Sigma }}_{\alpha }^0(Y)$ with lower-$\mathrm{\Pi }$ constituents, each $B_n$ has an ambient lift in its own rank by induction. Their sets of lifts are nonempty subsets of $\mathcal{P}(X)$; A1 chooses lifts $C_n$. Then ${\bigcup }_n{C}_n\in {\mathrm{\Sigma }}_{\alpha }^0(X)$ has trace $B$. If $B=Y\setminus D$ is ${\mathrm{\Pi }}_{\alpha }^0$, lift $D$ to $C$ and use $X\setminus C$, whose trace is $B$. This proves the reverse inclusion in both classes. For $Y=\mathrm{\varnothing }$ the same identities apply, with $\mathrm{\varnothing }$ an available lift throughout. QED.

If $X$ is nonempty, fix a countable dense sequence. Balls at its centres of positive rational radii form a countable basis: for $x\in O$ choose $ϵ>0$ with $B(x,ϵ)\subseteq O$, a centre within $ϵ\mathrm{/}4$ of $x$ and a rational radius between that distance and $ϵ\mathrm{/}2$. This ball contains $x$ and is inside $O$ by the triangle inequality. Enumerate this basis as $W_n$; if $X=\mathrm{\varnothing }$ take all $W_n=\mathrm{\varnothing }$. Set $U_1={\bigcup }_n\{c:c(n)=1\}\times W_n$. This is open by F4. For open $O$, the parameter $c(n)=1$ iff $W_n\subseteq O$ has section exactly $O$ by the basis property. Put $V_1=(\mathcal{C}\times X)\setminus U_1$; its sections exhaust the closed sets.

For each countable $\alpha >1$ choose a nondecreasing positive sequence ${\beta }_n^{\alpha }<\alpha$ with ${\sup }_n({\beta }_n^{\alpha }+1)=\alpha$. At successor $\alpha =\gamma +1$ take constant $\gamma$. At a limit enumerate its ordinals and take the maximum of $1$ and the first $n+1$ listed ordinals; finite maxima stay below the limit and are cofinal. These choices form a set-indexed family, so A1 applies. Recursively, using F5, set

Suppose $B={\bigcup }_j{B}_j$ with $B_j\in {\mathrm{\Pi }}_{{\gamma }_j}^0(X)$ and $1\le {\gamma }_j<\alpha$. Recursively choose $n_j>n_{j-1}$ least with ${\beta }_{n_j}^{\alpha }\ge {\gamma }_j$. Such indices occur arbitrarily late: otherwise the nondecreasing sequence would be bounded below ${\gamma }_j$, contradicting its cofinal property. By F1 place $B_j$ in rank ${\beta }_{n_j}^{\alpha }$, and place the empty set at every unused index. Inductive universality and A1 select a parameter for each of these sets; F3 codes this parameter sequence as $c$. Then $(U_{\alpha }{)}_c={\bigcup }_j{B}_j=B$. Complementation proves universality of $V_{\alpha }$. This proves the recursive universality assertion, including the empty set, without matching the original jth rank to the jth cofinal rank.

Apply this to $X=\mathcal{C}$ and put $D=\{c:(c,c)\mathrm{\notin }{U}_{\alpha }\}$. The diagonal is continuous since the preimage of a basic product $O\times P$ is $O\cap P$, so F2 gives $D\in {\mathrm{\Pi }}_{\alpha }^0$. If $D\in {\mathrm{\Sigma }}_{\alpha }^0$, universality gives $d$ with $D=(U_{\alpha }{)}_d$. At $d$ this says $d\in D$ iff $(d,d)\in U_{\alpha }$ iff $d\mathrm{\notin }D$, impossible. The complement of $D$ lies in the opposite difference.

Let $Y\subseteq Z$ be homeomorphic to $\mathcal{C}$ and $Z$ metrizable. By F2 the homeomorphism and its inverse preserve both classes, so step 3.1 supplies $D_Y\in {\mathrm{\Pi }}_{\alpha }^0(Y)\setminus {\mathrm{\Sigma }}_{\alpha }^0(Y)$. F2 lifts $D_Y$ to a ${\mathrm{\Pi }}_{\alpha }^0(Z)$ set $D_Z$. Were $D_Z$ also ${\mathrm{\Sigma }}_{\alpha }^0(Z)$, its trace would contradict the choice of $D_Y$. Thus $D_Z$ lies in the required difference, and its complement proves the dual difference. QED.

All strategies in all fixed-history subgames are subsets of a fixed set of position/move pairs. A1 selects legal default moves at all nonterminal positions, and a winning reachability strategy ${\sigma }_p$ for each $p\in W_P$, from its nonempty set of such strategies. A terminal position belongs to $W_P$ exactly when its label is taboo for $Q$: the already finished play is the only maximal play.

At a nonterminal $P$-position $p\in W_P$, the first move of ${\sigma }_p$ chooses a child $q$; restricting the strategy beyond that move proves $q\in W_P$. Conversely if a child $q\in W_P$ exists, choose that move and then follow ${\sigma }_q$, with defaults elsewhere. Every consistent maximal play then reaches a $Q$ taboo. Thus the some-child equivalence holds.

At a nonterminal $Q$-position $p\in W_P$, the opponent may choose any child; restricting ${\sigma }_p$ after each such choice shows every child belongs to $W_P$. Conversely, if every child belongs to $W_P$, after the opponent's first move to $q$ use the already selected ${\sigma }_q$. Each consistent play follows one fixed winning continuation and thus terminates at a $Q$ taboo. This proves the every-child equivalence, without requiring a uniform time bound.

If $p\in W_I\cap W_{II}$, follow the two respective winning strategies from the fixed history $p$. At each nonterminal stage the parity determines one prescribed legal move. Recursion F2, stopping at a terminal node if one occurs, yields a unique maximal play; if no terminal is reached, the union of its prefixes is an infinite branch. This play is consistent with both strategies, so each strategy forces it to terminate at a taboo for its opponent. A terminal cannot have both labels by F1. Hence the intersection is empty, and all assertions follow. QED.

A root in $W_P$ has a strategy reaching an opponent taboo, which wins for $P$ independently of $A$. Otherwise the root belongs to $S$, and the all-prefix definition makes $S$ prefix closed. A node of $S$ cannot be terminal in $T$, since each terminal is winning for the player opposite its label.

At $p\in S$, suppose $P$ is to move and $Q$ is the other player. No child is in $W_P$, since the some-child implication would put $p$ in $W_P$. Some child is outside $W_Q$, since otherwise the every-child implication would put $p$ in $W_Q$. This child avoids both sets, and all its earlier prefixes are prefixes of $p$; hence it belongs to $S$. Thus $S$ is pruned.

Let $\sigma$ win for $P$ on $S$. Follow it as long as play stays in $S$. If the opponent $Q$ first exits at child $q$ of $p\in S$, then $q\mathrm{\notin }{W}_Q$ by the some-child clause at the $Q$-position $p$. Since this is the first exit, the only failing prefix is $q$ itself, so $q\in W_P$. Switch to the fixed $P$ reachability strategy at $q$. A1 provides default legal moves after any first inconsistent own move, making the strategy total without affecting consistent plays.

A consistent play that exits therefore terminates at an opponent taboo. A consistent play that never exits cannot terminate by step 1.1, so is a branch of $S$; its payoff membership is unchanged by replacing $A$ with $A\cap [S]$, and $\sigma$ wins it. This proves the strategy transfer for either player.

A cylinder of $[T]$ restricts to the corresponding cylinder of $[S]$, so opens restrict to opens. Moreover $([T]\setminus B)\cap [S]=[S]\setminus (B\cap [S])$ and $({\bigcup }_n{B}_n)\cap [S]={\bigcup }_n(B_n\cap [S])$. Induction over any positive-rank complement/union expression therefore preserves its Borel level, at limits as well as successors. Applying the hypothesized pruned-tree determinacy and step 4.1 proves the taboo direction; the reverse takes a pruned tree with both taboo sets empty. QED.

Let $U=\{p:[T{]}_p\subseteq B\}$, and let $W$ be the positions from which $P$ has a strategy forcing a visit to $U$ at a finite time, allowing time zero. Strategy sets and the set of positions are sets; A1 fixes one such strategy for each $p\in W$ and fixes default legal moves. Every branch in $B$ has a prefix in $U$ by openness and F1.

At $p\mathrm{\notin }U$, if $P$ moves and $p\in W$, the strategy's first chosen child is in $W$ by restriction. Conversely a child in $W$ lets $P$ choose it and follow its selected strategy. If $Q$ moves and $p\in W$, restriction after every possible first opponent move makes all children belong to $W$. Conversely, if all children are in $W$, following the selected continuation for the child the opponent chooses forces a visit. Thus outside $W$, every child of a $P$-node avoids $W$, and at least one child of a $Q$-node avoids $W$.

If the initial position is in $W$, its selected strategy reaches $U$, and every continued branch lies in $B$ because it extends that visited node. If the initial position is outside $W$, use A1 to choose an avoiding child at each $Q$-node outside $W$ and defaults elsewhere. By step 2.1 every consistent branch remains outside $W$ and therefore outside $U$. Step 1.1 shows it is outside $B$. In this case $Q$ wins. This reasoning refers to the actual player at each node, so it also works after either parity of fixed history.

If the specified I payoff is closed, its complement is an open II payoff; apply step 3.1 with $P=II$, retaining the original turn parity. Finally F2 reduces a taboo game to either an already winning reachability case or a pruned residual game; cylinder restriction preserves open and closed sets. Applying the proved pruned result and F2 completes both cases. QED.