Fact-checked by Grok 2 weeks ago

Descriptive set theory

Descriptive set theory is a branch of that investigates the definable subsets of Polish spaces—separable completely metrizable topological spaces such as the real numbers—and their topological, measure-theoretic, and set-theoretic properties, with a focus on regularity phenomena that avoid pathologies arising from the . It classifies these sets according to their descriptive complexity, starting from basic open and closed sets and building hierarchies through countable unions, intersections, complements, and projections. The foundational objects of study in descriptive set theory are Polish spaces, which include familiar examples like \mathbb{R}^n, the $2^\mathbb{N}, and the \mathbb{N}^\mathbb{N}, all equipped with topologies that admit complete metrics. Borel sets form the starting point of the hierarchy: they are the smallest \sigma-algebra containing the open sets, generated by transfinite iterations of countable unions and complements up to countable ordinals, and classified into levels \Sigma^0_\alpha, \Pi^0_\alpha, and \Delta^0_\alpha for \alpha < \omega_1. Beyond Borel sets lies the projective hierarchy, obtained by iterating projections (existential quantifiers over the reals) and complements: the first level includes analytic sets (\Sigma^1_1, projections of Borel sets) and co-analytic sets (\Pi^1_1, their complements), with higher levels \Sigma^1_n and \Pi^1_n for n \geq 2. Historically, descriptive set theory emerged in the early 20th century amid efforts to understand measurable functions and sets, with pioneering contributions from (who introduced in 1898), , and (whose 1905 work on highlighted issues with measurability). The field crystallized in the 1920s through 's 1917 discovery of (initially called "sets of type \mathfrak{A}") and subsequent work by and on , addressing paradoxes like non-Borel . Mid-20th-century developments integrated recursion theory and infinitary games, influenced by , , and later and , while modern extensions explore connections to forcing, inner models, and large cardinals. Key results underscore the theory's emphasis on "good behavior": Suslin's theorem establishes that Borel sets are precisely the \Delta^1_1 sets (analytic with analytic complements), and uncountable Borel and analytic sets contain perfect subsets of cardinality $2^{\aleph_0} by the perfect set theorem. Under the axiom of projective determinacy (PD), all projective sets are Lebesgue measurable, have the , and satisfy uniformization and scale properties, enabling applications in harmonic analysis, ergodic theory, and the classification of Polish group actions via . These insights reveal deep structural uniformities in the continuum, bridging descriptive complexity with foundational questions in set theory.

Foundations

Polish spaces

Polish spaces form the foundational topological framework for descriptive set theory, providing a class of spaces where Borel structures and regularity properties can be effectively studied. A Polish space is defined as a separable completely metrizable topological space, meaning it admits a compatible metric that is complete and has a countable dense subset. This definition ensures that the space is rich enough to support countable bases while avoiding pathologies that complicate analysis. The term "Polish space" was proposed by Roger Godement in 1949, as a member of the Bourbaki group, reflecting the contributions of the Polish school of mathematics to the field. Prominent examples of Polish spaces include finite-dimensional Euclidean spaces \mathbb{R}^n for n \in \mathbb{N}, which are equipped with the standard metric and rational points as a countable dense subset. Infinite-dimensional instances encompass the Baire space \omega^\omega, consisting of all sequences of natural numbers with the product topology, and the Cantor space $2^\omega, the set of infinite binary sequences, both of which are zero-dimensional and compact in the latter case. Further examples are the Hilbert space \ell^2 of square-summable real sequences and more generally any separable Banach space, where completeness arises from the norm metric and separability from a countable dense set like rational combinations of basis elements. Key topological properties of Polish spaces include second-countability, which follows from the separability of the metric, allowing a countable basis for the topology. They are inherently metrizable, with the given complete metric inducing the topology, and this completeness guarantees that every Cauchy sequence converges within the space. Every Polish space possesses a countable dense subset, and the space itself serves as the metric completion of this subset under the induced metric, highlighting their constructive nature. A universal embedding property states that every Polish space is homeomorphic to a G_\delta subset of the [0,1]^\mathbb{N}, which itself is a compact Polish space; this fact, due to Lavrentiev's theorem combined with embedding results, underscores the uniformity of Polish spaces up to homeomorphism.

Standard Borel spaces

In the context of Polish spaces, which provide a separable completely metrizable topology essential for generating measurable structures, the Borel σ-algebra is defined as the smallest σ-algebra on the space that contains all open sets. This σ-algebra, denoted \mathcal{B}(X) for a Polish space X, is generated by taking countable unions, intersections, and complements of open sets, ensuring a rich yet controlled collection of measurable subsets suitable for descriptive set theory. A standard Borel space is a measurable space (X, \mathcal{A}) that is isomorphic to the Borel σ-algebra of a Polish space, meaning there exists a bijection f: X \to Y between X and a Polish space Y such that both f and its inverse map Borel sets to Borel sets. Equivalently, it can be realized as a Borel subset of a Polish space equipped with the subspace Borel σ-algebra. This isomorphism preserves the measurable structure, making standard Borel spaces a canonical framework for studying Borel measurability independent of specific topologies. Standard Borel spaces exhibit strong universality properties: every uncountable standard Borel space has cardinality $2^{\aleph_0}, the cardinality of the continuum, and is Borel-isomorphic to \mathbb{R} equipped with its Borel σ-algebra. The Borel isomorphism theorem states that two standard Borel spaces are Borel-isomorphic if and only if they have the same cardinality. For uncountable cases, this implies all such spaces are isomorphic to each other, underscoring their structural uniformity. Countable standard Borel spaces are classified up to Borel isomorphism solely by their cardinality, as any countable set equipped with its power set σ-algebra forms a standard Borel space, and isomorphisms between them are determined by bijective correspondences. This classification highlights the discrete nature of countable cases, contrasting with the continuum-rich uncountable ones.

