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的全局结构和递归可枚举集R的图灵度。这种理解所必需的要素包括确定R的普遍存在理论是否是可判定的，刻画在该结构中关于R或D的关系何时可定义，以及计算这些结构的自同构群。其次，Slaman计划对二阶算术的证明论理解作出贡献。在这种情况下，人们考虑形式公理系统，它假设(集合或实数的)宇宙在可定义的运算下是封闭的。例如，考虑一组公理，这些公理表明实数在算术可定义性的相对计算下是闭合的。Slaman计划在此背景下系统地研究连续统的组合集合论性质。他对守恒问题特别感兴趣：连续体的闭包性质何时会对一阶数理论产生非平凡的影响？可定义性的代数结构由图灵度很好地表示出来，图灵度是整数集合的一种分类，其中可以彼此计算的两个集合被认为是等价的。斯拉曼将在几个背景下研究图灵学位，以解决有关其关键特征的基本问题。非有效手段的必要性，例如不可计算的集合的存在，也可以从理论上证明；这激励了斯拉曼的计划，系统地研究连续统(即，大小等于所有实数的无限集合)的组合集合论性质。他对将连续体的集合论与其他重要集合联系起来的问题特别感兴趣。连续体的某些性质何时会影响到整数的基本性质？*