一个困扰数学家30多年的分类问题，终于被解决了！

作者 | Steve Nadis

编译 | 陈彩娴

编辑 | 青暮

一般情况下，当你要对某个特定地区的植物进行调查时，你可能会按植物的种类来划分。

就这种方法来看，如果是沿着托斯卡纳海岸的某些地带做这类调查并不会很困难，因为你大概率只会发现一种植物，就是海松（pinus pinaster）。但是，如果你要在亚马逊热带雨林中做植物统计，那你要找出雨林里所有植物的名字与数量就会非常困难，甚至可以说是“毫无可能”。

在探索广阔数学图景的征程上，数学家们也可能会遇到类似的挑战，尤其是对研究描述集合论的数学家而言，因为他们要尝试对分类问题的难度进行评级。有时候他们会认为某个分类任务很容易，有时候又会觉得某个分类任务太难，比如上述的亚马逊雨林植物分类问题。

描述集合论（descriptive set theory）只是集合论的一个分支，主要研究物体的集合，可以是数字、图形、空间中的点、向量，等等。实数、有理数、虚数本身就是一个集合。可以说，数学家的研究范围涵盖了方方面面。

几十年来，研究人员一直被一个分类问题所困扰。这个分类问题就是“无挠阿贝尔群”（torsion-free abelian groups，简称“TFAB”）。

TFAB 问题最早由数学家 Harvey Friedman 和 Lee Stanley 在1989年所发表的一篇论文（“A Borel Reducibility Theory For Classes of Countable Structures”）中提出。在这篇论文中，Harvey Friedman 与 Lee Stanley 介绍了一种比较可数结构分类问题难度的新方法，表明有些分类问题会非常复杂。

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

这个问题困扰了数学家们30多年。今年，都灵大学的数学家 Gianluca Paolini 与他之前的博士后导师、希伯来大学教授 Saharon Shelah 在网上发表的一篇论文（如下）终于解决了 TFAB 的相关问题。

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

1

计算无穷大

TFAB 问题涉及到一类无穷可数结构，可以帮我们理解数学家如何处理这些看似笨拙的数量。

首先，一组结构“可数”意味着什么？自然数 (0, 1, 2, 3 …) 是无穷的，但也被视为“可数”，所以自然数有时候也会被称为“可数数”（counting number）。如果你按顺序数这些自然数，它们可以完整地排列，（虽然你要花无穷的时间）。自然数集合中的元素，或者它的“基数”，被标记为“aleph-zero”。数学家把任何与自然数无穷集大小相同的集合都称为“可数”集合。

相反，实数（包括自然数、有理数和无理数）虽然也是无穷的，但它们却被归类为“不可数”。主要原因是实数太多：我们从19世纪80年代后期就知道，0 和 1 之间的实数比所有自然数加起来还要多。

所以有这么一种说法：无穷并非生而平等；有些无穷要比其他无穷大得多。实数集的“基数”也比自然数更大，因为实数更多。任何可数的集合要么是有穷的，要么如果是无穷的，且基数为 aleph-zero。

那么，数学家可以围绕这些概念来做怎样的研究？Friedman与Stanley 的论文，以及 Paolini 和 Shelah 的新工作都重点关注结构之间的同构（isomorphism）。虽然一些数学结构在本质上都是无穷，但仍有可能研究它们，并将它们与其他对象进行比较，以确定它们是否同构或大致相等。

例如，我们先看看两个无穷但可数的数字组：

第一组由所有整数组成，第二组则仅由偶数组成。这两个群彼此同构，因为它们具有相同数量的元素，也就是说，它们的无穷是相同的。而且，在这两组里，每一组中的元素都能对应另一组中的一个元素。此外，用于从一组映射到另一组的函数还必须保留组的运算和属性（如加法组合律）。

这类同构群并不完全相同，因为它们没有相同的元素，但它们确实有平行结构：一组中的每个元素都与另一组中的单个元素直接相关。通过一个函数就可以将第一个结构转换为第二个结构，如上例所示，只需将第一个结构中的每个元素乘以 2，就能得到第二个结构。如 Paolini 所介绍，即便没有完全相同的内容，同构结构也有“相同形状”。

同构概念正是 TFAB 问题的核心。

2

多复杂才算得上是复杂？

在 1989 年的论文中，Friedman 与 Stanley 主要想解决一个问题：给定一个可数结构族，既可以是无限组数字，也可以是图，那么，确定该族的对象是否彼此同构有多难？

Friedman 与 Stanley举了一个例子：有一组图，每个图都有可数但无穷个顶点。在两个标记为“同构”的可数图上，一个图中的顶点与另一个图中的顶点之间必须存在一对一的对应关系。如果一个图中的两个顶点由一条边连接，那么另一个图中相应的顶点也必须由一条边连接。大约如下：

Friedman 与 Stanley 提出，要确定两个可数图是否同构是极其复杂的。这使得所有可数图家族都变成“波莱尔完备”（Borel complete）——这个表达由他们在1989年的论文中首创，因为他们借助了法国数学家 Émile Borel 所设计的波莱尔函数（Borel function）。

Friedman  与 Stanley 很好奇：“还有哪些可数对象是波莱尔完备的？”这个问题，也是描述集合论的核心主题之一。

