一座新橋梁：連接無窮之奇的數(shù)學(xué)與計算機科學(xué)——Quanta Magazine

★置頂zzllrr小樂公眾號（主頁右上角）數(shù)學(xué)科普不迷路！

描述集合論（descriptive set theory）學(xué)者致力于研究無窮領(lǐng)域的小眾數(shù)學(xué)。如今，他們發(fā)現(xiàn)這些抽象問題竟能以具象的算法語言重新詮釋。

圖源：Valentin Tkach / Quanta Magazine

作者：Joseph Howlett（量子雜志撰稿人）2025-11-21

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號）2025-11-22

所有現(xiàn)代數(shù)學(xué)都建立在集合論的基礎(chǔ)之上 —— 這門學(xué)科研究如何組織抽象對象的集合。但通常，研究型數(shù)學(xué)家在解決自身問題時無需刻意考量集合論：他們只需默認(rèn)集合的行為符合預(yù)期，便可繼續(xù)開展研究。

描述集合論學(xué)者卻是例外。這個小眾的數(shù)學(xué)家群體從未停止探索集合的本質(zhì) —— 尤其是那些被其他數(shù)學(xué)家忽視的、奇特的無窮集合。

而他們的領(lǐng)域如今不再孤立。2023年，數(shù)學(xué)家安東?伯恩斯坦（Anton Bernshteyn）發(fā)表了一項重大發(fā)現(xiàn) https://link.springer.com/article/10.1007/s00222-023-01188-3 ，揭示了描述集合論這一遙遠(yuǎn)的數(shù)學(xué)前沿與現(xiàn)代計算機科學(xué)之間令人意外的深層關(guān)聯(lián)。

他證明，所有關(guān)于特定無窮集合的問題，都可轉(zhuǎn)化為計算機網(wǎng)絡(luò)通信相關(guān)的問題。這座連接兩大領(lǐng)域的橋梁讓雙方研究者都倍感震驚：集合論學(xué)者使用邏輯語言，計算機科學(xué)家則依賴算法語言；集合論探討無窮，計算機科學(xué)聚焦有限。從常理來看，兩者的問題本無關(guān)聯(lián)，更不用說等價了。

“這太不可思議了，” 布拉格查理大學(xué)的計算機科學(xué)家瓦茨拉夫?羅茲洪（Václav Rozhoň）表示，“按理說，這種關(guān)聯(lián)根本不該存在。”

自伯恩斯坦的成果發(fā)表以來，同行們紛紛探索如何利用這座 “橋梁” 在兩大領(lǐng)域間雙向推進，證明新定理，并嘗試將橋梁延伸至更多類別的問題。部分描述集合論學(xué)者甚至開始借鑒計算機科學(xué)的洞見，重構(gòu)自身領(lǐng)域的知識體系，并重新思考對無窮的理解。

安東·伯恩斯坦一直在發(fā)掘和探索集合論與更偏向應(yīng)用的領(lǐng)域（如計算機科學(xué)和動力系統(tǒng)）之間的重要聯(lián)系。

圖源：Siiri Kivimaki

“長期以來，我們一直在研究極為相似的問題，卻從未有過直接交流，” 卡內(nèi)基梅隆大學(xué)的描述集合論學(xué)者克林頓?康利（Clinton Conley）說，“這一發(fā)現(xiàn)為所有新的合作打開了大門。”

破碎的集合

伯恩斯坦本科時首次聽聞描述集合論 —— 當(dāng)時有教授稱這是一個曾有價值但如今已沒落的領(lǐng)域。一年多后，他才發(fā)現(xiàn)這位教授的說法有誤。

2014年，作為伊利諾伊大學(xué)的一年級研究生，伯恩斯坦選修了阿努什?采魯尼揚（Anush Tserunyan）的邏輯課程（后者后來成為他的導(dǎo)師之一）。采魯尼揚糾正了他的誤解。“我能進入這個領(lǐng)域全歸功于她，” 伯恩斯坦說，“她讓我意識到，邏輯與集合論就像膠水，連接著數(shù)學(xué)的各個不同分支。”

描述集合論可追溯至格奧爾格?康托爾（Georg Cantor）。1874年，康托爾證明了無窮存在不同的 “大小”（參閱 ）：例如，整數(shù)集（0、1、2、3……）與所有分?jǐn)?shù)組成的集合大小相同，但小于實數(shù)集的大小。

阿努什?采魯尼揚認(rèn)為描述性集合論是將數(shù)學(xué)不同部分連接在一起的連接組織。

圖源：Anush Tserunyan（阿努什?采魯尼揚）

當(dāng)時，數(shù)學(xué)家們對這種 “無窮的多樣態(tài)” 深感困惑。“這很難讓人理解，” 如今任職于加州大學(xué)洛杉磯分校的伯恩斯坦說。