Borel Sets

Borel hierarchy

The Borel hierarchy provides a transfinite classification of the Borel sets in a topological space, stratifying them according to the complexity of the operations needed to generate them from the open sets. This hierarchy is defined by transfinite induction on countable ordinals and captures the generative structure of the Borel σ-algebra. In Polish spaces, it plays a central role in by distinguishing levels of descriptive complexity within the Borel class. The hierarchy begins with the base levels: the class \Sigma^0_1 consists of all open sets, while \Pi^0_1 consists of all closed sets, which are the complements of open sets. For successor ordinals, \Sigma^0_{\alpha+1} is the collection of all countable unions of sets from \Pi^0_\alpha, and \Pi^0_{\alpha+1} is the collection of all countable intersections of sets from \Sigma^0_\alpha. At limit ordinals \lambda, the classes are defined cumulatively: \Sigma^0_\lambda = \bigcup_{\alpha < \lambda} \Sigma^0_\alpha and \Pi^0_\lambda = \bigcup_{\alpha < \lambda} \Pi^0_\alpha. The ambiguous classes at each level are given by \Delta^0_\alpha = \Sigma^0_\alpha \cap \Pi^0_\alpha, which include sets that can be represented in both existential and universal forms at that level of complexity. This inductive construction, originally systematized by , ensures that each level builds upon the previous ones through Boolean operations restricted to countable arity. The full class of Borel sets coincides with \bigcup_{\alpha < \omega_1} \Sigma^0_\alpha = \bigcup_{\alpha < \omega_1} \Pi^0_\alpha = \bigcup_{\alpha < \omega_1} \Delta^0_\alpha, where \omega_1 is the first uncountable ordinal; thus, every Borel set belongs to some \Delta^0_\alpha for a countable ordinal \alpha < \omega_1. In uncountable Polish spaces, the hierarchy is strict, meaning that for each countable ordinal \alpha < \omega_1, there exists a set in \Sigma^0_{\alpha+1} \setminus \Delta^0_\alpha, ensuring that the levels are properly increasing and no Borel set requires more than countably many iterations to generate. The Borel sets exhibit several key closure properties that reflect their generative nature. They are closed under complements (since \Pi^0_\alpha = \mathrm{co}\text{-}\Sigma^0_\alpha), countable unions, and countable intersections. Additionally, the class of Borel sets is closed under continuous preimages: for any continuous function f: X \to Y between topological spaces and any Borel set B \subseteq Y, the preimage f^{-1}(B) is Borel in X. The Borel class is also the smallest family containing the open sets and closed under these operations, though applying more general operations like the Souslin operation (countable unions over countable intersections indexed by trees) to Borel sets can produce non-Borel analytic sets.

Regularity properties of Borel sets

Borel sets exhibit several fundamental regularity properties that distinguish them from more general subsets of Polish spaces. These properties ensure that Borel sets behave well with respect to measure, category, and selection principles, making them central to classical descriptive set theory. In particular, every Borel subset of Euclidean space \mathbb{R}^n is Lebesgue measurable. This follows from the construction of Lebesgue measure, where open sets (which generate the Borel \sigma-algebra) are measurable, and the class of measurable sets is closed under countable unions, intersections, and complements, thereby including all Borel sets. A cornerstone regularity property is the perfect set theorem for Borel sets. Every uncountable Borel set in a Polish space contains a perfect subset, and thus has cardinality $2^{\aleph_0}, the cardinality of the continuum. This result, often called the perfect set property, arises from the Cantor-Bendixson analysis extended to the Borel hierarchy: the iterative derivative process, applied countably many times due to the countable length of the hierarchy, separates any Borel set into a countable scattered part and a perfect kernel. If the set is uncountable, the perfect kernel must be non-empty. In addition to measure-theoretic regularity, Borel sets possess the property of Baire. Every Borel set B in a Polish space differs from an open set by a meager (first-category) set, meaning there exists an open set U such that the symmetric difference B \Delta U is meager. This categorial regularity complements Lebesgue measurability and holds because Borel sets are constructed from open sets via operations that preserve the . Furthermore, Borel sets are Ramsey measurable: in the context of on infinite sets, every Borel subset of [N]^N (the space of infinite subsets of naturals) is either Ramsey null or has the Ramsey property, allowing selective partition properties without pathological behavior. These categorial and combinatorial properties underscore the "tame" nature of Borel sets. The capacity for selection without full axiom of choice is another key feature. Under dependent choice (DC), a weaker form of the axiom of choice sufficient for much of , points can be selected from sequences of non-empty sets. More generally, theorems like the guarantee measurable selectors for closed-valued Borel multifunctions. These alternatives to full AC ensure that Borel sets support constructive choice principles, avoiding non-measurable pathologies.

Analytic and Coanalytic Sets

Definitions and constructions

