现代数学建立在集合论的基础之上，它系统性地研究抽象对象集合的组织方式。然而，对于大多数研究型数学家而言，在解决具体问题时，他们通常不需要深入思考集合论本身，而可以将其性质视为理所当然。
但描述集合论的学者们是个例外。这个小众的数学家群体持续探究集合的根本性质，特别是那些其他人避之不及的奇异无穷集合。如今，这个领域不再孤单。2023年，数学家安东·伯恩施坦发表了一项深刻且令人惊讶的发现，在描述集合论的遥远前沿与现代计算机科学之间，架起了一座坚实的桥梁。
他证明，关于某类无穷集合的问题，可以完全转化为对计算机网络通信问题的描述。这座桥梁震惊了双方的研究者：集合论使用逻辑语言处理无穷概念，而计算机科学使用算法语言处理有限对象。这两类问题本不应有关联，更不用说等价。
“这确实非常难以置信，”布拉格查理大学的计算机科学家瓦茨拉夫·罗佐尼表示，“就像本不该存在的联系。”
自该成果发表后，研究者们开始探索如何在桥上双向通行，以证明两岸的新定理，并试图将桥梁延伸到新的问题类别。一些描述集合论学者甚至开始运用计算机科学的洞见，来重组整个领域的研究版图，重新思考对无穷本质的理解。
“长期以来我们一直在研究非常相似的问题，却从未直接交流过，”卡内基梅隆大学的描述集合论学者克林顿·康利指出，“这座桥梁为各种全新合作开启了大门。”
从误解到顿悟：一位数学家的跨界旅程
伯恩施坦本科时首次接触描述集合论，当时这门学科被描述为曾经重要但已衰落的领域。直到一年多后，他才发现这个说法是错误的。
2014年，作为伊利诺伊大学的研一学生，伯恩施坦选修了后来成为他导师之一的阿努什·采鲁尼安的逻辑学课程。她纠正了这一误解：“我进入这个领域完全归功于她。她真正展现了逻辑与集合论如同连接数学各个分支的万能胶。”
描述集合论可追溯至乔治·康托尔，他于1874年证明了存在不同等级的无穷大。例如，整数集与分数集规模相同，但都小于所有实数构成的集合。
当时，数学家们对这种无穷层级结构感到极度不适。作为回应，他们发展出了另一种衡量“规模”的概念——不是通过元素数量，而是通过集合可能占据的长度、面积或体积来度量，这被称为集合的“测度”。
最简单的测度类型——勒贝格测度——可以量化集合的长度。虽然0到1之间的实数集与0到10之间的实数集都具有相同的无穷基数，但前者的勒贝格测度为1，后者为10。
为了研究更复杂的集合，数学家使用其他类型的测度。集合结构越怪异，可用的度量方式就越少。描述集合论学者研究的是：根据不同的“测度”定义，哪些集合可以被度量。他们根据答案将集合排列成层级结构：顶端是易于构造且可用任意测度概念研究的集合；底端是“不可测”集合，它们过于复杂，无法被任何方式度量。
“人们常用‘病态的’来形容它们，”伯恩施坦解释道，“不可测集合的性质非常糟糕，既违反直觉又行为难测。”
这种层级结构不仅帮助集合论学者绘制领域图谱，还为他们提供了解决其他数学领域（如动力系统、群论和概率论）问题的重要工具。集合在层级中的位置决定了数学家能使用哪些工具。
因此，描述集合论学者如同管理着一个存有各类无穷集合及其度量方式的巨大图书馆，他们的工作是根据集合的复杂程度，将其归类到合适的书架上。
无穷图的着色谜题：从选择公理到可测集合
伯恩施坦研究的是由无限多个独立部分构成、每部分又包含无限多个节点的“无穷图”。这类图能够表征动力系统等重要集合，因此是描述集合论的重要方向。
以一个典型的无限图为例：从一个包含无限多个点的圆开始，选取一个点作为首节点，沿圆周移动一个固定距离（例如圆周长的五分之一）得到第二个节点，并用边连接两点。持续这个过程。
如果移动距离是圆周长的五分之一，五步后将回到起点，形成一个闭合环路。如果移动距离是一个无理数（不能用分数表示），这个过程将永无止境，形成一个无限长的节点序列。
但这只是图的第一部分。要生成图的其他部分，需要从圆上其他未被触及的点出发，重复相同的移动规则。最终，你会得到一个由无限多个独立部分构成的图，每个部分都包含无限多个节点。
数学家随后提出着色问题：能否仅用两种颜色为所有节点着色，并确保相邻节点颜色不同？表面上看，解决方案很直接：对图的每一部分，任选一个节点涂成蓝色，然后以黄蓝交替的模式为其余节点着色。
然而，完成这种着色依赖于一个隐藏假设——集合论中的选择公理。这是构建数学的基础公理之一，它允许我们从一组集合（即使是无限多个）的每一个中都选取一个元素来构成新集合。
在你的图中，有无限多个部分，对应无限多个集合。你从每个集合中选取了一个元素（即首先决定涂蓝的点），这使用了选择公理。由此产生的蓝点集合和黄点集合，在用勒贝格测度等工具衡量时，会变得“不可测”，数学家无法有效分析其性质。
这对描述集合论学者来说是无法接受的。因此，他们寻求在不使用选择公理的前提下实现“可测”着色，即产生的颜色集合是可度量的。
为此，考虑另一种着色方式：不是为离散的点着色，而是为连续的弧段着色。从第一节点（蓝）与第二节点（黄）之间的弧段开始涂蓝，接着为第二与第三节点之间的弧段涂黄，以此类推。
很快你会接近圆周的终点，最后会剩下一小段弧。假设最后涂色的弧段是黄色，那么这最后一段既不能涂蓝（会连接初始的蓝色弧段），也不能涂黄（会连接前一段黄色弧段）。你必须引入第三种颜色（例如绿色）才能完成着色。
这样得到的蓝、黄、绿色节点集都是圆周上可测的子集（即弧段），它们的长度可以被计算。因此，描述集合论学者将“双色问题”归入层级结构的底层（对应不可测集合），而“三色问题”则被置于允许应用多种测度概念的高层。
算法与无穷的相遇：一座改变学科图景的桥梁
研究生毕业后不久，伯恩施坦在参加一个关于分布式算法的计算机科学讲座时，产生了突破性的洞见。这类算法指导网络中的多台计算机在没有中央协调器的情况下同步执行任务。
一个典型例子是Wi-Fi路由器频道分配：相邻路由器需选择不同频段以避免干扰，这可以抽象为一个图着色问题。节点（路由器）只能与直接邻居通信，运行局部算法来为自己选择颜色，并通过迭代最终使整个网络达成合法的着色方案。
计算机科学家关注算法所需的步骤数（效率）。伯恩施坦意识到，计算机科学中“使用局部算法为有限图着色所需的最少颜色数”这个阈值，与描述集合论中“为特定无穷图进行可测着色所需的最少颜色数”的阈值惊人地相似。
这不仅仅是巧合。伯恩施坦开始构建具体的联系。他试图证明：每个高效的局部分布式算法，都能转化为对满足特定条件的无穷图进行勒贝格可测着色的方法。这意味着计算机科学的一个重要问题类别，与集合论高层级书架上的问题是等价的。
核心挑战在于：有限图中的算法可以为每个节点分配唯一标记以便追踪，但伯恩施坦研究的无穷图是“不可数”的，无法做到这一点。他需要一种更巧妙的标记方案，允许重复使用标记，但确保在任何一个局部邻域内标记不重复。
伯恩施坦成功证明了无论使用多少种标记，无论局部邻域多大，总存在这样的方案。这意味着总可以将计算机科学侧的算法安全地拓展到集合论侧。
这项证明揭示了计算与可定义性、算法与可测集合之间的深刻联系。数学家们开始利用这一发现进行双向探索。例如，罗佐尼与同事通过研究计算机科学语境下的对应问题，成功解决了特殊无穷图（树）的着色问题，同时也为研究相关的动力系统找到了新工具。
反过来，集合论的见解也被用于证明计算机科学中类似图着色问题的计算复杂度的新边界。
伯恩施坦搭建的桥梁不仅提供了解决具体问题的新工具，更让集合论学者获得了更清晰的领域视野。许多过去难以归类的问题现在有了转机，因为他们可以参照计算机科学中更为系统化的问题分类体系。
这一跨界研究正逐步改变数学家对集合论的看法，使其不再被视为与现实数学世界脱节的孤岛。“我正努力改变这种现状，”伯恩施坦表示，“希望人们能逐渐习惯思考无穷。”
发表于 前天 12:22
|
查看: 5|
回复: 0
