Mathematical Sciences: Computability and Mathematical Definability

数学科学：可计算性和数学可定义性

• 批准号: 9500878
• 负责人: Theodore Slaman
• 金额: $ 6万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-07-01 至 1997-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9500878&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Computability; Definability

9500878 Slaman Slaman intends to study computability and mathematical definability. This research will contribute to developing a complete understanding of the degree-theoretic structures associated with relative definability, such as the global structures of the Turing degrees D and the Turing degrees of the recursively enumerable sets R. Missing ingredients necessary to this understanding include determining whether the universal-existential theory of R is decidable, characterizing when a relation on R or D is definable within that structure, and calculating the automorphism groups of these structures. Secondly, Slaman plans contributions to the proof-theoretic understanding of second-order arithmetic. In that context, one considers formal axiom systems which postulate that the universe (of sets or of reals) is closed under definable operations. For example, one considers the collection of axioms that states that the reals are closed under relative computation of arithmetic definability. Slaman plans systematically to study the combinatorial set-theoretic properties of the continuum in this context. He is particularly interested in conservation questions: When do closure properties of the continuum have nontrivial consequences for first-order number theory? The algebraic structure of definability is well represented by the Turing degrees, a classification of sets of integers in which two sets that can be computed from each other are considered equivalent. Slaman will study the Turing degrees in several settings, to address fundamental questions about their critical features. The necessity of noneffective means, such as the existence of sets which are not computable, can also be demonstrated proof-theoretically; this motivates Slaman's program for the systematic investigation of the combinatorial set-theoretic properties of the continuum (i.e., of an infinite set of size equal to that of all real numbers). He is particularl y interested in questions which relate the set theory of the continuum to other important sets. When do certain properties of the continuum have bearing on elementary properties of the integers? ***

9500878 SLAMAN SLAMAN打算研究计算性和数学可确定性。 这项研究将有助于建立对与相对确定性相关的程度理论结构的完整理解，例如图灵d d的全球结构和递归列举的集合的图灵度。 R的普遍存在理论是可以决定的，它表征了R或D的关系在该结构中可以定义，并计算这些结构的自动形群。 其次，Slaman计划对二阶算术的证明理论理解的贡献。 在这种情况下，人们考虑了正式的公理系统，这些系统假定（集合或真实）的宇宙在可定义的操作下被关闭。 例如，人们考虑的公理集合指出，在算术确定性的相对计算下，实数是关闭的。 在这种情况下，Slaman计划系统地研究连续体的组合理论特性。 他对保护问题特别感兴趣：连续体的封闭特性何时对一阶数字理论产生非平凡的后果？ 定义性的代数结构由图灵度很好地表示，整个整数组的分类中，可以将两组可以彼此计算。 Slaman将在几种环境中研究图灵学位，以解决有关其关键特征的基本问题。 没有赋予手段的必要性，例如不可计算的集合的存在，也可以从理论上证明证明；这激发了Slaman的计划，以系统研究连续体的组合设置理论特性（即，无限大小等于所有实数的尺寸集）。 他特别对将连续体的集合理论与其他重要集的问题感兴趣。 连续体的某些属性何时与整数的基本特性有关？ ***