Analytic sets, denoted by \Sigma^1_1, form a central class in descriptive set theory, extending beyond the Borel hierarchy in Polish spaces. In a Polish space X, a set A \subseteq X is analytic if it is the continuous image of a Borel subset of another Polish space Y. Equivalently, A is the projection onto X of a Borel subset of the product space X \times Y, where Y is Polish. These definitions capture sets arising naturally from projections in analysis, such as those appearing in the study of solutions to differential equations or functional equations. A foundational construction of analytic sets employs the Suslin operation, introduced by Mikhail Suslin in his 1917 investigation of projections of Borel sets. For a sequence of subsets \{B_\sigma \subseteq X : \sigma \in {}^\mathbb{N}\langle \mathbb{N} \rangle\}, where {}^\mathbb{N}\langle \mathbb{N} \rangle denotes the set of finite sequences of natural numbers, the Suslin operation \Theta(\{B_\sigma\}) is defined as \Theta(\{B_\sigma\}) = \bigcup_{f \in \mathbb{N}^\mathbb{N}} \bigcap_{n \in \mathbb{N}} B_{f \upharpoonright n}, where f \upharpoonright n is the restriction of f to its first n values. When each B_\sigma is closed, \Theta(\{B_\sigma\}) yields an analytic set; moreover, every analytic set admits such a representation starting from closed sets. This operation highlights the tree-like structure underlying analytic sets, linking them to well-founded trees on the Baire space \mathbb{N}^\mathbb{N}. Coanalytic sets, denoted by \Pi^1_1, are defined as the complements of analytic sets in Polish spaces. Thus, if A \subseteq X is analytic, then X \setminus A is coanalytic. This class includes sets like the set of ill-founded trees on \mathbb{N}^\mathbb{N}, which are precisely the complements of well-founded trees defining certain analytic sets. Coanalytic sets share many regularity properties with analytic sets but exhibit distinct behaviors under axioms like the axiom of determinacy. In Polish spaces, every analytic set is the image of the Baire space \mathbb{N}^\mathbb{N} under a continuous function. This representation underscores the role of the Baire space as a "universal" domain for generating analytic sets via continuous maps, facilitating uniform treatments in proofs of regularity properties. A key structural fact is the existence of a universal analytic set, which parametrizes all analytic sets in a given Polish space. Specifically, there exists an analytic set U \subseteq [0,1] \times X such that every analytic subset A \subseteq X is of the form A = \{x \in X : (r, x) \in U\} for some r \in [0,1]. This universal set encodes the complexity of the entire \Sigma^1_1 class up to continuous preimages, enabling reductions and completeness arguments in the theory.

Separation and reduction principles

One of the fundamental results concerning analytic and coanalytic sets is the separation principle, which highlights their structural properties relative to Borel sets. The Lusin separation theorem asserts that if A and B are disjoint analytic subsets of a Polish space X, then there exists a Borel set C \subseteq X such that A \subseteq C and B \cap C = \emptyset. This theorem, originally proved by Nikolai Lusin in 1927, demonstrates that analytic sets can be separated by sets of lower complexity, unlike arbitrary sets where such separation may fail. A symmetric result holds for coanalytic sets: if A and B are disjoint coanalytic subsets of X, then there exists a Borel set C \subseteq X such that A \subseteq C and B \cap C = \emptyset. This follows by applying the separation theorem to the complements, which are disjoint analytic sets, and complementing the resulting Borel separator. Complementing the separation principle is the reduction property, which provides a way to refine disjoint analytic sets while preserving their union. The Lusin reduction theorem states that if A and B are disjoint analytic subsets of a Polish space X, then there exist analytic sets A' \subseteq A and B' \subseteq B such that A' \cap B' = \emptyset and A' \cup B' = A \cup B. This theorem, also due to , implies that the analytic sets are closed under a form of Boolean operations that satisfy more strongly, but it underscores the closure properties specific to analytic sets. Unlike , however, the class of analytic sets is not closed under complements; there exist analytic sets that are not , and consequently, their complements are coanalytic but not analytic. A canonical example of an analytic non-Borel set is constructed via diagonalization over the . Consider the space of , which parametrize all in a Polish space; one can define an analytic set consisting of those codes whose corresponding contains a fixed point, leading to a contradiction for and thus non-Borel analyticity. Uniformization principles further distinguish analytic and coanalytic sets from . For a relation R \subseteq X \times Y that is analytic, there exists an analytic uniformizer S \subseteq R such that for every x \in X with R_x \neq \emptyset, the section S_x is a singleton. This holds in , while uniformization by does not hold in general for . For coanalytic relations R \subseteq X \times Y, Kondo's uniformization theorem guarantees an analytic uniformizer in . However, achieving for analytic relations generally requires additional axioms such as (PD).

Projective Hierarchy

Projective sets

