Monadic Expansions, Borel Complexity, and Absoluteness in Model Theory

University Of Maryland, College Park, College Park MD

Investigators

Abstract

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.