無窮集合遇上算法：集合論的新橋梁

導語

描述集合論長期處于數學邊緣，被視為研究奇異無窮集合的孤僻領域。然而數學家安東·伯恩施坦的突破性成果意外搭建起集合論與現代計算機科學之間的橋梁，將無窮集合的可測性問題與分布式算法的效率聯系起來。這一跨界發現正重塑兩門學科的研究版圖，開啟理解“無窮”本質的新路徑。

關鍵詞：描述集合論、無窮集合、可測性、分布式算法、圖著色、無窮圖、可定義性與計算

Joseph Howlett丨作者

朱培元丨翻譯

趙思怡丨審校

文章題目：A New Bridge Links the Strange Math of Infinity to Computer Science 文章鏈接：https://www.quantamagazine.org/a-new-bridge-links-the-strange-math-of-infinity-to-computer-science-20251121/ 發表時間：2025年11月21日 文章來源：Quanta magazine

集合論的奇異世界與新興橋梁

現代數學的建立在集合論的基礎之上——這門學科研究如何對抽象的物體集合進行系統化組織。但通常情況下，研究型數學家解決具體問題時并不需要思考集合論本身。他們可以將集合的性質視為理所當然，繼續推進自己的工作。

描述集合論學者則是個例外。這個由數學家組成的小型群體從未停止研究集合的根本性質——尤其是其他數學家避之不及的奇異無窮集合。

如今，這片研究領域不再孤獨。2023年，數學家安東·伯恩施坦（Anton Bernshteyn）發表了一項深刻而令人驚異的發現，在描述集合論的遙遠數學前沿與現代計算機科學之間建立了橋梁。

他證明了關于某類無窮集合的所有問題，都可以轉化為計算機網絡通信問題的表達形式。連接這兩個學科的橋梁令雙方研究者都感到震驚：集合論使用邏輯語言，計算機科學使用算法語言；集合論處理無窮概念，計算機科學處理有限對象。這兩類問題本不應存在關聯，更不用說等價性。

“這確實非常難以置信，”布拉格查理大學（Charles University）的計算機科學家瓦茨拉夫·羅佐尼（Václav Rozhoň）表示，“就像本不該存在的聯系?！?/p>

自伯恩施坦的成果發表后，同行們開始探索如何在這座橋梁上往返穿梭，以證明兩岸的新定理，并試圖將橋梁延伸至新的問題類別。一些描述集合論學者甚至開始運用計算機科學的洞見來重組整個領域的研究版圖，重新思考對無窮本質的理解。

圖1：Anton Bernshteyn一直在揭示和探索集合論與更多應用領域之間的重要聯系，如計算機科學和動力系統。

“長期以來我們一直在研究非常相似的問題，卻從未直接交流過，”卡內基梅隆大學（Carnegie Mellon University）的描述集合論學者克林頓·康利（Clinton Conley）指出，“這座橋梁為各種全新合作開啟了大門?！?/p>

從誤解到頓悟：一位數學家的跨界旅程

伯恩施坦本科時期首次接觸描述集合論時，這門學科被描述為曾經重要但已衰落的領域。直到一年多后，他才發現那位教授的說法有誤。

2014年，作為伊利諾伊大學（University of Illinois）的研一學生，伯恩施坦選修了后來成為他導師之一的阿努什·采魯尼安（Anush Tserunyan）的邏輯學課程。她糾正了這個誤解：“我進入這個領域完全歸功于她。她真正展現了邏輯與集合論如同連接數學各個分支的萬能膠?！?/p>

圖2：Anush Tserunyan將描述集理論視為將數學不同領域聯系在一起的紐帶。

描述集合論可追溯至喬治·康托爾（Georg Cantor），他于1874年證明了存在不同等級的無窮大。例如，整數集｛0,1,2,3…｝與分數集規模相同，但小于所有實數構成的集合。

當時，數學家們對這種無窮大的層級結構感到極度不適?！昂茈y理解透徹，”現任職于加州大學洛杉磯分校（University of California, Los Angeles）的伯恩施坦說道。

