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的法定任务，并使用基金会的知识分子优点和更广泛的审查标准来评估值得获得支持。