论文部分内容阅读
长期以来图灵度形成的偏序结构D=(D,≤)是递归论的一个主要研究对象,对其子结构(R,≤)的研究则是一个重要分支。这里R是所有递归可枚举度的集合,递归可枚举度是可以由一个递归可枚举集合代表的图灵度,而递归可枚举集合在哥德尔不完备定理的证明中扮演了重要角色:给定一个递归的、协调的公理系统,如果它蕴含谓词演算,则其所有的定理构成一个非递归的递归可枚举集合。
R的研究历史上的第一个著名问题是(Post(1944)):是否存在除了O(递归集合构成的图灵度))和O(停机问题代表的图灵度)之外的递归可枚举度?这个问题的肯定答案由Friedberg(1957)和Mu(c)nik(1956)独立地发现,他们的证明引入了优先方法。接下来的几十年,人们在Friedberg—Mu(c)nik工作的基础上发展出更复杂的优先方法,并用这些方法发现了(R,<)的很多重要性质。
Sacks稠密性定理的证明导致许多人猜测冗是一个简单的结构,比如:Shoenfield(1965)猜想这个结构是齐次的(即如果一个偏序P可以嵌入R中,而且Q是P的一个扩张,则在R中也可以把P扩张到Q),而Sacks猜想R的一阶理论是递归的。Shoenfield的猜想被Lachlan(1966)和Yates(1966)独立地反驳。他们在反驳中构造了称为极小对的递归可枚举度:a∧b=0(a,b>0)(这样的a或b的集合加上0记为M)。Lachlan和Yates的工作引起人们对R局部性质的兴趣,人们期望通过引入更多的局部性质并且通过对局部性质的研究揭示R的整体性质,例如:Sacks的猜想是否成立?
然而Sacks猜想的反驳(Harrington and Shelah(1982))最终借助于在R中可定义地解释其它数学结构这样的模型论手段,而不是引入简单自然的局部性质。事实上模型论的方法早就应用在D的研究中。但是由R的局限性带来的复杂性,意味着应用模型论方法需要更复杂的技巧。这些技巧近年来由Nies,Shore,Slaman和Woodin等在Harrington and Shelah(1982)的基础上系统地发展起来。越来越多整体性质的研究都引入了模型论或者集合论的工具,需要其它逻辑分支的知识和技巧,也需要应用优先方法进行更加复杂的构造。在本论文中,我们将从格论和模型论的角度出发研究R的一些整体性质:可定义理想和滤子的存在性,子结构和R的关系,以及同余关系和商结构。为此我们将借助Nies,Shore和Slaman等发展的在R中解释数论模型(N,+,O)的工具。
本文将在第二章中研究R的一个理想。在这方而的一个重要结果是Ambos-Spies et al.(1984)发现的:R可以分解为一个超滤NC和一个素理想M,并且它们是可定义的。然而自此以后,人们一直未能找到其它可定义的代数子结构。这方面的突破一直等到Nies(2003)证明“所有R的可定义子集生成的理想也是可定义的”。Yu and Yang(2005)应用这一有力的结果找到了的更多的理想,其中的一个理想是由NB生成的。Li and Yang(2003)注意到NB的构造和PC的构造接近,因此问它们是否生成同一个理想。我们将证明上述的集合生成不同的理想,事实上PC生成一个之前未知的理想。另一方面我们证明了:任何非主理想都是R的∑1-初等子结构。这一结果从模型论的角度说明非主理想在一定程度上反映了R的性质。
在本论文的第三章,我们第一次给出定义滤子的一般手段:利用Nies(2003)的一个定理,我们证明“所有R的可定义子集生成的滤了也是可定义的”,这就意味着我们可以通过寻找R的可定义子集来寻找可定义的滤子。这是上述Nies关于可定义理想的结果的对偶。应用上述结论,我们找到两个新的可定义滤子:分别由Cups(M)和NSB生成的滤子。在此之前,NC是唯一已知的可定义滤子。
另一方面,R的商结构的一些基本性质至今没有被系统地研究,比如稠密性。Schwarz(1984)证明了(R/M,≤)是向下稠密的。在第四章,我们定义了一个并非由理想诱导的同余关系,并且证明其诱导的商结构并不稠密:另一方面,尽管此同余关系和“模NCup”非常相近,我们却能够证明它们并不相同。