作為應對這種不適感的努力之一，數學家們發展了另一種衡量規模的概念——不是通過元素數量，而是通過集合可能占據的長度、面積或體積來度量。這種度量方式被稱為集合的“測度”（與康托爾的“基數”概念相對）。最簡單的測度類型——勒貝格測度（Lebesgue measure）——可以量化集合的長度。雖然0到1之間的實數集與0到10之間的實數集都具有無窮基數且基數相同，但前者的勒貝格測度為1，后者為10。

圖3：Georg Cantor發現數學上的無限可以有許多不同的形式和大小。

為了研究更復雜的集合，數學家們使用其他類型的測度。集合結構越怪異，可用的度量方式就越少。描述集合論學者研究的是：根據不同的“測度”定義，哪些集合可以被度量。他們根據這些問題的答案將集合排列成層級結構：頂端是容易構造且可用任意測度概念研究的集合；底端是“不可測”集合，它們過于復雜而無法被任何方式度量。“人們常用‘病態的’來形容它們，”伯恩施坦解釋道，“不可測集合的性質非常糟糕，既違反直覺又行為難測。”

這種層級結構不僅幫助集合論學者繪制領域圖譜，還為他們提供了解決其他數學領域典型問題的重要工具。在動力系統、群論和概率論等領域，數學家需要了解所用集合的規模信息。集合在層級結構中的位置決定了他們能使用哪些工具解決問題。

因此，描述集合論學者如同圖書管理員，負責管理存有各類無窮集合（及其不同度量方式）的巨大書架。他們的工作是根據問題所需集合的復雜程度，將其歸置于合適的層級，供其他數學家參考。

無窮圖的著色謎題：從選擇公理到可測集合

伯恩施坦屬于專門研究由邊連接節點構成的無限圖（即圖論中的圖）的“圖書管理員”群體。他主要研究由無限多個獨立部分組成、每部分包含無限多個節點的圖。大多數圖論學者不研究這類圖，而是專注于有限圖。但這種無限圖能夠表征動力系統和其他重要集合類型，因此成為描述集合論的重要研究方向。

以伯恩施坦研究的典型無限圖為例：從一個包含無限多個點的圓開始，選取一個點作為首節點，沿圓周移動固定距離得到第二節點（例如移動圓周長的五分之一），用邊連接兩點。繼續移動相同距離得到第三節點，以此類推。

若每次移動五分之一圓周，五步后將回到起點。通常，若移動距離可用分數表示，節點將形成閉合環路；若移動距離無法用分數表示，此過程將永無止境，形成由無限多個連接節點組成的序列。

但這僅是圖的第一部分：盡管包含無限多個節點，卻未包含圓上所有點。要生成圖的其他部分，需從圓上其他點出發，每次移動與第一部分相同的距離，最終構建出第二個無限連接節點序列，且與第一部分完全斷開。

對圓上所有可能的新起點重復此過程，將得到由無限多個獨立部分構成的圖，每部分都包含無限多個節點。

數學家隨后提出著色問題：能否用兩種顏色為所有節點著色，且相鄰節點顏色不同？表面看解決方案很直接：觀察圖的第一部分，選取一個節點涂藍，其余節點按黃藍交替模式著色；對圖中每個部分重復此操作——選取一個節點涂藍，然后交替顏色。最終僅用兩種顏色即可完成任務。

但完成這種著色需要依賴一個隱藏假設，即集合論中的選擇公理（axiom of choice）。這是構建所有數學陳述的九大基礎之一。該公理指出：若從一組集合出發，可以從每個集合中選取一個元素組成新集合——即使面對無限多個集合。此公理雖能證明許多重要命題，但會導致奇異悖論，因此描述集合論學者通常避免使用。

你的圖包含無限多個部分，對應無限多個集合。你從每個集合中選取了一個元素——即每個部分中首先決定涂藍的點。所有這些藍點構成了新集合。你使用了選擇公理。

