新桥连接无穷数学与计算机科学
内容总结：
【本报讯】长久以来，集合论作为现代数学的基础，其深奥理论往往被大多数数学家视为无需触及的底层框架。然而，一个名为“描述集合论”的冷门分支，数十年来始终致力于研究无限集合的本质。2023年，数学家安东·伯恩施坦的一项突破性研究，在这一看似孤寂的领域与蓬勃发展的计算机科学之间，架起了一座令人惊异的桥梁。
传统上，描述集合论学者专注于对无限集合进行精细分类，尤其关注那些无法用常规方法测量的“病态集合”。他们如同数学界的图书馆员，将各类无限集合问题按复杂度分层归档。而计算机科学则聚焦于有限网络的高效算法，两者在语言与研究对象上似乎毫无交集。
伯恩施坦发现，描述集合论中关于无限图的着色问题（例如用最少的颜色为图中相连节点标注不同颜色），竟与分布式算法中的节点通信效率问题具有深刻等价性。通过构建巧妙的数学转换，他证明：计算机科学中基于局部通信的高效算法，可直接转化为描述集合论中对无限图进行“可测着色”的解决方案。这一发现打破了学科壁垒，让研究者能双向迁移工具与洞见。
“这简直不可思议，”布拉格查理大学计算机科学家瓦茨拉夫·罗仲坦言，“原本风马牛不相及的领域，竟存在如此紧密的对应关系。”如今，两大领域学者正借助这座桥梁相互启发：计算机科学家利用集合论工具攻克算法难题，而描述集合论者则参照计算机科学的分类体系，重新梳理本领域悬而未决的问题。
卡内基梅隆大学描述集合论学者克林顿·康利评价道：“我们实际上一直在研究相似的问题，只是从未直接对话。这座桥梁开启了全新的合作可能。”伯恩施坦希望，这项研究能改变数学家对无限集合研究的刻板印象，让“思考无限”成为更多学科的自然视角。
中文翻译：
一座新桥将奇妙的无穷数学与计算机科学相连
引言
现代数学全部建立在集合论基础之上——这门学科研究如何对抽象的对象集合进行归类。但通常情况下，研究数学家解决问题时并不需要思考集合论。他们可以理所当然地认为集合会按预期方式运作，然后继续自己的工作。
描述集合论学者是个例外。这个由数学家组成的小群体从未停止研究集合的基本性质——尤其是其他数学家避之不及的奇异无穷集合。
这个领域如今不再孤独。2023年，数学家安东·伯恩施坦发表了一项突破性研究，在描述集合论这个偏远数学前沿与现代计算机科学之间建立了深刻而惊人的联系。
他证明所有关于某类无穷集合的问题，都可以转化为关于计算机网络如何通信的问题。连接这两个学科的桥梁令双方研究者都感到震惊。集合论学者使用逻辑语言，计算机科学家使用算法语言。集合论处理无穷问题，计算机科学处理有限问题。它们的研究课题本无关联，更不用说等价。
"这确实非常奇特，"布拉格查理大学的计算机科学家瓦茨拉夫·罗宗表示，"就像本不该存在这样的联系。"
自伯恩施坦的成果问世后，同行们一直在探索如何在这座桥梁上往返穿梭，以证明两岸的新定理，并如何将桥梁延伸至新的问题类别。一些描述集合论学者甚至开始运用计算机科学领域的洞见来重新规划整个领域的版图，重新思考理解无穷的方式。
"长期以来我们一直在研究非常相似的问题，却从未直接交流过，"卡内基梅隆大学的描述集合论学者克林顿·康利说，"这为所有新的合作打开了大门。"
破碎的集合
伯恩施坦本科时首次听闻描述集合论——当时教授将其作为曾经重要但已衰落的领域举例。时隔一年多后，他才发现那位教授错了。
2014年，作为伊利诺伊大学的研一新生，伯恩施坦选修了后来成为他导师之一的阿努什·采鲁尼安的逻辑学课程。她纠正了这个误解。"我能进入这个领域完全归功于她，"他说，"她真正让我认识到逻辑和集合论就像是连接数学各个分支的黏合剂。"
描述集合论可追溯至乔治·康托尔，他于1874年证明了存在不同等级的无穷大。例如，整数集（0,1,2,3…）与所有分数集大小相同，但小于所有实数集。
当时，数学家们对这种无穷大的多样性深感不安。"这确实难以理解，"现任职于加州大学洛杉矶分校的伯恩施坦表示。
部分为了缓解这种不适，数学家发展了另一种衡量大小的概念——描述集合可能占据的长度、面积或体积，而非其包含元素的数量。这种大小概念被称为集合的"测度"（与康托尔的"基数"概念相对）。最简单的测度类型——勒贝格测度——可以量化集合的长度。虽然0到1之间的实数集与0到10之间的实数集都是无穷集且基数相同，但前者的勒贝格测度为1，后者为10。
为了研究更复杂的集合，数学家使用其他类型的测度。集合越"丑陋"，可用的测量方法就越少。描述集合论学者研究的问题是：根据不同的"测度"定义，哪些集合可以被测量？他们根据这些问题的答案将集合排列成层级结构。最顶层是那些易于构造且可用任意测度概念研究的集合。最底层是"不可测"集合，它们过于复杂根本无法测量。"人们常用'病态'来形容，"伯恩施坦说，"不可测集合确实糟糕。它们违反直觉，行为怪异。"
这种层级结构不仅帮助集合论学者绘制领域版图，还让他们洞悉可以使用哪些工具来解决数学其他领域中更典型的问题。动力系统、群论和概率论等领域的数学家需要了解所用集合的大小信息。集合在层级结构中的位置决定了他们能使用哪些工具来解决问题。
因此，描述集合论学者就像图书管理员，负责管理一个包含各类无穷集合（及其不同测量方法）的巨大书架。他们的工作是分析问题，确定解决问题需要多复杂的集合，并将其归到合适的书架，供其他数学家参考。
做出选择
伯恩施坦属于这样一类图书管理员：他们对由边连接的无穷节点集（称为图）相关问题进行分类。他特别研究由无限多个独立部分组成、每部分包含无限多个节点的图。大多数图论学者不研究这类图，而是专注于有限图。但这类无穷图可以表示动力系统和其他重要集合类型并提供相关信息，使其成为描述集合论学者的主要研究兴趣。
以下是伯恩施坦和同事们可能研究的无穷图示例：从一个包含无穷多个点的圆开始。选取一个点作为第一个节点。然后沿圆周移动固定距离得到第二个节点。例如，移动圆周长的五分之一。用边连接这两个节点。再移动相同距离到第三个节点，并将其与上一个节点连接。依此类推。
如果每次移动圆周长的五分之一，需要五步才能回到起点。一般来说，如果移动距离可以写成分数，节点将形成闭环。但如果距离不能写成分数，这个过程将永远继续下去，你会得到无限多个相连节点。
但不仅如此：这个无限长的序列仅构成图的第一部分。尽管它包含无限多个节点，但并未包含圆上所有点。要生成图的其他部分，从圆上其他任意点开始，每次移动与第一部分相同的距离，最终将构建出与第一部分完全分离的第二个无限节点序列。
对圆上所有可能的新起点重复此过程，将得到一个由无限多个独立部分组成的图，每部分又由无限多个节点组成。
数学家随后可以提出：能否按照特定规则为图中的节点着色？例如，仅使用两种颜色，能否为图中每个节点着色，使得任何两个相连节点颜色不同？解决方案看似简单：观察图的第一部分，选取一个节点涂成蓝色，然后以交替模式为其余节点着色：黄、蓝、黄、蓝。对图中每个部分重复此操作：选取一个节点涂蓝，然后交替着色。最终仅用两种颜色就能完成任务。
但完成这种着色依赖于一个隐藏假设，即集合论学者所称的选择公理。这是构建所有数学陈述的九个基本基石之一。该公理表明：若从一组集合开始，可以从每个集合中选择一个元素创建新集合——即使有无限多个集合需要选择。这个公理很有用，它允许数学家证明各种感兴趣的命题，但也会导致奇怪的悖论。描述集合论学者通常避免使用它。
你的图有无限多个部分，这对应着无限多个集合。你从每个集合中选择了一个元素——即每个部分中第一个决定涂成蓝色的点。所有这些蓝点形成了一个新集合。你使用了选择公理。
当你以蓝黄交替模式为剩余节点着色时，这就产生了问题。你是单独为每个节点（长度为零）着色，没有理解来自图不同部分的节点如何相互关联。这意味着你无法用长度来描述图中所有蓝色节点或所有黄色节点的集合。换句话说，这些集合是不可测的。数学家无法对它们进行任何有意义的描述。
对描述集合论学者而言，这不能令人满意。因此他们希望找到一种连续着色方法——不使用选择公理，且能产生可测集合。
为此，请回顾如何构建图的第一部分：在圆上选取一个节点，将其与一定距离外的第二个节点连接。现在将第一个节点涂蓝，第二个涂黄，并将它们之间的整个弧段涂蓝。同样，将第二和第三个节点之间的弧段涂黄，第三段弧涂蓝，依此类推。
很快你将几乎绕完整个圆——意味着除了落在剩余小弧段上的节点外，你已为图中所有节点分配了颜色。假设最后涂色的弧段是黄色。如何为这最后的小段着色？不能使用蓝色，因为这些节点会连接到你最初涂蓝的弧段上的节点；也不能使用黄色，因为它们会连接回前一段弧上的黄色节点。
必须使用第三种颜色（比如绿色）来完成着色。
尽管如此，最终得到的蓝色、黄色和绿色节点集合都只是圆周的片段，而非使用选择公理时得到的离散点集。你可以计算这些集合的长度，它们都是可测的。
因此，描述集合论学者将双色版本的问题置于层级结构的最底层（对应不可测集合），而三色问题则被置于更高层级的书架——那里可以应用多种测度概念。
伯恩施坦在研究生期间一直研究这类着色问题，将它们逐一归类。获得学位后不久，他偶然发现了一种可能一次性归类所有问题的方法——并证明这些问题具有比任何人想象的都更深刻、数学上更相关的结构。
轮番计算
伯恩施坦时常参加计算机科学讲座，那里的图是有限的，代表计算机网络。
2019年，其中一场讲座改变了他的职业生涯。讲座关于"分布式算法"——这些指令集同时在网络中的多台计算机上运行，在没有中央协调器的情况下完成任务。
假设某栋建筑内有一批Wi-Fi路由器。如果附近路由器使用相同的通信频段，会相互干扰。因此每个路由器需要选择与直接邻居不同的频段。
计算机科学家可以将其重新表述为图上的着色问题：将每个路由器表示为节点，用边连接附近的路由器。仅使用两种颜色（代表两个不同频段），找到为每个节点着色的方法，使任何两个相连节点颜色不同。
但有个难点：节点只能通过所谓的局部算法与直接邻居通信。首先，每个节点运行相同算法并为自己分配颜色，然后与邻居通信以了解周围小区域内其他节点的着色情况，接着再次运行算法决定保持还是更换颜色，重复此步骤直到整个网络实现正确着色。
计算机科学家想知道给定算法需要多少步骤。例如，任何能用两种颜色解决路由器问题的局部算法必然效率极低，但如果允许使用三种颜色，就能找到非常高效的局部算法。
在伯恩施坦参加的讲座中，演讲者讨论了不同类型问题的这种阈值。他意识到其中一个阈值听起来很像描述集合论世界中存在的阈值——关于以可测方式为某些无穷图着色所需的颜色数量。
对伯恩施坦而言，这不仅仅是巧合。不仅仅是计算机科学家也像图书管理员一样，根据算法效率对问题进行分类；也不仅仅是这些问题同样可以用图和着色来表述。
他想，或许这两个书架有更多共同之处。或许这两个领域之间的联系远比想象中深刻得多。
或许所有的书籍和书架都是相同的，只是用不同语言书写——需要一位翻译者。
打开大门
伯恩施坦开始明确这种联系。他想证明每个高效的局部算法都可以转化为用勒贝格可测方式为无穷图着色的方法（且满足某些重要附加性质）。也就是说，计算机科学中最重要的一个书架等价于集合论中最重要的一个书架（位于层级结构高层）。
他从计算机科学讲座中的网络问题类别入手，关注其核心规则——无论图有一千个节点还是十亿个，任何给定节点的算法都只使用其局部邻域信息。
要正确运行，算法只需为给定邻域中的每个节点标记唯一编号，以便记录附近节点信息并给出指令。在有限图中这很容易做到：只需为图中每个节点分配不同编号。
如果伯恩施坦能在无穷图上运行相同算法，就意味着他可以用可测方式为图着色——解决集合论侧的图着色问题。但有个问题：这些无穷图是"不可数"无穷的，无法唯一标记所有节点。
伯恩施坦的挑战是找到更巧妙的方法来标记这些图。
他知道必须重复使用标签，但只要附近节点标记不同就没问题。有没有办法分配标签而不会在同一个邻域中意外重复使用？
伯恩施坦证明总是存在这种方法——无论你决定使用多少标签，无论局部邻域有多少节点。这意味着你总能安全地将算法从计算机科学侧扩展到集合论侧。"在我们的框架中，任何算法都对应于描述集合论框架中可测着色任何图的方法，"罗宗说。
这个证明令数学家们惊讶。它展示了计算与可定义性、算法与可测集合之间的深刻联系。数学家们正在探索如何利用伯恩施坦的发现。例如，在罗宗及其同事今年发表的论文中，他们通过研究计算机科学背景下的相同问题，发现可以为称为树的特殊图着色。该结果还阐明了数学家可能使用哪些工具来研究树对应的动力系统。"尝试在一个我连基本定义都不理解的领域证明结果，这是非常有趣的经历，"罗宗说。
数学家们也一直在努力将问题反向转化。在一个案例中，他们使用集合论证明了某类问题求解难度的新估计。
伯恩施坦搭建的桥梁不仅为解决个别问题提供了新工具包，还让集合论学者能更清晰地审视自己的领域。过去有许多他们不知如何分类的问题，现在这种情况已经改变，因为集合论学者有计算机科学家更有序的书架作为指导。
伯恩施坦希望这个不断发展的研究领域能改变数学工作者对集合论学者工作的看法——不再视其遥远且与现实数学世界脱节。"我正努力改变这种状况，"他说，"我希望人们习惯思考无穷。"
英文来源：
A New Bridge Links the Strange Math of Infinity to Computer Science
Introduction
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.
At the time, mathematicians were deeply uncomfortable with this menagerie of different infinities. “It’s hard to wrap your head around,” said Bernshteyn, who is now at the University of California, Los Angeles.
Partly in response to that discomfort, mathematicians developed a different notion of size — one that described, say, how much length or area or volume a set might occupy, rather than the number of elements it contained. This notion of size is known as a set’s “measure” (in contrast to Cantor’s notion of size, which is a set’s “cardinality”). One of the simplest types of measure — the Lebesgue measure — quantifies a set’s length. While the set of real numbers between zero and 1 and the set of real numbers between zero and 10 are both infinite and have the same cardinality, the first has a Lebesgue measure of 1 and the second a Lebesgue measure of 10.
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 word people often use is ‘pathological,’” Bernshteyn said. “Nonmeasurable sets are really bad. They’re counterintuitive, and they don’t behave well.”
This hierarchy doesn’t just help set theorists map out the landscape of their field; it also gives them insights into what tools they can use to tackle more typical problems in other areas of math. Mathematicians in some fields, such as dynamical systems, group theory and probability theory, need information about the size of the sets they’re using. A set’s position in the hierarchy determines what tools they can use to solve their problem.
Descriptive set theorists are thus like librarians, tending to a massive bookshelf of different kinds of infinite sets (and the different ways of measuring them). Their job is to take a problem, determine how complicated a set its solution requires, and place it on the proper shelf, so that other mathematicians can take note.
Making a Choice
Bernshteyn belongs to a group of librarians who sort problems about infinite sets of nodes connected by edges, called graphs. In particular, he studies graphs that have infinitely many separate pieces, each containing infinitely many nodes. Most graph theorists don’t study these kinds of graphs; they focus on finite ones instead. But such infinite graphs can represent and provide information about dynamical systems and other important kinds of sets, making them a major area of interest for descriptive set theorists.
Here’s an example of the kind of infinite graph that Bernshteyn and his colleagues might study. Start with a circle, which contains infinitely many points. Pick one point: This will be your first node. Then move a fixed distance around the circle’s circumference. This gives you a second node. For example, you might move one-fifth of the way around the circle. Connect the two nodes with an edge. Move the same distance to a third node, and connect it to the previous one. And so on.
If you move one-fifth of the way around the circle each time, it’ll take five steps to get back where you started. In general, if you move any distance that can be written as a fraction, the nodes will form a closed loop. But if the distance can’t be written as a fraction, the process will go on forever. You’ll get an infinite number of connected nodes.
But that’s not all: This infinitely long sequence forms only the first piece of your graph. Even though it contains infinitely many nodes, it doesn’t contain all the points on the circle. To generate the other pieces of the graph, start at one of those other points. Now move the same distance at each step as you did in the first piece. You’ll end up building a second infinite sequence of connected nodes, totally disconnected from the first.
Do this for every possible new starting point on the circle. You’ll get a graph consisting of infinitely many separate pieces, with each piece made of an infinite number of nodes.
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.
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.
Your graph had infinitely many pieces. This corresponds to having infinitely many sets. You chose one item from each set — the first point you decided to color blue in each of the pieces. All those blue points formed a new set. You used the axiom of choice.
Which leads to a problem when you color the rest of the nodes in alternating patterns of blue and yellow. You’ve colored each node (which has zero length) separately, without any understanding of how nodes relate to one another when they come from different pieces of the graph. This means that you can’t describe the set of all the graph’s blue nodes, or the set of all its yellow nodes, in terms of length either. In other words, these sets are unmeasurable. Mathematicians can’t say anything useful about them.
To descriptive set theorists, this is unsatisfying. And so they want to figure out a way to color the graph in a continuous way — a way that doesn’t use the axiom of choice, and that gives them measurable sets.
To do this, remember how you built the first piece of your graph: You picked a node on a circle and connected it to a second node some distance away. Now color the first node blue, the second yellow, and the entire arc between them blue. Similarly, color the arc between the second and third nodes yellow. Color the third arc blue. And so on.
Soon, you’ll have made it almost completely around the circle — meaning that you’ve assigned a color to all the nodes in your graph except for the ones that fall in a small, leftover segment. Say the last arc you colored was yellow. How do you color this final, smaller segment? You can’t use blue, because these nodes will connect to nodes in the original arc you colored blue. But you also can’t use yellow, because these nodes connect back to yellow ones from the previous arc.
You have to use a third color — say, green — to complete your coloring.
Still, the sets of blue, yellow and green nodes you end up with are all just pieces of the circle’s circumference, rather than the scatterings of points you ended up with when you used the axiom of choice. You can calculate the lengths of these sets. They’re measurable.
Descriptive set theorists therefore place the two-color version of the problem on the lowest shelf in their hierarchy (for unmeasurable sets), while the three-color problem goes on a much higher shelf of problems — ones where lots of notions of measure can be applied.
Bernshteyn spent his years in graduate school studying such coloring problems, shelving them one by one. Then, shortly after he finished his degree, he stumbled on a potential way to shelve them all at once — and to show that these problems have a much deeper and more mathematically relevant structure than anyone had realized.
Round by Round
From time to time, Bernshteyn enjoys going to computer science talks, where graphs are finite and represent networks of computers.
In 2019, one of those talks changed the course of his 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.
But there’s a catch: Nodes can only communicate with their immediate neighbors, using so-called local algorithms. First, each node runs the same algorithm and assigns itself a color. It then communicates with its neighbors to learn how other nodes are colored in a small region around it. Then it runs the algorithm again to decide whether to keep its color or switch it. It repeats this step until the whole network has a proper coloring.
Computer scientists want to know how many steps a given algorithm requires. For example, any local algorithm that can solve the router problem with only two colors must be incredibly inefficient, but it’s possible to find a very efficient local algorithm if you’re allowed to use three.
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.
Perhaps, he thought, the two bookshelves had more in common than that. Perhaps the connection between these two fields went much, much deeper.
Perhaps all the books, and their shelves, were identical, just written in different languages — and in need of a translator.
Opening the Door
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.
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.
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. “Any algorithm in our setup corresponds to a way of measurably coloring any graph in the descriptive set theory setup,” Rozhoň said.
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. “This is a very interesting experience, trying to prove results in a field where I don’t understand even the basic definitions,” Rozhoň said.
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 tool kit 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.
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.”