作者 | Steve Nadis

編譯 | 陳彩嫻

編輯 | 青暮

一般情況下，當(dāng)你要對(duì)某個(gè)特定地區(qū)的植物進(jìn)行調(diào)查時(shí)，你可能會(huì)按植物的種類來劃分。

就這種方法來看，如果是沿著托斯卡納海岸的某些地帶做這類調(diào)查并不會(huì)很困難，因?yàn)槟愦蟾怕手粫?huì)發(fā)現(xiàn)一種植物，就是海松（pinus pinaster）。但是，如果你要在亞馬遜熱帶雨林中做植物統(tǒng)計(jì)，那你要找出雨林里所有植物的名字與數(shù)量就會(huì)非常困難，甚至可以說是“毫無可能”。

在探索廣闊數(shù)學(xué)圖景的征程上，數(shù)學(xué)家們也可能會(huì)遇到類似的挑戰(zhàn)，尤其是對(duì)研究描述集合論的數(shù)學(xué)家而言，因?yàn)?/span>他們要嘗試對(duì)分類問題的難度進(jìn)行評(píng)級(jí)。有時(shí)候他們會(huì)認(rèn)為某個(gè)分類任務(wù)很容易，有時(shí)候又會(huì)覺得某個(gè)分類任務(wù)太難，比如上述的亞馬遜雨林植物分類問題。

描述集合論（descriptive set theory）只是集合論的一個(gè)分支，主要研究物體的集合，可以是數(shù)字、圖形、空間中的點(diǎn)、向量，等等。實(shí)數(shù)、有理數(shù)、虛數(shù)本身就是一個(gè)集合?？梢哉f，數(shù)學(xué)家的研究范圍涵蓋了方方面面。

幾十年來，研究人員一直被一個(gè)分類問題所困擾。這個(gè)分類問題就是“無撓阿貝爾群”（torsion-free abelian groups，簡(jiǎn)稱“TFAB”）。

TFAB 問題最早由數(shù)學(xué)家 Harvey Friedman 和 Lee Stanley 在1989年所發(fā)表的一篇論文（“A Borel Reducibility Theory For Classes of Countable Structures”）中提出。在這篇論文中，Harvey Friedman 與 Lee Stanley 介紹了一種比較可數(shù)結(jié)構(gòu)分類問題難度的新方法，表明有些分類問題會(huì)非常復(fù)雜。

論文地址：https://www.jstor.org/stable/2274750?seq=1

這個(gè)問題困擾了數(shù)學(xué)家們30多年。今年，都靈大學(xué)的數(shù)學(xué)家 Gianluca Paolini 與他之前的博士后導(dǎo)師、希伯來大學(xué)教授 Saharon Shelah 在網(wǎng)上發(fā)表的一篇論文（如下）終于解決了 TFAB 的相關(guān)問題。

論文地址：https://arxiv.org/pdf/2102.12371.pdf

1

計(jì)算無窮大

TFAB 問題涉及到一類無窮可數(shù)結(jié)構(gòu)，可以幫我們理解數(shù)學(xué)家如何處理這些看似笨拙的數(shù)量。

首先，一組結(jié)構(gòu)“可數(shù)”意味著什么？自然數(shù) (0, 1, 2, 3 ...) 是無窮的，但也被視為“可數(shù)”，所以自然數(shù)有時(shí)候也會(huì)被稱為“可數(shù)數(shù)”（counting number）。如果你按順序數(shù)這些自然數(shù)，它們可以完整地排列，（雖然你要花無窮的時(shí)間）。自然數(shù)集合中的元素，或者它的“基數(shù)”，被標(biāo)記為“aleph-zero”。數(shù)學(xué)家把任何與自然數(shù)無窮集大小相同的集合都稱為“可數(shù)”集合。

相反，實(shí)數(shù)（包括自然數(shù)、有理數(shù)和無理數(shù)）雖然也是無窮的，但它們卻被歸類為“不可數(shù)”。主要原因是實(shí)數(shù)太多：我們從19世紀(jì)80年代后期就知道，0 和 1 之間的實(shí)數(shù)比所有自然數(shù)加起來還要多。