The projective hierarchy extends the Borel hierarchy by incorporating projections over the reals, generating increasingly complex classes of sets in Polish spaces. The base level consists of the analytic sets, denoted Σ¹₁, which are the projections of Borel subsets of X × ℝ for a Polish space X, and the coanalytic sets, denoted Π¹₁, which are their complements. For higher levels, a subset A ⊆ X belongs to Σ¹_{n+1} if it is the projection onto X of some set B ⊆ X × ℝ in Π¹_n; equivalently, A = {x ∈ X | ∃ y ∈ ℝ (x, y) ∈ B} where B ∈ Π¹_n(X × ℝ). The classes Π¹_{n+1} are defined as the complements of Σ¹_{n+1}, and the sets Δ¹_n = Σ¹_n ∩ Π¹_n form the ambiguous sets at level n. The projective sets are the union over all finite n of the Σ¹_n (or equivalently, the Δ¹_n) classes. The notation distinguishes between boldface and lightface versions of these classes. Boldface classes (often denoted with tildes, like Σ̃¹_n) allow arbitrary real parameters in their definitions, emphasizing topological properties in uncountable Polish spaces. Lightface classes (Σ¹_n without tildes) restrict to parameter-free definitions, typically involving effective or recursive constructions over countable structures like the naturals. In the constructible universe V = L, the projective sets coincide with the Δ¹₃ sets (the hierarchy collapses at level 3), whereas in general models of ZFC, non-projective sets exist beyond these finite levels. The collection of all projective sets forms a σ-algebra, meaning it is closed under countable unions, countable intersections, and complements. It is also closed under continuous preimages and images, reflecting the preservation of definability under continuous functions. However, individual pointclasses like Σ¹_{2k+1} are not closed under complements, as their complements fall into Π¹_{2k+1}. A representative example of a Σ¹₂ set is the collection of constructible reals, {x ∈ ℕ^ℕ | x ∈ L}, where L is Gödel's constructible universe; this set arises as an existential quantification over a coanalytic condition verifying constructibility. Another illustrative Σ¹₂ set involves trees on the naturals: the branches through certain trees whose well-founded parts are coanalytic can define sets like those encoding countable ordinals via existential projection over coanalytic tree properties. The finite-level projective hierarchy can be extended to transfinite levels using scales or uniformization under suitable axioms, and under sufficient determinacy assumptions, this extended hierarchy has length ω₁, stabilizing such that all projective sets appear by level ω₁.

Projective determinacy

Projective determinacy (PD) asserts that for every projective set A \subseteq \omega^\omega, the associated Gale-Stewart game—played on the Polish space \omega^\omega by two players alternately choosing natural numbers to build an infinite sequence x \in \omega^\omega, with Player I winning if x \in A and Player II winning otherwise—is determined, meaning either Player I or Player II has a winning strategy. These infinite games of perfect information extend the classical framework to higher descriptive complexity, where the payoff set A belongs to the projective hierarchy. The proof of PD relies on axioms extending ZFC, particularly large cardinal hypotheses. Assuming the existence of infinitely many Woodin cardinals, Martin and Steel established PD by constructing iterable inner models (mice) containing the relevant projective sets and verifying the existence of winning strategies via fine-structural analysis and iterability arguments. This approach calibrates the consistency strength: for instance, the determinacy of sets at the nth projective level follows from n Woodin cardinals, culminating in full PD with infinitely many. Equivalently, PD holds in the inner model L(\mathbb{R}) under the axiom of determinacy (AD), where strategies are definable over the reals, though establishing AD itself demands even stronger large cardinals, such as a measurable cardinal above infinitely many Woodins. PD has profound implications for the regularity of projective sets. Every projective set is Lebesgue measurable, has the property of Baire, and satisfies the perfect set property: it is either countable or contains a perfect subset, ensuring no projective set of reals has cardinality between \aleph_0 and the continuum without embedding a copy of $2^\omega. Additionally, PD implies projective uniformization: for any projective relation R \subseteq X \times Y with X, Y Polish spaces, there exists a projective function f: \{x \in X \mid \exists y (x,y) \in R\} \to Y such that (x, f(x)) \in R for all x in the domain. For the projective pointclasses, PD yields scale properties: each \mathbf{\Sigma}^1_n pointclass admits projective scales, which are \mathbf{\Sigma}^1_n prewellorderings of unbounded length in the reals, facilitating uniformization and reduction principles across the hierarchy. While the full axiom of determinacy AD implies PD by restricting to projective payoffs, AD contradicts the axiom of choice and requires substantially stronger consistency strength, consistent relative to the existence of a supercompact cardinal. In contrast, while \Delta^1_1 (Borel) determinacy follows from ZFC alone via Martin's theorem, determinacy for higher projective levels requires large cardinal hypotheses.

Wadge Theory

Wadge degrees

