貌似无限的有限——良拟序(well quasi orders)关系

我很久前录制过一期音频节目：“画树画出一个大数——TREE(3)介绍”，那期节目是我一直以来很受欢迎的一期节目。那期节目之后，就不断有听众问：为什么TREE(3)是有限的？虽然我在节目里提到，这个有限性是“克鲁斯卡尔树定理”（Kruskal Tree Theorem）的一个推论，但那时候，我并不知道“克鲁斯卡尔树定理”的具体内容。前段时间，我终于去研究了一下这个定理，发现又是一次大开眼界、脑洞大开的过程，所以准备给大家讲讲这个“克鲁斯卡尔树定理”。

讲之前，我还是准备给大家出一个思考题，这道题我不久前在公众号里推送过，思考一下这道题非常有益于理解今天的话题。

请你玩玩看如下的这个写数列游戏，游戏目标是写出尽可能长的数字序列。但要符合以下规则：

数列的第n项，最多有n位。
数列左边的项，不能“嵌入”所有其右边的项。“嵌入”的定义如下：

有数字字符串a和b，b的长度大于等于字符a，且存在以下情况：可以从b中删除若干字符，留下与a相等长度的字符串，留下的字符前后位置关系保持不变，并记作b’。如果a比b’按位比较，每一位数字上，a的数字都小于等于b’上的数字，称a可以“嵌入”b。比如：

a=“2” 可以嵌入 b=”3″，其中取b’=’3′

a=“321” 可以嵌入 b=”13312″，其中取b’=’332′

a=“132” 不可以嵌入 b=”2131″，因为b中找不到符合要求的3个字符的子串。

以上是游戏的定义。当用n个数字玩以上游戏，可以写出的数列的最长长度，记作s(n)。

当用一个数字“1”玩这个游戏时：

第一项为：1，再也无法写出第二项。因此s(1)=1。

当用两个数字“1”和”2″玩这个游戏时：

第一项可以写“2”，第二项可以写“1”。如此再也无法写出第三项。但如果第二项写“11“，则还可以写第三项”1“。整个数列是：

2, 11, 1。

所以s(2)=3。

请简单试试写写s(3)的前几项，重点思考两个问题：是否对任意大的n，s(n)总是有限的？另外，如果去掉游戏中第一个规则，数列长度是否总是有限的？

“克鲁斯卡尔树定理”与数学中许多优美的定理一样，它的最终命题形式非常短，但准备知识多，这个准备知识就是“良拟序”（Well Quasi Ordering，简写为“wqo”）。

这个“良拟序”与我之前介绍过的“良序”概念非常类似，所以我们只需要了解两者的区别。

你不知道“良序”概念也没关系，其实它与我们平时所熟悉的“小于等于”的概念别无二致。”序关系”就是数学家从“小于等于”这种比较性质中抽象出来的条件。“ $(\leq)$ ”有这样三个性质：

自反：就是对任意的a, 有a $(\leq)$ a；

反对称：如果a $(\leq)$ b 且b $(\leq)$ a，则a=b；

传递性：如果 a $(\leq)$ b，且b $(\leq)$ c，则a $(\leq)$ c；

这三条规则，就是我们熟悉到不能再熟悉的“ $(\leq)$ “的性质，没有任何新奇的东西。

“全序关系”就是再增加一条规则：所有元素之间能够比较。

“良序关系”就是再增加一条规则：所有非空子集必有一个最小元素。

那么现在说说“拟序”(quasi orders)关系，“拟序关系”其实就是“全序关系”里，去掉一个条件：“所有元素之之间可以比较”，去掉这个条件，就是拟序。也就是一个比大小的关系，符合自反，反对称和传递性质，就是拟序。带有拟序关系的集合称为“拟序集”。

严格来说，数学中的拟序或预序(pre-order)对“自反”这个条件是可选的，而不是必须的。所以满足“反对称“和”传递性”的二元关系就可以称为“拟序”或“预序”。而加入“自反”性质后，这个序关系被称为“非严格偏序”，具有“反自反”性质的序关系则称为“偏序”。

本文中涉及的拟序都带有自反特性，为简化起见，直接加入了“自反”性质到拟序定义中。

“拟”字的来历是一个拉丁语的单词“quasi”，意思是“接近的，类似的”。其实这个词在很多科技术语中都会出现，但它一般都会翻译成“准”，比如“准晶体“（quasicrystal），“准分子”（quasimolecule）等等。但可能因为“准序”这个词听上去太奇怪了，所以翻译成了“拟序”，但听上去还是很奇怪。但理解意思就好，”拟序“说白了，就是“接近”一个完整的序关系。之所以说“接近”，是因为元素之间有可能不能比较，而元素之间如果都能互相比较，那这个序关系完整，完全了，所以叫“全序”（total ordering）。

知道了拟序概念，有没有实际的例子呢？貌似数学里多数序关系都是全序的。这里大老李想到了一个很不错的带有拟序关系的集合例子，这个例子我也准备贯穿在文中使用，所以先给大家说一下这个例子。

我想的这个拟序集合例子就是复数中，实部和虚部都是自然数的那些复数，这个集合我姑且叫它“自然复数”：

自然复数: $({ a+bi : a\in \mathbb{N}, b\in \mathbb{N}})$

但是“自然复数”里的数本身是不能比大小的，但我可以定义这样一个“ $(\leq)$ ”的关系：

