Computing with Positive Information: Definability and Structure of Enumeration Degrees

正信息计算：枚举度的可定义性和结构

• 批准号: 1762648
• 负责人: Mariya Soskova
• 金额: $ 15万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2023-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1762648&HistoricalAwards=false
• 关键词: Computing; Positive; Information; Definability; Structure

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.

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

项目成果

Fragments of the theory of the enumeration degrees

• DOI: 10.1016/j.aim.2021.107686
• 发表时间: 2021-06
• 期刊: Advances in Mathematics
• 影响因子: 1.7
• 作者: S. Lempp;T. Slaman;M. Soskova

Characterizing the continuous degrees

表征连续度

• DOI: 10.1007/s11856-019-1943-x
• 发表时间: 2019
• 期刊: Israel Journal of Mathematics
• 影响因子: 1
• 作者: Andrews, Uri;Igusa, Gregory;Miller, Joseph S.;Soskova, Mariya I.
• 通讯作者: Soskova, Mariya I.

A STRUCTURAL DICHOTOMY IN THE ENUMERATION DEGREES

枚举程度的结构二分法

• DOI: 10.1017/jsl.2019.72
• 发表时间: 2020
• 期刊: Journal of symbolic logic
• 影响因子: 0.6
• 作者: Ganchev, Hristo;Kalimullin, Iskander;Miller, Joseph;Soskova, Mariya
• 通讯作者: Soskova, Mariya

The Rado path decomposition theorem

Rado路径分解定理

• DOI: 10.1007/s11856-019-1916-0
• 发表时间: 2019
• 期刊: Israel Journal of Mathematics
• 影响因子: 1
• 作者: Cholak, Peter A.;Igusa, Gregory;Patey, Ludovic;Soskova, Mariya I.;Turetsky, Dan
• 通讯作者: Turetsky, Dan