Computable model theory and invariant descriptive computability theory

可计算模型理论和不变描述可计算性理论

• 批准号: 2348792
• 负责人: Uri Andrews
• 金额: $ 29万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-07-01 至 2027-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2348792&HistoricalAwards=false
• 关键词: Computable; model; theory; invariant; descriptive

Mathematical logic grew out of a need to develop rigorous foundations for mathematics. Within mathematical logic, three major subfields are studied. Model theory understands mathematical objects by considering them through the lens of a formal language. Computability theory understands mathematical objects by considering them through the lens of computational complexity. Set theory understands mathematical objects through the foundational axioms of mathematics and how those axioms imply the object’s existence. This project focuses on some connections between computability theory and the other two subfields of logic. Regarding model theory, the project involves exploring the phenomenon when two mathematical objects look the same in terms of their formal languages, but one can be computed while the other cannot. In set theory, there is a rich theory exploring the complexity of 2-dimensional sets in terms of constructively embedding one into another. These embeddings are constructible in terms of the basic set-theoretic operations of unions and complements, but they may not be computable. The project will explore an analogous theory where one considers embeddings that must be computable. This project involves work with undergraduate and graduate students. The computable spectrum of a first-order theory asks which dimensions of models of that theory are computable. The spectrum problem in computable model theory, which has been a major open problem since the 70s, asks for which sets may be computable spectra of uncountably categorical theories, with a focus on strongly minimal theories. In this project, the aim is to give a reduction of the problem from a fully general framework down to the locally modular strongly minimal theories, which are geometrically tame and are closely related to groups. From there, the hope is to be able to give concrete answers as to which sets are spectra. Separately, this project will examine computable reduction on equivalence relations. One major direction is to use this complexity notion to examine algebraic decision problems in detail. In the past, the Turing degrees have been used to analyze algebraic decision problems, but these form a coarse yardstick, so all computably enumerable degrees seem to contain all natural algebraic decision problems. Using computable reductions on equivalence relations, there should be a much more interesting structure emerging.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.

数理逻辑源于建立严格的数学基础的需要，通过形式语言的视角来研究数学对象的模型理论。集合论通过数学的基本公理以及这些公理如何暗示对象的存在来理解数学对象，该项目重点关注可计算性理论与其他两个逻辑子领域之间的联系。理论中，该项目涉及探索当两个数学对象在形式语言上看起来相同，但一个可以计算而另一个不能计算时的现象。在集合论中，有丰富的理论探索二维集合的复杂性。这些嵌入在并集和补集的基本集合论运算方面是可构造的，但该项目将探索一种类似的理论，人们认为嵌入是该项目涉及本科生和研究生的工作，一阶理论的可计算谱询问该理论的模型的哪些维度是可计算的，这一直是一个主要的开放问题。 70 年代，询问哪些集合可以是不可数强分类理论的可计算谱，重点是强最小理论。在这个项目中，目标是将问题从完全通用的框架简化为局部模块化。最小理论，在几何上是温和的，并且与群密切相关，从那里，希望能够给出关于哪些集合是谱的具体答案，该项目将研究等价关系的可计算约简。使用这种复杂性概念来详细研究代数决策问题 过去，图灵度已被用来分析代数决策问题，但这些形成了一个粗略的尺度，因此所有可计算可枚举度似乎都包含了所有。使用等价关系的可计算约简，应该会出现一个更有趣的结构。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。