A New Bridge Links the Strange Math of Infinity to Computer Science

The original version of this story appeared in Quanta Magazine.

All of modern mathematics is built on the foundation of set theory, the study of how to organize abstract collections of objects. But in general, research mathematicians don’t need to think about it when they’re solving their problems. They can take it for granted that sets behave the way they’d expect, and carry on with their work.

Descriptive set theorists are an exception. This small community of mathematicians never stopped studying the fundamental nature of sets—particularly the strange infinite ones that other mathematicians ignore.

Their field just got a lot less lonely. In 2023, a mathematician named Anton Bernshteyn published a deep and surprising 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. The bridge connecting the disciplines surprised researchers on both sides. Set theorists use the language of logic, computer scientists the language of algorithms. Set theory deals with the infinite, computer science with the finite. There’s no reason why their problems should be related, much less equivalent.

“This is something really weird,” said Václav Rozhoň, a computer scientist at Charles University in Prague. “Like, you are not supposed to have this.”

Since Bernshteyn’s result, his peers have been exploring how to move back and forth across the bridge to prove new theorems on either side, and how to extend that bridge to new classes of problems. Some descriptive set theorists are even starting to apply insights from the computer science side to reorganize the landscape of their entire field, and to rethink the way they understand infinity.

“This whole time we’ve been working on very similar problems without directly talking to each other,” said Clinton Conley, a descriptive set theorist at Carnegie Mellon University. “It just opens the doors to all these new collaborations.”

Broken Sets

Bernshteyn was an undergraduate when he first heard of descriptive set theory—as an example of a field that had once mattered, then decayed to nothing. More than a year would pass before he found out the professor had been wrong.

In 2014, as a first-year graduate student at the University of Illinois, Bernshteyn took a logic course with Anush Tserunyan, who would later become one of his advisers. She corrected the misconception. “She should take all the credit for me being in this field,” he said. “She really made it seem that logic and set theory is this glue that connects all different parts of math.”

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, …), for instance, is the same size as the set of all fractions, but smaller than the set of all real numbers.