所以有這么一種說法：無窮并非生而平等；有些無窮要比其他無窮大得多。實(shí)數(shù)集的“基數(shù)”也比自然數(shù)更大，因?yàn)閷?shí)數(shù)更多。任何可數(shù)的集合要么是有窮的，要么如果是無窮的，且基數(shù)為 aleph-zero。

那么，數(shù)學(xué)家可以圍繞這些概念來做怎樣的研究？Friedman與Stanley 的論文，以及 Paolini 和 Shelah 的新工作都重點(diǎn)關(guān)注結(jié)構(gòu)之間的同構(gòu)（isomorphism）。雖然一些數(shù)學(xué)結(jié)構(gòu)在本質(zhì)上都是無窮，但仍有可能研究它們，并將它們與其他對(duì)象進(jìn)行比較，以確定它們是否同構(gòu)或大致相等。

例如，我們先看看兩個(gè)無窮但可數(shù)的數(shù)字組：

第一組由所有整數(shù)組成，第二組則僅由偶數(shù)組成。這兩個(gè)群彼此同構(gòu)，因?yàn)樗鼈兙哂邢嗤瑪?shù)量的元素，也就是說，它們的無窮是相同的。而且，在這兩組里，每一組中的元素都能對(duì)應(yīng)另一組中的一個(gè)元素。此外，用于從一組映射到另一組的函數(shù)還必須保留組的運(yùn)算和屬性（如加法組合律）。

這類同構(gòu)群并不完全相同，因?yàn)樗鼈儧]有相同的元素，但它們確實(shí)有平行結(jié)構(gòu)：一組中的每個(gè)元素都與另一組中的單個(gè)元素直接相關(guān)。通過一個(gè)函數(shù)就可以將第一個(gè)結(jié)構(gòu)轉(zhuǎn)換為第二個(gè)結(jié)構(gòu)，如上例所示，只需將第一個(gè)結(jié)構(gòu)中的每個(gè)元素乘以 2，就能得到第二個(gè)結(jié)構(gòu)。如 Paolini 所介紹，即便沒有完全相同的內(nèi)容，同構(gòu)結(jié)構(gòu)也有“相同形狀”。

同構(gòu)概念正是 TFAB 問題的核心。

2

多復(fù)雜才算得上是復(fù)雜？

在 1989 年的論文中，F(xiàn)riedman 與 Stanley 主要想解決一個(gè)問題：給定一個(gè)可數(shù)結(jié)構(gòu)族，既可以是無限組數(shù)字，也可以是圖，那么，確定該族的對(duì)象是否彼此同構(gòu)有多難？

Friedman 與 Stanley舉了一個(gè)例子：有一組圖，每個(gè)圖都有可數(shù)但無窮個(gè)頂點(diǎn)。在兩個(gè)標(biāo)記為“同構(gòu)”的可數(shù)圖上，一個(gè)圖中的頂點(diǎn)與另一個(gè)圖中的頂點(diǎn)之間必須存在一對(duì)一的對(duì)應(yīng)關(guān)系。如果一個(gè)圖中的兩個(gè)頂點(diǎn)由一條邊連接，那么另一個(gè)圖中相應(yīng)的頂點(diǎn)也必須由一條邊連接。大約如下：

Friedman 與 Stanley 提出，要確定兩個(gè)可數(shù)圖是否同構(gòu)是極其復(fù)雜的。這使得所有可數(shù)圖家族都變成“波萊爾完備”（Borel complete）——這個(gè)表達(dá)由他們?cè)?989年的論文中首創(chuàng)，因?yàn)樗麄兘柚朔▏?guó)數(shù)學(xué)家 émile Borel 所設(shè)計(jì)的波萊爾函數(shù)（Borel function）。

Friedman  與 Stanley 很好奇：“還有哪些可數(shù)對(duì)象是波萊爾完備的？”這個(gè)問題，也是描述集合論的核心主題之一。

