ZS Chen，语言学+中东语言本科, 在哲学系PhD学数学 阅读原文 讲到精彩巧妙的证明，那就不得不提及 Bill Wadge，加拿大维多利亚大学计算机科学系与数学系教授，在博一时把讨论班期末项目直接写成了博士毕业论文的故事。 在去 UC 伯克利读博之前，Bill Wadge 从来没有上过数理逻辑课，但是他博一参加的第一节数理逻辑讨论班的期末项目，就让他发现了如今数理逻辑和理论计算机科学中有名的 Wadge degrees、Wadge games 等概念，直接一举填满了他的博士毕业论文，也为他毕业后去做数学系 - 计算机系教授的职业生涯打开了一个漂亮的开局。(值得一提的是，Wadge 在博士毕业后，工作重心从数理逻辑转移到了 programming language) 对于这个令人羡慕的博士生涯，Wadge 本人则非常谦虚。在回忆起这一系列事情的时候，他说[1]： 我这份工作有很大程度的幸运成分：当时所有的工具都已经成型了，只是还没有人发现它们之间的联系而已。其中很多工具都有些年份，唯一比较新的工具就是对于无穷博弈的研究。要是没有无穷博弈，我还真做不出来这些问题 ... 现在回头看看，我唯一需要担心的事情就是错过 deadline。 所以 Bill Wadge 到底解决了什么问题？为什么会跟无穷博弈扯上关系？什么是无穷博弈？要了解这些问题，我们要从苏联数学家 Lyudmila Keldysh 的一份工作开始说起。 1. 问题背景 我们知道，以Luzin 筛或者连分数的方式，我们可以给实数集赋予一种数字化的视角，将实数集视为自然数数列的集合。 简单来说，我们给自然数序列的集合 赋予一个“光锥式”的拓扑基：对于一个有限长度的自然数序列 ，将型为 的“光锥”定为开集。可以证明，这样一个拓扑让这个空间同胚于无理数集。 The Baire space (Logician's reals)上的拓扑 “光锥”拓扑基的一个开集 这样的空间我们称为 Baire 空间，符号记作 。对于 Baire 空间中的开集，我们可以有一个很直观理解：一个集合 是开集，当且仅当" "这个问题可以被有限的信息肯定。什么意思呢？因为所有开集都是延长了某些有限序列的数列，所以只要我们知道开集 里面的数列都是对哪些字符串的延长，那么我们就可以对给定的数列 进行暴力搜索，看它是不是延长了我们想要的字符串。这里的重点在于：如果 ，那么这个事实就能在有限的时间内被我们肯定。 如何理解拓扑的定义？ 有了这种数字化的解读，一个随之而来的问题就是，这些数列跟它们相对应的拓扑性质会不会有联系？ 从这个角度出发，苏联数学家 Lyudmila Keldysh 考虑了如下几个通过描述数列来得到的 4 个集合，尝试探究数列的描述方式和它们的Borel 复杂度（开集、闭集、 、 ，...）之间的关系 ： 数字 0 在数列中出现至少一次 ： 数字 0 在数序列中出现无限次 ： 数列中有某个自然数出现无限次 ： 数列中有无限个自然数出现无限次 直觉上，这几个集合的复杂度应该是依次递增的，这点我们从它们的定义中用到的量词交替次数也能略微有所感觉。但是它们的复杂度是严格递增的吗？我们该如何证明？ 2. Keldysh 集合的 Borel 复杂度 通过上文中对开集的理解，我们不难看出，Keldysh 的集合 是开集：一旦一个数列中出现了 ，这个就成了既定事实，无法再被改变。所以“一个数列在 中吗？”这个问题，可以通过暴力搜索，只需用有限的信息就可以得到肯定的回答。 而由于 和 逻辑上分别对应着 和 ， 则不难被看成是 集，即可数个开集的交集： 类似地，我们也可以看出 是 ： 是 ： 这样看来，Keldysh 的问题相当于在问， 是否可能也是闭集？ 是否也可能是 的，又或者是开集或闭集？ 是否有可能是 或更低复杂度？ 是否有可能有更低的复杂度？ 3. 古典拓扑方法 想要解决一个数学问题，通常的反应就是先思考这是什么样的问题，可能需要用到什么领域的工具。Keldysh 将上文的问题看作一个纯拓扑项目，通过苏联式暴力手法（类似打了鸡血的"有理数集是 但不是 "的证明），直接解决了这个问题： 定理 (Keldysh, Luzin). 对于上述四个集合，，它们的复杂度是严格递增的。同时，它们的复杂度也都是非自对偶的（意思是说，不会是闭集，不会是，如此类推） 对于 这个简单情形，古典工具仍然尚可处理。 不可能是闭集，因为不难观察到 是稠密集合：每个有限字符串都可以被延伸进 中（我们只需往最后加一个 即可），所以可以得知每个数列都是 中的极限点（例如考虑将数列 保留越来越长的有限前段，后面全部改成 0）。而稠密闭集只能是整个空间，所以 是开集但不会是闭集。 接下来，对于 ，Keldysh 考虑了 Haudorff 的取 residue/adjoin 操作。Hausdorff 证明过，如果一个集合既是 又是 的，那么对它交替取 residue 和 adjoin 的操作一定能在可数步内将其穷尽。而 Keldysh 证明了 是稠密的，以及 的补集也是稠密的，由此她推论出，交替取 residue 和 adjoin 的操作无法在可数步内将 穷尽，所以 不能是 的，那么显然它而不能是更低复杂度的集合，例如开集或闭集。 从上面两个例子不难看出，从 到 ，证明难度和所用到的工具复杂程度都大大地增加了。Keldysh 对 和 的情况的证明更是惨绝人寰，既很难提炼出其中的思想，又很难直接推广到更复杂的集合上去。 这就是 Wadge 在 1966 年刚到 UC 伯克利读博一时，Addison 在数理逻辑讨论班上给他布置的期末项目：尝试找到更简单的、可推广的，对 Keldysh-Luzin 定理的证明。Wadge 自己回忆当时的反应是：“什么鬼，他是想让我做出比描述集合论创始人 Luzin 还强的工作吗？”[2] 然而 Wadge 还真找到了更好的证明，甚至从中提炼的 Wadge degree 和 Wadge hierarchy 这两个概念，在大大提升我们对 Borel 集结构的理解的同时，间接塑造了集合论中内模型论接下来半个世纪的走向。 而之所以 Wadge 能成功地解决这个问题，恰好就是因为他抛弃了拓扑学的视角，转而把这个问题看作一个可计算性理论和组合博弈论的问题。 4. 程序就是自然数上的连续映射，连续映射就是实数上的程序 对于 Baire 空间中的开集，我们前面提到过，它的元素是可以在有限时间内被判定的。1930 年，Keldysh 和 Luzin 做出他们的工作时，“有限时间”、“判定”、“暴力搜索”等概念对他们来说是陌生的。这些概念所对应的数学直觉 / 数学定义至少要等到 1936 年，丘奇和图灵开创了理论计算机这个学科之后。而 Wadge 在 1966 年时，显然就有了这个年代上优势。 如今熟悉理论计算机的读者可以看出，“能在有限时间内被暴力搜索肯定”的问题，对应的就是递归可枚举集(recursively enumerable set, r.e. set)。而在这个视角下，Baire 空间中的开集在直觉上就很显著地对应着那些递归可枚举集。而 clopen sets 则对应着可判定集， 对应着能解决停机问题（将停机问题作为 oracle）的那些图灵机可以计算的集合，如此类推。 但仅仅有这些对应还不够。真正让 Wadge 取得突破性进展的，还是 Addison 在讨论班上考虑的一个醍醐灌顶的问题：Baire 空间上的连续映射是什么样的？ 我们回顾连续映射的最一般定义： 是连续的，当且仅当任意开集在下的原像是开集。 相信许多人第一次接触到这个定义都有点摸不着头脑：为什么要这么定义？我们将看见，这个定义在我们目前的语境下会变得极其自然。 我们考虑一个输入和输出均为自然数的程序 ，将它看作一个函数 。最粗略地看，它的运作就是： Input: n 一些机械化的操作 Output: F(n) 直观上来说，这是一个有限的操作，它不需要跑遍所有的自然数（存在一个自然数 ，使得这段运行里面涉及到的最大的数字小于 ）。关键在于，对于这个程序所解决的问题，我们不需要知道这个问题的全貌。程序让我们可以在有限的时间内解决给定的这个问题的有限个个例。换句话说，给程序输入有限的信息，程序就能在有限的时间内输出有限的有效信息。 Input: {0, 1, 2, 3,...,n} 一些机械化的操作 * n+1 次 Output: {F(0), F(1), F(2), F(3),...,F(n)} 那么考虑 Baire 空间中的一个开集 ，它由一系列有限字符串 所确定，一个数列 当且仅当 延长了这其中某一个 。如果 是连续的，那么根据连续函数的定义， 也是一个开集 ，它也同样由一系列有限字符串 所确定。 假设 ，那么对于任意的自然数 ， ( 长度为 的前段) 确定了一个开集 。而由于连续性的定义， 也是一个开集，而且我们知道 。这就说明了 这样一个“光锥”，一定是被形如 的某个有限字符串所确定的。 换句话说，如果 是连续的，那么关于 的有限信息的问题(比如说 的第 6 位是什么数字)，我们都可以通过输入关于 的有限的信息，让 运行之后获取这个问题的答案。 特别地，我们可以抽象地把 看作一个“程序”： Input: g:N->N, n∈N 一些机械化的操作(有限时间会停机) Output: F(g)(n) 综上所述，我们得到了一个很惊人却又很优美的结果：实数上的连续函数，就是自然数上的可计算函数的“高阶”版本！实际上，上面的讨论就是对如下事实的非形式证明： 来自 David Marker 描述集合论讲义 5. 可计算归约 vs 连续归约 有了这样一个对连续函数的理解，我们的视野和可用的工具一下子就开阔了起来。 一个问题 能被可计算归约(many-one reducible)为另一个问题 （写作 ），当且仅当存在一个程序 ，使得对于任意自然数 ， 的真假等价于 。换句话说，如果我们想知道 知否为真，我们可以把 输入程序，得到输出 ，通过 的回答来得知 的真假。 不难发现，如果我们给程序的运行时间或者内存空间加以限制，我们就能得到计算复杂度常见的归约概念（例如多项式时间归约）。 事实. 如果一个问题可以被可计算归约 / 多项式时间归约为问题，那么就会继承的可计算复杂度 / 计算性复杂度。 比如说，如果 ，然后 是递归可枚举，那么 也是递归可枚举的。类似地，如果 多项式时间归约为 ，并且 是 NP 问题，那么 也是 NP 问题。 稍微换一个写法，如果可计算函数 将 归约为 ，那么实际上我们就有 。这个写法是不是有点熟悉？没错，这跟连续函数几乎如出一辙！这么看来，连续函数不仅仅是高阶的递归函数，它还是一个归约概念。 https://www.zhihu.com/question/27039635/answer/2529851194 在可计算性理论中，如果我们想证明一个集合 不是递归可枚举的，那么其中一个办法就是将一个非递归可枚举的集合，比如说停机问题的补集， ，归约为 。这样子的话，如果 可枚举，那么我们就可以通过枚举 来枚举不停机的图灵机，这样子就可以解决停机问题，矛盾。 Many-one reduction 这个归约概念，在 1959 年时由 Hartley Rogers 在Computing degrees of unsolvability一文中提出。在 Wadge 对期末项目一筹莫展时，导师 Addison 正是布置给他读这篇论文，希望能让他有所启发。 仿佛如奇迹般地巧合一样，Rogers 的论文考虑了如下四个集合： ：非空的 r.e.集的下标 ：无穷的 r.e.集的下标 ：包含了无穷 r.e.集下标的 r.e.集 ：包含了无穷多个无穷 r.e.集下标的 r.e.集的下标 并且证明了： 定理. 对于上述四个集合，，它们的复杂度是严格递增的。同时，低于或与相同复杂度的任意集合都能被可计算归约为。 是不是 Wadge 被布置的期末项目很像？值得注意的是，Rogers 在证明这个定理时完全没有用到任何的拓扑工具！ 有了这个先例，Wadge 考虑通过连续归约的方式来重新证明 Keldysh-Luzin 定理。如果连续函数就是递归函数，那么可计算归约对应着的就是连续归约： 定义. 令为连续函数，对于任意集合，如果 （或者等价地，当且仅当），那么我们称可以被连续归约，或 Wadge 归约，为 ，记作 事实. 如果 Borel 集 可以被连续归约(又称 Wadge 归约)为 Borel 集 （），那么就会继承的 Borel 复杂度。 那么根据类比，我们就有了这样一个策略：如果我们想证明一个集合 不是 的，那么我们尝试将所有 集都归约为 。如果对于任意 集合 ，我们都有 ，那么 就不可能是 的。这是因为，根据 Lebesgue 的工作，我们知道存在 但非 的集合，所以如果 是 的，那么所有 集都会同时是 的，与 Lebesgue 的结果矛盾。 存在非 Borel 的解析集: Suslin 是如何给 Lebesgue 纠错的 这个类比如此地合拍，就仿佛在向我们暗示，Keldysh-Luzin 定理实际上不是一个拓扑问题，而是一个高阶理论计算机问题。 6. Wadge games，必胜策略与连续归约 有了这样的证明策略，Wadge 接下来要做的事情就很实际了。首先，模仿理论计算机科学中“完备”(complete)的概念，我们尝试给出“最复杂的开集 / 闭集 / / ...”的定义： 定义. 令为 Borel 层级中的一层。称集合为- 完备的，当且仅当所有集都能被连续归约为。 如果我们把相应的集合 / 复杂度 / 归约概念稍微改一改，那么不难看出计算复杂度中的“ - 完备”概念，就是这一类概念的一个特例。 所以 Wadge 目前能做的一件事情就是，证明 Keldysh 的 对各自的复杂度是完备的。这一步就需要涉及到构造性的工作：比如说，随便给定一个开集 ，我们该如何构造一个连续函数 ，使得 当且仅当 ？这一步就是无穷博弈出现的地方。 我们抛弃掉古典的拓扑概念，转而继续跟着【连续 - 程序】二元性的视角。给定一个开集 和 ，如果我想说服你 能被规约为 ，那么我需要做的就是“编写”一个“程序” ，使得 中元素的有限信息，都能在有限时间内，通过将 的元素的有限信息输入 的方式所获得。 而你要做的就是想办法让我的程序出错：你想制造一个数列 ，使得 但 ，或者 但 。 所以我写的程序和你就进入了一段博弈，Wadge game of and ，记作 ： 第一回合，你给出一个自然数，我打开我的程序，输入，让它跑一会。 如果它输出了结果，那么我就给出；如果它需要更多信息，那么我就选择跳过这一回合，让你进入下一回合。 下一回合，你再给出一个自然数，我给我的程序输入，如此类推。 也就是说，我作为玩家 II，你作为玩家 I，我们进行可数无限回合的上述博弈。规定： 玩家 II 不能永远地 pass 玩家 II 获胜，当且仅当在玩家 I 极限处得到的数列属于，当且仅当玩家 II 的数列 (注意此处删掉了所有的 pass) 属于。 这个游戏中玩家的策略，就是一个【从目前已经给出了的有限自然数序列到自然数】的一个函数。根据我们到目前的讨论，不难证明，对于任意集合 ，如果玩家 II 在 中有必胜策略，那么 就可以被连续归约到 （考虑对任意 ，玩家 I 在第 n 回合出 的，玩家 II 用他的必胜策略来防守）。 反之，如果存在一个连续归约 ，那么玩家 II 就可以从这个连续函数 中读出他的必胜策略：玩家 II 一直选择跳过，让玩家 I 出 ，直到某一个 时，对某个自然数 ，我们有 ，那么此时玩家 II 就选择出 。（练习：为什么这样的自然数总会存在？） 然后玩家 II 继续一直跳过，直到玩家 I 出了某一个 ，使得对于某个 我们有 ，如此类推。 这里的直觉是，玩家 II 将连续函数 当作一个程序来用，输入目前玩家 I 已经出了的自然数序列，考虑它所确定的“光锥”，即考虑这场博弈所有可能的“未来”，算出最有可能帮助玩家 II 获胜的行动。同时，在程序有足够信息输出下一步行动之前，玩家 II 选择不行动。不难验证，由于该策略是由连续映射 给出，这个策略最后会保证玩家 II 满足胜利条件。 所以我们相当于考虑了如下事实： 定理 (Wadge). 在 Wadge game 中，玩家 II 有必胜策略当且仅当。 7. 定理证明 要证明 是完备开集，我们只需要证明对于任意开集 ，玩家 II 在 中有必胜策略。这个策略非常简单： 策略：令开集为一系列 basic open sets 的并集。玩家 II 默认每回合都出自然数 1，除非到某回合时他观察到玩家 I 到目前为止出的序列延长了某个，如果这个情况发生了，那么玩家 II 就出一个 0，接下来每个回合随便出一个数字即可。 这里利用的仍然是开集的半可判定性质：如果一个数列进入了开集中，那么这个事实在这个数列的枚举中只需要有限步就可以确定了，而且一旦确定了这个事实也无法被更改。所以一旦玩家 I 的序列的有限前段告诉我们它的最终结果会进入开集，那么玩家 II 就可以放心地出一个 0 来赢得博弈。 所以我们有： 定理. 是完备开集；特别地，不可能是闭集。 对于 ，想要证明它是完备 集，我们的策略类似，因为 要求 0 在序列中出现无限次，所以玩家 II 可以以“停止出 0”作为要挟，让玩家 I 消除可能的反例： 策略：令为集，其中为开集，并且不失一般性地假设。 玩家 II 仍然默认只出 1，除非到某个回合，他观察到玩家 I 到目前为止出的序列进入了某个，。如果这个情况发生了，那么玩家 II 就出一个 0。 这样一个策略保证玩家 II 获胜，因为如果玩家 I 在极限处得到的序列 ，那么 就需要在被列举出来时进入过无穷多个 ，根据策略，玩家 II 此时就保证会出无穷多个 0，使得玩家 II 在极限处得到的序列属于 。反过来说，如果玩家 I 最后得到的序列不属于 ，那就说明它最多只属于某个 ，并且不属于 ，那么根据策略，玩家 II“停止出 0”的威胁就会在第 回合生效，之后再也不会出 0，所以得到的序列也不属于 。 定理. 是完备的集；特别地，它不可能是集，所以它的复杂度也严格高于。 要证明 是完备的 集，给定一个 集 ，我们给玩家 II 可数多张草稿纸，每回合玩家 I 出的数字都被玩家 II 抄在所有草稿纸上。 然后，在第 张草稿纸上，玩家 II 采用 的策略即可。在第 k 回合，我们看前 张草稿纸上， 的前 回合，如果玩家 II 在这其中某几个子博弈中有出过 0，那么玩家 II 在这里也出 0，不然的话，玩家 II 就出目前他出过的最大数字 +1 (这样确保了前面出现过的自然数不会再出现)。不难论证，这样的策略是玩家 II 的必胜策略。 也情况类似，借用之前几个博弈进行套娃式的策略即可，感兴趣的读者可以自行尝试。 与此同时，我们还可以通过给玩家 I 找到必胜策略来证明不可能存在归约： 定理. 不存在一个连续函数使得。 证明：我们只需给玩家 I 在 中找到必胜策略即可。这样一个策略可以被看作是保证让潜在的连续函数 跑出 bug 的一个方案。策略如下： 玩家 I 先出一个 0，等待玩家 II 出数字，如果玩家 II 选择跳过该回合或者出了一个非 0 的数字，那么玩家 I 就继续出 0。 如果玩家 II 在某一回合出了 0，那么玩家 I 就选择出上一回合的数字 +1，并且在等待玩家 II 出数字时一直出这个新数字，直到玩家 II 出下一个 0 为止。 这样一个策略是玩家 I 的必胜策略：如果玩家 II 出了无数个 0，那么玩家 I 出的数字就会不断地递增，每个数字也只可能出现有限次；如果玩家 II 出了有限个 0，那么在他最后一次出 0 之后，玩家 I 的行动就不会再改变，所以那个回合玩家 I 出的自然数就会出现无限次。证毕 注：不难看出，如果我们将规则改为不允许玩家 II 跳过目前回合，那么这个游戏必胜策略所对应的函数就是 Lipschitz 函数。 8. 总结 Wadge game 和 Wadge 归约这两个概念直接给类似 Keldysh-Luzin 定理的问题打开了全新的视角，融入了新发明的可计算理论和无穷博弈工具，直接将 Keldysh-Luzin 定理推广到了所有有穷的 Borel 层级上。除此之外，Wadge 归约这一概念本身也帮助我们明晰了 Borel 集的结构：1975 年，Donald Martin 在 Annals of Mathematics 里发表了如下定理 定理 (Martin, "Borel Determinacy"). 对于一类特定的双人无穷博弈，如果它的 payoff 集是 Borel 的，那么这个博弈必然存在玩家 I 或玩家 II 的必胜策略。 这个定理推广了无穷博弈的开创者 Gale-Stewart 更早期的定理： 定理 (Gale, Stewart). 对于一类特定的双人无穷博弈，如果它的 payoff 集开集或闭集，那么这个博弈必然存在玩家 I 或玩家 II 的必胜策略。 ZS Chen：Baire space 上闭集的树形式, 以及 Gale-Stewart 定理的证明 Wadge 证明了他的 Wadge games 可以被等价地转换为 Borel determinacy 中满足条件的那种博弈。那么这时我们就能得到一个推论，展现了 Borel 集优美的秩序： 推论. 对于 Baire 空间的任意 Borel 集，要么，要么 (注：为的补集)。 证明：考虑 。Borel determinacy 表明了这个博弈必然有某个玩家有必胜策略。如果玩家 II 有必胜策略，那么 。如果玩家 I 有必胜策略，注意到“ ”的否定等价于“ ”，那么这个必胜策略就会生成一个他作为玩家 II 参加 时的必胜策略。证毕。 这就说明了，Borel 集在 的排序下，几乎是一个线序。现代集合论的一个活跃研究方向，就是在什么情况下我们可以将这一秩序拓展至更多类型的集合上。 近年来内模型论文献中对 iteration strategy 的研究，也展示了 Wadge 归约的重要性。内模型论专家 Grigor Sargsyan 就曾经评价过，描述集合论和内模型论究其根本都是对 Wadge hierarchy 的研究，只是描述集合论用的是递归论框架，内模型论用的是 iteration strategy 框架。 Why does inner model theory need so much descriptive set theory (and vice versa)? 关于这段证明的历史和其中的数学，Bill Wadge 的个人网站上有着非常详细的描述，其中https://billwadge.com/2020/09/07/wadge-degrees-the-origin-story 一文中有着很有趣的个人体验描述，其中包含同班学神 Prikry 是如何碾压他的，他的研究如何被他舍友调的 Tequila sunrise 所拖延，和 60 年代 UC 伯克利的校园风气等，读起来很有趣。 阅读原文
