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 上的关系何时可在该结构内定义，并计算这些结构的自同构群。 其次，斯拉曼计划为二阶算术的证明理论理解做出贡献。 在这种情况下，我们考虑正式的公理系统，它假设宇宙（集合或实数）在可定义的运算下是封闭的。 例如，人们考虑一组公理，该公理指出实数在算术可定义性的相对计算下是封闭的。 斯拉曼计划在这种背景下系统地研究连续统的组合集合论性质。 他对守恒问题特别感兴趣：连续统的闭包性质何时对一阶数论产生重要影响？ 可定义性的代数结构可以用图灵度很好地表示，图灵度是整数集的分类，其中可以相互计算的两个集合被认为是等价的。 斯拉曼将在多种环境下研究图灵度，以解决有关其关键特征的基本问题。 无效手段的必要性，例如不可计算的集合的存在性，也可以从理论上证明；这激发了斯拉曼的计划，系统地研究连续统（即大小等于所有实数的无限集合）的组合集合论性质。 他对将连续统集合论与其他重要集合联系起来的问题特别感兴趣。 连续统的某些性质何时与整数的基本性质有关？ ***