從之后的幾年里，F(xiàn)riedman、Stanley和其他學(xué)者已經(jīng)確定了幾類滿足波萊爾完備性標(biāo)準(zhǔn)的數(shù)學(xué)對(duì)象，包括樹（一種簡(jiǎn)化的圖）、線性階數(shù)和數(shù)字集（自然或?qū)崝?shù)），字面上是順序排列，就像數(shù)軸上的數(shù)字一樣。

但在 1989 年論文所考慮的許多情況中，只有 TFAB 拒絕通過同構(gòu)進(jìn)行分類。首先，TFAB群在本質(zhì)上是一組數(shù)字。每個(gè) TFAB 由遵循特定群規(guī)則的實(shí)數(shù)的可數(shù)子集組成，例如在加減規(guī)則下封閉（因此對(duì)于該群中的任何數(shù)字 p 和 q，p + q 和 p - q 也包含在群中）。它還遵守交換律（即 p + q = q + p），這也是阿貝爾群的標(biāo)志。最后，“無撓”（torsion-free）的意思是，如果 g 是群中的非零元素，那么 g + g 永遠(yuǎn)不可能等于零，g + g + g 也不能，g + g + g +g 也不能……依此類推。

30多年來，數(shù)學(xué)家們一直想知道：“如果我們有兩個(gè)（可數(shù)）無撓阿貝爾群，那么，當(dāng)我們?cè)谠儐査鼈兪欠裢瑯?gòu)時(shí)，這個(gè)問題的難度是簡(jiǎn)單、中等還是最難？”在1989年論文所提出的問題中，這個(gè)問題所用的解決時(shí)間最長(zhǎng)。

終于，在今年，Shelah 和 Paolini 找到了突破的方法。

3

跨結(jié)構(gòu)轉(zhuǎn)換

他們解決這個(gè)問題的方法，是借鑒了經(jīng)典數(shù)學(xué)家思維：將一個(gè)難題簡(jiǎn)化為一個(gè)容易的問題。如果他們能夠證明 TFAB 與另一個(gè)已知的波萊爾完備結(jié)構(gòu)族（例如可數(shù)圖族）一樣復(fù)雜，那么也就可以證明 TFAB 也是波萊爾完備的。

這就好比，如果你想知道一個(gè)人是否是世界上最高的人，那么與其將Ta和地球上的每個(gè)人都比對(duì)，還不如去找被公認(rèn)為最高的人比，看看誰(shuí)更高。

Shelah 解釋，在決定使用可數(shù)圖作為衡量標(biāo)準(zhǔn)后，他們面臨關(guān)鍵的下一步：創(chuàng)建一個(gè)函數(shù)（特別是波萊爾類的函數(shù)），可以“將一個(gè)圖轉(zhuǎn)換成一個(gè)無撓阿貝爾群”。他們的函數(shù)需要接收一個(gè)圖作為輸入，并產(chǎn)生一個(gè) TFAB 作為輸出，在這個(gè)過程中將信息從圖傳遞到 TFAB 群。也就是說，函數(shù) f 必須滿足以下關(guān)系：當(dāng)且僅當(dāng) f(G) 和 f(H) 是可數(shù)且彼此同構(gòu)的 TFAB 時(shí)，兩個(gè)可數(shù)圖 G 和 H 才彼此同構(gòu)。

這項(xiàng)任務(wù)并不容易，因?yàn)闆]有“技術(shù)”來連接如此不同的數(shù)學(xué)對(duì)象。所以，他們不得不為這個(gè)問題發(fā)明一項(xiàng)“技術(shù)”。

用 Laskowski 的說法，問題的關(guān)鍵是找出這項(xiàng)技術(shù)。就像蘋果與橙子，圖和群沒有相同的詞匯。在這種情況下，我們要做的就是建立對(duì)應(yīng)關(guān)系。

