1-genericity in the enumeration degrees
1-genericity in the enumeration degrees
复制标题
1-枚举程度的通用性
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
K. Copestake
中科院分区：
文献类型：
--
作者：
K. Copestake
一般集和n-一般集的图灵度的结构已经得到了相当广泛的研究，特别是对于n = 1和n = 2。1-类属集最初是由D. Posner [11]，此后做了很多工作，特别是C. G. Jockusch和C. T. [15]见[16]，见[17]。在枚举度（见下面的定义）中，注意力以前仅限于泛型集合和函数。J. Case在他的论文[1]中对许多结果使用了泛型。本文提出了1-类属部分函数的概念，研究了该类函数在枚举度下的结构和特征。我们发现1-类属函数的e度是拟最小的。然而，在1-类属e-度中没有e-度极小，因为如果一个1-类属函数被递归地分割成n个或无穷多个部分，则得到的函数是e-独立的（在K定义的意义上）。McEhrman [8]）和1-generic。这一结果也表明，任何递归可归序偏序都可以嵌入到任何1-类属度之下。图灵度中的许多结果在枚举度中有直接的平行关系。将最小图灵度构造应用于偏度（偏函数的e-度）产生一个类最小的总偏度ae;也就是说，所有在ae以下度的函数都有偏递归扩张。
The structure of the Turing degrees of generic and n-generic sets has been studied fairly extensively, especially for n = 1 and n = 2. The original formulation of 1-generic set in terms of recursively enumerable sets of strings is due to D. Posner [11], and much work has since been done, particularly by C. G. Jockusch and C. T. Chong (see [5] and [6]). In the enumeration degrees (see definition below), attention has previously been restricted to generic sets and functions. J. Case used genericity for many of the results in his thesis [1]. In this paper we develop a notion of 1-generic partial function, and study the structure and characteristics of such functions in the enumeration degrees. We find that the e-degree of a 1-generic function is quasi-minimal. However, there are no e-degrees minimal in the 1-generic e-degrees, since if a 1-generic function is recursively split into finitely or infinitely many parts the resulting functions are e-independent (in the sense defined by K. McEvoy [8]) and 1-generic. This result also shows that any recursively enumerable partial ordering can be embedded below any 1-generic degree. Many results in the Turing degrees have direct parallels in the enumeration degrees. Applying the minimal Turing degree construction to the partial degrees (the e-degrees of partial functions) produces a total partial degree ae which is minimal-like; that is, all functions in degrees below ae have partial recursive extensions.