从之后的几年里，Friedman、Stanley和其他学者已经确定了几类满足波莱尔完备性标准的数学对象，包括树（一种简化的图）、线性阶数和数字集（自然或实数），字面上是顺序排列，就像数轴上的数字一样。

但在 1989 年论文所考虑的许多情况中，只有 TFAB 拒绝通过同构进行分类。首先，TFAB群在本质上是一组数字。每个 TFAB 由遵循特定群规则的实数的可数子集组成，例如在加减规则下封闭（因此对于该群中的任何数字 p 和 q，p + q 和 p – q 也包含在群中）。它还遵守交换律（即 p + q = q + p），这也是阿贝尔群的标志。最后，“无挠”（torsion-free）的意思是，如果 g 是群中的非零元素，那么 g + g 永远不可能等于零，g + g + g 也不能，g + g + g +g 也不能……依此类推。

30多年来，数学家们一直想知道：“如果我们有两个（可数）无挠阿贝尔群，那么，当我们在询问它们是否同构时，这个问题的难度是简单、中等还是最难？”在1989年论文所提出的问题中，这个问题所用的解决时间最长。

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

3

跨结构转换

他们解决这个问题的方法，是借鉴了经典数学家思维：将一个难题简化为一个容易的问题。如果他们能够证明 TFAB 与另一个已知的波莱尔完备结构族（例如可数图族）一样复杂，那么也就可以证明 TFAB 也是波莱尔完备的。

这就好比，如果你想知道一个人是否是世界上最高的人，那么与其将Ta和地球上的每个人都比对，还不如去找被公认为最高的人比，看看谁更高。

Shelah 解释，在决定使用可数图作为衡量标准后，他们面临关键的下一步：创建一个函数（特别是波莱尔类的函数），可以“将一个图转换成一个无挠阿贝尔群”。他们的函数需要接收一个图作为输入，并产生一个 TFAB 作为输出，在这个过程中将信息从图传递到 TFAB 群。也就是说，函数 f 必须满足以下关系：当且仅当 f(G) 和 f(H) 是可数且彼此同构的 TFAB 时，两个可数图 G 和 H 才彼此同构。

这项任务并不容易，因为没有“技术”来连接如此不同的数学对象。所以，他们不得不为这个问题发明一项“技术”。

用 Laskowski 的说法，问题的关键是找出这项技术。就像苹果与橙子，图和群没有相同的词汇。在这种情况下，我们要做的就是建立对应关系。

然后，他们真的是在比较无穷组的苹果和无穷组的橙子。幸运的是，他们找到了一种将问题简化的方法：你只要处理一个通用的图，而无需处理所有图。这个通用图非常庞大，以至于它的子图已经包含了所有可能的可数图。

通过这种方式，Paolini 和 Shelah 可以构建必要的函数，从而证明图和 TFAB 处于一种平等的地位。他们找到了一种将无挠阿贝尔群与图相关联的方法，以便保留同构。

而且，由于数学家已经知道可数图族是波莱尔完备的，也就是在同构方面是最复杂的，那么，也就是说，可数 TFAB 族也必须是波莱尔完备的。

4

研究前景

那么，他们的研究成果有可能取得更通用的结论吗？Kechris 的说法是：有待观察，但很有可能。

在解决了可数 TFAB 的问题后，Paolini 和 Shelah 已经在进行进一步的探索，将研究目标对准不可数 TFAB，并称“可能会有不一样的结果”。

事实上，Shelah 有一个理论，就是当你将问题推到更高的基数时，问题可能会变得更简单，因为当数字变得非常大时，重要数字之间的距离也会增加，比如质数和整数的平方。

同时，他们这篇关于可数 TFAB 的论文已经有一些直接的实际意义。例如，这个族没有能够告诉你两个 TFAB 是否同构的鲜明属性（即“不变量”），但可数 TFAB 的波莱尔完备性可以直接告诉你这个答案。

在未来，数学家们可能会发现其他类别的无穷可数结构，例如图与 TFAB，它们在确定同构时最为复杂。不过，仅仅知道 TFAB 的可能复杂程度，就可以将问题进行简化，都有利于帮助分类学家与描述集合理论家的进一步工作。

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

赠书福利 

AI科技评论本次联合【图灵教育】为大家带来10本《算法（第四版）》正版新书。

AI科技评论将一共选出 10名读者，每人送出《算法（第四版）》一本。

在2021年8月8日二条文章（不是本文，仅限AI科技评论微信公众号端）留言区留言，欢迎大家畅所欲言，谈一谈你对本书的看法和期待。在综合留言质量（留言是敷衍还是走心）和留言点赞最高（注：点赞最高的前10不意味着一定会中奖）的读者中选出10位读者获得赠书。获得赠书的读者请联系 AI 科技评论客服（aitechreview）。

• 留言内容会有筛选，例如“选我上去”、“这书写的很棒（仅仅几个字）”等内容将不会被筛选，亦不会中奖。

• 留言送书活动时间为2021年8月8日 – 2021年8月12日（23:00），活动推送时间内仅允许赠书福利中奖一次。

  雷锋网雷锋网(公众号：雷锋网)雷锋网

雷锋网特约稿件，未经授权禁止转载。详情见。