然后，他們真的是在比較無窮組的蘋果和無窮組的橙子。幸運(yùn)的是，他們找到了一種將問題簡(jiǎn)化的方法：你只要處理一個(gè)通用的圖，而無需處理所有圖。這個(gè)通用圖非常龐大，以至于它的子圖已經(jīng)包含了所有可能的可數(shù)圖。

通過這種方式，Paolini 和 Shelah 可以構(gòu)建必要的函數(shù)，從而證明圖和 TFAB 處于一種平等的地位。他們找到了一種將無撓阿貝爾群與圖相關(guān)聯(lián)的方法，以便保留同構(gòu)。

而且，由于數(shù)學(xué)家已經(jīng)知道可數(shù)圖族是波萊爾完備的，也就是在同構(gòu)方面是最復(fù)雜的，那么，也就是說，可數(shù) TFAB 族也必須是波萊爾完備的。

4

研究前景

那么，他們的研究成果有可能取得更通用的結(jié)論嗎？Kechris 的說法是：有待觀察，但很有可能。

在解決了可數(shù) TFAB 的問題后，Paolini 和 Shelah 已經(jīng)在進(jìn)行進(jìn)一步的探索，將研究目標(biāo)對(duì)準(zhǔn)不可數(shù) TFAB，并稱“可能會(huì)有不一樣的結(jié)果”。

事實(shí)上，Shelah 有一個(gè)理論，就是當(dāng)你將問題推到更高的基數(shù)時(shí)，問題可能會(huì)變得更簡(jiǎn)單，因?yàn)楫?dāng)數(shù)字變得非常大時(shí)，重要數(shù)字之間的距離也會(huì)增加，比如質(zhì)數(shù)和整數(shù)的平方。

同時(shí)，他們這篇關(guān)于可數(shù) TFAB 的論文已經(jīng)有一些直接的實(shí)際意義。例如，這個(gè)族沒有能夠告訴你兩個(gè) TFAB 是否同構(gòu)的鮮明屬性（即“不變量”），但可數(shù) TFAB 的波萊爾完備性可以直接告訴你這個(gè)答案。

在未來，數(shù)學(xué)家們可能會(huì)發(fā)現(xiàn)其他類別的無窮可數(shù)結(jié)構(gòu)，例如圖與 TFAB，它們?cè)诖_定同構(gòu)時(shí)最為復(fù)雜。不過，僅僅知道 TFAB 的可能復(fù)雜程度，就可以將問題進(jìn)行簡(jiǎn)化，都有利于幫助分類學(xué)家與描述集合理論家的進(jìn)一步工作。

原文鏈接：https://www.quantamagazine.org/mathematicians-solve-decades-old-classification-problem-20210805/

贈(zèng)書福利 

AI科技評(píng)論本次聯(lián)合【圖靈教育】為大家?guī)?strong>10本《算法（第四版）》正版新書。

AI科技評(píng)論將一共選出 10名讀者，每人送出《算法（第四版）》一本。

在2021年8月8日二條文章（不是本文，僅限AI科技評(píng)論微信公眾號(hào)端）留言區(qū)留言，歡迎大家暢所欲言，談一談你對(duì)本書的看法和期待。在綜合留言質(zhì)量（留言是敷衍還是走心）和留言點(diǎn)贊最高（注：點(diǎn)贊最高的前10不意味著一定會(huì)中獎(jiǎng)）的讀者中選出10位讀者獲得贈(zèng)書。獲得贈(zèng)書的讀者請(qǐng)聯(lián)系 AI 科技評(píng)論客服（aitechreview）。

• 留言內(nèi)容會(huì)有篩選，例如“選我上去”、“這書寫的很棒（僅僅幾個(gè)字）”等內(nèi)容將不會(huì)被篩選，亦不會(huì)中獎(jiǎng)。

• 留言送書活動(dòng)時(shí)間為2021年8月8日 - 2021年8月12日（23:00），活動(dòng)推送時(shí)間內(nèi)僅允許贈(zèng)書福利中獎(jiǎng)一次。

  雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)

雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。