英文
Post’s problem
简介
不递归、不完备的re集的存在问题.1944年，波兰-美国数理逻辑学家波斯特(Post，E.L.)提出了如下著名问题：是否存在非递归并且非完备的re集? 即是否存在re度a，使0<Ta<T0′?此问题即波斯特问题.波斯特本人为解决此问题做了许多工作.他计划构造一个re集A，使得A具有某种可定义的(与A非递归相容的)性质，并且这种性质能保证A非T完备.称此计划为波斯特规划.波斯特试图构造一个re集A，使得A是足够“稀疏”的，并且这种“稀疏”性最终能保证A非T完备.他首先定义了单纯集，并证明了它的存在性，还证明了单纯集不是m完备的.但事实上，单纯集仍可能是tt完备的(从而也是T完备的).于是，他又定义了补集比单纯集更稀疏的超单纯集和超超单纯集，它们不再是tt完备的.他构造了一个超单纯集，但未能证明超超单纯集的存在性，也没有证明超单纯集或超超单纯集不是T完备的.到1954年，德克尔(Dekker，J.)证明了超单纯集不一定不是T完备的.后来，曼希尔(Myhill，J.)又引进了极大集的概念，这是可能做到的使re集的补集最稀疏的情况.弗里德贝格(Friedberg，R.M.)证明了极大集与超超单纯集的存在性，而耶茨(Yates，C.E.M.)则构造了一个T完备的极大集，从而使得用构造一个稀疏的补集的方法，来解决波斯特问题的希望最终破灭.首先解决波斯特问题的是弗里特贝格和穆切尼克(Mucnik，A.A.).1956年至1957年，他们分别独立地创造了有穷损伤方法，并用此方法证明了存在两个不可比的re度(因而它们也都是非递归且非T完备的)，从而成功地解决了波斯特问题.
虽然按照波斯特原来建议的方法无法实现波斯特规划，但实现这个规划的努力一直没有停止.1973年，刁格太夫(Degtev，A.N.)证明了，存在某个正等价关系η及re集A，使得A为非递归、半递归及η极大的.1976年，马琴科夫(Marchenkov，S.S.)证明了：η超超单纯集不是Q完备的，并且re半递归集如果不是Q完备的，也一定不是T完备的.因此刁格太夫构造的非递归、半递归及η极大的re集，即为非递归且非T完备的re集.但这个结果并未完全实现波斯特规划，因为η超超单纯集的概念不是一阶可定义的.直到1990年，哈林顿(Harrington，L.)和索尔(Soare，R.I.)找到了一个一阶可定义性质Q(A)，使得满足该性质的re集都是非递归且非T完备的，并且他们证明了存在满足Q(A)条件的re集，从而成功地实现了波斯特规划.他们给出的性质Q(A)为
(∃C)A⊂mC(ᗄB⊆C)(∃D⊆C)(ᗄS)S⊂C[[B∩(S-A)=D∩(S-A)]→(∃T)C⊂T[A∩(S∩T)=B∩(S∩T)]]，
其中A⊂mC表示A为C的主子集，A⊂B表示存在非空(re)C，使A∪C=B并且A∩C=∅.