CAREER: Advances in Comparing Complexity

假设我们得到了一组不同的数学对象。我们如何才能有效地比较它们的复杂性呢？目前解决这一问题的基础是在20世纪60年代随着超级大国建设的发展而建立的。粗略地说，超能力提供了一种根据一套连贯的条件放大原始物体的方法，称为超滤镜。不同的超滤产生不同的放大，但尽管如此，通过观察这种放大的范围和特征，在一些基本情况下是可能的，在更复杂的情况下推测是可能的，检测和分类结构的基本驱动因素。人们可以通过被称为“凯斯勒的订单”的预购来精确地描述这一点。凯斯勒序结构的一些重要而引人注目的特例是七十年代在模型理论的数学领域内提出的，对它的发展起到了非常重要的作用。长期以来，进一步研究的困难是双重的：一个足以检测和解释超滤器放大细节的数学理论还没有开发出来，而且人们对超滤器的结构知之甚少--也许它们之间的差异可能比已知的例子所显示的要大得多。该协会2009年的博士论文和早期论文重新打开了这一领域，加深了我们对超滤与理论相互作用的理解。在这些发展中，有一些与极值组合学中的一些现象的联系，例如斯杰梅雷迪著名的正则性引理。最近，Pi和Shelah的联合工作利用这种发展中的方法来比较复杂性，以解决不同数学领域的问题，例如一个关于连续统的基数不变量的60年前的问题，以及对正则性引理中存在的不规则对的刻画。因此，本项目的一个广泛目标是根据其可能的应用，加深我们对超滤检测和分类的复杂性的本质的理解，同时从模型理论分类理论解决相关问题，并努力解决关于凯斯勒序结构的某些基本问题。通过助学金、课程、暑期计划和访问的方式，该项目旨在包括来自PI机构的本科生和研究生，并支持具有一系列相关专业知识的访客。相关教育项目的一个组成部分将涉及培养有数学天赋的高中生。更详细地说，拟议的研究涉及一个大规模的模型理论分类计划，该计划建立了一个比较理论复杂性的框架，以及它与有限组合学、集合论和一般拓扑学中复杂性研究的新联系。在这一背景下，一个长期悬而未决的问题是确定凯斯勒1967年理论秩序的结构。回想一下，如果D是I上的正则超滤子，M，N是可数语言中的初等等价模型，我们得到M的D-超幂在不超过|I|的集合上实现所有类型当且仅当N的D-超幂实现。如果是这样的话，设T是结合理论，假设D饱和T.Keisler在可数理论上的(前)序，通常被认为是等价类上的偏序，设T小于或等于T‘，如果每个饱和T’的正则超滤子也饱和T。本课题的三个主要研究目的如下：第一种是在凯斯勒序的框架下研究简单不稳定理论的模型理论。二是建立了一类不简单但不具有强树性质SOP2的理论的结构理论的开端，并解决了超滤子构造的相关问题。第三是进一步发展与Szmeredi正则性和Ramsey理论的相互作用，并从应用的角度考察早期结果的有效性。

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.