There is a Turing functional $\Phi $ taking $A^\prime $ to a theory $T_A$ whose complexity is exactly that of the jump of A, and which has the property that $A \leq _T B$ if and only if $T_A \trianglelefteq T_B$ in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.

We show that the analysis of Keisler’s order can be localized to the study of φ-types. Specifically, if is a regular ultrafilter on λ such that and M is a model whose theory is countable, then is λ+-saturated iff it realizes all φ-types of size λ.

Let T 1 , T 2 be countable first-order theories, M i ⊨ T i , and ������ any regular ultrafilter on λ ≥ $\aleph_{0}$ . A longstanding open problem of Keisler asks when T 2 is more complex than T 1 , as measured by the fact that for any such λ, ������, if the ultrapower (M 2 ) λ /������ realizes all types over sets of size ≤ λ, then so must the ultrapower (M 1 ) λ /������. (...) In this paper, building on the author's prior work [12] [13] [14], 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. We show that there is a minimum unstable theory, a minimum TP 2 theory, and that maximality is implied by the density of certain graph edges (between components arising from Szemerédi-regular decompositions) remaining bounded away from 0, 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 TP 2 theory is flexible. (shrink)

For a first-order formula φ(x; y) we introduce and study the characteristic sequence ⟨P n : n < ω⟩ of hypergraphs defined by P n (y₁…., y n ):= $(\exists x)\bigwedge _{i\leq n}\varphi (x;y_{i})$ . We show that combinatorial and classification theoretic properties of the characteristic sequence reflect classification theoretic properties of φ 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. (shrink)

The characteristic sequence of hypergraphs Pn:n<ω associated to a formula φ, introduced in Malliaris [5], is defined by Pn=i≤nφ. We continue the study of characteristic sequences, showing that graph-theoretic techniques, notably Szemerédi’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 φ and of the Pn to density between components in Szemerédi-regular decompositions of graphs in the characteristic sequence. In addition, we use Szemerédi 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. (shrink)

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. By our prior work it suffices to consider types given by instances of a single formula. In this article, we analyze a class of formulas φ whose associated characteristic sequence of hypergraphs can be seen as describing realization of first- and second-order types in ultrapowers on one hand, and (...) properties of the corresponding ultrafilters on the other. 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 , yet their scope in Keisler’s order does not extend beyond Tfeq. The proof applies Shelah’s classification of second-order quantifiers. (shrink)

This is a short expository account of the regularity lemma for stable graphs proved by the authors, with some comments on the model theoretic context, written for a general logical audience.

In The Global Financial Crisis, contributors argue that the complexity of the Global Financial Crisis challenges researchers to offer more comprehensive explanations by extending the scope and range of their traditional investigations.

We explore Shelah's model‐theoretic dividing line methodology. In particular, we discuss how problems in model theory motivated new techniques in model theory, for example classifying theories by their potential (consistently with Zermelo–Fraenkel set theory with the axiom of choice (ZFC)) spectrum of cardinals in which there is a universal model. Two other examples are the study (with Malliaris) of the Keisler order leading to a new ZFC result on cardinal invariants and attempts to clarify the “main gap” by reducing (...) the dependence of certain versions on (highly independent) cardinal arithmetic. (shrink)

We set up a general context in which one can prove Sauer-Shelah type lemmas. We apply our general results to answer a question of Bhaskar [1] and give a slight improvement to a result of Malliaris and Terry [7]. We also prove a new Sauer-Shelah type lemma in the context of op-rank, a notion of Guingona and Hill [4].

In this paper, we provide a new characterization of Keisler’s order in terms of saturation of Boolean ultrapowers. To do so, we apply and expand the framework of ‘separation of variables’ recently developed by Malliaris and Shelah. We also show that good ultrafilters on Boolean algebras are precisely the ones which capture the maximum class in Keisler’s order, answering a question posed by Benda in 1974.