$(a+bi\leq c+di)$ iff $(a\leq c, b\leq d)$

自然复数中的两个数，a $(\leq)$ b，当且仅当a的实部小于等于b的实部，且a的虚部小于等于b的虚部。

(上图中：A<=C<=B,而C,D,E之间不可比较)

也就是从图像上来看，偏左下角的数会小于等于偏右上角的的数。那么，我请各位自行验证，这样一个“ $(\leq)$ ”构成了“自然复数”里的一个拟序关系，就是满足自反、反对称、传递性。这些是很显然的。

那么这个” $(\leq)$ “是全序关系吗？显然不是，因为存在两个不可比较的元素，比如1+2i和2+i，这两者就不可比较，谁都没有小于等于谁。从图像上看，即一个数与其左上和右下区域的数是不可比的。所以这个“ $(\leq)$ ”不是全序关系。

以上，我给出了一个是拟序，但不是全序关系的例子。现在希望把“良序关系”的概念推广到“拟序”上，因为“非空子集必有最小元素”这个性质非常有用，特别是在无穷集合上。

但我们发现，如果直接给“拟序集”套用“非空子集必有最小元素”这个性质不再适用，因为拟序集合中可能存在元素两两不可比较的情况，那么这个“最小”的意思就是不明确的。

但数学家曲线救国，他们这样来定义“良拟序”：

某个集合X和其上的某个拟序关系 $(\leq)$ ，对X中的所有无穷序列 $(x_1, x_2,\cdots ,x_i, \cdots )$ ，存在某个“递增对” $(x_i)$ , $(x_j)$ :

$(x_i\leq x_j)$ 且x<j。

也就是，如果你从拟序集里写出一个无穷数列，那么你不可避免地，会写出两个元素，左边的元素小于等于其右边的某一个，就是总有两个元素是有序的，那么这个序关系就是良拟序关系。

这里能马上得出一个推论，就是良拟序集中的每个无穷序列中，必有”无穷递增子序列”(infinity increasing chain)。

可以用反证法，证明以上结论。如果某个无穷序列中，只有有限个递增对的话，且最右边的一对是a<=b，那把b之前的元素全部丢弃，剩下的序列仍然是无穷序列，但不存在有序对了，那么它就不符合良拟序定义，这不可能。所以良拟序的每个无穷序列中，必有无穷递增子序列。

以上这个拟序集的定义中，因为需要判断所有的无穷序列，所以它在判断一个拟序关系是否是良拟序的情况下，不太好用。所以经常用到的是以下良拟序的性质或者等价定义，它是把原来的定义反过来考察。

原先的定义形式是：对所有的无穷序列，存在一对排序好的元素。那它反过来就是，不存在某个无穷序列，其中没有排序好的元素。那么对拟序集来说，没有排序好意味着两种情况：左边的大于右边的，或者不可比。所以我们这里得到了两个良拟序的性质：

良拟序集中，不存在”无穷递降序列”（infinity decreasing chain）。也就是其中的元素越来越小，且无穷多，这样的序列不存在。

良拟序集中，不存在”无穷不可比(较)序列”(infinity anti-chain)，也就是不能写出一个无穷子集，其中没有任何两个元素是可以比较的。

以上就是良拟序集的两个重要性质，并且可以证明，只要拟序集符合这两条性质，那么它就是良拟序集，所以它也是良拟序的一个等价定义。

分析一下之前提到的的“自然复数”集合和那个 $(\leq)$ 关系，它构成“良拟序”吗？那就看看“自然复数”是否符合以上两条性质。

第一：“自然复数”中是否存在一个“无穷递降序列”呢？显然是不存在，因为递降的话，也就是序列中的数在图像上会越来越靠左下角发展，那么迟早会撞上原点，那就没法再往小的数字写了，所以“自然复数”中不存在无穷递降序列。

第二：“自然复数”中是否存在“无穷不可比序列”呢？这个问题稍微难一点，但是，你会发现，自然复数中也不存在无穷不可比序列。可以用反证法考虑。假设写出了一个无穷不可比序列，里面任何两个元素都不可比。之前说了，一个元素只有与其左上或者右下的元素不可比。

如果考虑序列第一项之后的序列，必定存在无穷多个元素位于第一项的左上角或者右下角，不妨假设有无穷多个元素在第一项的右下角。

考察这无穷多个右下角的元素，因为仍然需要保持其中的元素两两不可比，那么你会发现你不得不把数字不断的往右下角发展。因为向左上的发展是受第一项的位置限制的，向右上或左下发展那就会产生可比的数字，那只有不断的往右下发展，迟早会撞上x轴，再也写不下去了。而对左上角的分析结果是类似的，你需要不断的往左上写数字，那么迟早会撞上y轴。

因此，我们的“自然复数”集中就不可能存在无穷不可比序列。

以上我们证明了我们“自然复数”集中不存在无穷递降序列和无穷不可比序列，所以它是一个良拟序集。

以上结论有一个一般化后的结论(由Nash-Williams给出)：

如果有拟序集: $(\left\langle\preceq_{1}, A_{1}\right\rangle)$ 和 $(\left\langle\preceq_{2}, A_{2}\right\rangle)$ ，并定义 $(A_1)$ 和 $(A_2)$ 的笛卡尔积 $(A_1 \times A_2)$ 上的拟序关系 $(\preceq)$ ：