這導致在用藍黃交替模式為剩余節點著色時出現問題：你單獨為每個節點（長度為零）著色，卻未考慮來自圖不同部分的節點如何關聯。這意味著你無法用長度來描述圖中所有藍點集或所有黃點集。換言之，這些集合是不可測的，數學家無法對其性質進行有效分析。

這對描述集合論學者而言難以接受。因此他們尋求在不使用選擇公理的前提下實現連續著色，從而獲得可測集合。

為此，回顧構建圖第一部分的方式：在圓上選取一個節點，連接至一定距離外的第二節點?，F將第一節點涂藍，第二節點涂黃，兩者之間的整個弧段涂藍；接著將第二與第三節點間的弧段涂黃；第三段弧涂藍，依此類推。

很快將接近圓周終點——此時除一小段剩余弧段外，圖中所有節點已分配顏色。假設最后涂色的弧段為黃色，該如何處理這最后的小段？不能使用藍色，因為這些節點會連接至初始藍色弧段中的節點；也不能使用黃色，因為它們會連接回前一段黃色弧段中的節點。

必須引入第三種顏色（例如綠色）才能完成著色。然而，這樣得到的藍、黃、綠色節點集都是圓周的可測子集（即弧段），而非使用選擇公理時得到的離散點集。你可以計算這些集合的長度，它們都是可測的。

因此，描述集合論學者將雙色問題歸入層級結構的底層（對應不可測集合），而三色問題則置于允許應用多種測度概念的高層書架。

算法與無窮的相遇：一座改變學科圖景的橋梁

伯恩施坦在研究生期間持續研究此類著色問題，逐個歸類。獲得學位后不久，他偶然發現了一種系統性解決方案的可能路徑——這些問題的數學結構遠比人們認知的更為深刻。

伯恩施坦偶爾會參加計算機科學的講座，那里研究的圖是有限的，代表計算機網絡。2019年的一場講座改變了他的學術軌跡。該講座關于“分布式算法”（distributed algorithms）——指導網絡中多臺計算機在沒有中央協調器的情況下同步執行任務的指令集。

以建筑內的Wi-Fi路由器為例：相鄰路由器若使用相同通信頻段會產生干擾，因此每個路由器需選擇與直接鄰居不同的頻道。計算機科學家將其抽象為圖著色問題：用節點表示路由器，邊連接相鄰節點，使用兩種顏色（代表兩個不同頻段）為每個節點著色，且相鄰節點顏色不同。

但存在約束條件：節點只能通過所謂局部算法（local algorithms）與直接鄰居通信。首先，每個節點運行相同算法為自己著色，再與鄰居通信了解周邊節點著色情況，隨后決定是否保持或更改顏色，重復此過程直至整個網絡完成合法著色。

計算機科學家關注算法所需的步驟數：例如任何使用兩種顏色的局部算法都極低效，但若允許使用三種顏色，則能找到高效局部算法。

聽講座時，伯恩施坦意識到演講者討論的不同問題閾值中，有一個與描述集合論中的某個閾值極其相似——即對特定無限圖進行可測著色所需的顏色數。對伯恩施坦而言，這不僅是巧合。不僅是計算機科學家也像圖書管理員般根據算法效率歸類問題，也不僅是這些問題同樣可用圖著色形式表達?；蛟S兩個“書架”的共通之處遠不止于此?；蛟S這兩個領域的聯系遠比想象中更深?；蛟S所有“書籍”及其“書架”本質相同，只是書寫語言各異——亟需一位翻譯者。

伯恩施坦開始具體構建這種聯系。他試圖證明：每個高效局部算法都能轉化為對滿足特定條件的無限圖進行勒貝格可測著色的方法。這意味著計算機科學的重要問題類別與集合論高層級書架具有等價性。

他從計算機科學講座中的網絡問題類別入手，關注其核心原則——無論圖包含千個節點還是十億節點，任何節點的算法都只使用其局部鄰域信息。

要正常運行，算法只需為給定鄰域內的每個節點標記唯一編號，以便記錄鄰近節點信息并發出指令。這在有限圖中很容易實現：只需為圖中每個節點分配不同編號。

