Bridging Infinity: How Descriptive Set Theory and Computer Science Are Rewriting Their Own Foundations

All of modern mathematics is built on set theory, the discipline that organizes abstract collections of objects. Usually this foundation is taken for granted: researchers may investigate differential equations, topology or number theory without ever invoking the axioms of set theory directly. Descriptive set theorists, however, dedicate themselves to the very question of how sets behave, especially the infinite varieties that other mathematicians routinely ignore. Over the past decade a quiet revolution has taken place. In 2023 Anton Bernshteyn published a result that pulls the remote world of descriptive set theory into the concrete language of algorithms. He proved that every problem about a certain class of infinite sets can be reformulated as a question about how networks of computers communicate. The bridge that connects the disciplines surprised researchers on both sides, because set theorists speak in the language of logic while computer scientists use algorithms, and because one deals with the infinite and the other with finite structures. “This is *really* weird,” remarked Václav Rozhoň, a computer scientist at Charles University. “You’re not supposed to have this.” Since that breakthrough scholars have been pushing the frontiers of the connection, extending it to new problems and exchanging ideas in both directions. For some at the forefront of descriptive set theory the computational perspective has begun to reshape their whole view of infinity, influencing not only proofs but also the taxonomy of the field. The roots of descriptive set theory date back to Georg Cantor’s pioneering work on the sizes of infinite sets. While Cantor distinguished between cardinalities—counting the number of elements—mathematicians later introduced notions of size based on measure, such as Lebesgue measure. These measures quantify how much “length” or “area” a set occupies, allowing mathematicians to classify sets into a hierarchy from easily measurable to completely pathological, non‑measurable sets. This hierarchy is not merely a bookkeeping exercise; it informs what tools can be used to tackle problems in dynamical systems, group theory, probability and other areas. Bernshteyn’s career illustrates how a deep understanding of this taxonomy can yield unexpected alliances. As an undergraduate he was drawn to descriptive set theory only to discover it had receded from the mainstream. A graduate course with Anush Tserunyan, later his adviser, reopened his path and positioned set theory as the connective tissue across mathematics. The class of problems that have attracted Bernshteyn’s focus are infinite graphs with infinitely many connected components, each containing infinitely many nodes. Such graphs are rare in classical graph theory but are crucial in modeling dynamical systems. A typical example involves nodes placed on a circle, joined by edges that skip a fixed arc length. Depending on whether that length is rational or irrational, the graph may be a finite cycle or an infinite sequence of points that never returns to its starting point. A central question for these graphs is whether the vertices can be colored using a finite palette so that adjacent vertices receive distinct colors. A naïve two‑coloring protocol invokes the axiom of choice to pick an initial vertex in each component—an act that generates unmeasurable sets. To avoid the axiom of choice, Bernshteyn introduced a continuous coloring scheme: color each arc in turn while alternating colors and introduce a third color only when a break arises. The resulting partitions of the circle are measurable, placing the problem higher up in the descriptive hierarchy than its two‑color cousin and making it amenable to classical measure‑theoretic methods. The turning point for Bernshteyn came at a computer‑science conference in 2019. The speaker discussed distributed algorithms—local procedures run simultaneously on each node of a network to accomplish global tasks without a central coordinator. The classic example is frequency assignment for Wi‑Fi routers: adjacent routers must choose different channels. In graph‑theoretic terms this is a proper coloring problem on a finite graph. In a local algorithm each node first chooses a tentative color, then exchanges its choice with its immediate neighbors and, if necessary, recomputes its color. The efficiency of such an algorithm is measured by how many communication rounds are needed to achieve a proper coloring. Remarkably, Bernshteyn observed that the threshold for needing a third color in the network setting mirrors the threshold for measurably coloring the infinite graph on the set‑theoretic side. Bolstered by this insight, Bernshteyn set out to make the connection precise. He proved that any efficient local algorithm that operates on a finite graph can be translated into a Lebesgue‑measurable coloring of an infinite graph that satisfies additional structural properties. The bridge hinges on labeling nodes with finite identifiers that are reused only outside local neighborhoods—a combinatorial construction that holds for graphs of arbitrary cardinality. The implications are two‑fold. First, a vast array of decidability questions solvable by distributed algorithms now yield concrete information about measurable colorings, opening new pathways for set theorists. Second, the translation reverses: measurable structures in set theory can provide new estimation tools for computational complexity. Recent work by Rozhoň and collaborators leverages this duality to bound the chromatic numbers of tree‑like graphs and to analyze associated dynamical systems. Beyond the exchange of results, the bridge has reshaped the perception of descriptive set theory itself. Where earlier it seemed a niche, ivory‑tower discipline focused on pure infinitary curiosities, it now stands as a fertile ground for practical, algorithmic insight. Bernshteyn hopes the community will shift from viewing infinity as a distant mathematical abstraction to embracing it as an integral part of everyday mathematical practice. Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.