更改

===The lattice of recursively enumerable sets===

===The lattice of recursively enumerable sets===

When Post defined the notion of a simple set as an r.e. set with an infinite complement not containing any infinite r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. This lattice became a well-studied structure. Recursive sets can be defined in this structure by the basic result that a set is recursive if and only if the set and its complement are both recursively enumerable. Infinite r.e. sets have always infinite recursive subsets; but on the other hand, simple sets exist but do not have a coinfinite recursive superset. Post (1944) introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are r.e. sets such that every r.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the recursive sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; Harrington and Soare (1991) found eventually such a property.

When Post defined the notion of a simple set as an r.e. set with an infinite complement not containing any infinite r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. This lattice became a well-studied structure. Recursive sets can be defined in this structure by the basic result that a set is recursive if and only if the set and its complement are both recursively enumerable. Infinite r.e. sets have always infinite recursive subsets; but on the other hand, simple sets exist but do not have a coinfinite recursive superset. Post (1944) introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are r.e. sets such that every r.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the recursive sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; Harrington and Soare (1991) found eventually such a property.

When Post defined the notion of a simple set as an r.e. set with an infinite complement not containing any infinite r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. This lattice became a well-studied structure. Recursive sets can be defined in this structure by the basic result that a set is recursive if and only if the set and its complement are both recursively enumerable. Infinite r.e. sets have always infinite recursive subsets; but on the other hand, simple sets exist but do not have a coinfinite recursive superset. Post (1944) introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are r.e. sets such that every r.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the recursive sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; Harrington and Soare (1991) found eventually such a property.

When Post defined the notion of a simple set as an r.e. set with an infinite complement not containing any infinite r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. This lattice became a well-studied structure. Recursive sets can be defined in this structure by the basic result that a set is recursive if and only if the set and its complement are both recursively enumerable. Infinite r.e. sets have always infinite recursive subsets; but on the other hand, simple sets exist but do not have a coinfinite recursive superset. Post (1944) introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are r.e. sets such that every r.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the recursive sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; Harrington and Soare (1991) found eventually such a property.

当波斯特将简单集合的概念定义为 r.e。无限补集，不包含任何无限 r.e。集，他开始研究包含下递归可枚举集的结构。这个晶格成为一个研究得很好的结构。当且仅当集合及其补集都是递归可枚举的时，可以通过集合是递归的这一基本结果定义递归集合。无穷无尽的爱。集合总是有无限递归子集; 但另一方面，简单集合存在，但没有余无限递归超集。Post (1944)引入了已有的超简单集和超简单集，后来又构造了极大集。让每一个 r.e。超集要么是给定极大集的有限变形，要么是共有限变形。波斯特研究这个格的最初动机是找到一个结构性的概念，这样每个满足这个性质的集合既不在递归集合的图灵度中，也不在停止问题的图灵度中。波斯特没有找到这样一个性质，他的问题的解决方案采用了优先权方法，哈林顿和索尔(1991)最终找到了这样一个性质。

当波斯特将单纯集定义为一个具有无限补集且不包含任何无限r.e.集的r.e.集时，他开始研究其包含的可递归枚举集的结构。晶格成为一个研究得很好的结构。在这种结构中，递归集合可以通过以下基本结果定义:当且仅当集合及其补集都是递归可枚举时，集合是递归的。无限r.e.集总是有无限递归子集。但另一方面，单纯集存在，但没有无限递归超集。波斯特(1944)引入了已有的超单纯集和超超单纯集，后来又构造了极大集，让每一个 r.e.超集要么是给定极大集的有限变形，要么是共有限变形。波斯特研究格的最初动机是找到一个结构性的概念，这样每个满足这个性质的集合既不在递归集合的图灵度中，也不在停止问题的图灵度中。波斯特没有找到这样一个性质，他的问题的解决方案采用了优先级方法，哈林顿和索尔(1991)最终找到了这样一个性质。

 

 

===Automorphism problems===

===Automorphism problems===