In descriptive set theory, the Wadge reducibility provides a fine-grained measure of complexity for subsets of Polish spaces, particularly the Baire space \omega^\omega or the Cantor space $2^\omega. For subsets A, B \subseteq X where X is a Polish space, A \leq_W B if there exists a continuous function f: X \to X such that A = f^{-1}(B). This relation captures how the descriptive complexity of A can be "reduced" to that of B via continuous preimages, extending beyond the coarser unions and intersections of the Borel hierarchy. The equivalence relation A \equiv_W B holds if A \leq_W B and B \leq_W A, partitioning the power set into Wadge degrees, which are the equivalence classes under \equiv_W. These degrees form a partial order under the induced ordering from \leq_W, classifying sets up to continuous reducibility and providing a hierarchy that refines both the Borel and projective hierarchies. For Borel and analytic sets, this ordering yields a complete classification, where each degree corresponds to a unique level of continuous complexity. A foundational result, known as Wadge's lemma, states that for any Borel sets A, B \subseteq \omega^\omega, either A \leq_W B or B \leq_W \omega^\omega \setminus A. This dichotomy implies that the Wadge degrees of Borel sets form a well-ordering, with the Borel fragment comprising a initial segment of the full hierarchy. Under the axiom of determinacy (AD), the lemma extends to all subsets of \omega^\omega, ensuring the entire Wadge hierarchy is well-founded and linear except for antichains of length at most 2; the length of this full hierarchy is the ordinal \Theta, the supremum of ordinals surjective onto the reals. In ZFC alone, the Borel Wadge degrees form a well-order of length \varepsilon_0 \cdot \omega_1, where \varepsilon_0 is the least fixed point of the exponential function on ordinals and \omega_1 is the first uncountable ordinal, vastly exceeding the length \omega_1 of the standard Borel hierarchy. Wadge degrees are classified as self-dual if \deg_W(A) = \deg_W(\omega^\omega \setminus A), meaning the degree is invariant under complementation, or form non-self-dual pairs otherwise, where \deg_W(A) and \deg_W(\omega^\omega \setminus A) are distinct but incomparable except through the dichotomy. Self-dual degrees correspond to levels where sets are continuously equivalent to their complements, often arising in the "true" or diagonal levels of the hierarchy, while non-self-dual pairs appear in asymmetric positions, such as q_\mu and its complement for limit ordinals \mu. The self-dual Borel degrees alone form a well-order of type \varepsilon(\omega_1)_1, the least ordinal fixed by the Veblen function \varepsilon(\cdot) at \omega_1. A key distinction arises between continuous and Lipschitz reducibility: A \leq_L B if A = f^{-1}(B) for a Lipschitz continuous f with d(f(x), f(y)) \leq K \cdot d(x, y) for some constant K > 0. Lipschitz reductions are strictly stronger than continuous ones, yielding a subhierarchy of Wadge degrees that collapses certain levels; for instance, all clopen sets are Lipschitz-equivalent, but the full continuous Wadge hierarchy separates more finely within Borel classes. This distinction is crucial for effective versions, where Lipschitz degrees align more closely with computable reductions.

Degrees of Borel sets

The Borel Wadge degrees are the equivalence classes of Borel subsets of Polish spaces under Wadge equivalence, where two Borel sets A and B are equivalent if there exists a continuous bijection f with continuous inverse such that A = f^{-1}(B). The ordering on these degrees is induced by Wadge reducibility: A \leq_W B if there is a continuous function f such that A = f^{-1}(B). This forms the Borel Wadge hierarchy, a restriction of the full Wadge hierarchy to Borel sets. Due to Martin's theorem on Borel determinacy, the reducibility relation is well-founded on Borel sets, making the hierarchy a well-order. The Borel Wadge hierarchy embeds the classical as an initial segment but refines it through continuous reductions, distinguishing sets that are indistinguishable at the level of Borel complexity classes. For instance, within the \Sigma^0_2 Borel class, there are \omega_1 many distinct Wadge degrees, corresponding to a tower of \omega_1 iterations of basic operations on clopen sets; this contrasts with the finite Borel of 2 for complete \Sigma^0_2 sets. Such refinements arise from the ability of continuous functions to simulate arithmetic operations on the descriptive complexity of sets, leading to a finer classification than the inductive levels of the \Sigma^0_\alpha and \Pi^0_\alpha for \alpha < \omega_1. The Borel Wadge degrees form a well-order of length \varepsilon_0 \cdot \omega_1. This length reflects the exhaustive classification of Borel complexity via continuous reductions, corresponding to the Veblen normal form with base \omega_1. The structure includes complete intervals analogous to those in the : non-self-dual degrees appear in pairs, consisting of a degree d and its \hat{d} (where sets in \hat{d} are complements of sets in d), separated by no other degrees. These pairs occur at successor positions in the hierarchy and at limit ordinals of uncountable , while self-dual degrees (where d = \hat{d}) arise at limit ordinals of countable . This alternation—pairs followed by self-dual degrees—mirrors the closure properties and duality in the , with the semi-linear ordering principle ensuring no incomparabilities within Borel classes. Wadge degrees for Borel sets provide a of Borel subsets up to continuous , turning the quasi-order of Wadge reducibility into a linear order on the degrees. This connects directly to the broader theory of Wadge reducibility, where continuous functions act as witnesses for complexity comparisons, enabling a complete descriptive ordering of Borel sets beyond mere topological or inductive definitions.

Borel Equivalence Relations

Definitions and examples

A Borel equivalence relation on a X is an E \subseteq X \times X that is Borel as a subset of the product space X \times X. These relations arise naturally in descriptive set theory as a framework for studying classification problems on standard Borel spaces, where Borel sets form the underlying \sigma-algebra generated by the open sets. A basic example is the equality relation \Delta_1 on the Cantor space $2^\omega, where x \Delta_1 y if and only if x = y; this is a Borel equivalence relation, meaning it is Borel reducible to on the reals. Another fundamental example is E_0, the eventual relation on $2^\mathbb{N}, defined by x E_0 y if and only if there exists m \in \mathbb{N} such that x_n = y_n for all n \geq m; E_0 is a countable Borel equivalence relation that is the simplest non- one under Borel reducibility. Many Borel equivalence relations arise as orbit equivalences from Borel group actions. For a Borel action of a group G on a X, the orbit equivalence relation E_G^X is defined by x E_G^X y if and only if there exists g \in G such that y = g \cdot x; this relation is Borel. In particular, turbulent actions yield highly complex Borel equivalence relations: an action G \curvearrowright X is turbulent if every is dense and meager in X, and for every x \in X and open sets U \ni x, V \ni e (the identity), the local orbit \{ g \cdot y \mid y \in U, g \in V \} is somewhere dense in U. A Borel equivalence relation is turbulent if it is the orbit equivalence of a turbulent action, in which case every contains a dense embedding of any countable Borel equivalence relation. Countable Borel equivalence relations, where each class is countable, are classifiable by countable structures via Borel codes, as established by the Feldman-Moore theorem, which shows they are precisely the orbit equivalences of Borel actions of countable groups. Hyperfinite Borel equivalence relations are those Borel reducible to E_0, such as the orbit equivalence relations arising from free Borel actions of \mathbb{Z} on a Polish space, which can be expressed as increasing unions of finite Borel equivalence relations.

