学海网

递归可枚举度的一些代数性质，毕业论文，共97页。
摘要
长期以来图灵度形成的偏序结构D = (D;·) 是递归论的一个主要研究对象，对其子结构R = (R;·) 的研究则是一个重要分支。这里R 是所有递归可枚举度的集合，递归可枚举度是可以由一个递归可枚举集合代表的图灵度，而递归可枚举集合在哥德尔不完备定理的证明中扮演了重要角色：给定一个递归的公理系统，如果它蕴含谓词演算，则其所有的定理构成一个非递归的递归可枚举集合。
R 的研究历史上的第一个著名问题是（Post (1944)）：是否存在除了0（递归集合构成的图灵度））和00（停机问题代表的图灵度）之外的递归可枚举度？这个问题的肯定答案由Friedberg (1957) 和Muˇcnik (1956) 独立地发现，他们的证明引入了优先方法。接下来的几十年，人们在Friedberg-Muchnik 工作的
基础上发展出更复杂的优先方法，并用这些方法发现了(R;﹤) 的很多重要性质，比如R 是稠密的（Sacks (1964)），即(8a; b 2 R)(a ﹤ b ! (9c 2 R)(a ﹤c ﹤ b))；R 是一个上半格，一般来说两个元素的下确界不存在（Lachlan(1966)，Yates (1966)）。
Sacks 稠密性定理的证明导致许多人猜测R是一个简单的结构，比如：Shoenfield(1965) 猜想这个结构是齐次的（即如果一个偏序P可以嵌入R中，而且Q是P的一个扩张，则在R中也可以把P扩张到Q），而Sacks 猜想R 的一阶理论是递归的。Shoenfield的猜想被Lachlan (1966) 和Yates (1966) 独立地反驳。他们在反驳中构造了称为极小对的递归可枚举度：a ^ b = 0（这样的a或b的集合记为M）。Lachlan 和Yates 的工作引起人们对R 局部性质的兴趣，人们期望通过引入更多的局部性质并且通过对局部性质的研究揭示R 的整体性质，例如：Sacks 的猜想是否成立？
然而Sacks 猜想的反驳（Harrington and Shelah (1982)）最终借助于在R 中可i定义地解释其它数学结构这样的模型论手段，而不是引入简单自然的局部性质。事实上模型论的方法早就应用在D的研究中。但是由R的局限性带来的复杂性，意味着应用模型论方法需要更复杂的技巧。这些技巧近年来由Nies,Shore, Slaman 和Woodin 等在Harrington and Shelah (1982) 的基础上系统地发展起来。越来越多整体性质的研究都引入了模型论或者集合论的工具，需要其它逻辑分支的知识和技巧，也需要应用优先方法进行更加复杂的构造。
在本论文中，我们将从格论和模型论的角度出发研究R 的一些整体性质：可定义理想和滤子的存在性，子结构和R 的关系，以及同余关系和商结构。为此我们将借助Nies, Shore 和Slaman 等发展的在R 中解释数论模型(N;+; 0) 的工具。
我们将在第二章中研究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”非常相近，我们却能够证明它们并不相同。
关键词: 递归可枚举度; 上半格; 理想; 滤子; 同余关系; 子结构; 可定义.