CAREER: Advances in Comparing Complexity

假设我们有一组不同的数学对象。我们怎样才能比较它们的复杂性呢？目前对这一问题的研究方法的基础是在20世纪60年代随着超级大国结构的发展而建立的。粗略地说，超能力提供了一种根据一组连贯的条件来放大原始对象的方法，称为超滤波器。不同的超滤波器产生不同的放大，但尽管如此，通过观察这种放大的范围和特性，在一些基本情况下是可能的，在更复杂的情况下，检测和分类结构的基本驱动因素是可能的。人们可以通过一个被称为“凯斯勒顺序”的前顺序来精确地描述这种情况。一些重要的和惊人的特殊情况下的结构凯斯勒的秩序制定了在七十年代的数学领域内的模型理论和非常富有成效的发展。长期以来，进一步研究的困难是双重的：一个足以检测和解释超滤器放大细节的数学理论还没有发展出来，而且人们对超滤器的构造知之甚少--也许它们的变化比已知的例子所暗示的要大得多。 PI的2009年博士论文和早期论文重新打开了这一领域，发展了我们对超滤器和理论相互作用的理解。这些发展与极值组合学中的一些现象有关，例如Szemeredi著名的正则性引理。最近，PI和Shelah的联合工作利用这种发展中的方法来比较复杂性，以解决数学不同领域的问题，例如60年前关于连续统基数不变量的问题以及正则引理中不规则对存在的表征。 因此，本项目的一个广泛的目的是发展我们的理解的性质的复杂性，超滤波器检测和分类，根据其可能的应用，同时解决相关问题的模型理论分类理论和工作，以解决某些基本问题的结构Keisler的顺序。通过助学金、课程、暑期项目和访问，该项目旨在包括PI机构内的本科生和研究生，并为访问者提供一系列相关专业知识。相关教育项目的一个组成部分将涉及培养数学天才的高中生。更详细地说，拟议的研究涉及模型论中的大规模分类程序，该程序构建了一个框架，用于比较理论的复杂性，以及其与有限组合学、集合论和一般拓扑学中复杂性研究的新兴联系。 一个长期存在的开放性问题在这方面是问题的决定结构凯斯勒1967年秩序的理论。回想一下，如果D是I上的正则超滤子，并且M，N是可数语言中的初等等价模型，则M的D-超幂实现大小不超过|我|当且仅当N的D-超幂成立。如果是这样，设T是伴随理论，并且我们说D饱和T。Keisler的（前）顺序可数理论，往往被认为是一个偏序的等价类，设置T小于或等于T'，如果每一个经常超滤饱和T'也饱和T。本项目的三个主要研究目标如下。 第一个是通过Keisler阶的框架研究简单不稳定理论的模型理论。第二个是为一类不简单但不具有强树性质SOP 2的理论建立结构理论的开端，这些理论在Keisler阶中不是最大的，并解决超滤子构造的相关问题。第三是进一步发展与Szemeredi正则性和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.