Complexity and classification

Borel reducibility provides a fundamental tool for comparing the of Borel equivalence relations. Given two Borel equivalence relations E on a X and F on a Y, we say E \leq_B F if there exists a Borel f: X \to Y such that for all x, z \in X, x \, E \, z f(x) \, F \, f(z). This relation orders Borel equivalence relations by embedding their quotient structures via Borel maps, allowing for a partial based on descriptive set-theoretic strength. A key representation result is the Feldman-Moore theorem, which characterizes countable Borel equivalence relations (BERs) as arising from group . Specifically, every countable BER on a is the induced by a Borel of a countable group on that space. This theorem, originally from an unpublished manuscript by Feldman and Moore, enables the study of such relations through dynamical systems and . The Glimm-Effros dichotomy offers a profound classification principle for BERs, extending earlier work on transformation groups. For any Borel equivalence relation E on a , either E is smooth—meaning E \leq_B \Delta_\mathbb{R}^1, the relation on \mathbb{R}—or there is a continuous of E_0 into E, where E_0 is the eventual relation on $2^\mathbb{N}. This , proved by Harrington, Kechris, and Louveau, separates "simple" BERs amenable to Borel selectors from those exhibiting turbulent, non-classifiable behavior. Countable BERs admit a universal member within their class: there exists a countable BER U on a Polish space such that every countable BER F satisfies F \leq_B U. This relation can be realized as the orbit equivalence of a Borel action of the on countably many generators, highlighting the richness of the reducibility . Classification of countable BERs up to Borel reducibility and conjugacy ( via Borel bijections preserving the ) often proceeds through structural invariants, revealing a spectrum from hyperfinite to highly complex cases. Hjorth's of turbulence provides a critical for obstructing complete classifications. A BER E is if it is the orbit of a turbulent . Turbulent relations, as developed by Hjorth, cannot be classified by countable structures in a Borel way, marking a boundary for descriptive complexity in equivalence relation . Further bounds on the complexity of BERs arise from results of Kechris, Solecki, and Todorčević, who established a for Borel graphs stating that the Borel chromatic number is either at most countable or equal to the . In particular, their work links the chromatic numbers of associated Borel graphs to broader structural properties, providing quantitative limits on the descriptive complexity needed for selectors or . These bounds refine the understanding of when BERs admit Borel uniformizations or fall into turbulent categories.

Effective Descriptive Set Theory

Lightface Borel and analytic sets

In effective descriptive set theory, the lightface Borel hierarchy consists of pointclasses defined using recursive parameters, intersecting the classical with the arithmetic hierarchy of recursion theory. The class \Sigma^0_1 comprises the open sets, or equivalently, the recursively enumerable subsets of Polish spaces, while \Sigma^0_{n+1} is formed by countable unions ( over the naturals) with recursive enumerations of the complements of \Sigma^0_n sets, with \Pi^0_n as the complements of \Sigma^0_n and \Delta^0_n = \Sigma^0_n \cap \Pi^0_n. These classes are generated from basic open sets via recursive codes, ensuring all operations—such as countable unions, intersections, and complements—are computable. The lightface analytic sets, denoted \Sigma^1_1, are the projections of lightface \Pi^0_1 sets, or equivalently, the over reals of closed sets defined recursively: a set A \subseteq X is \Sigma^1_1 if there exists a recursive R \subseteq \omega^\omega \times X \times \omega^\omega such that x \in A if and only if \exists \alpha \in \omega^\omega \, R(\alpha, x). These sets coincide with the projections of computable trees on \omega^{<\omega} \times \omega^{<\omega}, emphasizing their recursive definability without arbitrary parameters. The coanalytic sets \Pi^1_1 are the complements of \Sigma^1_1 sets, and \Delta^1_1 = \Sigma^1_1 \cap \Pi^1_1 consists of those sets recursive in the hyperjump, forming the hyperarithmetic sets. The \Delta^1_1 sets occupy a distinguished position as the union of the lightface up to \omega_1^{ck}, marking the boundary where effective definability stabilizes before the full transfinite extension to ordinal levels below \omega_1^{ck}. Effective uniformization for \Sigma^1_1 relations fails in the absence of parameters, as boldface analogs require non-recursive choices, but lightface versions succeed via computable selections. A key distinction from their boldface counterparts lies in closure properties: lightface classes are closed under recursive operations, such as computable substitutions and quantifications, whereas boldface Borel and analytic sets permit arbitrary real parameters, leading to broader but less effective hierarchies. For instance, the intersection of a recursive \Sigma^1_1 set with its complement (a \Pi^1_1 set) yields a \Delta^1_1 set, reflecting the computability inherent in lightface definitions. Kleene's basis theorem asserts that every nonempty \Sigma^1_1 set contains a \Delta^1_1 (hyperarithmetic) member. This ensures the of a hyperarithmetic , with applications to inductive definitions and well-founded relations in recursive settings.