為回應(yīng)這種困惑，數(shù)學(xué)家們提出了一種新的 “大小” 概念 —— 描述集合所占據(jù)的長度、面積或體積，而非其包含的元素數(shù)量。這種 “大小” 被稱為集合的 “測度”measure（與康托爾提出的 “基數(shù)” cardinality相對）。最簡單的測度類型之一是勒貝格測度，用于量化集合的長度。例如，0 到 1 之間的實數(shù)集與 0 到 10 之間的實數(shù)集都是無窮集，且基數(shù)相同，但前者的勒貝格測度為 1，后者為 10。

為研究更復(fù)雜的集合，數(shù)學(xué)家們會使用其他類型的測度。集合越 “不規(guī)則”，可用于測量它的方法就越少。描述集合論學(xué)者的核心問題是：哪些集合能通過不同的 “測度” 定義進行測量？他們根據(jù)答案將集合劃分為不同層級：層級頂端是構(gòu)造簡單、可通過任意測度定義研究的集合；層級底端則是 “不可測集”—— 這些集合過于復(fù)雜，根本無法測量。“人們常用‘病態(tài)’pathological來形容它們，” 伯恩斯坦說，“不可測集非常特殊，違背直覺且行為反常。”

這種層級分類不僅幫助集合論學(xué)者梳理領(lǐng)域版圖，還為其他數(shù)學(xué)分支的研究者提供了工具選擇的依據(jù)。動力系統(tǒng)、群論、概率論等領(lǐng)域的數(shù)學(xué)家需要了解其研究對象集合的大小，而集合在層級中的位置決定了他們可使用的解題工具。

因此，描述集合論學(xué)者就像圖書管理員，打理著一個收藏著各類無窮集合（及對應(yīng)測量方法）的巨大書架。他們的工作是：接收一個問題，判斷其解所需集合的復(fù)雜程度，然后將問題歸置到合適的 “書架” 上，供其他數(shù)學(xué)家參考。

格奧爾格?康托爾發(fā)現(xiàn)數(shù)學(xué)的無限可以有許多不同的形態(tài)和大小。

圖源：Emilio Segre Visual Archives

做出選擇

伯恩斯坦所屬的研究群體專注于整理與 “圖” 相關(guān)的無窮集合問題 —— 圖是由節(jié)點和連接節(jié)點的邊組成的結(jié)構(gòu)。他尤其關(guān)注具有無窮多個獨立分支、且每個分支包含無窮多個節(jié)點的圖。大多數(shù)圖論學(xué)者不研究這類圖，而是聚焦于有限圖。但這類無窮圖能表征動力系統(tǒng)及其他重要集合的信息，因此成為描述集合論學(xué)者的主要研究方向之一。

以下是伯恩斯坦及其同事研究的一類無窮圖示例：

從一個包含無窮多個點的圓開始，選取一個點作為第一個節(jié)點；

沿著圓周移動固定距離，得到第二個節(jié)點（例如移動圓周的五分之一），用邊連接這兩個節(jié)點；

繼續(xù)移動相同距離得到第三個節(jié)點，與前一個節(jié)點連接，依此類推。

如果每次移動的距離是分?jǐn)?shù)（如五分之一），則經(jīng)過有限步后會回到起點，節(jié)點形成閉合回路；

但如果移動距離無法表示為分?jǐn)?shù)，則這個過程會無限進行，形成無窮多個相互連接的節(jié)點。

圖源：Mark Belan / 編譯：zzllrr小樂

但這只是圖的第一個分支。即便包含無窮多個節(jié)點，它也未覆蓋圓上的所有點。要生成其他分支，只需從圓上未被包含的點出發(fā)，按相同距離移動，即可形成第二個無窮節(jié)點序列，且與第一個分支完全獨立。

對圓上所有可能的起點重復(fù)這一過程，最終會得到一個由無窮多個獨立分支組成的圖，每個分支都包含無窮多個節(jié)點。

數(shù)學(xué)家們會探討這類圖的著色問題：例如，僅用兩種顏色，能否為所有節(jié)點著色，使得任意兩個相鄰節(jié)點顏色不同？表面上看，解決方案很簡單：

對第一個分支，任選一個節(jié)點染藍(lán)色，其余節(jié)點按 “黃 - 藍(lán) - 黃 - 藍(lán)” 的交替模式著色；

對所有其他分支重復(fù)此操作，最終僅用兩種顏色即可完成著色。

但這個著色過程依賴于一個隱含假設(shè) —— 集合論中的 “選擇公理”。這是構(gòu)建所有數(shù)學(xué)命題的九大基本公理之一，其核心是：給定任意多個集合，即使集合數(shù)量無窮，也能從每個集合中選出一個元素組成新集合。選擇公理十分有用，能幫助數(shù)學(xué)家證明各類重要命題，但也會導(dǎo)致奇特的悖論，因此描述集合論學(xué)者通常會回避它。

