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 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.

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 )$.