Suppose we are given a collection of diverse mathematical objects. How might we compare their complexity in a productive way? The foundations of the present approach to this question were built in the 1960s with the development of the ultrapower construction. Roughly speaking, ultrapowers give a way of amplifying the original object in accordance with a coherent set of conditions, called an ultrafilter. Different ultrafilters produce different amplifications, but nonetheless by observing the range and characteristics of such amplifications it is in a few fundamental cases possible, and in more complex cases conjecturally possible, to detect and classify the basic drivers of structure. One can make this description precise via a pre-order known as "Keisler's order. Some important and striking special cases of the structure of Keisler's order were worked out in the seventies within the mathematical field of model theory and were very productive for its development. The difficulty in going further had long been double: a mathematical theory sufficient to detect and explain the details of the amplification by ultrafilters had not been developed, and little was known about the construction of ultrafilters - perhaps they may vary much more than the known examples suggest. The PI's 2009 PhD thesis and early papers re-opened this area, developing our understanding of the interaction of ultrafilters and theories. Among these developments were connections to some phenomena in extremal combinatorics, such as Szemeredi's celebrated regularity lemma. Recently, joint work of the PI and Shelah has leveraged this developing approach to the comparison of complexity to solve problems in diverse areas of mathematics, such as a sixty-year-old question about cardinal invariants of the continuum and a characterization of the existence of irregular pairs in the regularity lemma. A broad aim of the present project is therefore to develop our understanding of the nature of the complexity which ultrafilters detect and classify, in light of its possible applications, while addressing related problems from model theoretic classification theory and working to settle certain basic questions about the structure of Keisler's order. By means of assistantships, courses, summer programs, and visits, the project aims to include both undergraduates and graduate students from within the PI's institution and to support visitors with a range of relevant expertise. A component of the associated education project will involve training mathematically talented high school students.

In more detail, the proposed research concerns a large-scale classification program in model theory, which builds a framework for comparing the complexity of theories, and its emerging connections to the study of complexity in finite combinatorics, set theory, and general topology. A longstanding open problem in this context is the problem of determining the structure of Keisler's 1967 order on theories. Recall that if D is a regular ultrafilter on I, and M, N are elementarily equivalent models in a countable language, we have that the D-ultrapower of M realizes all types over sets of size no more than |I| iff the D-ultrapower of N does. If so, let T be the associated theory, and let us say that D saturates T. Keisler's (pre-)order on countable theories, often considered as a partial order on the equivalence classes, sets T less than or equal to T' if every regular ultrafilter which saturates T' also saturates T. Three main research aims of the present project are the following. The first is to investigate the model theory of simple unstable theories via the framework of Keisler's order. The second is to build the beginnings of a structure theory for the class of theories which are not simple but do not have the strong tree property SOP2, those conjecturally not maximal in Keisler's order, and to address related questions of ultrafilter construction. The third is to develop further the interactions with Szemeredi regularity and Ramsey theory and to investigate the effectiveness of earlier results with a view towards applications.

National Science Foundation (NSF)
Division of Mathematical Sciences (DMS)
Application #
Program Officer
Tomek Bartoszynski
Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
University of Chicago
United States
Zip Code