补充资料：递归集合论

递归集合论
recursive set theory

(见[3]). 早求非T完全集的期望产生了极大集的概念.这个事实曾经被作为对Post问题的一个自然解答E.Post本人藉对递归一可枚举集的补集强加上越来越严的限制定义出了超单集、超超单集的类，且证明了超一单集不会是tt完全的.于是一补集为无穷集的递归可枚举集A称为超单的(h乡详r一sjmple)(超超单的(hype卜】lyper一s”刀pk))，如果不存在两两不相交的有穷(递归，可枚举)集的可计算序列使得每个集都和A的补集的交非空.这些集类的定义不是用格沦术语给出的，实际上已经证明“是超单集”不具有‘格沦性质.但是己经证明了一个具有无穷补集的递归一可枚举集A是超超单集，当且仅当对任意递归一可枚举集B存在递归集R使得R三B且(B\A)‘R，即已证明了“是超超单集”的性质是格论的性质.已经构造出一个不具有极大超集的超超单集(1 3J)并且也证明了对任意非递归的递归可枚举集A存在格、的一个自同构小使得小(A)是一个了完全集(【61)，所以已经证明了想找一个不含递归集和T完全集的格论性质是徒劳的. 也有〔与【7〕的看法相同的)观点，按照这观点，递归集合论要研究N的子集的在递归置换下不变的性质.与此相一致，两个集合A、B称为有相同的递归等价类型(reeursivee明ivalence tyPe)，若有一个单射可计算函数f使得f(A)二B且.厂一’(B)二A.不含具有无穷递归可枚举子集的集合的那些递归等价类型称为孤立元(jsol).一旦对孤立元定义了方便的加法和乘法运算就可以开展孤立元的“算术”的研究. 递归一可枚举集和可归约性的性质的研究不仅和递归函数理沦的其他方向有联系，而且也可以在逻辑、模型论和代数中找到应用.递归集合论有它自己的研究方法.最有名的方法是所谓的优先方法(prio-rity meth浏)，这个方法已得到了极深奥的结果.【补注】由于算法可以用不同语言描述后，人们可以系统地对算法的描述赋之以自然数，方法很简单，就是把所用的语言的表达式枚举出来，首先按长度，其次按字母序排(见递归(recurs沁n)).因此可计算函数类和递归可枚举集类也可被枚举.第n个可计算函数即是由被赋之以数n的算法所计算的函数，_几第n个递归一可枚举集是第，，个可计算函数的值域.这里，，称为递归可尽争半的熬(nUmber of‘he recursively-ellunlerable set)(亦见递归函数(化culsive filnetion). 上面讲的几st问题的否定解通常称为My叨HKF血dberg定理〔Much吐一Fried比rgthe。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。