Hyperarithmetic hierarchy

The hyperarithmetic arises in effective descriptive set theory as an extension of the , incorporating transfinite iterations of the Turing jump operator along computable ordinals up to the Church-Kleene ordinal \omega_1^{ck}, the smallest non-computable ordinal. This classifies lightface Borel sets and coincides with the class of \Delta_1^1 sets, which are both \Sigma_1^1 and \Pi_1^1. Developed primarily in the , the theory traces its origins to works by Stephen Kleene, Emil Post, and Andrzej Mostowski, who explored generalizations of recursive and arithmetical sets beyond finite-type quantifiers. Kleene's of arithmetical predicates and quantifiers provided a foundational framework, showing that hyperarithmetic sets are precisely those definable using quantification over the hyperarithmetic reals. Formally, for the empty oracle, a set A \subseteq \omega belongs to the hyperarithmetic class HYP if there exists a computable ordinal notation \alpha < \omega_1^{ck} such that A is Turing reducible to the \alpha-th iterated Turing jump of the , denoted $0^{(\alpha)}. The Church-Kleene ordinal \omega_1^{ck} is the supremum of the order types of all computable well-orderings on \omega, and notations for ordinals below it are given by Kleene's \mathcal{O}, the set of codes for computable ordinals. The levels are defined recursively: \Sigma_0^{hyp} = \Pi_0^{hyp} = \Sigma_0^0 \cap \Pi_0^0 (the clopen sets), and for limit ordinals \lambda, \Sigma_\lambda^{hyp} = \bigcup_{\beta < \lambda} \Sigma_\beta^{hyp}, with successor levels \Sigma_{\alpha+1}^{hyp} consisting of countable unions of sets from \Pi_\alpha^{hyp}, and dually for \Pi. Relative to a real x, the extends to ordinals below \omega_x^1, the least upper bound of ordinals computable from x. Equivalently, the hyperarithmetic sets are the subsets of \omega appearing in the constructible hierarchy L at levels below \omega_1^{ck}, i.e., HYP = P(\omega) \cap L_{\omega_1^{ck}}. This characterization links the hierarchy to admissible ordinals and second-order arithmetic, where hyperarithmetic sets are those definable in the structure (\omega, +, \times, \in) with parameters from HYP. The class HYP is closed under Turing reducibility, countable unions, and complements, but not under arbitrary projections, distinguishing it from bolder projective classes. A cornerstone result is the Spector-Gandy theorem, which states that every \Pi_1^1 formula is equivalent to an arithmetic formula with an additional existential quantifier over the hyperarithmetic reals: for any \Pi_1^1 set P \subseteq \omega, there exists an arithmetic formula \psi such that n \in P if and only if \exists z \in \mathrm{HYP} \, \psi(n, z). Independently established by Clifford Spector and Robin Gandy in , this normal form theorem highlights the "effectively Borel" nature of \Delta_1^1 sets and enables uniform representations of coanalytic sets. Kleene's basis theorem complements this by asserting that every nonempty \Sigma_1^1 set contains a member Turing reducible to \mathcal{O}, the canonical complete \Pi_1^1 set of ordinal notations. Gandy's basis theorem further refines this, guaranteeing that such sets contain hyperlow reals, where the jump hierarchy stabilizes early relative to \omega_1^{ck}. These results underpin applications in higher recursion theory, such as the uniformity of the and the of countable \Sigma_1^1 sets, all of whose are hyperarithmetic by Harrison's . The hierarchy's and basis theorems facilitate proofs of for certain effective and reductions in Borel equivalence relations.

