Computing with Positive Information: Definability and Structure of Enumeration Degrees

图灵度用于衡量确定任意数是否为给定自然数集的成员的难度。这一措施可以扩展到捕捉数学中其他对象的有效内容，例如实数。在其他情况下，图灵可缩减性是不够的。例如，已知不可能为单位区间上的每个连续函数分配图灵度。在这种和许多其他情况下，图灵约简的扩展，列举约化，被证明为建构性数学提供了一个更好的框架。然而，枚举度还没有像图灵度那样得到彻底的研究。这个项目的目标是扩大对枚举度的结构及其与图灵度的关系的理解。该项目旨在开发新的方法，研究结构的组合性质，并分离出决定结构逻辑特征的特殊等级，特别关注一阶可定义性。建构性数学，特别是代数和拓扑学，将是此类课程的来源。该项目旨在利用图灵度的偏序和枚举度之间的密切关系来提取两个方向的新信息。度理论中的一个重大开放问题是图灵度的结构是否是刚性的。这个问题与图灵度上一阶可定义关系的一种可能的分类有很强的联系。以前的工作已经将这个问题与枚举度的刚性问题联系起来：如果图灵度是刚性的，那么枚举度也是刚性的。枚举度的刚性虽然仍然是开放的，但可以被证明是更容易接近的。研究者和合作者通过自然结构关系建立了枚举度结构上一系列关系的一阶可定义性。该项目的一个重要目标是继续这一调查路线，建立枚举度上的一阶可定义关系的武器库，并使我们更接近枚举度的刚性问题的解决方案。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Turing degrees are used to measure how difficult it is to determine whether an arbitrary number is a member of a given set of natural numbers. This measure can be extended to capture the effective content of other objects in mathematics, such as real numbers. In other cases, Turing reducibility is not sufficient. For example, it is known to be impossible to assign a Turing degree to every continuous function on the unit interval. In that and many other cases, an extension of Turing reducibility, enumeration reducibility, turns out to provide a better framework for constructive mathematics. However, enumeration degrees have not been as thoroughly investigated as Turing degrees. The goal of this project is to expand understanding of the structure of enumeration degrees and their relationship to Turing degrees. The project aims to develop new methods, investigate combinatorial properties of the structure, and isolate special classes of degrees that determine the logical character of the structure, with a special focus on first-order definability. Constructive mathematics, specifically algebra and topology, will be the source for such classes. The project aims to utilize the intimate interplay between the partial orders of the Turing degrees and the enumeration degrees to extract new information in both directions.A major open problem in degree theory asks if the structure of the Turing degrees is rigid. This problem is strongly connected to a possible classification of the first-order definable relations on the Turing degrees. Prior work has established a link between this problem and the rigidity problem for the enumeration degrees: if the Turing degrees are rigid then so are the enumeration degrees. The rigidity of the enumeration degrees, while still open, can turn out to be more approachable. The investigator and collaborators have established the first-order definability of a series of relations on the structure of the enumeration degrees via natural structural relations. An important goal of this project is to continue this line of investigation, building an arsenal of first-order definable relations on the enumeration degrees and bringing us closer to a solution to the rigidity problem for the enumeration degrees.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.