圖4：計算機科學家Václav Rozhoň一直在利用集合論和網絡科學之間新發現的聯系來解決他感興趣的問題。

若能將相同算法應用于無限圖，則意味著可以用可測方式為圖著色，從而解決集合論側的圖著色問題。但難題在于：這些無限圖是“不可數”的，無法為所有節點分配唯一標記。伯恩施坦的挑戰在于找到更巧妙的標記方法。他知道必須重復使用標記，但只要鄰近節點標記不同即可。是否存在避免在同一鄰域重復使用標記的方法？

伯恩施坦證明了無論使用多少種標記，無論局部鄰域包含多少節點，總存在這樣的標記方案。這意味著總可以安全地將計算機科學側的算法拓展至集合論側。“我們框架中的任何算法都對應描述集合論框架下任意圖的可測著色方法，”羅佐尼總結道。

這項證明令數學家們震驚，它揭示了計算與可定義性、算法與可測集合之間的深刻聯系。數學家們開始探索如何利用這一發現。例如羅佐尼與同事在今年發表的論文中，通過研究計算機科學語境下的對應問題，成功為特殊圖（樹，trees）著色。該成果同時揭示了研究對應動力系統可能使用的工具?！皣L試在連基本定義都不理解的領域證明結論，是非常有趣的體驗，”羅佐尼表示。

數學家們也在進行反向翻譯工作：他們運用集合論證明了某類問題計算難度的新估計。

伯恩施坦搭建的橋梁不僅為解決具體問題提供了新工具，還讓集合論學者獲得了更清晰的領域視野。許多過去無法分類的問題現在有了轉機，因為集合論學者可以參照計算機科學更系統化的“書架”進行歸類。

伯恩施坦希望這一不斷發展的研究領域能改變數學家對集合論研究的看法——不再視其為與現實數學世界脫節的邊緣領域?！拔艺Ω淖冞@種現狀，”他表示，“希望人們能逐漸習慣思考無窮?！?/p>

人工智能與數學讀書會

數十年來，人工智能的理論發展和技術實踐一直與科學探索相伴而生，尤其在以大模型為代表的人工智能技術應用集中爆發的當下，人工智能正在加速物理、化學、生物等基礎科學的革新，而這些學科也在反過來啟發人工智能技術創新。在此過程中，數學作為兼具理論屬性與工具屬性的重要基礎學科，與人工智能關系甚密，相輔相成。一方面，人工智能在解決數學領域的諸多工程問題、理論問題乃至圣杯難題上屢創記錄。另一方面，數學持續為人工智能構筑理論基石并拓展其未來空間。這兩個關鍵領域的交叉融合，正在揭開下個時代的科學之幕。

為了探索數學與人工智能深度融合的可能性，集智俱樂部聯合同濟大學特聘研究員陳小楊、清華大學交叉信息學院助理教授袁洋、南洋理工大學副教授夏克林三位老師，共同發起“人工智能與數學”讀書會，希望從 AI　for　Math，Math　for　AI 兩個方面深入探討人工智能與數學的密切聯系。讀書會已完結，現在報名可加入社群并解鎖回放視頻權限。

詳情請見：

拓撲學課程：從空間直覺到系統科學

你是否曾思考過：為什么咖啡杯在數學上可以變成甜甜圈？為什么混沌系統中會出現周期軌、可約化結構和“奇怪吸引子”模式？為什么神經網絡、量子物理甚至心理結構，都可以從“拓撲”角度理解？

拓撲學不僅是數學的抽象分支，更提供了系統的思維方式，讓我們理解連續性、結構不變性乃至復雜系統的整體規律。從歐拉七橋問題到DNA的纏結，從量子場論到思維科學與腦科學，拓撲學思想正在各學科中普遍而深刻地重塑著我們的認知方式。

集智學園聯合北京大學博士金威老師開設，課程將于11月23日開啟，現在加入可享早鳥價格。

詳情請見：

1.

2.

3.

4.

5.

6.