A New Bridge Links the Strange Math of Infinity to Computer Science
A New Bridge Links the Strange Math of Infinity to Computer Science
In the world of mathematics, there exists a small community of researchers known as descriptive set theorists. They are an exception to the rule, as they continue to study the fundamental nature of sets, particularly the strange infinite ones that other mathematicians often ignore. Their field has just gotten a lot less lonely, thanks to a deep and surprising connection between descriptive set theory and modern computer science.
The Bridge Connecting Descriptive Set Theory and Computer Science
In 2023, mathematician Anton Bernshteyn published a connection between the remote mathematical frontier of descriptive set theory and modern computer science. He showed that all problems about certain kinds of infinite sets can be rewritten as problems about how networks of computers communicate. This bridge connecting the disciplines surprised researchers on both sides. Set theorists use the language of logic, while computer scientists use the language of algorithms. Set theory deals with the infinite, while computer science deals with the finite. There's no reason why their problems should be related, much less equivalent.
The Field of Descriptive Set Theory
Descriptive set theory dates back to Georg Cantor, who proved in 1874 that there are different sizes of infinity. The set of whole numbers (0, 1, 2, 3, ...) is the same size as the set of all fractions, but smaller than the set of all real numbers. Anush Tserunyan sees descriptive set theory as the connective tissue that holds different parts of mathematics together.
The Hierarchy of Sets
To study more complicated sets, mathematicians use other types of measures. The uglier a set is, the fewer ways there are to measure it. Descriptive set theorists ask questions about which sets can be measured according to different definitions of "measure." They then arrange them in a hierarchy based on the answers to those questions. At the top are sets that can be constructed easily and studied using any notion of measure you want. At the bottom are "unmeasurable" sets, which are so complicated they can't be measured at all.
The Problem of Coloring Infinite Graphs
Mathematicians can then ask whether it's possible to color the nodes in this graph so that they obey certain rules. Using just two colors, for instance, can you color every node in the graph so that no two connected nodes are the same color? The solution might seem straightforward. Look at the first piece of your graph, pick a node, and color it blue. Then color the rest of the piece's nodes in an alternating pattern: yellow, blue, yellow, blue. Do the same for every piece in your graph: Pick a node, color it blue, then alternate colors. Ultimately, you'll use just two colors to achieve your task.
The Axiom of Choice
But to accomplish this coloring, you had to rely on a hidden assumption that set theorists call the axiom of choice. It's one of the nine fundamental building blocks from which all mathematical statements are constructed. According to this axiom, if you start with a bunch of sets, you can choose one item from each of those sets to create a new set—even if you have infinitely many sets to choose from. This axiom is useful, in that it allows mathematicians to prove all sorts of statements of interest. But it also leads to strange paradoxes. Descriptive set theorists avoid it.
The Connection to Computer Science
In 2019, one of those talks changed the course of Bernshteyn's career. It was about "distributed algorithms" – sets of instructions that run simultaneously on multiple computers in a network to accomplish a task without a central coordinator. Say you have a bunch of Wi-Fi routers in a building. Nearby routers can interfere with each other if they use the same communication frequency channel. So each router needs to choose a different channel from the ones used by its immediate neighbors. Computer scientists can reframe this as a coloring problem on a graph: Represent each router as a node, and connect nearby ones with edges. Using just two colors (representing two different frequency channels), find a way to color each node so that no two connected nodes are the same color.
The Thresholds for Different Kinds of Problems
At the talk Bernshteyn was attending, the speaker discussed these thresholds for different kinds of problems. One of the thresholds, he realized, sounded a lot like a threshold that existed in the world of descriptive set theory – about the number of colors required to color certain infinite graphs in a measurable way. To Bernshteyn, it felt like more than a coincidence. It wasn't just that computer scientists are like librarians too, shelving problems based on how efficiently their algorithms work. It wasn't just that these problems could also be written in terms of graphs and colorings.
The Bridge Between Descriptive Set Theory and Computer Science
Bernshteyn set out to make this connection explicit. He wanted to show that every efficient local algorithm can be turned into a Lebesgue-measurable way of coloring an infinite graph (that satisfies some additional important properties). That is, one of computer science's most important shelves is equivalent to one of set theory's most important shelves (high up in the hierarchy). He began with the class of network problems from the computer science lecture, focusing on their overarching rule – that any given node's algorithm uses information about just its local neighborhood, whether the graph has a thousand nodes or a billion.
The Labeling Problem
To run properly, all the algorithm has to do is label each node in a given neighborhood with a unique number, so that it can log information about nearby nodes and give instructions about them. That's easy enough to do in a finite graph: Just give every node in the graph a different number. If Bernshteyn could run the same algorithm on an infinite graph, it meant he could color the graph in a measurable way – solving a graph-coloring question on the set theory side. But there was a problem: These infinite graphs are "uncountably" infinite. There's no way to uniquely label all their nodes.
The Solution to the Labeling Problem
Bernshteyn's challenge was to find a cleverer way to label the graphs. He knew that he'd have to reuse labels. But that was fine so long as nearby nodes were labeled differently. Was there a way to assign labels without accidentally reusing one in the same neighborhood? Bernshteyn showed that there is always a way – no matter how many labels you decide to use, and no matter how many nodes your local neighborhood has. This means that you can always safely extend the algorithm from the computer science side to the set theory side.
The Implications of the Bridge
The proof came as a surprise to mathematicians. It demonstrated a deep link between computation and definability, and between algorithms and measurable sets. Mathematicians are now exploring how to take advantage of Bernshteyn's discovery. In a paper published this year, for instance, Rozhoň and his colleagues figured out that it's possible to color special graphs called trees by looking at the same problem in the computer science context. The result also illuminated which tools mathematicians might use to study the trees' corresponding dynamical systems.
The Future of Descriptive Set Theory
Mathematicians have also been working to translate problems in the other direction. In one case, they used set theory to prove a new estimate of how hard a certain class of problems is to solve. Bernshteyn's bridge isn't just about having a new toolkit for solving individual problems. It has also allowed set theorists to gain a clearer view of their field. There were lots of problems that they had no idea how to classify. In many cases, that's now changed, because set theorists have computer scientists' more organized bookshelves to guide them.
Conclusion
Bernshteyn hopes this growing area of research will change how the working mathematician views set theorists' work – that they'll no longer see it as remote and disconnected from the real mathematical world. "I'm trying to change this," he said. "I want people to get used to thinking about infinity."
Source: https://www.wired.com/story/a-new-bridge-links-the-strange-math-of-infinity-to-computer-science/
