Descriptive set theory

Descriptive set theory studies definable subsets of spaces such as the Baire space of sequences, with particular emphasis on hierarchies of complexity, regularity properties and infinite games.

The set-theoretic Baire space is ${\omega }^{\omega }$, the set of all infinite sequences of natural numbers, with the product topology obtained from discrete $\omega$.

For $A\subseteq M^{\omega }$, the game $G(A)$ has two players alternately choose elements of the move set $M$, producing $x\in M^{\omega }$. Player I wins exactly when $x\in A$. Both players see the whole finite position before making each move.

A covering consists of a new game tree, a length-preserving prefix map to the original tree, and maps taking strategies of each player to strategies of that same player. Every play following a projected strategy lifts to a play following the original strategy, with identical projection or a premature terminal loss for that strategy's player. Terminal outcomes inherited from the original tree are respected. The strategy maps are local in depth. These conditions transfer every winning strategy, for any payoff pulled back by the prefix map. A $k$-covering leaves all positions, outcomes and strategy choices through depth $k$ unchanged.

In a sequence of game coverings whose unchanged initial depths tend to infinity, each finite game-tree level eventually stabilizes. These stable levels form a limit game. Compositions of prefix projections and depth-local strategy maps give limit projections and strategy maps. Lift a compatible play coherently through successive coverings. If no premature loss occurs, stabilization of its finite prefixes supplies a compatible limit play. If a premature loss occurs, subsequent lift lengths cannot increase and eventually stabilize, supplying a losing terminal limit play. This proves the lifting condition for the limit covering. It makes countably many pulled-back payoffs clopen simultaneously in the covering proof of Borel determinacy theorem.

A covering of an infinite game unravels a payoff when its inverse image is a clopen subset of the new infinite-play space. A closed payoff can be unravelled by letting Player I announce a subset of the first exit positions, and letting Player II accept that announcement or challenge one announced position. Accepted plays stop at exit positions, while challenged plays are forced through the challenged exit. Strategy-transfer maps make this more than an ordinary continuous representation of the payoff. Depth-stabilizing inverse limits of coverings handle countable unions in a transfinite induction.

After a fixed even-depth prefix, Player I announces a move and a set $X$ of first exit positions from a closed set of infinite plays. Player II accepts, or challenges an exit $r\in X$. Acceptance follows the old game until the first exit, where I wins exactly when that exit belongs to $X$. A challenge forces play through $r$ and then resumes the old game. Infinite accepted plays remain in the closed payoff; infinite challenged plays are outside it. Thus the pulled-back payoff is clopen. For an I-strategy, transfer by initially accepting and switching to the challenged simulation at an exit in $X$. For an II-strategy, announce the set of exits that this strategy never challenges under any announcement; it must accept this set. An exit outside it permits a challenged simulation, while an exit inside it is a premature loss for II. These maps prove the game covering lifting condition, rather than merely continuity of the projection.

In a turn-based game on a set of positions, Player I wins if the play visits a specified set $F$ infinitely often. Such games are determined even on infinite arenas. With $\mathrm{Pre}(X)$ meaning positions where I can force the next position into $X$, the winning region is the greatest fixed point of $X\mapsto \mu Y((F\cap \mathrm{Pre}(X))\cup \mathrm{Pre}(Y))$. Inner ordinal ranks force the next visit; outer removal ranks give Player II only finitely many visits outside the winning region.

A strategy assigns one legal move to every finite position at which its player is to move. A play follows the strategy when every move of that player is the assigned move.

A strategy is winning when every play that follows it is won by its player.

An infinite game of perfect information is determined when one of its two players has a winning strategy in an infinite game.

Every infinite game of perfect information on a set-sized move alphabet with a Borel payoff in its discrete product topology has a winning strategy in an infinite game for one player. A proof strengthens the induction hypothesis to existence of arbitrary-depth-preserving game coverings unravelling the payoff. The closed-set announcement construction starts the induction. For countable unions, successive coverings stabilize each finite level and their inverse limit makes every constituent payoff clopen; their union is open and can be unravelled once more.

