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 NIP，则该类是野生的，例如，C中未标记结构的增长率是超指数的，并且对于某个整数n，类不是n-wqo。 潜在的规范斯科特句子已被证明是一个有用的工具，在确定可数结构的不变类的博雷尔复杂性和研究打算简化这些方法，探索厚度和类的模型。该项目旨在计算每个互代数理论的Borel复杂度。 具有非极大不可数谱的理论是可分类的。最近关于素模型存在性的技术结果使得解决Vaught猜想对于可分类理论和可能对于超稳定理论来说都是容易的。在一阶逻辑中，理论的aleph 1-范畴性是一个绝对的概念，这可以从Baldwin-Lachlan对aleph 1-范畴性的刻画中看出。PI的目的是确定是否可以找到一个类似的表征aleph 1-范畴的句子L（ω 1，ω），或等价的类原子模型。具体来说，该项目旨在确定aleph 1-categoricity是否是绝对的原子模型类。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.