Monadic Expansions, Borel Complexity, and Absoluteness in Model Theory

这个研究项目属于模型论，是数理逻辑的一个分支。模型理论的大部分内容都是关于一个理论如何控制它的模型类，它只是一种形式语言中的一组句子。PI先前已经研究了一个理论在其模型中允许或禁止某些组合构型的机制；本项目在几个背景下继续这些调查。在某些情况下，这项研究与计算学习理论融合得很好。例如，如果一个理论禁止独立性，那么在该理论模型中产生的所有概念，即可定义集，都符合可能近似正确（PAC）的学习框架。本项目将为本科生和研究生提供研究训练机会。更详细地说，PI已经注意到有限结构的遗传类C的复杂性与无限模型Th(C)的一元展开之间的紧密联系。有一个层次结构的分界线，如单一的NFCP、单一的稳定性和单一的NIP。与Braunfeld合作，PI具有Th(C)为单根NIP的模型的多个特征。项目预计将显示,如果一些模型Th (C)不是monadically夹,然后类是野生的,例如,增长率未标记的结构C是superexponetial类并不是n-wqo整数n。潜在的规范斯科特句子已被证明是一个有用的工具在决定波莱尔不变类可数结构的复杂性和研究打算简化这些方法的探索的厚度和groundedness类模型。该项目旨在计算每个互代数理论的Borel复杂度。具有非极大不可数谱的理论是可分类的。最近关于素数模型存在性的技术成果，使得对可分类理论和可能对超稳定理论解决沃特猜想变得容易。在一阶逻辑中，理论的alph1 -categoricity是一个绝对概念，这可以从Baldwin-Lachlan对alph1 -categoricity的刻画中看出。PI的目的是确定是否可以在L（ω, ω）的句子的α - 1类别中找到类似的特征，或者等效地用于原子模型类。具体地说，该项目打算确定对于原子模型的类来说，alpha1 -categoricity是否是绝对的。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This research project is in model theory, which is a branch of mathematical logic. Much of model theory concerns the ways in which a theory, which is simply a set of sentences in a formal language, controls its class of models. The PI has previously investigated on mechanisms by which a theory can either admit or forbid certain combinatorial configurations in its models; this project continues these investigations in several contexts. In some cases, this investigation melds well with computational learning theory. As one example, if a theory forbids the independence property, then all the concepts i.e., definable sets, arising in the models of the theory conform to the probably approximately correct (PAC) learning framework. This project will provide research training opportunities for undergraduate and graduate students.In more detail, the PI has noted a strong connection between the complexity of hereditary classes C of finite structures and monadic expansions of infinite models of Th(C). There is a hierarchy of dividing lines, such as monadic NFCP, monadic stability, and monadic NIP. Working with Braunfeld, the PI has multiple characterizations of a model of Th(C) being monadically NIP. The project expects to show that if some model of Th(C) is not monadically NIP, then the class is wild, e.g., the growth rate of unlabelled structures in C is superexponetial and the class is not n-wqo for some integer n. Potential canonical Scott sentences have proved to be a useful tool in determining the Borel complexity of invariant classes of countable structures and the research intends to streamline these methods by exploring thickness and groundedness of classes of models. The project aims to compute the Borel complexity of every mutually algebraic theory. Theories with non-maximal uncountable spectrum are classifiable. Recent technical results about the existence of prime models make it tractable to settle Vaught's conjecture for classifiable theories and possibly for superstable theories as well. In first order logic, aleph1-categoricity of a theory is an absolute notion, as can be seen by the Baldwin-Lachlan characterization of aleph1-categoricity. The PI aims to determine whether a similar characterization can be found for aleph1-categoricity of sentences of L(omega1, omega), or equivalently for classes of atomic models. Specifically, the project intends to determine whether aleph1-categoricity is absolute for classes of atomic models.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.