With the axiom of choice, enumerate both players' binary-move strategies in an infinite game in length $\mathfrak{c}$. Each strategy admits $\mathfrak{c}$ compatible plays. At stage $\alpha$, reserve a fresh play following I's strategy as a loss for I, and a fresh play following II's strategy as a win for I. Avoid all previously reserved plays, which number less than $\mathfrak{c}$. The collection of the second reservations is a payoff set against which neither player has a winning strategy in an infinite game. This uses no regularity assumption on $\mathfrak{c}$.

An infinite game of perfect information with an open set of winning plays for I in the product topology on a discrete move set has a winning strategy in an infinite game for one player. Construct a winning-position attractor in an infinite game by transfinite recursion; ranks give I a terminating descent strategy inside it, and its complement gives II a strategy avoiding every winning prefix. The move set need not be countable, in the usual set theory with axiom of choice.

Allow terminal positions of an infinite game of perfect information to carry a losing-player label. A clopen set of infinite winning plays still gives a determined infinite game. At a position where all infinite continuations have one winner, the other player can win only by forcing a terminal loss for that winner. The usual winning-position attractor in an infinite game decides this reachability game. The tree of remaining undecided positions is well-founded: every infinite branch would eventually have its clopen payoff decided by a prefix. Assign the already decided winners upwards by well-founded recursion. Terminal labels are essential; a terminal node created by a covering need not be lost by the player whose turn would have come next.

Start with positions whose entire extension cylinder set lies in the winning open set. At each successor stage add I-positions with some successor already present and II-positions with every successor already present; take unions at limit ordinals. The stable set is the least fixed point of this order-preserving operation. The first entry ordinal supplies a strictly decreasing rank until the winning prefix is reached.

The axiom of determinacy states that every game $G(A)$ with $A\subseteq {\omega }^{\omega }$ is determined. Its version for a move set $M$ is denoted ${\mathsf{AD}}_M$.

Projective determinacy states that every infinite game of perfect information whose payoff is a projective set is determined.

A quasistrategy assigns a nonempty set of allowed moves to every position at which its player moves. It is winning when every play consistent with those allowed moves is won by that player.

An infinite game of perfect information is quasidetermined when one of the players has a winning quasistrategy. Choosing one allowed move at every relevant position refines a winning quasistrategy to a winning strategy in an infinite game whenever the required restricted choice principle holds.

For every move set $M$, the statement that every quasidetermined subset of $M^{\omega }$ is determined is equivalent in ZF to ${\mathsf{AC}}_{M^{<\omega }}(M)$. The forward direction encodes an arbitrary family of nonempty subsets of $M$ into a quasidetermined game; the reverse direction chooses one move from each value of a winning quasistrategy.

For $A\subseteq X\times Y$, a uniformization is a function $f$ on the projection of $A$ to $X$ such that $(x,f(x))\in A$ for every $x$ in that projection. It chooses one witness from every nonempty vertical section of $A$.

Under ${\mathsf{AD}}_X$, every relation $A\subseteq X\times X$ has a uniformization. Let the first moves of Players I and II be $x$ and $y$, and let II win when $x$ is outside the projection of $A$ or $(x,y)\in A$. Player I cannot have a winning strategy, so the first response of a winning strategy for II uniformizes $A$.

A pointclass is a collection of subsets of topological spaces, usually specified by a common definability or closure condition.

An analytic subset of a Polish space is a continuous image of a Borel set, equivalently a projection of a closed subset of its product with the Baire space of sequences.

A coanalytic set is the complement of an analytic set.

The projective hierarchy starts with the Borel sets and repeatedly applies projection and complementation. Its members are the projective sets.

A projective set belongs to some finite level of the projective hierarchy.

A subset of a Polish space has the perfect set property when it is countable or contains a nonempty perfect subset. Every uncountable analytic set contains a perfect subset and consequently has cardinality $2^{{\aleph }_0}$.

Let $T\subseteq (X\times \omega {)}^{<\omega }$ be a tree. Its projection isThe tree $T$ is a Suslin representation of $p[T]$.

