Abstract: We show that the analysis of Keisler's order can be localized to the study of \phi-types. Specifically, if D is a regular ultrafilter on \lambda \geq \aleph_0 such that \lcf(\omega, D) \geq \lambda^+ and M is a model whose theory is countable, then M^\lambda/D is \lambda^+-saturated iff it realizes all \phi-types over sets of size \lambda.
Abstract: This article introduces and develops the theory of characteristic sequences. For a first-order formula \phi(x;y) we introduce and study the characteristic sequence (P_n : n \in \omega) of hypergraphs defined by P_n(y1, . . . , yn) := \exists x (\bigwedge_{i\leq n} \phi(x;y) ). We show that combinatorial and classification theoretic properties of the characteristic sequence reflect classification theoretic properties of \phi and vice versa. The main results are a characterization of NIP and of simplicity in terms of persistence of configurations in the characteristic sequence. Specifically, we show that some tree properties are detected by the presence of certain combinatorial configurations in the characteristic sequence while other properties such as instability and the independence property manifest themselves in the persistence of complicated configurations under localization.
Abstract: The characteristic sequence of hypergraphs (P_n : n \in \omega) associated to a formula \phi(x; y), introduced in [5], is defined by P_n(y1, . . . yn) = \exists x (\bigwedge_{i\leq n} \phi(x;y_i)). We continue the study of characteristic sequences, showing that graph-theoretic techniques, notably Szemer\'edi's celebrated regularity lemma, can be naturally applied to the study of model-theoretic complexity via the characteristic sequence. Specifically, we relate classification-theoretic properties of \phi and of the P_n (considered as formulas) to density between components in Szemer\'edi-regular decompositions of graphs in the characteristic sequence. In addition, we use Szemer\'edi regularity to calibrate model-theoretic notions of independence by describing the depth of independence of a constellation of sets and showing that certain failures of depth imply Shelah's strong order property SOP3; this sheds light on the interplay of independence and order in unstable theories.
Abstract: Let T_1, T_2 be countable first-order theories, M_i a model of T_i, and D any regular ultrafilter on \lambda \geq \aleph_0. A longstanding open problem of Keisler asks when T2 is more complex than T1, as measured by the fact that for any such \lambda and D, M^\lambda/D realizes all types over sets of size at most \lambda. In this paper, building on the author's prior work [11] [12] [13], we show that the relative complexity of first-order theories in Keisler's sense is reflected in the relative graph-theoretic complexity of sequences of hypergraphs associated to formulas of the theory. After reviewing prior work on Keisler's order, we present the new construction in the context of ultrapowers, give various applications to the open question of the unstable classification, and investigate the interaction between theories and regularizing sets. Notably, we show that there is a minimum TP2 theory, and that maximality is implied by the density of certain graph edges (between components arising from Szemeredi-regular decompositions) remaining bounded away from 0 and 1. We also introduce and discuss flexible ultrafilters, a relevant class of regular ultrafilters which reflect the sensitivity of certain unstable (non low) theories to the sizes of regularizing sets, and prove that any ultrafilter which saturates the minimal TP2 theory is flexible.
Abstract: We consider the question, of longstanding interest, of realizing types in regular ultrapowers. In particular, this is a question about the interaction of ultrafilters and theories, which is both coarse and subtle. It suffices to consider types given by instances of a single formula. In this article, we analyze a class of formulas \phi whose associated characteristic sequence of hypergraphs can be seen as describing both realization of first- and second-order types in ultrapowers as well as properties of the corresponding ultrafilters. These formulas act, via the characteristic sequence, as points of contact with the ultrafilter D, in the sense that they translate structural properties of ultrafilters into model-theoretically meaningful properties and vice versa. Such formulas characterize saturation for various key theories (the theory of the random graph T_{rg}, the theory of a parametrized family of independent equivalence relations T_{feq}), yet their scope in the order \trianglelefteq does not extend beyond T_{feq}. The proof applies Shelah's classification of second-order quantifiers.
Abstract: We develop a framework in which Szemer\'edi's celebrated Regularity Lemma for graphs interacts with core model-theoretic ideas and techniques. Our work relies on a coincidence of ideas from model theory and graph theory: arbitrarily large half-graphs coincide with model-theoretic instability, so in their absence, structure theorems and technology from stability theory apply. In one direction, we address a problem from the classical Szemer\'edi theory. It was known that the 'irregular pairs' in the statement of Szemer\'edi's regularity lemma cannot be eliminated, due to the counterexample of half-graphs (i.e., the order property). We show that half-graphs are the only essential difficulty, by giving a much stronger version of Szemer\'edi's regularity lemma for stable graphs, in which there are no irregular pairs, the bounds are significantly improved, and each component satisfies an indivisibility condition. In the other direction, we take a more model-theoretic approach, and give several new Szemer\'edi-type partition theorems for graphs with the non-k_*-order property. The first theorem gives a partition of any stable graph into indiscernible components (i.e., each component is either a complete or an empty graph) whose interaction is strongly uniform. To prove this, we first give a finitary version of the classic model-theoretic fact that stable theories admit large sets of indiscernibles, by showing that in finite stable graphs one can extract much larger indiscernible sets than expected by Ramsey's theorem. The second and third theorems allow for a much smaller number of components at the cost of weakening the 'indivisibility' condition on the components. We also discuss some extensions to graphs without the independence property. All graphs are finite and all partitions are equitable, i.e. the sizes of the components differ by at most 1. In the last three theorems, the number of components depends on the size of the graph; in the first theorem quoted, this number is a function of \epsilon only, as in the usual Szemer\'edi regularity lemma.
Abstract: This paper contributes to the set-theoretic side of understanding Keisler's order. We consider properties of ultrafilters which affect saturation of unstable theories: the lower cofinality \lcf(\aleph_0, D) of \aleph_0 modulo D, saturation of the minimum unstable theory (the random graph), flexibility, goodness, goodness for equality, and realization of symmetric cuts. We work in ZFC except when noted, as several constructions appeal to complete ultrafilters thus assume a measurable cardinal. The main results are as follows. First, we investigate the strength of flexibility, known to be detected by non-low theories. Assuming \kappa > \aleph_0 is measurable, we construct a regular ultrafilter on \lambda \geq 2^\kappa which is flexible (thus: ok) but not good, and which moreover has large \lcf(\aleph_0) but does not even saturate models of the random graph. This implies (a) that flexibility alone cannot characterize saturation of any theory, however (b) by separating flexibility from goodness, we remove a main obstacle to proving non-low does not imply maximal, and (c) from a set-theoretic point of view, consistently, ok need not imply good, addressing a problem from Dow 1985. Under no additional assumptions, we prove that there is a loss of saturation in regular ultrapowers of unstable theories, and give a new proof that there is a loss of saturation in ultrapowers of non-simple theories. More precisely, for D regular on \kappa and M a model of an unstable theory, M^\kappa/D is not (2^\kappa)^+-saturated; and for M a model of a non-simple theory and \lambda = \lambda^{<\lambda}, M^\lambda/D is not \lambda^{++}-saturated. Finally, we investigate realization and omission of symmetric cuts, significant both because of the maximality of the strict order property in Keisler's order, and by recent work of the authors on SOP_2. We prove that if D is a \kappa-complete ultrafilter on \kappa, any ultrapower of a sufficiently saturated model of linear order will have no (\kappa, \kappa)-cuts, and that if \de is also normal, it will have a (\kappa^+, \kappa^+)-cut. We apply this to prove that for any n < \omega, assuming the existence of n measurable cardinals below \lambda, there is a regular ultrafilter D on \lambda such that any D-ultrapower of a model of linear order will have n alternations of cuts. Moreover, D will \lambda^+-saturate all stable theories but will not (2^{\kappa})^+-saturate any unstable theory, where \kappa is the smallest measurable cardinal used in the construction.
Abstract: Via two short proofs and three constructions, we show how to increase the model-theoretic precision of a widely used method for building ultrafilters. We begin by showing that any flexible regular ultrafilter makes the product of an unbounded sequence of finite cardinals large, and then prove directly that a ``bottleneck'' in the inductive construction of a regular ultrafilter on \lambda (i.e. a point after which all antichains of P(\lambda)/D have cardinality less than \lambda) essentially prevents any subsequent ultrafilter from being flexible, \emph{thus} from saturating any non-low theory. The constructions are as follows. First, we construct a regular filter D on \lambda so that any ultrafilter extending D fails to $\lambda^+$-saturate ultrapowers of the random graph, \emph{thus} of any unstable theory. The proof constructs the omitted random graph type directly. Second, assuming existence of a measurable cardinal $\kappa$, we construct a regular ultrafilter on $\lambda > \kappa$ which is $\lambda$-flexible but not $\kappa^{++}$-good, improving our previous answer to a question raised in Dow 1975. Third, assuming a weakly compact cardinal $\kappa$, we construct an ultrafilter to show that $\lcf(\aleph_0)$ may be small while all symmetric cuts of cofinality $\kappa$ are realized. Thus certain families of pre-cuts may be realized while still failing to saturate any unstable theory. Our methods advance the general problem of constructing ultrafilters whose ultrapowers have a precise degree of saturation.
Abstract: We give the first (ZFC) dividing line in Keisler's order among the unstable theories, specifically among the simple unstable theories. That is, for any infinite cardinal \lambda for which there is \mu < \lambda \leq 2^\mu, we construct a regular ultrafilter D on \lambda such that (i) for any model M of a stable theory or of the random graph, M^\lambda/D is \lambda^+-saturated but (ii) if Th(N) is not simple or not low then N^\lambda/D is not \lambda^+-saturated. The non-saturation result relies on the notion of flexible ultrafilters. To prove the saturation result we develop a property of a class of simple theories, called Qr1, generalizing the fact that whenever B is a set of parameters in some sufficiently saturated model of the random graph, |B| = \lambda and \mu < \lambda \leq 2^\mu, then there is a set A with |A| = \mu such that any nonalgebraic p \in S(B) is finitely realized in A. In addition to giving information about simple unstable theories, our proof reframes the problem of saturation of ultrapowers in several key ways. We give a new characterization of good filters in terms of ``excellence,'' a measure of the accuracy of the quotient Boolean algebra. We introduce and develop the notion of {moral} ultrafilters on Boolean algebras. We prove a so-called ``separation of variables'' result which shows how the problem of constructing ultrafilters to have a precise degree of saturation may be profitably separated into a more set-theoretic stage, building an excellent filter, followed by a more model-theoretic stage: building moral ultrafilters on the quotient Boolean algebra, a process which highlights the complexity of certain patterns, arising from first-order formulas, in certain Boolean algebras.
Abstract: Motivated by Keisler's order, a far-reaching program of understanding basic model-theoretic structure through the lens of regular ultrapowers, we prove that for a class of regular filters D on I, |I| = \lambda > \aleph_0, the fact that P(I)/D has little freedom (as measured by the fact that any maximal antichain is of size <\lambda, or even countable) does not prevent extending D to an ultrafilter D_1 on I which saturates ultrapowers of the random graph. "Saturates" means that M^I/D_1 is (\lambda^+)-saturated whenever M is a model of the random graph. This was known to be true for stable theories, and false for non-simple and non-low theories. This result and the techniques introduced in the proof have catalyzed the authors' subsequent work on Keisler's order for simple unstable theories. The introduction, which includes a part written for model theorists and a part written for set theorists, discusses our current program and related results.
Abstract: We connect and solve two longstanding open problems in quite different areas: the model-theoretic question of whether $SOP_2$ is maximal in Keisler's order, and the question from set theory/general topology of whether $\mathfrak{p} = \mathfrak{t}$, the oldest problem on cardinal invariants of the continuum. We do so by showing these problems can be translated into instances of a more fundamental problem which we state and solve completely, using model-theoretic methods.
Abstract: Cantor proved in 1874 that the continuum is uncountable, and Hilbert's first problem asks whether it is the smallest uncountable cardinal. A program arose to study cardinal invariants of the continuum, which measure the size of the continuum in various ways. By work of Godel and of Cohen, Hilbert's first problem is independent of ZFC (Zermelo-Fraenkel set theory with the axiom of choice). Much work both before and since has been done on inequalities between these cardinal invariants, but some basic questions have remained open despite Cohen's introduction of forcing. The oldest and perhaps most famous of these is whether ''\mathfrak{p} = \mathfrak{t}'' which was proved in a special case by Rothberger (1948), building on Hausdorff (1936). In this paper we explain how our work on the structure of Keisler's order, a large-scale classification problem in model theory, led to the solution of this problem in ZFC as well as of an a priori unrelated open question in model theory.
Abstract: In the first edition of Classification Theory, the second author characterized the stable theories in terms of saturation of ultrapowers. Prior to this theorem, stability had already been defined in terms of counting types, and the unstable formula theorem was known. A contribution of the ultrapower characterization was that it involved sorting out the global theory, and introducing nonforking, seminal for the development of stability theory. Prior to the present paper, there had been no such characterization of an unstable class. In the present paper, we first establish the existence of so-called optimal ultrafilters on Boolean algebras, which are to simple theories as Keisler's good ultrafilters are to all theories. Then, assuming a supercompact cardinal, we characterize the simple theories in terms of saturation of ultrapowers. To do so, we lay the groundwork for analyzing the global structure of simple theories, in ZFC, via complexity of certain amalgamation patterns. This brings into focus a fundamental complexity in simple unstable theories having no real analogue in stability.
Abstract: We apply the recently developed technology of cofinality spectrum problems to prove a range of theorems in model theory. First, we prove that any model of Peano arithmetic is lambda-saturated iff it has cofinality at least lambda and the underlying order has no (kappa, kappa)-cuts for regular kappa strictly less than lambda. Second, assuming instances of GCH, we prove that SOP2 characterizes maximality in the interpretability order trianglestar, settling a prior conjecture and proving that SOP2 is a real dividing line. Third, we establish the beginnings of a structure theory for NSOP2, proving that NSOP2 can be characterized by the existence of few inconsistent higher formulas. In the course of the paper, we show that \mathfrak{p}_s = \mathfrak{t}_s in any weak cofinality spectrum problem closed under exponentiation (naturally defined). We also prove that the local versions of these cardinals need not coincide, even in cofinality spectrum problems arising from Peano arithmetic.
Abstract: We prove a regularity lemma with respect to arbitrary Keisler measures mu on V, nu on W where the bipartite graph (V,W,R) is definable in a saturated structure M and the formula R(x,y) is stable. The proof is rather quick and uses local stability theory. The special case where (V,W,R) is pseudofinite, mu, nu are the counting measures and M is suitably chosen (for example a nonstandard model of set theory), yields the Malliaris-Shelah stable regularity lemma though without explicit bounds or equitability.
Abstract: We prove, in ZFC, that there is an infinite strictly descending chain of classes of theories in Keisler's order. Thus Keisler's order is infinite and not a well order. Moreover, this chain occurs within the simple unstable theories, considered model-theoretically tame. Keisler's order is a central notion of the model theory of the 60s and 70s which compares first-order theories (and implicitly ultrafilters) according to saturation of ultrapowers. Prior to this paper, it was long thought to have finitely many classes, linearly ordered. The model-theoretic complexity we find is witnessed by a very natural class of theories, the n-free k-hypergraphs studied by Hrushovski. This complexity reflects the difficulty of amalgamation and appears orthogonal to forking.
Abstract: We discuss a range of open problems at the intersection of set theory, model theory, and general topology, mainly around the construction of ultrafilters. Along the way we prove uniqueness for a weak notion of cut.
Abstract: Our investigations are framed by two overlapping problems: finding the right axiomatic framework for so-called cofinality spectrum problems, and a 1985 question of Dow on the conjecturally nonempty (in ZFC) region of OK but not good ultrafilters. We define the lower-cofinality spectrum for a regular ultrafilter \de on \lambda and show that this spectrum may consist of a strict initial segment of cardinals below \lambda and also that it may finitely alternate. We define so-called `automorphic ultrafilters' and prove that the ultrafilters which are automorphic for some, equivalently every, unstable theory are precisely the good ultrafilters. We axiomatize a bare-bones framework called ''lower cofinality spectrum problems'', consisting essentially of a single tree projecting onto two linear orders. We prove existence of a lower cofinality function in this context and show by example that it holds of certain theories whose model theoretic complexity is bounded.
Abstract: Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subgraphs. In the present paper we reprove their theorem using many of the same ideas, but with the key model-theoretic ingredient of first determining the so-called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds and offers a different structural perspective on the graphs in question. Complementing this, we give an infinitary proof which implies the finite result.
Abstract: Mainly expository paper discussing two open problems, written for a commemoration of the Godel prize fellowships. (Available on request)
Abstract: These notes are based on Appalachian Set Theory lectures given by M. Malliaris on November 5, 2016 with D. Casey as the official scribe. The aim of the lectures was to present the setup and some key arguments of "Cofinality spectrum problems in model theory, set theory and general topology" by Malliaris and Shelah. This provides a sketch of the proof that p=t and that SOP2 theories are maximal in Keisler's order.
Abstract: We investigate the interpretability ordering $\trianglelefteq^*$ using generalized Ehrenfeucht-Mostowski models. This gives a new approach to proving inequalities and investigating the structure of types.
Abstract: The article motivates saturation of ultrapowers from a general mathematical point of view.
Abstract: We construct a countable simple theory which, in Keisler's order, is strictly above the random graph and also in some sense orthogonal to the building blocks of the recently discovered infinite descending chain. As a result we prove in ZFC that there are incomparable classes in Keisler's order.
Abstract: We show that every approximately differentially private learning algorithm (possibly improper) for a class H with Littlestone dimension~d requires Ω(log*(d)) examples. As a corollary it follows that the class of thresholds over N can not be learned in a private manner; this resolves open question due to [Bun et al., 2015, Feldman and Xiao, 2015]. We leave as an open question whether every class with a finite Littlestone dimension can be learned by an approximately differentially private algorithm.
Abstract: This paper builds model-theoretic tools to detect changes in complexity among the simple theories. We develop a generalization of dividing, called shearing, which depends on a so-called context c. This leads to defining c-superstability, a syntactical notion, which includes supersimplicity as a special case. We prove a separation theorem showing that for any countable context c and any two theories T1, T2 such that T1 is c-superstable and T2 is c-unsuperstable, and for arbitrarily large mu, it is possible to build models of any theory interpreting both T1 and T2 whose restriction to the language of T1 is mu-saturated and whose restriction to the language of T2 is not (aleph_1)-saturated. (This suggests "c-superstable" is really a dividing line.) The proof uses generalized Ehrenfeucht-Mostowski models, and along the way, we clarify the use of these techniques to realize certain types while omitting others. In some sense, shearing allows us to study the interaction of complexity coming from the usual notion of dividing in simple theories and the more combinatorial complexity detected by the general definition. This work is inspired by our recent progress on Keisler's order, but does not use ultrafilters, rather aiming to build up the internal model theory of these classes.
Abstract: Solving a decades-old problem we show that Keisler's 1967 order on theories has the maximum number of classes. The theories we build are simple unstable with no nontrivial forking, and reflect growth rates of sequences which may be thought of as densities of certain regular pairs, in the sense of Szemerédi's regularity lemma. The proof involves ideas from model theory, set theory, and finite combinatorics.
.
| space |