FRG: Collaborative Research: Computability-Theoretic Aspects of Combinatorics

FRG：协作研究：组合学的可计算性理论方面

• 批准号: 1854136
• 负责人: Peter Cholak
• 金额: $ 27.2万
• 依托单位: University of Notre Dame
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1854136&HistoricalAwards=false
• 关键词: FRG; Collaborative; Research; Computability; Theoretic

Computability theory arose out of the development by Turing and others of a mathematically precise definition of the notion of algorithm. One of the most fruitful developments in this field has been the study of the algorithmic content of mathematics. At the same time, concerns about the foundations of mathematics have led to the analysis of different formal systems for mathematical reasoning, and the study of the relative power of such systems. The computability-theoretic approach has turned out to play a key role in this project. Combinatorics is an area of mathematics whose methods and results underlie a great deal of mathematical reasoning, so the study of its algorithmic content and of the systems required to formalize its methods is particularly important. Computable combinatorics has a long history, but has seen a recent surge of interest highlighting the fact that computability-theoretically natural notions tend to be combinatorially natural, and vice-versa. This project aims to strengthen the connections between computability theory and combinatorics by increasing our understanding of the algorithmic content of combinatorial principles, through a concerted group effort to use what we have learned in recent years to systematize the area further, work toward solving a number of its outstanding questions, and explore its outward-facing aspects.This project will address major open problems such as determining whether Hindman's Theorem holds arithmetically, and whether it is equivalent to its restriction to sums of length at most two; determining the first-order part of Ramsey's Theorem for pairs, and clarifying the computability-theoretic relationship between this principle and its stable version; and determining the exact proof-theoretic strength of Laver's Theorem. More importantly, it will focus on the development of lines of research particularly relevant to the growing interest in connections between computability theory and combinatorics, including the study of questions of methodological interest to combinatorialists, for instance ones involving Hindman's Theorem and the use of ultrafilters in combinatorics; the development of new proofs of combinatorial theorems inspired by questions regarding the computational content of these theorems, along the lines of Montalban's new proof of Laver's Theorem; the analysis and comparison of different general methods, such as the use of ultrafilters, topological dynamics, and probabilistic methods; the development of notions of comparison between theorems that, while still computability-theoretic in spirit, are closer to being direct reflections of combinatorial differences; the understanding of splittings of combinatorial principles into computationally and combinatorially simpler parts; the study of the usefulness of combinatorially-defined objects as computational oracles; and the study of the first-order consequences of the existence of combinatorially-defined second-order objects. This project is thus aimed at developing the study of the connections between computability theory and combinatorics along a large number of related directions, making use of the computability-theoretic, proof-theoretic, and combinatorial expertise of its PIs, senior personnel, and key collaborators.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.

可计算性理论源于图灵和其他人对算法概念的数学精确定义的发展。该领域最富有成效的发展之一是对数学算法内容的研究。与此同时，对数学基础的关注导致了对数学推理的不同形式系统的分析，以及对这些系统的相对能力的研究。可计算性理论方法在该项目中发挥了关键作用。组合学是数学的一个领域，其方法和结果是大量数学推理的基础，因此对其算法内容和形式化其方法所需的系统的研究尤为重要。可计算组合学有着悠久的历史，但最近人们的兴趣激增，突显了这样一个事实：可计算性理论上的自然概念往往是组合自然的，反之亦然。该项目旨在通过增加我们对组合原理的算法内容的理解来加强可计算性理论和组合学之间的联系，通过集体努力利用我们近年来学到的知识进一步系统化该领域，努力解决一些问题该项目将解决主要的开放性问题，例如确定 Hindman 定理在算术上是否成立，以及它是否等价于其对最多二长度和的限制；确定拉姆齐对定理的一阶部分，并阐明该原理与其稳定版本之间的可计算性理论关系；并确定拉弗定理的确切证明理论强度。更重要的是，它将重点关注与可计算性理论和组合学之间的联系日益增长的兴趣相关的研究方向的发展，包括组合学家感兴趣的方法论问题的研究，例如涉及辛德曼定理和超滤器在计算中的使用的问题。组合学；受有关这些定理的计算内容的问题的启发，沿着 Montalban 的 Laver 定理的新证明的思路，开发了组合定理的新证明；不同通用方法的分析和比较，例如超滤器、拓扑动力学和概率方法的使用；定理之间比较概念的发展，虽然在精神上仍然是可计算性理论，但更接近于组合差异的直接反映；了解将组合原理分解为计算和组合上更简单的部分；研究组合定义对象作为计算预言的有用性；以及研究组合定义的二阶对象存在的一阶后果。因此，该项目旨在利用其 PI、高级人员和关键合作者的可计算性理论、证明理论和组合专业知识，沿着大量相关方向发展可计算性理论和组合学之间联系的研究该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。