A set $A\subseteq {\omega }^{\omega }$ is $X$-Suslin when $A=p[T]$ for a tree $T\subseteq (X\times \omega {)}^{<\omega }$.

A $\kappa$-Suslin set is an $X$-Suslin set with $X=\kappa$. If $X$ injects into $Y$, relabelling a Suslin representation shows that every $X$-Suslin set is $Y$-Suslin.

Every $A\subseteq {\omega }^{\omega }$ is $2^{{\aleph }_0}$-Suslin. Give each $a\in A$ its own label and use the tree of finite pairs $(a\upharpoonright n,a\upharpoonright n)$, then relabel the first coordinate by an injection into a set of size $2^{{\aleph }_0}$.

For an infinite cardinal number $\kappa$, every ${\kappa }^{+}$-Suslin set is a union of ${\kappa }^{+}$ many $\kappa$-Suslin sets. A countable sequence of ordinals below the successor cardinal ${\kappa }^{+}$ is bounded there, so restrict the representing tree successively to labels below each $\alpha <{\kappa }^{+}$.

Every ${\aleph }_1$-Suslin set is a union of ${\aleph }_1$ analytic sets. Every countable sequence of countable ordinals is bounded below ${\omega }_1$, and after restricting all labels below one countable ordinal the first-coordinate space can be recoded by $\omega$.

The set $\mathrm{WF}\subseteq {\omega }^{\omega }$ consists of the reals coding well-orders of $\omega$. For $x\in \mathrm{WF}$, the norm $\Vert x\Vert$ is the order type of the well-order coded by $x$.

Every analytic set contained in $\mathrm{WF}$ has bounded rank: if $A\subseteq \mathrm{WF}$ is analytic, thenIn particular, the well-order codes produced continuously from all counterplays against one strategy have bounded ranks whenever they are all well-founded.

In the Solovay rank-comparison game, Players I and II produce $x,y\in {\omega }^{\omega }$; ill-founded codes lose before ranks are compared, and among well-order codes the prescribed inequality between $\Vert x\Vert$ and $\Vert y\Vert$ decides the winner. No strategy for Player I can uniformly produce a well-order code at least as long as every code produced by Player II.

There is a coordinatewise causal map $S:{\omega }^{\omega }\to {\omega }^{\omega }$ that recodes a relation after adjoining a new least element. If $x\in \mathrm{WF}$, then $S(x)\in \mathrm{WF}$ and $\Vert S(x)\Vert =\Vert x\Vert +1$; the tagged coding also ensures $S(x)\ne x$ when $x\notin \mathrm{WF}$. Because the first $n+1$ output coordinates depend only on the first $n+1$ input coordinates, Player II can produce $S(x)$ online.

An inner model $M$ is projectively well-ordered when there is a projective relation that well-orders the real numbers belonging to $M$.

For an inner model $M$, the ordinal ${\omega }_1^M$ is the least ordinal that $M$ regards as uncountable. Equivalently, it is the supremum of the order types of the well-order codes belonging to $M$. It can be countable in the ambient universe.

If $M$ is projectively well-ordered and projective determinacy holds, then ${\omega }_1^M$ is countable in the ambient universe. Otherwise, selecting with the projective well-order the least $M$-code for each countable ordinal produces an uncountable projective set of unique well-order codes. It has no perfect subset by the boundedness theorem for well-order codes, contradicting the perfect set property implied by projective determinacy.

Assume the axiom of determinacy. If $\lambda$ is a surjective image of the Baire space of sequences and, for every $\xi <\lambda$, the power set $\mathcal{P}(\xi )$ is a surjective image of that space, then $\mathcal{P}(\lambda )$ is also a surjective image of it.

For $A\subseteq \lambda$, the Friedman–Moschovakis coding game asks the players to present coherent local codes for initial segments $A\cap \xi$ while challenging each other at larger ordinals. The diagonal and boundedness argument rules out a winning strategy for Player I; a winning strategy for Player II determines at most one set $A$. Coding strategies by reals therefore gives a surjection from the Baire space of sequences onto $\mathcal{P}(\lambda )$.