在上述著色問題中，圖的無窮多個分支對應(yīng)無窮多個集合，而從每個分支中選擇第一個染藍(lán)色的節(jié)點，本質(zhì)上就是在運用選擇公理。當(dāng)后續(xù)按交替模式著色時，每個節(jié)點（長度為零）都是被單獨處理的，我們無法理解來自不同分支的節(jié)點之間的關(guān)聯(lián) —— 這意味著，所有藍(lán)色節(jié)點組成的集合和所有黃色節(jié)點組成的集合都無法用長度來描述，即這些集合是不可測的，數(shù)學(xué)家們無法從中獲取有用信息。

這讓描述集合論學(xué)者感到不滿意。他們希望找到一種 “連續(xù)” 的著色方式 —— 不依賴選擇公理，且能得到可測集合。具體方法如下：

回顧第一個分支的構(gòu)建過程：

從圓上一點出發(fā)，按固定距離連接下一個節(jié)點；

給第一個節(jié)點染藍(lán)色，第二個節(jié)點染黃色，并將兩者之間的弧段也染藍(lán)色；

第二個節(jié)點與第三個節(jié)點之間的弧段染黃色，第三個弧段染藍(lán)色，依此類推。

很快，著色會幾乎覆蓋整個圓，僅剩一小段未著色的區(qū)域。假設(shè)最后一段著色的弧是黃色，那么這段剩余區(qū)域該如何著色？既不能用藍(lán)色（因為這些節(jié)點與藍(lán)色弧段的節(jié)點相鄰），也不能用黃色（因為與黃色弧段的節(jié)點相鄰）—— 必須使用第三種顏色（如綠色）才能完成著色。

最終，藍(lán)色、黃色和綠色節(jié)點組成的集合都是圓周的一部分，而非運用選擇公理時那種分散的點集。這些集合的長度可以計算，是可測的。

因此，描述集合論學(xué)者將 “兩色著色問題” 歸置到層級的最底層（對應(yīng)不可測集），而 “三色著色問題” 則被歸置到更高層級 —— 這類問題可通過多種測度定義進行研究。

伯恩斯坦在研究生階段一直致力于研究這類著色問題，并逐一將它們歸類。獲得學(xué)位后不久，他偶然發(fā)現(xiàn)了一種可一次性歸類所有這類問題的方法，并意識到這些問題蘊含著比人們此前認(rèn)知更深層、更具數(shù)學(xué)意義的結(jié)構(gòu)。

一輪又一輪

伯恩斯坦偶爾會參加計算機科學(xué)講座。在計算機科學(xué)中，圖是有限的，通常用于表征計算機網(wǎng)絡(luò)。

2019年，一場關(guān)于 “分布式算法” 的講座改變了他的職業(yè)生涯。分布式算法是指在網(wǎng)絡(luò)中的多臺計算機上同時運行的指令集，無需中央?yún)f(xié)調(diào)器即可完成任務(wù)。

舉個例子：一棟建筑中有多臺 Wi-Fi 路由器，相鄰路由器若使用相同通信信道會產(chǎn)生干擾，因此每臺路由器需選擇與相鄰路由器不同的信道。

計算機科學(xué)家可將其轉(zhuǎn)化為圖著色問題：

每個路由器視為一個節(jié)點，相鄰路由器用邊連接；

僅用兩種顏色（代表兩種信道），為所有節(jié)點著色，使得相鄰節(jié)點顏色不同。

但這里有個關(guān)鍵限制：節(jié)點只能通過 “局部算法” 與直接相鄰的節(jié)點通信。具體流程為：

每個節(jié)點運行相同算法，為自己分配一個顏色；

與相鄰節(jié)點通信，了解周邊小范圍區(qū)域內(nèi)其他節(jié)點的著色情況；

再次運行算法，決定保留或更改自身顏色；

重復(fù)上述步驟，直至整個網(wǎng)絡(luò)完成合規(guī)著色。

計算機科學(xué)家關(guān)注的是特定算法所需的步驟數(shù)。例如，僅用兩種顏色解決路由器著色問題的局部算法效率必然極低，但如果允許使用三種顏色，則能找到高效的局部算法。

在伯恩斯坦參加的這場講座中，演講者討論了不同問題的 “閾值”（如著色所需的最少顏色數(shù)）。他突然意識到，其中一個閾值與描述集合論中的某個閾值極為相似 —— 即給特定無窮圖進行可測著色所需的最少顏色數(shù)。

對伯恩斯坦而言，這絕非巧合：

計算機科學(xué)家也像 “圖書管理員”，根據(jù)算法效率為問題分類；

