Descriptive set theory

Descriptive set theory studies definable subsets of spaces such as the real line and the Baire space of sequences. It relates how a set is described to its topological and measure-theoretic regularity.

The Borel sets arise from open sets by complements and countable unions. Projecting a Borel set produces an analytic set, which need not be Borel. For example, the set of infinite sequences that admit a witness sequence satisfying a Borel condition is naturally analytic: the witness is an existentially quantified real. The subject gives precise complexity hierarchies for such definitions and connects regularity with infinite games of perfect information and determinacy.

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 choosing an action from the current full game state rather than from the entire prior history. In a finite reachability game, the first-entry rank in the winning fixed-point iteration gives such a strategy by choosing a successor of smaller rank. The state must include all information affecting legal moves, such as ownership of reversible assignments and the player to 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.

Assume the axiom of choice, and let $A\subseteq {\omega }^{\omega }$. Every such $A$ is $2^{{\aleph }_0}$-Suslin. To see this, use the elements of Baire space of sequences as labels. For each $a\in A$, put the nodeof length $n$ into a tree, including its prefixes. The label sequence repeats the same entire real $a$ at every position. An infinite branch therefore projects to that particular $a$, rather than merely to a limit of elements of $A$. The projection is exactly $A$.

A bijection between the label set ${\omega }^{\omega }$ and a cardinal of size $2^{{\aleph }_0}$ converts this into the usual Kappa-Suslin set representation. The well-ordering of the labels uses choice; without it, the real-labelled tree is still available but an ordinal-sized relabelling needs a separate hypothesis.

In ZFC, if $\kappa$ is an infinite cardinal number, every ${\kappa }^{+}$-Suslin set is a union of ${\kappa }^{+}$ many Kappa-Suslin sets. Let a tree $T$ on ${\kappa }^{+}\times \omega$ represent the set. Each branch uses only countably many ordinal labels, so its labels are bounded below ${\kappa }^{+}$, since the successor cardinal is regular in ZFC.

For each $\alpha <{\kappa }^{+}$ restrict $T$ to labels below $\alpha$. Since $|\alpha |\le \kappa$, its projection is a Kappa-Suslin set; taking their union recovers the original projection. The boundedness step requires $\mathrm{cf}({\kappa }^{+})>\omega$. It must not be used without a suitable choice or cofinality assumption in settings involving the axiom of determinacy.

In ZFC, every ${\aleph }_1$-Suslin set is a union of ${\aleph }_1$ many analytic sets. A branch through a representing tree uses a countable sequence of countable ordinals. That sequence is bounded below ${\omega }_1$, so restrict the labels successively below $\alpha <{\omega }_1$.

Each restricted label set is countable and can be encoded by natural numbers; its projection is therefore an analytic set. The union of these projections is the original set. This is the $\kappa ={\aleph }_0$ case of Successor-Suslin decomposition. The proof explicitly uses the uncountable cofinality of ${\omega }_1$ and countable recoding, hypotheses that need care without the axiom of choice.

The set of well-order codes $\mathrm{WF}\subseteq {\omega }^{\omega }$ consists of codes for strict well-orders $(D,R)$ on subsets $D\subseteq \omega$. The norm $\Vert x\Vert$ is their order type. Every countable ordinal, including finite ordinals and zero, has such a code.

For a coding convenient for games, ignore $x(0)$ as a tag. At coordinate $x(n+1)$ record the domain bit for $n$ and the finitely many relation bits $R(i,j)$ with $\max (i,j)=n$, in a fixed order. Read these bits from the binary expansion, ignoring unused higher bits. The code belongs to $\mathrm{WF}$ exactly when the decoded relation is a strict well-order of its decoded domain. This convention makes local recoding operations explicit and allows an arbitrary domain subset, rather than incorrectly requiring every well-order to have domain all of $\omega$.

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.

One explicit version of a Solovay rank-comparison game has Players I and II alternately choose natural numbers, producing $x,y\in {\omega }^{\omega }$. Declare that Player I wins exactly whenThus Player I must produce a valid well-order code whose rank is at least the rank of Player II's valid code. This payoff states the convention for invalid codes and for equality, which are part of the definition of the game.

Player II can win by producing the causal rank-raising map on well-order codes $S(x)$: a valid input gets rank $\Vert x\Vert +1$, and an invalid input already loses for Player I. Alternatively, if a strategy for Player I were winning, all its possible outputs would form an analytic set contained in $\mathrm{WF}$. The boundedness theorem for well-order codes bounds their ranks below a countable ordinal. Player II could simply play a code of a larger ordinal, contradicting that strategy. The game exposes how descriptive boundedness obstructs an online attempt to dominate every countable rank.

Using the coordinate convention in set of well-order codes, there is a causal map $S:{\omega }^{\omega }\to {\omega }^{\omega }$ that adds a new greatest element to the coded relation. Relabel every old element $n$ as $n+1$, adjoin $0$ to the domain, and place every old domain element below $0$. If $x\in \mathrm{WF}$, thenAdding a greatest element gives this successor rank; adding a least element would instead give $1+\Vert x\Vert$, which need not be larger for an infinite ordinal.

Set the unused tag $S(x)(0)=x(0)+1$, making $S(x)\ne x$ for every input. Coordinate1 records the new element0 and is constant. Coordinate $n+2$ records the relabelled old element $n+1$, its relations to earlier old elements, and its relation to the new greatest element; this uses only $x(n+1)$ and earlier input coordinates. Thus Player II can output $S(x)(m)$ immediately after seeing $x(m)$. Ill-foundedness of an old relation persists in its relabelled copy. This explicit coding justifies the online strategy in the Solovay rank-comparison game.

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.

The Friedman–Moschovakis coding game turns strategies into codes for sets of ordinals. An explicit ${\omega }_1$ instance makes its mechanism visible. Fix $A\subseteq {\omega }_1$. Let a real $y$ code a countable well-order together with a marked subset of its domain. Write $E(y,z)$ when the rank of the well-order code $z$ is the rank of a marked element in that coded order. A suitable $y$ can therefore code $A\cap \eta$ for any particular countable ordinal $\eta$.

Players I and II produce reals $x,y$. Player II wins if $x\notin \mathrm{WF}$, or if $y$ correctly codes membership in $A$ through rank $\Vert x\Vert$: for every $z\in \mathrm{WF}$ with $\Vert z\Vert \le \Vert x\Vert$,A winning strategy for Player I would produce only well-order codes. Its possible outputs form an analytic set, so their ranks are bounded by the boundedness theorem for well-order codes. Player II could then play one real coding $A$ through a larger countable rank, defeating the strategy. Under the axiom of determinacy, Player II consequently has a winning strategy.

Such a strategy determines at most one $A$: play any code of an ordinal $\xi$ against it and inspect its response at rank $\xi$. Strategies themselves are coded by reals, giving the coding consequence for subsets of ${\omega }_1$. The general Friedman–Moschovakis coding lemma replaces these countable-order codes and analytic boundedness by the corresponding uniform coding and covering machinery; independently choosing unrelated codes for every initial segment does not supply that uniformity.^[ref]