警告 : 这篇文章的主体部分未完成，并且可能将来也不会完成了。
太离谱了。
TREE(3)
如果你看过一些数学科普，那么你应该知道\(TREE(3)\)。
\(TREE(2)\)随便就数过来了，而这个数是如此之大，并且它还是有限的，这真是太奇怪了。
Minimal Set
给一个语言(字符串的集合)\(L\)，它可以是无限集，它的Minimal Set定义为从小到大排序之后字典序最小的语言，使得\(L\)中每个串都包含至少一个Minimal Set中的串作为子序列。
这真是太奇怪了!为什么无限集的Minimal Set是有限的/yun，下面我们就来说明这个事情。但是在此之前先贴几个结论。
要求有限集的Minimal Set是简单的，只需要从小到大模拟即可。但是无限集的Minimal Set只能猜测大小然后硬冲了。
十进制下素数的Minimal Set是\(2,3,5,7,11,19,41,61,89,409,449,499,881,991,6469,6949,9001,9049,9649,9949,60649,666649,946669,60000049,66000049,66600049\)，总之就是搜到7e7即可。这可以用一个18个状态的自动机表示。
十进制下合数的Minimal Set是\(4,6,8,9,10,12,15,20,21,22,25,27,30,32,33,35,50,51,52,55,57,7072,75,77,111,117,171,371,711,713,731\)，总之就是搜到1e3即可。
据猜测十进制下\(2\)的幂的Minimal Set是\(1,2,4,8,65536\)。
结论1 定义\(\leq\)为字符串之间的二元关系运算，\(a\leq b\)当且仅当\(a\)是\(b\)的子序列。
定义一个关系是好的，指的是不存在无限长的反链，也就是不存在一个集合满足其元素两两不可比。结论1是，对于字符集有限的字符串集合，\(\leq\)是好的。
这是Higman引理的一个经典推论。
证明
考虑对于所有让\(\leq\)不好的序列们(这样的序列不妨称作 见鬼序列)，显然必然存在一个见鬼序列使得每一项长度至少是\(2\)。找到其中按长度比较字符串的话，字典序最小的这样的序列\(t\)，把每一项的第一个字符拿出来作为序列\(a\)，剩下的部分作为序列\(s\)，那么\(s\)显然也是见鬼的。
因为\(a\)的每项只有一个字符，而\(a\)是无限的，于是一定存在一个字符出现了无限次，假设它出现的位置构成序列\(p\)。那么容易发现序列\(t_1,t_2,...,t_{p_1-1},s_{p_1},s_{p_2},...\)必然也是见鬼的，而按长度比较的话\(s_{p_1}\)比\(t_{p_1}\)短了\(1\)，所以\(t\)必然不是字典序最小的。这就证完了。
Higman引理
开始胡乱翻译。
拟序集和有限基
拟序(quasi-order，或称 预序 preorder?不过我觉得 拟序 舒服一点)是二元关系\(\leq\)，它满足自反性和传递性。它和偏序的区别在于不需要满足反对称性，也就是\(a\leq b,b\leq a\Rightarrow a\sim b\)。
良拟序是一种拟序\(\leq\)，使得每个无限序列\(a\)(但每个元素是有限大小的)中都有两个元素\(a_i,a_j\)使得\(i<j,a_i\leq a_j\)，也就是存在顺序对。容易发现有一对顺序对，等价于有无限对顺序对。
在拟序集\(A\)中，定义一个集合\(B\)的闭包\(\mathrm{cl}(B)\)是所有\(b\in B,a\in A,b\leq a\)的\(a\)组成的集合。闭集指的是闭包是自己的集合，显然一个闭包必然是闭集。开集指的是补集是闭集的集合。
定义一个拟序集是有限基的(finite basis property)，当且仅当它的每个闭子集都是一个有限集的闭包。
有限基是个很优秀的性质，比如
定理1 对于一个拟序集\(A\)，以下几件事是等价的 :
-
它是有限基的，也就是每个闭子集都是一个有限集的闭包。
-
它的闭子集们构成的极长真包含链(每一个包含上一个)必然终结于同一个集合(这个集合看起来一定是\(A\)本身)。不过这个感觉翻译错了?
-
对于它的任意子集\(B\)，存在一个有限集\(B_0\)满足\(B_0\subset B\subset\mathrm{cl}(B_0)\)。
-
每个\(A\)中元素组成的无限序列存在顺序对，也就是这个拟序是良拟序。
-
每个\(A\)中元素组成的无限序列不可能是下降的或者(两两)不可比的。
-
每个\(A\)中元素组成的无限序列存在一个无限长的上升子序列。
证明 略。
定理2 对于一个有限基的拟序集，它的每个子集和每个同态像也是有限基的。
子集是显然的。同态像呢?也是显然的。
但是拟序集的同态像***是啥啊，fuck/fn
定理3 两个有限基的拟序集的基数积也是有限基的。基数积就是拟序集的笛卡尔积，其中\((a_1,b_1)\leq (a_2,b_2)\)定义为\(a_1\leq b_1,a_2\leq b_2\)。
证明 感觉就很像对的。
定理4(拟序集序列上的归纳法) 定义一个拟序集序列\(M^\prime_1,...M^\prime_n\)是由\(M_1,...,M_n\)下降(descent)得来的，当且仅当从右往左找到两个序列第一个不同的位置\(r\)，两个序列满足\(M^\prime_r\)是\(M_r\)的真开子集，且\(i<r\)的\(M^\prime_i\)是任意有限基的拟序集。
有一个命题是关于一个拟序集序列的。如果 : 这个命题对于拟序集序列\(M_1,...,M_n\)是假的，可以推出这个命题对于任意一个由它下降得到的拟序集也是假的；那么这个命题在每个\(M_i\)都是有限基的时候是真的。
证明 考虑若干引理。
引理4.1(拟序集上的归纳法) 如果一个命题满足 : 它对一个拟序集的所有真开子集成立，那么它对这个拟序集成立(当然它要对空成立)；那么它对每个有限基的拟序集成立。这是对拟序集的一种归纳法。
证明 显然/hanx。如果它对某个拟序集不成立，那么它对这个拟序集的某个真开子集也不成立，那么就会形成一条无限长的包含链，所以根据定理1它就不有限基了。
引理4.2 如果一个拟序集删掉每个元素的闭包之后都是有限基的，那么它是有限基的。
证明
引理4.3
定义一个代数(algebra)是一个二元组\((A,M)\)，其中\(A\)是一个字符集，而\(M\)是一个 \(A\)的元组集合到\(A\)的映射 的集合，这里元组可以是\(0\)元组。定义\(M_r\)说的是\(M\)中所有对\(r\)元组的映射的集合。\(M\)不一定是有限的，但是这里要求存在某个\(n\)使得\(r>n\)的\(M_r\)是空的。国内的定义好像不太一样。
定义一个字符集的字符串集(闭包)\(A^\ast\)说的是它组成的字符串的集合。
定义一个代数\((A,M)\)的M-子代数(M-subalgebra，简称 子代数)是另一个代数\((B,M)\)，其中\(B\subseeteq A\)，并且\(M\)中的映射们对\(B\)仍是封闭的，也就是说\(B\)的元组经过\(M\)的映射还是在\(B\)中。定义一个代数是极小的，当且仅当它没有自己之外的子代数。
极小代数不一定是空的，因为我们允许\(M\)中出现对\(0\)元组的映射，空并不是所有代数的子代数。(你觉得这个并不能证明?实际上我没想证明/hanx)
总之极小代数这个定义看起来很奇怪。一会你就懂了（
现在有一个定义在\(A\)上的拟序\(\leq\)，如果它对于代数\((A,M)\)的任意\(a,b\in A,x,y\in A^\ast,\mu\in M\)有\(a\leq b\Rightarrow\mu(xay)\leq\mu(xby)\)，那么就称这个拟序和这个代数构成了一个拟序代数。当然其中\(x,y\)的长度和是\(\mu\)的参数个数\(-1\)。接下来我们提到\(a,b,x,y,\mu,\lambda\)一般也是这个意思(\(\lambda\)也指映射)。
定义这个拟序\(\leq\)是一个整除(divisibility order)，当且仅当对于任意\(\mu,a,x,y\)，有\(a\leq\mu(xay)\)。
如果现在有\(n+1\)个分别在\(M_0,...,M_n\)上的拟序了，定义一个\(A\)上的拟序和它们是兼容(compatible)的，当且仅当对于任意\(\lambda,\mu\in M_r,x\in A^\ast\)，有\(\lambda\leq\mu\Rightarrow\lambda(x)\leq\mu(x)\)。
引理1 对于一个整除代数\((A,M)\)，它的一个子代数\((A_0,M)\)并上它的一个闭子集\(X\)还是它的一个子代数。
证明 设\(\mu\)是一个\(r\)个参数的映射，\(a_1,...,a_r\)是\(A_0\cup X\)的元素，\(b=\mu(a_1,...,a_r)\)。于是
-
如果\(a_1,...,a_r\)都是\(A_0\)的元素，那么\(b\)也是\(A_0\)的元素，因为\((A_0,M)\)是一个子代数。
-
如果某个\(a_i\)不是\(A_0\)的元素，那么它就是\(X\)的元素。同时有\(a_i\leq b\)，这里是在\(A\)上的整除的意义下。于是\(b\)必然是\(X\)的元素，因为\(X\)是闭集。
定理1(Higman引理) 对于一个极小代数\((A,M)\)，其中\(M\)满足每个\(M_r\)都是有限基的拟序集(也就是说它上面有一个拟序，这个逆序使得它有限基)，那么\(A\)在任意与所有\(M_r\)上的拟序们兼容的整除的意义下是有限基的。请反复阅读这句话，确保你理解了。
证明 我不理解。咕咕咕/hanx