References

  1. [1]
    [PDF] DESCRIPTIVE SET THEORY - UCLA Mathematics
    Apr 8, 2009 · My aim in this monograph is to give a brief but coherent exposition of the main results and methods of descriptive set theory. I have made ...
  2. [2]
    [PDF] Descriptive Set Theory
    These are informal notes for a course in Descriptive Set Theory given at the University of Illinois at Chicago in Fall 2002. While I hope to give a fairly.
  3. [3]
    [PDF] Introduction to descriptive set theory - Mathematics and Statistics
    Oct 16, 2025 · Descriptive set theory has found applications in harmonic analysis, dynamical systems, functional analysis, and various other areas of ...
  4. [4]
    [PDF] Sur les structures boréliennes du spectre d'une C-algèbre - Numdam
    Bref, B, muni de la topologie de la convergence simple forte, est un espace polonais. ... KURATOWSKI, Topologie I, 4e éd., Monografie Mat., t. 20, Varsovie, 1958.
  5. [5]
    None
    Below is a merged response that consolidates all the information from the provided segments into a single, comprehensive summary. To maximize detail and clarity, I will use a table in CSV format for key definitions, theorems, and surrounding context, followed by a narrative summary that integrates additional details and useful URLs. This approach ensures all information is retained while maintaining readability and density.
  6. [6]
    [PDF] Borel Structures and Borel Theory - School of Computer Science
    Definition 1.1. A set A equipped with a σ-algebra B is said to be a standard Borel space if there is Polish topology for which B is the ...<|control11|><|separator|>
  7. [7]
    [PDF] The emergence of descriptive set theory - Boston University
    Lebesgue's concept of measurable set subsumed the Borel sets, and his analytic definition of measurable function had the simple consequence of closure under ...<|control11|><|separator|>
  8. [8]
    [PDF] Version of 30.9.08 Chapter 42 Descriptive set theory At this point, I ...
    Sep 30, 2008 · The first section describes Souslin's operation and its basic set-theoretic properties up to first steps in the theory of 'constituents' (421N- ...
  9. [9]
    Sur les ensembles analytiques - EuDML
    Sur les ensembles analytiques. Nicolas Lusin · Fundamenta Mathematicae (1927). Volume: 10, Issue: 1, page 1-95; ISSN: 0016-2736 ...Missing: parfaits | Show results with:parfaits
  10. [10]
    [PDF] Introduction to Classical Descriptive Set Theory - Logic at Stanford
    Oct 13, 2015 · inductive definitions of each hierarchy. I.e.: For Borel, we use the open sets. For Projective, we use the analytic sets, which are (relatively).
  11. [11]
    Large Cardinals and Determinacy
    May 22, 2013 · ... (all Borel sets of reals are determined), PD (all projective sets of reals are determined) and ADL(ℝ) (all sets of reals in L(ℝ) are determined).
  12. [12]
    A PROOF OF PROJECTIVE DETERMINACY Let OJ be the set of all ...
    Assuming the existence of more Woodin cardinals,. Page 22. 92. D. A. MARTIN AND J. R. STEEL. Woodin can strengthen the conclusion of his theorem, replacing L(! ...
  13. [13]
    https://www.math.ucla.edu/~ineeman/dlc.pdf
  14. [14]
    Regularity properties, projective sets, determinacy, $\text{AD}^+
    Projective determinacy from large cardinals. Woodin showed that Π n + 1 1 -determinacy follows from the existence of n Woodin cardinals with a measurable ...
  15. [15]
    [PDF] Reducibility and Determinateness on the Baire Space
    descriptive set theory. Also, this chapter presents an informal and intuitive approach to games and continuity that is vital for understanding much of the.
  16. [16]
    Wadge degrees and descriptive set theory - SpringerLink
    Aug 28, 2006 · Wadge degrees and descriptive set theory. Conference paper; First Online: 01 January 2006. pp 151–170; Cite this conference paper.Missing: seminal | Show results with:seminal
  17. [17]
    Borel-Wadge degrees - EuDML
    In this note we investigate the structure of Borel-Wadge degrees under the assumption of the Axiom of Determinacy. ... Set theory. 03E15: Descriptive set ...
  18. [18]
    [PDF] The Wadge Hierarchy of Max-Regular Languages - mimuw
    In 1979, Klaus Wagner described a classification of ω-regular sets in terms of the graph- theoretical structure automata known as the the Wagner hierarchy [15].
  19. [19]
    Borel Sets of Finite Rank on JSTOR
    J. Duparc, Wadge Hierarchy and Veblen Hierarchy Part I: Borel Sets of Finite Rank, The Journal of Symbolic Logic, Vol. 66, No. 1 (Mar., 2001), pp. 56-86.
  20. [20]
    (PDF) Borel-Wadge degrees - ResearchGate
    Aug 6, 2025 · Two sets of reals are Borel equivalent if one is the Borel pre-image of the other, and a Borel-Wadge degree is a collection of pairwise ...
  21. [21]
    [PDF] The theory of countable Borel equivalence relations - Caltech PMA
    May 12, 2023 · The theory of definable equivalence relations has been a very active area of research in descriptive set theory during the last three decades.
  22. [22]
    [PDF] HJORTH'S TURBULENCE THEOREM In this note, we give a short ...
    Dec 12, 2022 · E+ is called the Friedman-Stanley jump of E, and it is a theorem that E <B E+ if E is a Borel equivalence relation. We can iterate this jump ...
  23. [23]
    [PDF] turbulence, representations, and trace-preserving actions
    To show that a Borel equivalence relation E on X is not smooth, it suffices to demonstrate. the existence of a Borel probability measure on X which is ergodic ...
  24. [24]
    [PDF] The theory of countable Borel equivalence relations - Caltech PMA
    The theory of definable equivalence relations has been a very active area of research in descriptive set theory during the last three decades. It serves as.<|control11|><|separator|>
  25. [25]
    [PDF] Universal Borel actions of countable groups - Mathematics Department
    G is universal. Recall that a countable Borel equivalence relation E is said to be universal if. F ≤B E for every countable Borel equivalence relation F.
  26. [26]
    Classification and Orbit Equivalence Relations
    a Borel equivalence relation F all of whose equivalence classes are countable such ... there is a turbulent Polish G-space Y and a continuous G-embedding from. Y ...
  27. [27]
    [PDF] Effective Descriptive Set Theory - UC Berkeley math
    Aug 21, 2024 · We define the interpretation of a Borel code inductively. Definition 1.26. If (T,l) is a Borel code, then its interpretation is the Borel.
  28. [28]
    [PDF] Kleene [1943], Post [1944] and Mostowski [1947] . . . . . . . . . . . 2 1A ...
    Nov 9, 2016 · (total) function f : Nn → N is hyperarithmetical if it is recursive in some Ha; HYP is the set of all hyperarithmetical sets, and if A ≤T.Missing: Δ¹_1 clopen
  29. [29]
    [PDF] Descriptive Set theory - George Barmpalias
    Nov 30, 2009 · The set of Borel codes can be defined as the smallest class of reals which contains the codes for closed sets and is closed.<|separator|>