# 9.3 Descriptive Set Theory Descriptive set theory studies definable subsets of spaces such as the real line, the Baire space, and the Cantor space, and its main goal is to understand how the complexity of a set is related to the way the set can be described. The subject begins with topological spaces that are rich enough to support analysis but structured enough to allow precise classification, and the central examples are spaces whose points can be understood as infinite sequences, real numbers, functions, or codes for mathematical objects. ### Polish Spaces A Polish space is a topological space whose topology comes from a complete separable metric. Thus a space $X$ is Polish if there is a metric $d$ on $X$ such that: $$ d $$ induces the topology of $X$, every Cauchy sequence converges in $X$, and there is a countable dense subset of $X$. Polish spaces are important because they include most spaces used in classical analysis, while still having enough countability structure to support effective classification by definability. ### Example 9.48 The real line: $$ \mathbb{R} $$ with the usual metric is a Polish space. The Cantor space: $$ 2^\omega $$ is the space of all infinite binary sequences, and it is Polish with the product topology. The Baire space: $$ \omega^\omega $$ is the space of all functions from $\omega$ to $\omega$, and it is also Polish with the product topology. The space: $$ \mathbb{R}^n $$ is Polish for every natural number $n$, and many function spaces used in analysis are Polish after choosing the appropriate topology. ### Open and Closed Sets Let $X$ be a Polish space. A set $U \subseteq X$ is open if for every $x \in U$ there is an open ball around $x$ contained in $U$. A set $F \subseteq X$ is closed if its complement: $$ X \setminus F $$ is open. Open sets represent positive local information, because membership in an open set can be verified by finding a sufficiently small neighborhood. Closed sets represent negative local information, because nonmembership in a closed set can be verified by entering an open complement. ### Definition 9.49 (Borel Sets) Let $X$ be a Polish space. The Borel subsets of $X$ are the smallest collection of subsets of $X$ that contains all open sets and is closed under countable unions, countable intersections, and complements. The collection of all Borel subsets of $X$ is denoted: $$ \mathcal{B}(X) $$ Borel sets are the sets that can be built from open sets by applying countable set theoretic operations. ### Borel Hierarchy The Borel sets are organized into levels according to the number and type of operations needed to define them. The first levels are: $$ \Sigma^0_1 $$ for open sets, and: $$ \Pi^0_1 $$ for closed sets. After this, a set belongs to: $$ \Sigma^0_{n+1} $$ if it is a countable union of sets from: $$ \Pi^0_n $$ and a set belongs to: $$ \Pi^0_{n+1} $$ if it is a countable intersection of sets from: $$ \Sigma^0_n $$ A set belongs to: $$ \Delta^0_n $$ if it belongs to both: $$ \Sigma^0_n $$ and: $$ \Pi^0_n $$ This hierarchy measures the descriptive complexity of Borel sets. ### Example 9.50 Every open set is in: $$ \Sigma^0_1 $$ Every closed set is in: $$ \Pi^0_1 $$ A countable union of closed sets is called an $F_\sigma$ set and belongs to: $$ \Sigma^0_2 $$ A countable intersection of open sets is called a $G_\delta$ set and belongs to: $$ \Pi^0_2 $$ For example, the set of rational numbers: $$ \mathbb{Q} \subseteq \mathbb{R} $$ is countable, and each singleton is closed, so: $$ \mathbb{Q} $$ is an $F_\sigma$ set. ### Lemma 9.51 Every Borel subset of a Polish space is obtained at some countable stage of the Borel hierarchy. Proof The Borel sets are defined as the smallest collection containing the open sets and closed under countable unions and complements. Starting with the open sets, one constructs the hierarchy through countable ordinal stages. At successor stages one closes under countable unions and complements, and at limit stages one takes the union of all earlier stages. Because each operation used in the definition of Borel sets is countable, every particular Borel definition uses only countably many previous steps. Therefore every Borel set appears at some countable stage of the hierarchy. ### Continuous Images Let $X$ and $Y$ be Polish spaces. A function: $$ f:X\to Y $$ is continuous if for every open set $U\subseteq Y$, the inverse image: $$ f^{-1}(U) $$ is open in $X$. Continuous functions preserve topological information in a controlled way. In descriptive set theory, they are used to compare the complexity of sets and to define important classes beyond the Borel sets. ### Definition 9.52 (Analytic Sets) Let $X$ be a Polish space. A set $A\subseteq X$ is analytic if there exists a Polish space $Y$ and a Borel set: $$ B\subseteq X\times Y $$ such that: $$ A=\{x\in X:\exists y\in Y,\ (x,y)\in B\} $$ Equivalently, $A$ is analytic if it is the continuous image of a Borel subset of a Polish space. The class of analytic sets is denoted: $$ \Sigma^1_1 $$ Analytic sets arise naturally when a definition contains an existential quantifier over an infinite object. ### Example 9.53 Let: $$ T\subseteq \omega^{<\omega} $$ be a tree, meaning a set of finite sequences closed under initial segments. The set of trees with an infinite branch is analytic, because the assertion "there exists an infinite branch through $T$" has the form: $$ \exists f\in \omega^\omega \ \forall n \ (f{\upharpoonright}n\in T) $$ The quantified object $f$ is an infinite sequence, and the remaining condition is Borel. Thus analytic sets naturally describe problems where one asks for the existence of an infinite witness. ### Definition 9.54 (Coanalytic Sets) A set $A\subseteq X$ is coanalytic if its complement is analytic. The class of coanalytic sets is denoted: $$ \Pi^1_1 $$ Thus: $$ A\in \Pi^1_1 $$ if and only if: $$ X\setminus A\in \Sigma^1_1 $$ Coanalytic sets often express universal statements about infinite objects. ### Lemma 9.55 Every Borel set is analytic. Proof Let $A\subseteq X$ be Borel. Take $Y$ to be a one point Polish space, say: $$ Y=\{0\} $$ Then: $$ A\times \{0\} $$ is a Borel subset of: $$ X\times Y $$ and: $$ A=\{x\in X:\exists y\in Y,\ (x,y)\in A\times\{0\}\} $$ Thus $A$ is analytic. ### Theorem 9.56 (Suslin Theorem) A subset of a Polish space is Borel if and only if it is both analytic and coanalytic. In symbols: $$ \Delta^1_1 = \Sigma^1_1 \cap \Pi^1_1 $$ Proof First suppose $A$ is Borel. By Lemma 9.55, $A$ is analytic. Since the complement of a Borel set is Borel, the complement $X\setminus A$ is also analytic. Hence $A$ is coanalytic. Conversely, suppose $A$ is analytic and coanalytic. Then there are Borel descriptions of $A$ and of its complement by projection from suitable Polish spaces. The separation theorem for analytic sets says that if two disjoint analytic sets can be separated, then there is a Borel set separating them. Applying this to $A$ and $X\setminus A$ gives a Borel set $B$ such that: $$ A\subseteq B $$ and: $$ B\cap (X\setminus A)=\varnothing $$ The second condition implies: $$ B\subseteq A $$ Therefore: $$ A=B $$ and so $A$ is Borel. ### Projective Sets The projective hierarchy extends the analytic and coanalytic classes by alternating existential and universal quantification over reals. The first level is: $$ \Sigma^1_1 $$ the analytic sets. The dual class is: $$ \Pi^1_1 $$ the coanalytic sets. Higher levels are defined recursively. A set belongs to: $$ \Sigma^1_{n+1} $$ if it is the projection of a: $$ \Pi^1_n $$ set. A set belongs to: $$ \Pi^1_{n+1} $$ if its complement belongs to: $$ \Sigma^1_{n+1} $$ The projective hierarchy organizes sets according to the complexity of definitions using quantifiers over real numbers. ### Example 9.57 A typical analytic definition has the form: $$ x\in A \quad \text{if and only if} \quad \exists y\in \omega^\omega \ B(x,y) $$ where $B$ is Borel. A typical coanalytic definition has the form: $$ x\in A \quad \text{if and only if} \quad \forall y\in \omega^\omega \ B(x,y) $$ where $B$ is Borel. A typical: $$ \Sigma^1_2 $$ definition has the form: $$ x\in A \quad \text{if and only if} \quad \exists y\in \omega^\omega \forall z\in \omega^\omega \ B(x,y,z) $$ where $B$ is Borel. ### Regularity Properties A regularity property says that a definable set behaves like a well behaved measurable or topological set, even if arbitrary subsets of the real line may behave pathologically. The main regularity properties studied in descriptive set theory are the following. A set has the perfect set property if it is either countable or contains a nonempty perfect subset. A set has the Baire property if it differs from an open set by a meager set. A set is Lebesgue measurable if it can be assigned a Lebesgue measure in the usual complete measure algebra. These properties hold for all Borel sets and all analytic sets, but they may fail for arbitrary sets of reals in the presence of the axiom of choice. ### Definition 9.58 (Perfect Set Property) A subset $A\subseteq \mathbb{R}$ has the perfect set property if either $A$ is countable or there exists a nonempty perfect set: $$ P\subseteq A $$ A perfect set is a closed set with no isolated points. The perfect set property implies that an uncountable definable set of reals has size continuum, because every nonempty perfect subset of $\mathbb{R}$ has cardinality: $$ 2^{\aleph_0} $$ ### Theorem 9.59 Every uncountable analytic subset of a Polish space contains a nonempty perfect subset. Proof Let $A\subseteq X$ be analytic and uncountable. Since $A$ is analytic, there is a closed set: $$ C\subseteq \omega^\omega $$ and a continuous function: $$ f:C\to X $$ such that: $$ f[C]=A $$ One analyzes the closed set $C$ through its associated tree of finite approximations. If the image $f[C]$ is uncountable, then the tree must contain enough splitting to build a perfect subtree. A perfect subtree gives a continuous injection from: $$ 2^\omega $$ into: $$ A $$ or at least into a subset of $A$ after restricting to appropriate branches. The image of this perfect set under the continuous map gives a nonempty perfect subset of $A$, after passing to a suitable closed subset on which the map behaves injectively. Thus $A$ contains a perfect subset. ### Definition 9.60 (Baire Property) A set $A\subseteq X$ has the Baire property if there exists an open set $U\subseteq X$ such that: $$ A \triangle U $$ is meager. Here: $$ A \triangle U = (A\setminus U)\cup(U\setminus A) $$ is the symmetric difference. A set is meager if it is a countable union of nowhere dense sets. The Baire property says that $A$ is equal to an open set up to a topologically small error. ### Definition 9.61 (Lebesgue Measurability) A set $A\subseteq \mathbb{R}$ is Lebesgue measurable if it belongs to the completion of the Borel sigma algebra with respect to Lebesgue measure. Equivalently, $A$ is Lebesgue measurable if for every set $E\subseteq \mathbb{R}$: $$ m^*(E)=m^*(E\cap A)+m^*(E\setminus A) $$ where $m^*$ is outer measure. Lebesgue measurability says that $A$ can be assigned a length, area, or measure in a way compatible with countable additivity. ### Theorem 9.62 Every analytic subset of a Polish space has the Baire property, and every analytic subset of $\mathbb{R}$ is Lebesgue measurable. Proof We explain the main idea. Analytic sets are continuous images of Borel sets. Borel sets have the Baire property and are Lebesgue measurable in the real case. Although continuous images do not preserve all Borel structure, analytic sets still admit sufficiently regular approximations by Borel sets. For the Baire property, one uses the fact that analytic sets can be approximated by open sets modulo meager error through the Suslin operation. For Lebesgue measurability, one uses the projection theorem and regularity of Borel measures on Polish spaces to show that analytic projections remain measurable. The detailed proof requires the machinery of capacibility or classical regularity theorems, but the conclusion is that analytic definability prevents the pathological behavior possible for arbitrary sets of reals. ### Complete Sets A set at a given level of complexity is complete if every set at that level can be reduced to it by a sufficiently simple function, usually a continuous function. ### Definition 9.63 (Continuous Reduction) Let $A\subseteq X$ and $B\subseteq Y$, where $X$ and $Y$ are Polish spaces. We say that $A$ is continuously reducible to $B$, written: $$ A \leq_W B $$ if there exists a continuous function: $$ f:X\to Y $$ such that for all $x\in X$: $$ x\in A \quad \text{if and only if} \quad f(x)\in B $$ This means that membership in $A$ can be transformed continuously into membership in $B$. ### Definition 9.64 (Complete Analytic Set) An analytic set $A$ is complete analytic if every analytic set is continuously reducible to $A`. Equivalently, $A$ is among the most complex analytic sets. A complete analytic set cannot be Borel, because if it were Borel, then every analytic set would reduce to a Borel set in a way that would collapse the distinction between Borel and analytic complexity. ### Example 9.65 The set of ill founded trees on $\omega$ is complete analytic. Let: $$ \mathrm{IF}=\{T\subseteq \omega^{<\omega}: T \text{ has an infinite branch}\} $$ The condition that $T$ has an infinite branch can be written as: $$ \exists f\in \omega^\omega \ \forall n \ (f{\upharpoonright}n\in T) $$ which is analytic. Moreover, every analytic set can be coded as the set of parameters for which a corresponding tree has an infinite branch. Thus $\mathrm{IF}$ is complete analytic. ### Descriptive Set Theory and Forcing Descriptive set theory interacts strongly with forcing because forcing often adds new reals, changes the structure of sets of reals, and helps analyze the regularity properties of definable sets. For example, forcing can be used to build models in which certain projective sets have regularity properties, or models in which certain definable well orderings of the reals exist. Large cardinals also influence descriptive set theory. Strong large cardinal assumptions imply strong regularity properties for projective sets, especially when combined with determinacy principles. ### The Role of Definability The central distinction in descriptive set theory is between arbitrary sets and definable sets. Arbitrary subsets of: $$ \mathbb{R} $$ can be extremely pathological, especially under the axiom of choice. Definable sets such as Borel, analytic, coanalytic, and projective sets are much more structured. Descriptive set theory therefore provides a bridge between topology, measure theory, logic, and set theory by studying how definability controls mathematical behavior.