兩類問題都可通過圖和著色來表述。

他猜想，這兩個 “書架” 的共性遠(yuǎn)不止于此 —— 兩大領(lǐng)域的關(guān)聯(lián)可能遠(yuǎn)比想象中更深層。或許，所有的 “書籍” 和 “書架” 本質(zhì)上都是相同的，只是用不同語言書寫，亟需一位 “翻譯者”。

打開大門

伯恩斯坦著手將這種關(guān)聯(lián)具象化。他希望證明：每一種高效的局部算法，都能轉(zhuǎn)化為對無窮圖的勒貝格可測著色方式（滿足一些額外的重要性質(zhì)）。也就是說，計算機科學(xué)中最重要的 “書架” 之一，與集合論中最重要的 “書架” 之一（層級頂端）是等價的。

他從計算機科學(xué)講座中提到的網(wǎng)絡(luò)問題類別入手，聚焦其核心規(guī)則：無論圖有一千個還是十億個節(jié)點，任意節(jié)點的算法僅需利用其局部鄰域的信息。

算法要正常運行，只需為給定鄰域內(nèi)的每個節(jié)點分配唯一編號，以便記錄相鄰節(jié)點的信息并發(fā)出指令。在有限圖中，這很容易實現(xiàn) —— 只需給每個節(jié)點分配不同的編號。

計算機科學(xué)家瓦茨拉夫·羅茲洪（Václav Rozhoň）利用集合論與網(wǎng)絡(luò)科學(xué)之間新發(fā)現(xiàn)的聯(lián)系來解決他感興趣的問題。

圖源：托馬什·普林克（Tomá? Princ），查理大學(xué)

如果伯恩斯坦能在無窮圖上運行相同的算法，就意味著他能以可測方式為無窮圖著色，從而解決集合論中的圖著色問題。但問題在于：這些無窮圖是 “不可數(shù)” 的無窮集，無法為所有節(jié)點分配唯一編號。

伯恩斯坦面臨的挑戰(zhàn)是找到更巧妙的編號方式。他知道必須重復(fù)使用編號，但只要相鄰節(jié)點的編號不同即可。那么，是否存在一種方法，能在不重復(fù)使用鄰域內(nèi)編號的前提下分配標(biāo)簽？

伯恩斯坦證明了這種方法始終存在 —— 無論使用多少個標(biāo)簽，無論局部鄰域包含多少個節(jié)點。這意味著，計算機科學(xué)中的算法總能安全地推廣到集合論領(lǐng)域。“我們框架中的任何算法，都對應(yīng)著描述集合論框架中對任意圖的可測著色方式，” 羅茲洪說。

這一證明讓數(shù)學(xué)家們倍感意外：它揭示了計算與可定義性、算法與可測集之間的深層聯(lián)系。如今，數(shù)學(xué)家們正積極利用伯恩斯坦的發(fā)現(xiàn)：例如，在今年發(fā)表的一篇論文中，羅茲洪及其同事通過計算機科學(xué)的視角，解決了一類特殊圖（樹）的著色問題 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.29 。該結(jié)果還闡明了數(shù)學(xué)家可用于研究樹對應(yīng)的動力系統(tǒng)的工具。“在一個連基本定義都不懂的領(lǐng)域證明結(jié)果，這是一種非常有趣的體驗，” 羅茲洪說。

數(shù)學(xué)家們也在嘗試反向 “翻譯” 問題。例如，他們利用集合論，對某類問題的求解難度得出了新的估算。 https://arxiv.org/abs/2111.03683

伯恩斯坦搭建的 “橋梁” 不僅提供了一套解決單個問題的新工具，還讓集合論學(xué)者能更清晰地審視自身領(lǐng)域。此前，許多問題無法分類，如今情況發(fā)生了改變 —— 集合論學(xué)者可以借助計算機科學(xué)家更系統(tǒng)的 “書架” 來指導(dǎo)分類。

伯恩斯坦希望這一新興研究領(lǐng)域能改變職業(yè)數(shù)學(xué)家對集合論研究的看法 —— 不再將其視為脫離現(xiàn)實數(shù)學(xué)世界的遙遠(yuǎn)領(lǐng)域。“我正努力改變這一點，” 他說，“我希望人們能習(xí)慣思考無窮。”

參考資料

https://www.quantamagazine.org/a-new-bridge-links-the-strange-math-of-infinity-to-computer-science-20251121/

https://link.springer.com/article/10.1007/s00222-023-01188-3

https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.29

https://arxiv.org/abs/2111.03683

小樂數(shù)學(xué)科普近期文章

出版社和作家自薦通道

小樂數(shù)學(xué)科普薦書

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

置頂加星★

數(shù)學(xué)科普不迷路！