250个数学难题：3

递归可枚举度中的格嵌入问题和双量词理论可判定性问题

Lattice Embedding Problem and The Decidability Problem of H₂-Theory in Recursively Enumerable Degrees

递归可枚举度的格嵌入问题的历史可以追溯到 20 世纪 60 年代, 从那时起, 很多递归论学家都在该问题上花过心血, 但至今仍未完全解决. 研究格嵌入问题的动机之一是揭示度结构的复杂程度. 此外已知的关于格的不可判定性结果, 通过嵌入可以引入到递归可枚举度当中. 问题叙述很简单：

格嵌入问题 一个格能被嵌入递归可枚举度的充分必要条件是什么?

我们简单回顾格嵌入问题的历史, 由于篇幅关系我们略去文献出处及术语的定义, 读者可以参考文献 [1]、[2]. 1966 年 Lachlan 和 Yates 独立地证明了极小对的存在, 从而推出钻石格可以嵌入. 这是格嵌入的第一个结果. 此后, Lerman 和Thomason 证明了所有可数分配格都可以嵌入, Lachlan 1970 年证明了非分配格 M₃和 N₅ 可以嵌入, 1980 年, Lachlan 和 Soare 举出了第一个不可嵌入格的例子 S₈. 80年代末, 人们一度分离出所谓非嵌入性条件, 并猜想所有不满足该条件的格都可以嵌入. 但 Lempp 和 Lerman 1997 年找到一个他们称为 L₂₀ 的格并不满足该条件但也不能嵌入.

显然格嵌入问题的解决会使人们对递归可枚举度本身的代数结构有更清晰的了解, 但它的意义并不局限于此, 人们普遍认为格嵌入问题的解决会为递归可枚举度片断可判定性问题扫清技术障碍.

从逻辑角度来看, 关于一个数学结构的最重要问题之一是其理论是否可以判定,也就是说是否有一个算法能够判断任意语句在该结构中是否成立. 1982 年 Harrington 和 Shelah 证明了递归可枚举度的理论是不可判定的. 从那以后, 问题转化成到底在哪一个片段上该理论是不可判定的. 1998 年empp, Nies 和 Slaman 证明了三量词理论是不可判定的. 由于在 50 年代末人们已知单量词理论是可以判定的, 所以唯一留下的问题是：

双量词理论可判定性问题 递归可枚举度的双量词理论是不是可以判定的?由于格嵌入问题是双量词理论可判定性问题的一个有代表性的子问题, 人们普遍认为应该从格嵌入问题入手, 解决格嵌入问题的思想或许能应用到后一问题上.

参 考 文 献

[1] Lempp S, Lerman M and Solomon R. Embedding finite lattices into the computably enumerable degrees-a status survey // Chatzidakis Z, Keopke P and Pohlers W. Logic Colloquium’02, Lecture Notes in Logic, 27, ASL, Wellesley, MA, 2006

[2] Lerman M. Embeddings into the computably enumerable degrees // Cholak P, Lempp S, Lerman M and Shore R A, eds. omputability theory and its applications(Boulder,CO, 1999), Contemp Math, 257: 191-205. AMS, Providence, RI, 2000

撰稿人：杨 跃

新加坡国立大学