Interactions between Computability Theory and Model Theory

可计算性理论与模型理论之间的相互作用

• 批准号: 1600228
• 负责人: Uri Andrews
• 金额: $ 25.6万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-08-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1600228&HistoricalAwards=false
• 关键词: Interactions; between; Computability; Theory; Model

While computability theory studies complexity of mathematical objects from a computational point of view, model theory studies complexity of mathematical objects from a structural point of view. This project aims to deepen understanding of the interactions between these two different notions of complexity. In general, one expects that the more structured an object is, the easier it is to compute information about it. This research project aims to elucidate how a mathematical object having an understandable theory relates to computability of facts about the object.In particular, this project works towards understanding certain problems in computable model theory: the spectrum of computable models question asks which sets of dimensions can arise as the dimensions of computable models of some uncountably categorical theory. The project will investigate distinguishing this problem based on the geometric nature of the theory, with the goal of advancing understanding in the cases where the theory satisfies the Zilber trichotomy. This project also aims to advance understanding of the degree spectra of theories. The degree spectrum of a theory measures how hard it is to compute any model of that theory. The investigator aims to develop a newer notion that will highlight connections between properties of the theory and the properties of the spectrum, providing a further link between computability and model theory. The project also investigates index sets of model theoretic notions; this is a computability-theoretic way to measure the complexity of a property. Knowing the exact complexity of a property aids in working with these properties in the most direct and efficient manner possible, thus spurring further research progress.

可计算性理论从计算的角度研究数学对象的复杂性，而模型理论从结构的角度研究数学对象的复杂性。该项目旨在加深对这两种不同的复杂性概念之间相互作用的理解。一般来说，人们期望对象的结构化程度越高，计算有关它的信息就越容易。该研究项目旨在阐明具有可理解理论的数学对象如何与该对象的事实的可计算性相关。特别是，该项目致力于理解可计算模型理论中的某些问题：可计算模型的频谱问题询问哪些维度集可以作为某些不可数分类理论的可计算模型的维度而出现。该项目将研究根据理论的几何性质来区分这个问题，目的是促进对理论满足 Zilber 三分法的情况的理解。该项目还旨在增进对理论度谱的理解。理论的度谱衡量计算该理论的任何模型的难度。研究人员的目标是开发一个新的概念，强调理论属性和谱属性之间的联系，提供可计算性和模型理论之间的进一步联系。该项目还研究了模型理论概念的索引集；这是一种衡量属性复杂性的可计算性理论方法。了解属性的确切复杂性有助于以最直接、最有效的方式处理这些属性，从而促进进一步的研究进展。