This article originally appeared in Quanta Magazine. Modern mathematics is fundamentally rooted in set theory, the foundational framework for organizing abstract collections of objects. While most research mathematicians rely on set theory implicitly when solving problems, a distinct community—descriptive set theorists—has continued to explore the fundamental nature of sets, particularly those with infinite cardinality, which are often overlooked by their peers.

Descriptive Set Theory: A Niche of Mathematical Inquiry

In 2023, Anton Bernshteyn (University of California, Los Angeles) published a landmark result connecting descriptive set theory to modern computer science, revealing a profound equivalence between problems in these traditionally disjoint fields. This discovery surprised researchers on both sides: set theory deals with abstract infinities and logical definability, while computer science focuses on finite algorithms and computational complexity. The bridge between them was unexpected, as their methodological frameworks and subject domains seemed unrelated.

Václav Rozhoň (Charles University, Prague) characterized the result as "a surprising deviation from conventional mathematical frameworks," noting that "the alignment of these two disciplines was neither intuitively obvious nor previously recognized."

From Misconception to Discovery: Bernshteyn’s Path

Bernshteyn’s engagement with descriptive set theory began with an undergraduate misconception: he was taught the field had "decayed into irrelevance" after initial contributions. This misunderstanding persisted until his graduate studies at the University of Illinois, where his advisor Anush Tserunyan corrected him, emphasizing descriptive set theory’s enduring role in classifying sets by complexity.

Descriptive set theory traces to Georg Cantor’s 1874 work on infinite cardinality, which established that sets like the natural numbers (ℕ) are "countably infinite," while the real numbers (ℝ) are "uncountably infinite." To analyze such sets, mathematicians distinguish between cardinality (size) and measure (length/area/volume). Descriptive set theorists formalize a hierarchy of sets based on measurability, from "simple" sets (easily measured) to "pathological" (nonmeasurable, or "unmeasurable") sets that resist standard measure-theoretic analysis.

The Hierarchy of Measurability

Cantor’s work on infinities sparked a crisis of intuition: mathematicians struggled to reconcile "different sizes of infinity." To address this, Lebesgue introduced Lebesgue measure—a foundational tool for quantifying length, area, or volume of sets. Descriptive set theorists extended this framework to classify sets by their "complexity":

• Measurable sets: Obeying standard measure-theoretic axioms (e.g., intervals, open/closed sets).

• Nonmeasurable (pathological) sets: Defying such axioms, often constructed using the axiom of choice (AC), a foundational principle asserting the existence of "choice sets" for infinite collections.

Infinite Graphs and Coloring Problems

Bernshteyn focused on infinite graphs—collections of nodes (points) and edges (connections)—with infinitely many components, each containing infinitely many nodes. In such graphs, "pathological" behavior arises when coloring nodes to avoid adjacent duplicates, a classic problem in graph theory.

Consider an infinite graph formed by iteratively placing nodes on a circle with fixed angular spacing (e.g., 1/5 of the circumference). If the spacing is irrational, the nodes form a dense, unclosed sequence, generating infinitely many disconnected components. Coloring these components with two colors—relying on AC—yields nonmeasurable sets, as the color assignments cannot be described by length or area. In contrast, a three-coloring (using a continuous, AC-free strategy) results in measurable sets, placing two-coloring problems in the lowest tier of descriptive set theory’s hierarchy (nonmeasurable) and three-coloring in a higher tier (measurable).

A Meeting of Disciplines: Algorithms and Graphs

Bernshteyn’s breakthrough emerged during a 2019 talk on distributed algorithms—computer protocols where multiple nodes (e.g., routers) communicate locally to solve problems without a central authority. He recognized that coloring problems in distributed networks (e.g., assigning distinct "channels" to adjacent routers) mirror the infinite graph coloring problems in descriptive set theory.

Formalizing this analogy, Bernshteyn proved that any distributed algorithm for graph coloring (with local communication constraints) is equivalent to a measurable coloring of an infinite graph in descriptive set theory. His result hinges on the ability to map algorithmic steps to measurable color assignments, even for uncountably infinite node sets, by leveraging the compactness of topological spaces and continuity of local rules.

Implications and New Collaborations

This equivalence has already yielded cross-disciplinary advances. For example, Rozhoň and colleagues used Bernshteyn’s framework to analyze tree graphs (a key class of infinite graphs), deriving bounds on the complexity of distributed coloring protocols and relating these to dynamical system behavior. Conversely, set theorists now use descriptive set theory to characterize computational hardness, formalizing longstanding conjectures about algorithmic complexity.

Bernshteyn’s work bridges descriptive set theory with computer science, transforming both fields. By integrating previously isolated tools, it redefines how mathematicians approach infinite structures, rendering descriptive set theory less "remote" and more integral to mainstream mathematical practice. As Bernshteyn notes, "The goal is to make descriptive set theory a foundational pillar, not a niche curiosity, by demonstrating its relevance to diverse mathematical problems."

Original story reprinted with permission from Quanta Magazine.

The Simons Foundation supports editorially independent reporting on science and mathematics to enhance public understanding.