1 Introduction↩︎

The motivation for this paper is to amalgamate two distinct generalizations of the classic Ramsey’s Theorem. Ramsey’s Theorem [1] says that, fixing finite \(n\) and \(c\) in advance, one can find large, finite homogeneous subsets for colorings of \(n\)-sized sets with \(c\) colors, as long as the set originally colored was big enough. In the well-known arrow notation¹, this can be stated as follows.

There are two ways for this to be generalized. The first generalization is to coloring other classes of structures. An important observation is that coloring subsets of a given set is the same as coloring increasing tuples of that length according to some fixed linear order, so Ramsey’s Theorem can be seen as a result about coloring linear orders and finding homogeneous copies of linear orders within it. A Ramsey class \(\mathcal{K}_0\) is a class of finite structures where a variant of Ramsey’s Theorem holds: given finite \(k < \omega\) and \(A, B \in \mathcal{K}_0\), there is some \(C \in \mathcal{K}_0\) such that any coloring of the copies of \(B\) appearing in \(C\) by \(k\) colors gives rise to a copy of \(A\) in \(C\) that is homogeneous for this coloring. This is written as \[C \xrightarrow{} (A)^B_k\] Independently, Nešetřil and Rödl [3] and Abramson and Harrington [4] showed that the class of finite, linearly ordered \(\tau\)-structures is a Ramsey class when \(\tau\) is a finite relational language. Since then the theory of Ramsey classes has become a productive area connecting combinatorics, dynamics, and model theory (the connection to model theory is partially explained below; a nice survey on Ramsey classes is Bodirsky [5]).

The second generalization is to remove the restriction ‘finite’ in the statement of Ramsey’s Theorem. Allowing the arity of the coloring (the upper exponent in the arrow relation) to be infinite would make positive results contradict the axiom of choice (see [6]), so we focus on finite arity colorings. Ramsey’s Theorem can be easily generalized to \(\omega \xrightarrow{} (\omega)^n_c\) for all finite \(n, c\). Moving to infinitely many colors and uncountable homogeneous sets, Erdős and Rado [7] proved the following (and, unlike most bounds in finite Ramsey theory, the left-hand cardinal is known to be optimal).

This has been generalized in many directions, including unbalanced and polarized partition relations. Excellent surveys can be found in Erdős, Hajnal, Máté, and Rado [6] and Hajnal and Larson [2].

We give a general framework for generalizations of the Erdős-Rado Theorem along the lines of Ramsey classes, appropriately called combinatorial Erdős-Rado classes (Definition 11, see later in this introduction for a discussion of Erdős-Rado classes). Roughly, a class \(\mathcal{K}\) is a combinatorial Erdős-Rado class if it satisfies enough instances of \(\lambda \xrightarrow{\mathcal{K}} (\kappa)^n_\kappa\), where this means any coloring of \(n\)-tuples from any \(\lambda\)-big structure in \(\mathcal{K}\) with \(\kappa\)-many colors has a homogeneous substructure that is \(\kappa\)-big (Section 3 makes these notions of ‘big’ and ‘homogeneous’ precise). Note that we require that all \(n\)-tuples are colored, rather than coloring copies of a single structure as in Ramsey classes. Many partition relations of this sort (positive and negative) already exist in the literature, and we collect the most relevant and place them in this framework in Section 3.1.

Our main interest in these results comes from model theory, specifically building generalized indiscernibles in nonelementary classes. An (order) indiscernible sequence indexed by a linear order \(I\) is a sequence \(\{\boldsymbol{a}_i : i \in I\}\) in a structure \(M\) where the information (specifically, the type) about the elements \(\boldsymbol{a}_{i_1}, \dots, \boldsymbol{a}_{i_n}\) computed in the structure \(M\) only depends on the ordering of the indices \(i_1, \dots, i_n\). Generalized indiscernibles replace the linear orders with some other index class: trees, functions spaces, etc. Generalized indiscernibles (and the related notion of generalized blueprints) appear in Shelah [8], and we recount the definitions in Section 2.

In elementary classes (those axiomatizable in first-order logic), indiscernibles exist because of Ramsey’s Theorem and compactness. Moving to more complicated index classes \(\mathcal{K}\), the combinatorics necessary to build generalized indiscernibles from \(\mathcal{K}\) are exactly the same as requiring that \(\mathcal{K}\) be the directed colimits of a Ramsey class \(\mathcal{K}_0\) (see [9]). In both of these constructions, restriction to finite structures is sufficient to build indiscernibles because the compactness theorem reduces satisfiability to satisfiability of finite sets.

The study of nonelementary classes typically focuses on those axiomatizable in nice logics beyond first-order and, slightly more broadly, on Abstract Elementary Classes. Abstract Elementary Classes (introduced by Shelah [10]) give an axiomatic framework for a class of structures \(\mathbb{K}\) and a strong substructure notion \(\prec_\mathbb{K}\) meant to encompass a wide variety of nonelementary classes. A key feature of nonelementary classes is that they lack the structure that the compactness theorem endows on elementary classes. Indeed, Lindström’s Theorem [11] says that no logic stronger than first-order can satisfy the classical (countable) compactness theorem and the downward Löwenheim-Skolem property. In practice, stronger logics tend to fail compactness (the cofinality quantifier logics \(\mathbb{L}(Q^{\text{cof }}_\alpha)\) are a notable exception [12], [13]). Thus, different methods are necessary to build indiscernibles in Abstract Elementary Classes.

For order indiscernibles, this method comes by way of Morley’s Omitting Types Theorem [14] using the Erdős-Rado Theorem mentioned above (an exposition appears in [15]). For generalized indiscernibles, the generalization of the Erdős-Rado Theorem to combinatorial Erdős-Rado classes described above gives the desired tools. We call \(\mathcal{K}\) an Erdős-Rado class if we can build \(\mathcal{K}\)-indiscernibles in any Abstract Elementary Class (Definition 20 and Theorem 2). Generalized indiscernibles have occasionally seen use in nonelementary classses (for instance, [16], [17], [18]).

The use of structural partition relations allows us to present a unified framework for generating generalized indiscernibles in nonelementary classes. This allows us to generalize Morley’s result as Generalized Morley’s Omitting Types Theorem 1. There is also some work in this direction in Shelah [19], and we compare them in Remark 25.

We also make explicit category theoretic formulations of (generalized) Ehrenfeucht-Mostowski models and indiscernible collapse. This is motivated by a statement of Morley’s Omitting Types Theorem by Makkai and Paré in their work on accessible categories [20]. Essentially, generalized blueprints correspond to nice functors, and we prove a converse to this as well (Theorem 5).

We would like to thank Sebastian Vasey, Lynn Scow, and a very thorough referee for comments on initial drafts. We thank Saharon Shelah for pointing out the argument for Proposition 17, although he suggests it is well-known.

1.1 Outline↩︎

Section 2 gives the necessary preliminaries on abstract classes of structures, types, and generalized indiscernibles and blueprints. We also include a description in Section 2.3 of the examples we will consider in this paper. Section 3 gives the definition of combinatorial Erdős-Rado classes and of the structural partition relation that defines them. Section 3.1 gives several known (and a few new) examples and counterexamples of these classses. Section 4 defines Erdős-Rado classes and proves the main link between the two notions, Generalized Morley’s Omitting Types Theorem 1. Section 5 describes several extensions and partial converses to this result, including the category theoretic perspective on blueprints. Section 6 gives three applications of this technology: stability spectra of tame AECs, indiscernible collapse in nonelementary classes, and the interpretability order.

Note that the definition of Erdős-Rado classes (Definition 20) does not actually depend on that of combinatorial Erdős-Rado classes (Definition 11) or any of Section 3. However, we give the combinatorial definitions first, as they provide the largest class of examples of Erdős-Rado classes.

1.2 Conventions↩︎

Throughout the paper, we deal with different classes of structures, normally referred to by \(K\) in some font with some decoration. To aid the reader, we observe the following convention:

• the script or calligraphic \(K\)–typeset as \(\mathcal{K}\)–will be used as the domain or index class that we wish to build generalized indiscernibles from. They typically have few assumptions of model-theoretic structure on them. Erdős-Rado classes will be of this type, and the class of linear orders form the prototypical example.

• the bold \(K\)–typeset as \(\mathbb{K}\)–will be used as the target class that we wish to build generalized indiscernibles in. They will typically be well-structured in some model-theoretic sense. Elementary classes and Abstract Elementary Classes form the prototypical examples.

We also observe two important conventions with respect to types that might be missed by the model-theoretically inclined reader that skips the Preliminaries Section (see Definition 4):

1. Since we never deal with types over some parameter set², we omit the domain of types throughout. For example, we write \(tp_{\mathcal{K}}(\boldsymbol{a}; I)\) for the \(\mathcal{K}\)-type of \(\boldsymbol{a}\) over the empty set computed in \(I\), rather than \(tp_{\mathcal{K}}(\boldsymbol{a}/\emptyset; I)\); and

2. \(\mathbb{K}^\tau\) is the class of all \(\tau\)-structures with \(\tau\)-substructure \(\subseteq_\tau\) as the strong substructure relation. In particular, \(tp_\tau\) is the type in this class, which turns out to be quantifier-free type (Proposition 5).

Note that Sections 5.3 and 6.1 require more knowledge about Abstract Elementary Classes. This can be found in, e.g., Baldwin [15].

2 Preliminaries↩︎

2.1 Classes of structures and types↩︎

We want to have a very general framework for classes of structures in a common language along with a distinguished substructure relation. Although much more general than we need, we can use the notion of an abstract class (this formalization is originally due to Grossberg). Additionally, we expect our Erdős-Rado classes to have orderings (similar to, e.g., [5] for Ramsey classes), so we introduce the notion of an ordered abstract class. An alternative would be to consider equivalence classes of types in the Stone space after modding out by permutation of the indices, but requiring an ordering seems simpler.

Note that the examples presented tend to be universal classes (and mostly relational), in which case the type is determined by the quantifier-free type in \(\mathbb{L}_{\omega, \omega}\). However, we offer a more general framework because it adds little technical difficulty and offers the possibility to wider applicability. For instance, well-founded trees (Example 7, 18) are not a universal class.

We will also use the types of elements. Most of the classes we consider will not be elementary (either in axiomatization of \(\mathcal{K}\) or ordering \(\leq_\mathcal{K}\)), so syntactic types give way to semantic notions. Specifically, we use the notion of Galois types (also called semantic or orbital types) used in the study of Abstract Elementary Classes (and originated in [21]). However, in most cases, this will be the same as quantifier-free types. Note that we typically drop any adjective and use ‘type’ or sometimes ‘\(\mathcal{K}\)-type’ to refer to the following semantic definition, although we will decorate the symbol with the ambient class. Although we use the ‘index class’ notation \(\mathcal{K}\) throughout Definition 4, we will use these ideas for both index classes and target classes.

Understanding this notation is key to the rest of the paper, so we unravel these notions in some examples.

First, consider \(\mathbb{K}^\tau\). \(\mathbb{K}^\tau\)-embeddings are injections that preserve and reflect the \(\tau\)-structure. Then \(\text{S}_\tau\) refers to all \(\mathbb{K}^\tau\)-types in this class, and these types turn out to be exactly quantifier-free types in the language.

Note that although we say ‘\(\mathbb{K}^\tau\)-types are quantifier-free types’, the statement \[tp_\tau\left(\boldsymbol{a}; M\right) = tp_{qf}\left(\boldsymbol{a};M\right)\] is technically false: the left-hand side is a (rank-initial subset of) equivalence class of pairs, while the right hand side is a \(|\tau|+\aleph_0\)-sized collection of quantifier-free formulas.

Proof: The second item is well-known and can be proved in many ways. One way is to take \(M_0\subseteq M_1, M_2\) and freely generate the \(\tau\)-structure on \(M_1 \cup M_2\) by closing under functions and adding no relations; this even proves a disjoint version of amalgamation. The second item is proved similarly after first identifying \(\boldsymbol{a}_0\) and \(\boldsymbol{a}_1\) in the union; this is possible exactly because they share the same quantifier-free type.
Note that \(\mathbb{K}^\tau\) might fail to have the joint embedding property. In fact, this property is equivalent to \(\mathbb{K}^\tau\) having a unique \(0\)-type, and is satisfied whenever \(\mathbb{K}^\tau\) has no constants (or \(0\)-ary functions).

As a second example, consider the class \(\mathcal{K}^{2-or}\) (which will be used in Example 1). This is defined more generally in Example 3, but this case consists two disjoint linear orders \((I_0, I_1)\) where everything in \(I_0\) is less than everything in \(I_1\). Then \(\text{S}_{2-or}\) is the collection of all \(\mathbb{K}^{2-or}\)-types. In particular, an increasing tuple \(\boldsymbol{a}\) from a model \((I_0, I_1)\) in \(\mathbb{K}^{2-or}\) can be written as \(\boldsymbol{a}_0, \boldsymbol{a}_1\) where each \(\boldsymbol{a}_\ell\) is an increasing tuple (possibly empty) from \(I_\ell\). A proof similar to (and simpler than) Proposition 5 shows that \(\mathbb{K}^{2-or}\)-types are also quantifier free types. Thus, an element \(p \in \text{S}^{inc, n}_{2-or}\) is determined by some number \(k\leq n\) that indicates that the tuple is an increasing \(k\)-tuple from the first linear order, followed by an increasing \((n-k)\)-tuple from the second part.

A similar statement is true for \(\mathcal{K}^{\chi-or}\), although a type \(p \in \text{S}^{inc, n}_{\chi-or}\) is determined by a partition of \(n\) into \(\chi\)-many pieces, most of which are empty when \(\chi\) is infinite.

2.2 Generalized indiscernibles and blueprints↩︎

The following generalizes the normal theory of blueprints and Ehrenfeucht-Mostowski models begun in [23]. These generalized notions appear in [8].

Being proper for \(\mathcal{K}\) is the same as being proper for \((\mathcal{K}, \mathbb{K}^{\tau(\Phi)})\). Note that if \(\Phi \in \Upsilon^{\mathcal{K}}[\mathbb{K}]\), then the blueprint \(\Phi\) actually maps \(\text{S}^{inc}_{\mathcal{K}} \to S_\mathbb{K}\). An observant reader might complain that the description in Definition 1.([genem-item]) uniquely describes a model, but is short on proving it’s existence. However, the existence of such a model follows from standard arguments about EM models, see, e.g., [24]. Our formalism has \(I\) be the generating set for \(EM(I, \Phi)\) (and later indiscernibles), rather than passing to a skeleton.

From a category-theoretic perspective, a blueprint \(\Phi \in \Upsilon^{\mathcal{K}}[\mathbb{K}]\) induces a functor \(\Phi:\mathcal{K}\to \mathbb{K}\) that is faithful, preserves direceted colimits, and induces a natural transformation between the ‘underlying set’ functor of each concrete category. We return to this perspective in Section 5.2 and derive a converse Theorem 3 of the Generalized Morley’s Omitting Types Theorem 1.

Using generalized blueprints, we can build models with generalized indiscernibles (see Theorem 2 for this in action).

An important fact to keep in mind is that, in nonelementary classes, not every collection of indiscernibles can be turned into a blueprint; [15] provides such an example. This is in contrast to first-order, where every infinite set of indiscernibles can be stretched (see [25]).

2.3 Our examples↩︎

There will be several examples that we will develop here and in Section 3.1. Here, we define the relevant classes and note the syntactic characterization of their types (normally quantifier-free). Section 3.1 explains how these classes fit within the framework of Erdős-Rado classes. In each case, the strong substructure relation is just substructure for the appropriate language unless noted otherwise.

Of course, these tree examples can be continued on past height \(\omega\), but we know of no results (positive or negative) on these classes in terms of the Erdős-Rado notions.

3 Structural Partition Relations and Combinatorial Erdős-Rado Classes↩︎

We will formulate a version of the normal partition relation for classes other than linear orders in Definition 10. This will encapsulate the idea that any coloring of \(n\)-tuples from a large structure will have a large substructure that behaves the same way with respect to this coloring. First, we consider an example that indicates some of the difficulties and the need for new concepts, namely bigness notions (Definition 7) and type-homogeneity (Definition 9).

This example exposes two issues.

• First, we could take \(\bar{I^*}\) to be \((\emptyset, I_1)\), which is homogeneous for this coloring. However, taking one of the partitions to be empty goes against the point of working in \(\mathcal{K}^{2-or}\). So we will attach to these classes a notion of size (or bigness) that takes the structure of the class into account.

• Second, we colored the pairs using information about their type. This meant that we could place restrictions on the structure of any homogeneous subset. To allow for big homogeneous sets we will allow for the ‘single color’ to depend on the type of tuple.

For the first issue, we define abstractly what it means to be a bigness notion. The only requirements are a monotonicty condition and some weak degree of universality. For each class from Subsection 2.3, we make its associated bigness notion explicit in Subsection 3.1. Many natural bigness notions correspond to a degrees of universality after removing the order, but other cases are more complex (see Examples 17 or 18).

Note that the omission of will lead to some nonstandard notation, e.g., \(\mathcal{K}^{\chi-or}_\mu\) are the at least \(\mu\)-big elements of \(\mathcal{K}^{\chi-or}\) according to the bigness notion given in Example 14, rather than all elements of \(\mathcal{K}^{\chi-or}\) whose universe has cardinality \(\mu\).

Turning to homogeneity, the key observation from Example 12 was that the types of tuples are extra information that can be used to define a coloring. In the class of linear orders, there is only one increasing type of an \(n\)-tuple, so this issue doesn’t arise. In the general case, we can always use the type as information to color a tuple, so we want homogeneity to mean that the type is the only information that can be used to determine the color of a tuple.

In Example 12, the entire set \(\bar{I}\) is type-homogeneous for the given coloring.

With these new concepts in hand, we can define the structural partition relation.

Since the associated bigness notion for \(\mathcal{K}^{or}\) is simply cardinality, \((\lambda) \xrightarrow{or} (\mu)^\alpha_\kappa\) is the normal partition relation. In particular, positive instances of the structural partition relation are guaranteed by the Erdős-Rado Theorem, which states that \(\beth_{n-1}(\kappa)^+ \xrightarrow{or} (\kappa^+)^n_\kappa\) for every cardinal \(\kappa\) and every \(n < \omega\). We only consider this relation with \(\alpha\) finite.

Polarized partition relations (see [6]) are similar to \(\xrightarrow{\chi-or}\), but typically specify (in our language) the type of the tuple to be considered (and so are more like the Ramsey class-style partition relations, although we use them in Remark 16).

We have focused on the difference between the Ramsey-style structural partition relation (that fixes the type of the tuples colored) and the Erdős-Rado-style structural partition relation (that colors all tuples of a fixed length). These differ on a case-by-case basis, but the referee points out that if there are finitely many \(n\)-types in the class, then enough Ramsey-style structural partition results can be strung together to get a type-homogeneous coloring. That is, if \(\mathcal{K}\) is a Ramsey class with finitely many \(n\)-types for each \(n<\omega\), then for each \(n, k<\omega\) and \(A \in \mathcal{K}\), there is a \(C^* \in \mathcal{K}\) such that any coloring of \(n\)-tuples of \(C^*\) with \(k\) colors has a type-homogeneous copy of \(A\). We also use a version of this argument in Remark 16.

We will list several further positive instances of structural partition relations (new and old) in Subsection 3.1.

From the structural partition relation, we can define combinatorial Erdős-Rado classes as those that satisfy structural partition relations for all inputs on the right side.

The primary results and discussions deal with colorings that fix the arity \(n\) of the coloring. However, it is sometimes useful to consider colorings that color all tuples of arity \(\leq n\) at once (the ‘sometimes’ in this paper is Theorem 7). It turns out that this stronger relation holds in any combinatorial Erdős-Rado class and is witnessed by an iterate of the normal witnessing functions.

Proof: We work by induction on \(n<\omega\). For \(n=1\), there is nothing to prove. Suppose this holds for some \(n<\omega\).

Let \(X \in \mathcal{K}\) by \(F^*(\mu, n+1)\)-big and we have a coloring \[c:[X]^{\leq n+1}\to \kappa\] From definition of \(F^*\), we have \[\left(F^*(\mu, n+1)\right) \xrightarrow{\mathcal{K}} \left(F^*(\mu, n)\right)^{n+1}_{\kappa}\] so there is \(X_0 \subseteq X\) that is \(F^*(\mu, n)\)-big and type-homogeneous for \(c\) restricted to the \((n+1)\)-tuples. By induction, \[\left(F^*(\mu, n)\right) \xrightarrow{\mathcal{K}} \left(\mu\right)^{\leq n}_{\kappa}\] There is \(X_1 \subseteq X_0\) that is \(\mu\)-big and type-homogeneous for \(c\) restricted to the \((\leq n)\)-tuples. Then \(X_1 \subseteq X\) is \(\mu\)-big and type-homogeneous for all of \(c\), proving the proposition.

3.1 Examples and some counter-examples↩︎

We show that the examples introduced in Section 2.3 are combinatorial Erdős-Rado classes or mention results indicating they are not. In most cases, no claim of the optimality of the witnessing functions is made. While interesting from a combinatorial perspective, any reduction of the bounds on the order of ‘finitely many power set operations’ will not affect the witnesses for these classes being Erdős-Rado via an application of the Generalized Morley’s Omitting Types Theorem 1. Note that none of these results were originally stated in the notation of Definition 10 (especially since that notation was originated for this paper); however, we have translated those results into this language to illustrate our notions.

Note that the classic results on the Sierpinski coloring [26]⁶ show that dense linear orders do not form a combinatorial Erdős-Rado class. One could work to develop an infinite version of Ramsey degree, but we defer that for later.

As alluded to above, Shelah essentially proves this proposition except that Shelah’s result had a lower cardinal on the left-hand side and assumed each piece to be well-ordered (rather than just linearly ordered); thanks again to the referee for catching this mistake. We raise the cardinal on the left-hand side to make up for this lack of well-ordering. The author believes that the theorem could probably be proven with Shelah’s original bound (and similarly for the trees in Example 16), but since it doesn’t affect the final bound for being an Erdős-Rado Class, we don’t pursue that here.

Proof: Let \(\bar{I} = (I_i; <_i)_{i < \chi} \in \mathcal{K}^{\chi-or}\) be \(\lambda\)-big for \(\lambda = \beth_{1}\left(\beth_{n(n+1)}(\kappa)^+\right)^+\) and fix a coloring \[c:\left[\bigcup_{i <\chi} I_i\right]^n \to \kappa\] WLOG, each \(I_i\) has size exactly \(\lambda\). In order to invoke Shelah’s result, the \(I_i\)’s must be well-ordered, so fix a well-ordering ordering \(<_i^*\) of each \(I_i\).

First, we apply the binary Erdős-Rado Theorem to the pieces: define colorings \[d_i:[I_i]^2 \to 2\] by considering the agreement of the two orderings \[d_i(x,y) :=\begin{cases} 0 & x <_i y \iff x <^*_i y\\ 1 & x<_iy \iff y<^*_i x \end{cases}\] By Erdős-Rado, there are \(I_i^* \subseteq I_i\) of size \(\beth_{n(n+1)}(\kappa)^+\) that are homogeneous. Now, we can define a well-ordering \(<^+\) on all of \(\bar{I}^*:=\bigcup_{i<\chi} I^*_i\) to be the concatenation of the \(<^*_i\)’s. The key property we have constructed (crucially using the homogeneity) is that, for any tuples \(\boldsymbol{a}, \boldsymbol{b}\in \bar{I}^*\), we have \[\begin{align} tp_{\chi-or}\left(\boldsymbol{a};\left( I^*_i, <^*_i\right)_{i<\chi}\right) &=& tp_{\chi-or}\left(\boldsymbol{b};\left( I^*_i, <^*_i\right)_{i<\chi}\right)\\ &\iff& \\ tp_{\chi-or}\left(\boldsymbol{a};\left( I^*_i, <_i\right)_{i<\chi}\right) &=& tp_{\chi-or}\left(\boldsymbol{b};\left( I^*_i, <_i\right)_{i<\chi}\right) \end{align}\]

Now, we restrict the coloring \[c^*:\left[\bar{I}^*\right]^n\to \kappa\] and apply Shelah’s result to the well-ordered \(\left(I_i^*, <^+\right)_{i<\chi}\). This gives \(J_i \subseteq I^*_i\) of size \(\kappa^+\) so \(\left(J_i, <^+\right)_{i<\chi}\) is type-homogeneous for \(c^*\) and, therefore, for \(c\). By the key property above, the \(\kappa^+\)-big \[\left(J_i, <_i\right)_{i<\chi} \subseteq(I_i, <_i)_{i<\chi}\] is also type-homogeneous for \(c\), as desired.

Proof: Given a coloring \(c:[\chi \cdot \lambda]^n \to \mu\), we define an auxiliary coloring \(d:[\lambda]^n \to {}^{\left(\chi^n\right)}\mu\) given by \(d(\gamma_1, \dots, \gamma_n)\) is the function that maps \((i_1, \dots, i_n) \in \chi^n\) to \(c(\chi\cdot\gamma_1+i_1, \dots, \chi \cdot\gamma_n+i_n)\). There is a \(\kappa\)-sized homogeneous \(X \subseteq\lambda\) by assumption. Enumerate an initial segment as \(\{\gamma_\alpha \mid \alpha < \kappa\}\) and define the set \[\chi \otimes X := \{\chi \cdot \gamma_{\left(\chi\cdot \beta+i\right)} + i : \chi \cdot \beta + i < \kappa\text{ and }i < \chi\}\] We claim that this structure (with the induced \(\chi\)-or structure) is type homogeneous for \(c\).

Suppose that \((\chi\cdot \gamma_{(\chi \cdot \beta_1 + i_1)} + i_1, \dots, \chi\cdot \gamma_{(\chi \cdot \beta_n + i_n)} + i_n)\), \((\chi\cdot \gamma_{(\chi \cdot \beta'_1 + i'_1)} + i'_1, \dots, \chi\cdot \gamma_{(\chi \cdot \beta'_n + i'_n)} + i'_n) \in \chi \otimes X\) have the same \(\chi\)-or type. First, this means that \(P_\beta\) holds of \(\chi\cdot \gamma_{(\chi \cdot \beta_\ell + i_\ell)} + i_\ell\) iff it holds of \(\chi\cdot \gamma_{(\chi \cdot \beta'_\ell + i'_\ell)} + i'_\ell\); thus \(i_\ell = i'_\ell\) for all \(\ell \leq n\). Second, for ordinals⁸ \(\gamma \neq \gamma'\) and \(\beta, \beta' < \chi\), we have that \[\chi \cdot \gamma + \beta < \chi \cdot \gamma' +\beta' \text{ iff }\gamma < \gamma'\] Thus, we have that for each \(\ell, k < n\), \[\begin{align} \gamma_{(\chi \cdot \beta_\ell + i_\ell)} < \gamma_{(\chi \cdot \beta_k + i_k)} &\iff& \chi \cdot \gamma_{(\chi \cdot \beta_\ell + i_\ell)} + i_\ell < \chi \cdot \gamma_{(\chi \cdot \beta_k + i_k)} + i_k\\ &\iff& \chi \cdot \gamma_{(\chi \cdot \beta'_\ell + i'_\ell)} + i'_\ell < \chi \cdot \gamma_{(\chi \cdot \beta'_k + i'_k)} + i'_k\\ &\iff& \gamma_{(\chi \cdot \beta'_\ell + i'_\ell)} < \gamma_{(\chi \cdot \beta'_k + i'_k)} \end{align}\]

Thus, \((\gamma_{(\chi\cdot \beta_1+i_1)}, \dots, \gamma_{(\chi\cdot \beta_1+i_1)}), (\gamma_{(\chi\cdot \beta'_1+i'_1}, \dots, \gamma_{(\chi\cdot \beta'_1+i'_1)}) \in [X]^n\) have the same \(or\)-type and \(d\) of them is the same function. Thus, we can conclude \[\begin{align} c\left(\chi\cdot \gamma_{(\chi \cdot \beta_1 + i_1)} + i_1, \dots, \chi\cdot \gamma_{(\chi \cdot \beta_n + i_n)} + i_n\right) &=& d(\gamma_{(\chi\cdot \beta_1+i_1)}, \dots, \gamma_{(\chi\cdot \beta_1+i_1)})\left(i_1, \dots, i_n\right)\\ &=& d(\gamma_{(\chi\cdot \beta_1+i_1)}, \dots, \gamma_{(\chi\cdot \beta_1+i_1)})\left(i'_1, \dots, i'_n\right)\\ &=& d(\gamma_{(\chi\cdot \beta'_1+i'_1)}, \dots, \gamma_{(\chi\cdot \beta'_1+i'_1)})\left(i'_1, \dots, i'_n\right)\\ &=&c\left(\chi\cdot \gamma_{(\chi \cdot \beta'_1 + i'_1)} + i'_1, \dots, \chi\cdot \gamma_{(\chi \cdot \beta'_n + i'_n)} + i'_n \right) \end{align}\]

Proof: The proof follows the same strategy as Proposition 15. First, we take a \(\lambda=\beth_{1}\left(\beth_{k(n,m)}(\kappa)^+\right)^+\)-big \(n\)-tree \(T\) and a coloring \(c\). WLOG \(T\) is exactly \(\lambda\)-splitting at each non-terminal node. Then we can provide a global well-ordering so that \(T\) is a copy of \({}^{\leq n}\lambda\). First, we use binary Erdős-Rado to pass to a \(\beth_{k(n,m)}(\kappa)^+\)-big \(T_* \subseteq T\) where \(T_*\) is either the well-ordered or the reverse well-ordered on each level. Second, we use the Shelah result on the well-ordered \(T_*\) to get a \(\kappa^+\)-big \(T_{**}\) that is type-homogeneous for \(c\) with the well-ordering. Using the initial coloring, this means that \(T_{**}\) is type-homogeneous for the original ordering as well.

Note that the bound here is much larger than the other bounds (which are all below \(\beth_\omega(\kappa)\)). For instance, \[\beth_{1,2}(\kappa) = \beth_{\beth_{\kappa^+}(\kappa)^+}(\kappa)\] This impacts the witness for being an Erdős-Rado class (see Remark 22), but we do not know if the left-hand side here is a tight bound. Also, well-founded trees are closely related to scattered linear orders (those not containing a copy of \(\mathbb{Q}\); see [31] building on work of Hausdorff), so this result forms a counterpoint to the nonexample coming from Sierpinski colorings.

\(\mathcal{K}^{wf-tr}\) is also important as an Erdős-Rado Class that is not axiomatiable in \(\mathbb{L}_{\infty, \omega}\) and does not even form an Abstract Elementary Class because it is not closed under unions of chains. Worse, the class of well-founded trees could not even be the models of such a class (ignoring the substructure relation). These models could be used to define well-ordering and this is impossible in Abstract Elementary Classes.

Proof: Let \((I, E, <) \in \mathcal{K}^{ceq}_{\beth_{n(n+3)}(\kappa)^+}\) and color it with \(c:[I]^n \to \kappa\). We will use two already established facts: \[{\beth_{n(n+3)}(\kappa)^+} \xrightarrow{{\beth_{n-1}(\kappa)^+}-or} ({\beth_{n-1}(\kappa)^+})^n_\kappa\] \[{\beth_{n-1}(\kappa)^+} \xrightarrow{or}(\kappa^+)^n_\kappa\] First, find \(\{i_\alpha \in I \mid \alpha < {\beth_{n-1}(\kappa)^+}\}\) that are \(E\)-nonequivalent. Set \(I_1 = \bigcup_{\alpha<{\beth_{n-1}(\kappa)^+}} (i_\alpha/E)\) and note that \((I_1, i_\alpha/E, <)_{\alpha<{\beth_{n-1}(\kappa)^+}}\in \mathcal{K}^{{\beth_{n-1}(\kappa)^+}-or}_{\beth_{n(n+3)}(\kappa)^+}\). Then \(c\) still colors \([I_1]^n\), so use the result to find \(I_2 \subseteq I_1\) and \(c^*:\text{S}_{{\beth_{n-1}(\kappa)^+}-or}\to \kappa\) so that \((I_2, i_\alpha/E \cap I_2, <)_{\alpha < {\beth_{n-1}(\kappa)^+}} \in \mathcal{K}^{{\beth_{n-1}(\kappa)^+}-or}_{\beth_{n-1}(\kappa)^+}\) is type-homogeneous for \(c\) with \(c^*\).

Now consider the structure \(\left(\{i_\alpha \mid \alpha < {\beth_{n-1}(\kappa)^+}\}, <\right) \in \mathcal{K}^{or}_{\beth_{n-1}(\kappa)^+}\). We want to give an auxiliary coloring \(d:[{\beth_{n-1}(\kappa)^+}]^n \to {}^A \kappa\), where \(A = \{ s\in {}^n (n+1) \mid \sum_{i<n} s(i) = n\}\). Then \[d\left(\{\alpha_1 < \dots < \alpha_n\}\right)\] is the function that takes \(s \in A\) to \(c(\{j_1, \dots, j_n\})\) for \(j_1, \dots, j_n \in I_2\) such that, for each \(k\), \(s(k)\)-many of the \(j_\ell\)’s come from the equivalence class of \(i_{\alpha_k}\). Note that this is a well-defined coloring because \(I_2\) was \(\mathcal{K}^{\beth_{n-1}(\kappa)^+-or}\)-type-homogeneous for \(c\). Then we can find \(X \subseteq{\beth_{n-1}(\kappa)^+}\) of size \(\kappa^+\) and \(d^*:A \to \kappa\) such that \(X\) is \(\mathcal{K}^{or}\)-type-homogeneous for \(d\) with color \(d^*\).

Set \(I_* = \{i\in I_2 \mid i E i_\alpha \text{ for some }\alpha \in X\}\), \(E_* = E \upharpoonright(I_*^2)\), and \(<_* = < \upharpoonright(I_*^2)\).

Claim: \((I_*, E_*, <_*) \in \mathcal{K}^{ceq}_{\kappa^+}\) is type-homogeneous for \(c\). Since \(|X|={\kappa^+}\), \(I_*\) has \({\kappa^+}\)-many equivalence classes. For each \(\alpha \in X\), \(i_\alpha/E_* = i_\alpha/E \cap I_2\) and has size at least \({\beth_{n-1}(\kappa)^+} > {\kappa^+}\). Thus, \((I_*, E_*, <_*)\) is \({\kappa^+}\)-big.

For homogeneity, let \(j_1 <_* \dots <_* j_n; j_1' <_* \dots <_* j_n' \in I_*\) have the same \(\mathcal{K}^{ceq}\)-type. Then these tuples are each \(<\)-increasing, from \(I_2\), and each element of each tuple is equivalent to an element of \(\{i_\alpha \mid \alpha \in X\}\). Because they have the same \(\mathcal{K}^{ceq}\)-type, there are \(\alpha_1 < \dots < \alpha_n; \alpha_1' < \dots < \alpha_n'\) from \(X\) that contain these witnesses and a single map \(s \in A\) that maps \(\ell<n\) to \[|\{k \mid j_k E_* i_{\alpha_\ell}\}| = |\{k \mid j'_k E_* i_{\alpha'_\ell}\}|\] By the homogeneity of \(X\), we have that \(d^* = d\left(\{\alpha_1, \dots, \alpha_n\}\right) = d\left(\{\alpha'_1, \dots, \alpha'_n\}\right)\). Thus, \[\begin{align} c\left(\{j_1, \dots, j_n\}\right) &=& d\left(\{\alpha_1, \dots, \alpha_n\}\right)(s)\\ &=& d^*(s)\\ &=&d\left(\{\alpha'_1, \dots, \alpha'_n\}\right)(s)\\ &=& c\left(\{j'_1, \dots, j'_n\}\right) \end{align}\]

4 Erdős-Rado Classes and the Generalized Morley’s Omitting Types Theorem↩︎

Erdős-Rado classes (Definition 20) are those that allow one to build generalized indiscernibles in nonelementary classes, especially those definable in terms of type omission. Since these classes are often axiomatized in stronger logics, one could formulate the modeling property of Ramsey classes in terms of these stronger logics (in fact, Shelah [19] does this, and we compare the notions in Remark 25). However, this is not how order indiscernibles are typically built in Abstract Elementary Classes. Instead, we continue to work with indiscernability in a first-order (and even quantifier-free) context, but strengthen the modeling property so that type omission is preserved.

Note that there are two variants of being an Erdős-Rado class here, and a few more in Definition 26. The cofinal variant is the most common, and gives the sharpest applications.

Note that (2) implies (1) by taking the constant sequences \(I_\alpha = I\) and \(M_\alpha = M\). Also note that the definition of cofinal Erdős-Rado classes is only new when the \(\chi\) is limit; otherwise, the definition is equivalent to a normal Erdős-Rado class at its predecessor.

We refer to Definition 20.([erc-item]) or Definition 20.([erc2-item]) as the Erdős-Rado condition. See Remark 25 for a comparison with Ramsey conditions.

Before our main theorem, we need one more auxilliary definition. This definition will transform the witnessing function for combinatorial Erdős-Rado classes into witnessing functions for cofinal Erdős-Rado classes.

Although a formally new cardinal, in practice, this tends to give the same bounds as the normal Morley’s Omitting Types Theorem (see Remark 22).

The following theorem is the main source of Erdős-Rado classes.

The statement of Theorem 1 makes no mention of types or their omission in the statement, although this notion appears in the name. This connection is made in Theorem 2, which shows that if a blueprint is generated from (Skolemized) models that all omit some type, then any model built from the blueprint also omits the type. Morley is classically credited with the original result and gave the basic argument, but an important technical improvement is due to Chang, see [35].
Proof: Fix \(\daleth_\alpha=\daleth^F_\alpha\), \(g=g^\mathcal{K}\), and \(f=f^{\mathcal{K},F}\) from Definition 21.

Suppose that we are given \(f_\alpha:I_\alpha\to M_\alpha\) for cardinals \(\alpha < f(\mu)\). First, we thin out the sequence in two ways. Although \(\mathcal{K}\) has a unique \(0\)-type (recall Remark 8), the models \(M_\alpha \in \mathcal{K}^\tau\) might realize distinct \(0\)-types. However, the number of possible \(0\)-types is \(\leq 2^{|\tau|} < g(\mu)^+\). Thus, by passing to cofinal sequence (and using the monotonicity of bigness)¹¹ and restricting the models, we instead work with functions \(f_\alpha:I_\alpha \to M_\alpha\) for each \(\alpha < g(\mu)^+\) such that each \(I_\alpha\) is \(\daleth_\alpha\)-big and all \(M_\alpha\) satisfy the same \(0\)-type \(p^*\in \text{S}_\tau^0\).

We will build, for \(n<\omega\) and \(\alpha < g(\mu)^+\),

• \(\Phi_n:\text{S}^{inc, n}_\mathcal{K}\to S^n_\tau\);

• \(\beta_n(\alpha)<g(\mu)^+\);

• \(\gamma_{n+1}(\alpha) < g(\mu)^+\);

• \(I^n_\alpha \in\mathcal{K}\) that is \(\daleth_\alpha\)-big;

• \(h^{n+1}_\alpha:I^{n+1}_\alpha \to I^n_{\gamma_{n+1}(\alpha)}\) that is a \(\mathcal{K}\)-morphism; and

• \(f^n_\alpha:I^n_\alpha \to M_{\beta_n(\alpha)}\)

such that

1. \(\beta_0(\alpha) = \alpha\); \(I^0_\alpha = I_\alpha\); and \(f^0_\alpha = f_\alpha\);

2. for each \(\alpha < g(\mu)^+\) and \(i_1<\dots<i_n \in I^n_\alpha\), we have that \[\Phi_n\left(tp_\mathcal{K}(i_1, \dots, i_n; I_\alpha^n)\right) = tp_\tau\left(f_\alpha^n(i_1), \dots, f_\alpha^n(i_n); M_{\beta_n(\alpha)}\right)\]

3. the \(\Phi_n\) are coherent in the following sense: if \(p \in \text{S}_\mathcal{K}^{inc,n}\) and \(s \subseteq n\), then \[\Phi_n\left(p\right)^s = \Phi_{|s|}\left(p^s\right)\] (see Definition 4.([type-rest-item]) for this notation);¹² and

4. given \(\alpha < g(\mu)^+\) and \(n<\omega\), we have that \(\alpha \leq \beta_n(\alpha)\); \(\alpha \leq \gamma_n(\alpha)\); and \(\beta_{n+1}(\alpha) = \beta_n\left(\gamma_{n+1}(\alpha)\right)\), and the following commutes \[\xymatrix{I_\alpha^{n+1} \ar[rr]^{f_\alpha^{n+1}} \ar[dr]_{h_\alpha^{n+1}}& & M_{\beta_{n+1}(\alpha)}\\ & I_{\gamma_{n+1}(\alpha)}^n \ar[ur]_{f^n_{\gamma_{n+1}(\alpha)}} &}\]

This is enough: Set \(\Phi := \bigcup_{n<\omega}\Phi_n\). Then this is a function with domain \(\text{S}^{inc}_\mathcal{K}\) and range \(\text{S}_\tau\). Moreover, the coherence condition ([coh-cond]) implies that it is proper for \(\mathcal{K}\). Now we wish to show that it has the type reflection required by the Erdős-Rado condition, see Definition 20.([erc2-item]).

Let \(p \in \text{S}_{\mathcal{K}}^{inc,n}\) and \(\alpha_0 < f(\mu) = \daleth_{g(\mu)^+}\). Then there is \(\alpha_1<g(\mu)^+\) so \(\alpha_0<\daleth_{\alpha_1}\). \(I^n_{\alpha_1}\) is \(\aleph_0\)-big, so there is \(i_1< \dots< i_n \in I^n_{\alpha_1}\) realizing \(p\). Then, by ([phi-cond]) of the construction \[\begin{align} \Phi(p) = \Phi_n\left(tp_\mathcal{K}(i_1, \dots, i_n; I_{\alpha_1}^n)\right) = tp_\tau\left(f_{\alpha_1}^n(i_1), \dots, f_{\alpha_1}^n(i_n); M_{\beta_n(\alpha_1)}\right) \end{align}\] If \(n=0\), then \(I^0_{\alpha_1} = I_{\alpha_1}\) and we are done. If \(n>0\), we compose the \(h\)-embeddings to define \[h^*:=h^1_{\gamma_1^{-1}(\beta_n(\alpha_1))}\circ\dots\circ h^{n-1}_{\gamma_{n+1}(\alpha_1)}\circ h^n_{\alpha_1}: I^{n+1}_\alpha \to I_{\beta_n(\alpha_1)}\] This satisfies \(f^n_{\alpha_1} = f_{\beta_n(\alpha_1)} \circ h^*\). Thus, \(h^*(i_1), \dots, h^*(i_n) \in I_{\beta_n(\alpha_1)}\) realize \(p\) and \[\Phi(p) = tp_\tau\left(f_{\beta_n(\alpha_1)}\left(h^*(i_1)\right), \dots, f_{\beta_n(\alpha_1)}\left(h^*(i_n)\right); M_{\beta_n(\alpha_1)}\right)\] Since \(\daleth_{\beta_n(\alpha_1)}> \alpha_0\), this completes the proof.
Construction: We work by induction on \(n\).
For \(n=0\), we must deal with the unique \(0\)-type \(p_0 \in \text{S}^{inc, 0}_\mathcal{K}\). Recalling the first step to ensure each \(M_\alpha\) has the same \(0\)-type \(p^*\), we can set \(\Phi_0:= \{(p_0, p^*)\}\) and use what we are given: \(\beta_0(\alpha)=\alpha\); \(I_\alpha^0 =I_\alpha\); and \(f_\alpha^0=f_\alpha\).
For \(n+1\), suppose we have completed the construction up to stage \(n\). Fix some \(\alpha < g(\mu)^+\). Then we have \(F(\daleth_\alpha, n+1) \leq \daleth_{\alpha+1}\) by definition. Consider the coloring \[c^{n+1}_\alpha:[I^n_{\alpha+1}]^{n+1}\to \text{S}^{n+1}_\tau\] given by, for \(i_1<\dots<i_{n+1} \in I^n_{\alpha+1}\), \[c^{n+1}_\alpha \left(\{i_1, \dots , i_{n+1}\}\right) = tp_\tau\left(f^n_{\alpha+1}(i_1), \dots, f^n_{\alpha+1}(i_{n+1}); M_{\beta_n\left(\alpha+1\right)}\right)\] By monotonicity of bigness, we have \[\left(\daleth_{\alpha+1}\right) \xrightarrow{\mathcal{K}} \left(\daleth_\alpha\right)^{n+1}_{2^\mu}\] Thus there is \(\daleth_\alpha\)-big \(\bar{I}^{n+1}_\alpha \in \mathcal{K}\); \(\bar{h}^{n+1}_\alpha: \bar{I}^{n+1}_\alpha \to I^n_{\alpha+1}\); and \(c^{*, n+1}_\alpha:\text{S}^{inc, n+1}_\mathcal{K}\to \text{S}^{n+1}_\tau\) witnessing the type-homogeneity, that is, such that for all \(i_1<\dots<i_{n+1} \in \bar{I}^{n+1}_\alpha\), we have \[tp_\tau\left(f_{\alpha+1}^{n}\circ \bar{h}^{n+1}_\alpha(i_1), \dots, f_{\alpha+1}^{n}\circ \bar{h}^{n+1}_\alpha(i_{n+1}); M_{\beta_n\left(\alpha+1\right)}\right) = c^{*, n+1}_\alpha\left(tp_\mathcal{K}(i_1, \dots, i_{n+1}; \bar{I}_\alpha^{n+1})\right)\] For each \(\alpha < g(\mu)^+\), we have built a function \(c_{\alpha}^{*, n+1}:\text{S}^{inc, n+1}_\mathcal{K}\to S^{n+1}_\tau\). Since \(\text{cf }(g(\mu)^+)=g(\mu)^+\) is greater than the number of these functions, there is \(X\subseteq g(\mu)^+\) of size \(g(\mu)^+\) and \(c^{*, n+1}:\text{S}^{inc, n+1}_\mathcal{K}\to \text{S}^{n+1}_\tau\) such that, for all \(\alpha \in X\), \(c^{*, n+1}_\alpha=c^{*, n+1}\). Set \(\pi:X\cong g(\mu)^+\) to be the collapse of \(X\). Then \(\alpha \leq \pi^{-1}(\alpha)\) for all \(\alpha \in g(\mu)^+\).

Set

1. \(\Phi_{n+1} = c^{*, n+1}\);

2. \(I_\alpha^{n+1} = \bar{I}^{n+1}_{\pi^{-1}(\alpha)}\);

3. \(\gamma_{n+1}(\alpha) = \pi^{-1}(\alpha)+1\);

4. \(\beta_{n+1}(\alpha) =\beta_n\left(\pi^{-1}(\alpha)+1\right)\);

5. \(h_\alpha^{n+1}=\bar{h}^{n+1}_{\pi^{-1}(\alpha)}\);

6. \(f_\alpha^{n+1} = f^n_{\pi^{-1}(\alpha)+)} \circ h_\alpha^{n+1}\)

These satisfy the pieces of the construction: by induction, each of the \(c^{*,n+1}_\alpha\)’s extend \(c^{*, n}\) in the sense that the restriction to \(n\)-types is determined by \(c^{*,n}\). This gives the coherence. The other properties are routine to verify.

The following extends the normal notion of PC classes to include classes with a strong substructure relation. Note that Chang’s Presentation Theorem [35] implies any \(\mathbb{L}_{\infty, \omega}\)-axiomatizable class with ‘elementary according to a fragment’ as the strong substructure is what we will call a PC pair, and Shelah’s Presentation Theorem [10] extends this to Abstract Elementary Classes.

A version of Theorem 2 also holds for Erdős-Rado classes (without the cofinal adjective) when there is a single embedding from a \(f(|\tau_1|)\)-big member of \(\mathcal{K}\) into \(M\).

Proof: Let \(T_1\) and \(\Gamma\) in the language \(\tau_1\) witness that \(\mathbb{K}\) is a PC pair. By a further Skolem expansion, we can assume that \(T_1\) is universal and the types of \(\Gamma\) are quantifier-free. Let \(f_\alpha:I_\alpha \to M_\alpha\) for \(\alpha < f(|\tau_1|)\) as in the hypothesis. Since \(\mathcal{K}\) is \(\left(|\tau_1|, f(|\tau_1|)\right)\)-cofinally Erdős-Rado, we can find a blueprint \(\Phi \in \Upsilon^{\mathcal{K}}[\tau_1]\) satisfying the Erdős-Rado condition, Defintion 20.([erc2-item]).

First, we wish to show that \(\Phi\) is proper for \((\mathcal{K}, \mathbb{K})\). For membership in \(\mathbb{K}\), let \(I \in \mathcal{K}\). First, suppose that \(`\forall \boldsymbol{x}\phi(\boldsymbol{x})\text{'} \in T_1\) with \(\phi(\boldsymbol{x})\) quantifier-free. If \(EM(I, \Phi) \vDash \neg \forall \boldsymbol{x}\phi(\boldsymbol{x})\), then there is \(\boldsymbol{a}\in EM(I, \Phi)\) witnessing this. Since \(EM(I, \Phi)\) is generated by \(\tau_1\)-terms, there are \(\tau_1\)-terms \(\sigma_1,\dots, \sigma_n\) and \(i_1, \dots, i_k \in I\) such that \(\boldsymbol{a}= \sigma_1^{EM(I, \Phi)}(\boldsymbol{i}), \dots, \sigma_n^{EM(I, \Phi)}(\boldsymbol{i})\); without loss, these satisfy \(i_1 < \dots < i_k\).

Set \(p = tp_\mathcal{K}(\boldsymbol{i}; I)\). By the Erdős-Rado condition, there is some \(\alpha < f(\mu)\) and \(j_1<\dots<j_k\) such that \[tp_{\tau_1}\left(i_1, \dots, i_k; EM(I, \Phi)\right) = \Phi(p) = tp_{\tau_1}\left(f_\alpha(j_1), \dots, f_\alpha(j_k); M_\alpha\right)\] In particular, \[M_\alpha \vDash \neg\phi\left(\sigma_1(\boldsymbol{j}), \dots, \sigma_n(\boldsymbol{j})\right)\] But this contradicts that \(M_\alpha\) models \(T_1\).

The same argument shows that any quantifier-free type which is realized in \(EM(I, \Phi)\) is realized in cofinally many \(M_\alpha\). Since all types in \(\Gamma\) are quantifier-free, \(EM(I, \Phi)\) must omit all of them. So \(EM_\tau(I, \Phi) \in \mathbb{K}\)

For substructure, this follows from the definition for PC pair and the fact that \(\Phi\) is proper for \((\mathcal{K}, \mathbb{K}^{\tau_1})\).

5 Further results↩︎

5.1 Reversing Generalized Morley’s Omitting Types Theorem↩︎

We would like to have a converse to the Generalized Morley’s Omitting Types Theorem 1 that says that all Erdős-Rado classes come from a combinatorial result. However, this seems unlikely to be true (and we discuss candidates for this in Section 5.4). The issue is that the definition of a (cofinally) Erdős-Rado class is not as tied to the relevant bigness notion, but the definition of a combinatorial Erdős-Rado class is. In particular, the definition leaves open the possibility that there is only a single witness to the Erdős-Rado condition, while combinatorial Erdős-Rado classes require a big set of witnesses to the type-homogeneity. If we strengthen this requirement, then we get a converse.

Proof: The proof of the Generalized Morley’s Omitting Types Theorem 1 proves (1): the \(I^n_\alpha\) built in that proof are exactly the ones needed to witness ‘strong.’ The proof of (2) is straightforward. We prove (3), which is enough to prove (4). The idea is that a potential coloring is turned into a structure, and the derived blueprint is used to figure out the colors for the large set.

Let \(\lambda < \chi\) and \(c:[I]^n \to \mu\) be a coloring of \(I \in \mathcal{K}^{\boldsymbol{big}}_\chi\). We build this into a two-sorted structure \[M = \langle I, \mu; c, \alpha\rangle_{\alpha<\mu}\] We have an embedding \(f:I \to M\) given by the identity. Then \(|\tau(M)| =\mu\), so the strong Erdős-Rado property gives us a blueprint \(\Phi:\text{S}^{inc}_\mathcal{K}\to \text{S}_{\tau(M)}\) as in Definition 26 with witnessing sets \(I^n_\alpha\).
Claim 1: For every \(p \in \text{S}^{inc, n}_\mathcal{K}\), there is a unique \(\alpha_p < \mu\) such that \(``c(x_1, \dots, x_n) = \alpha_p\text{"} \in \Phi(p)\).

Take \(I^n_\omega \leq_\mathcal{K}I\) witnessing the strong Erdős-Rado property and find \(i_1 < \dots < i_n \in I^n_\omega\) realizing \(p\); such a tuple exists by the definition of a bigness notion. Then \(\Phi(p) = tp_{\tau(M)}(i_1, \dots, i_n; M)\). This has a color, so \(\alpha_p = c(i_1, \dots, i_n)\).\(\dagger_{\text{Claim 1}}\)
Set \(c^*:\text{S}^{inc, n}_\mathcal{K}\to \mu\) to be the function that takes \(p\) to \(\alpha_p\).
Claim 2: \(I^n_\lambda\) is type-homogeneous for \(c\) as witnessed by \(c^*\).

Straightforward.\(\dagger_{\text{Claim 2}}\)
Since \(I^n_\lambda\) is \(\lambda\)-big, this proves the theorem.\(\dagger_{\text{Theorem \ref{gmott-con-thm}}}\)
Note that this is not an exact converse because there is some slippage in the witnessing functions. However, this doesn’t affect the bounds on the Erdős-Rado class.

5.2 A category theoretic interpretation of blueprints↩︎

This section gives a category theoretic perspective on the results we’ve proven and indiscernibles in general. It requires more category theoretic background than the rest of the paper (such as [20] or [37]), but can be skipped. This theme will be explored further in [38].

Makkai and Paré give the following statement credited to Morley. For a logic \(\mathcal{L}\), an ‘\(\mathcal{L}\)-elementary category’ is (a category equivalent to) one where the objects are models of some fixed \(\mathcal{L}\)-theory \(T\) and arrows are \(\tau\)-homomorphisms between models that are elementary for some fragment of \(\mathcal{L}\) containing \(T\).

This is not phrased as Morley (likely) ever wrote it, but this is the classic proof of Morley’s Omitting Types Theorem. The functor \(\Phi\) comes from the blueprint that takes \(I \in \mathcal{K}^{or}\) to \(EM_\tau(I, \Phi) \in \mathbb{K}\). With generalized indiscernibles in hand, we have a generalization.

We include a proof to make the translation more clear (and in part because Makkai and Paré do not give a proof). Recall that \(\mathcal{K}^{wf-tr}\) is an Erdős-Rado class that is not \(\mathbb{L}_{\infty, \omega}\)-axiomatizable.
Proof: Let \(\mathcal{K}\) be an Erdős-Rado class and \(\mathbb{K}\) be a large, \(\mathbb{L}_{\infty, \omega}\)-elementary category. Fix \(f:Card\to Card\) witnessing that \(\mathcal{K}\) is Erdős-Rado. By virtue of being large, there is \(M \in \mathbb{K}\) such that \(\|M\| \geq f(\mu)\), where \(\mu\) is the size of fragment witnessing that \(\mathbb{K}\) is a \(\mathbb{L}_{\infty, \omega}\)-elementary category. Thus by Theorem 2 and Chang’s Presentation Theorem, there is a blueprint \(\Phi \in \Upsilon^\mathcal{K}[\mathbb{K}]\). Define a functor \(F: \mathcal{K}\to \mathbb{K}\) by, for \(I \in \mathcal{K}\), \(F(I) = EM_\tau(I, \Phi)\) and, for \(f: I \to J\) in \(\mathcal{K}\), \(Ff\) the map that takes \(\sigma^{EM(I, \Phi)}(i_1, \dots, i_n)\) for a \(\tau(\Phi)\)-term \(\sigma\) to \(\sigma^{EM(J, \Phi)}\left(f(i_1) , \dots, f(i_n)\right)\).

This is clearly faithful. Moreover, the \(EM\) construction commutes with directed colimits, so \(F\) preserves them.
This proof works by noting that blueprints can be seen as well-behaved functors. We can actually specify the properties of these functors to obtain a converse. The one additional property that we need is that the size of \(EM_\tau(I,\Phi)\) is determined by \(|I|\) and an additional cardinal parameter representing \(|\tau(\Phi)|\). The following is based on an argument developed with John Baldwin in the case \(\mathcal{K}= \mathcal{K}^{or}\).

For this, we need the following definition:

Note that all universal classes \(\mathcal{K}\) are \(\mathbb{L}_{\infty, \omega}\)-axiomatizable by saying no finite tuple generates a structure not in \(\mathcal{K}\).

Proof: Let \(T \subseteq\mathbb{L}_{\infty, \omega}(\tau)\) such that \(\mathbb{K}\) is (equivalent to) \(\textrm{Mod }T\). Enumerate the \(\mathcal{K}\)-types as \(\langle p_i^n \in \text{S}^n_\mathcal{K}\mid i < \mu_n \rangle\), and pick some \(I_i^n \in \mathcal{K}\) that is generated by elements \(a^{i,n}_1, \dots, a^{i, n}_n\) that realize \(p^n_i\). We expand each \(F(I^n_i)\) to a \(\tau^*:= \tau(\mathbb{K}) \cup \{F^n_\alpha: \alpha < \mu_F, n<\omega\}\)-structure as in Shelah’s Presentation Theorem. In fact, we only give an explicit description of the \(\{F^n_\alpha:\alpha<\mu_F\}\) structure on the \(F(I^n_i)\): for each \(n < \omega\) and \(i < \mu_n\), define these functions so that \(\{F^n_\alpha(a^{i, n}_1, \dots, a^{i,n}_n) : \alpha < \mu\}\) enumerates the universe of \(F(I_i^n)\). Then define the remaining functions arbitrarily.

Since \(F\) preserves directed colimits and \(\mathcal{K}\) is generated by the \(I_i^n\) under directed colimits, we can lift these expansions to the rest of \(F"\mathcal{K}\). Taking \(I\) large enough, we can define a blueprint \(\Phi \in \Upsilon^{\mathcal{K}}[\tau^*]\). For all \(I\), the \(\tau\)-reduct of \(EM_{\tau^*}(I, \Phi)\) is canonically isomorphic to \(F(I)\). Thus, \(\Phi\) is as desired.
Note that this converse requires that models be of a predictable size. Specializing to linear order, we demand that \(\Phi(n)\) be the same for all \(n < \omega\). This is necessary for the formalism we’ve given where \(\tau(\Phi)\) consists of functions that can be applied to any element of \(EM(I, \Phi)\). To state the most general result, we could change this to only apply the functions of \(\tau(\Phi)\) to the skeleton \(I\). Then the different sizes of \(\Phi(n)\) could be dealt with by having different numbers of functions of different cardinalities. But this seems like a marginal gain after what would be significant technical pain. Additionally, the requirement that \(\mathcal{K}\) be universal can be removed.

We return to this category theoretic perspective in Section 6.2 when discussing indiscernible collapse. The existence of a minimal, large \(\mathbb{L}_{\infty, \omega_1}\)-elementary category (and a version of EM models for those theories) is still open, although [39] discusses this issue and places some restrictions on it.

5.3 Generalized Shelah’s Omitting Types Theorem↩︎

The application of Morley’s Omitting Types Theorem to Abstract Elementary Classes is normally done through Shelah’s Presentation Theorem, which gives a type omitting characterization of these classes (see Theorem 2 for this argument). Moving beyond this, Shelah has proved an omitting types theorem that strengthens this and specifically applies to to Abstract Elementary Classes in that it references Galois types rather than syntactic types ([40] and [41] both use some version of this). The key addition is a reduction in the cardinal threshold for type omission at the cost of less control over what types are omitted. The main combinatorial tool is still using the Erdős-Rado Theorem to build Ehrenfeucht-Mostowski models, so we can similarly prove a version for any Erdős-Rado class.

One nonstandard piece of notation is necessary.

The proof of the above adapts the proof of Shelah’s Omitting Types Theorem just as Theorem 1 adapts Morley’s original; see the notes by the author for a very detailed proof of (the ordinary) Shelah’s Omitting Types Theorem [42].

5.4 End-approximations↩︎

Generalized Morley’s Omitting Types Theorem 1 is the primary source of Erdős-Rado classes, but not the only source. The proof that \(\mathcal{K}^{\omega-tr}\) is an Erdős-Rado class uses the fact that elements of it can be approximated by trees of height \(n\), and each \(\mathcal{K}^{n-tr}\) is combinatorial Erdős-Rado class. We capture this behavior in an abstract condition in Defintion 30 below, and Proposition 31 shows that \(\mathcal{K}^{\omega-tr}\) fits into this framework.

Note that since the language is finitary, we can always decompose the objects covered in Definition 30.([endex-def-colimit]) as the canonical colimits of it’s restrictions; that is, if \(I \in \mathcal{K}\), then \[I = \bigcup_{n<\omega} \left(I\upharpoonright n\right)\]

The lifting condition Definition 30.([lift-cond]) and the type determination condition Defintion 30.([type-det-cond]) are the key properties. Our initial motivation for this framework was to show that \(\mathcal{K}^{\omega-tr}\) is an Erdős-Rado class. After sending him a draft, Baldwin pointed us to [18], where this is already shown. We hope this framework can be applied in other situations.

Proof: The proof is straightforward. The truncation map \(\cdot \upharpoonright n\) truncates a tree of height \(\geq n\) to its \(\leq n\) levels. Any \(p \in S^n_{\mathcal{K}^{\omega-tr}}\) specifies the max height \(k_p\) of a realization.

For condition ([lift-cond]), let \(I, J, f\) be as there. Build \(\hat{I}\) by specifying \(\hat{I} \upharpoonright n = I\) and, given maximal \(\eta \in I\), the successors of \(\eta\) in \(\hat{I}\) are an isomorphic copy the successors of \(f(\eta)\) in \(J\). Since \(J\) is at least \(\alpha\)-splitting, so is \(\hat{I} \in \mathcal{K}^{n+1}_\alpha\), and the isomorphisms give the lift \(\hat{f}:\hat{I} \to J \upharpoonright n+1\).

For condition ([type-det-cond]), given \(p \in \text{S}(\mathcal{K})\), set \(k_p\) to the maximum height of the realizations. This is finite and \(p \upharpoonright k_p\) determines all of the information in the type.
The other natural candidate is that \(\mathcal{K}^{(\omega,\sigma)-hg}\) might be end approximated by \(\{\mathcal{K}^{(k, \sigma)-hg}\mid k<\omega\}\). However, the crucial lifting condition fails: we can arrange a saturated/big \(H \in \mathcal{K}^{(3, \sigma)-tr}\) and pick a subgraph \(G \subseteq H\) that is saturated/big for unary types that the \(\mathcal{K}^{(2, \sigma)-hg}\) part can see, but not for the binary relations in \(\mathcal{K}^{(3, \sigma)-hg}\). The author suspects that more refined methods could still prove \(\mathcal{K}^{(\omega, \sigma)-hg}\) is an Erdős-Rado class, but we don’t do that here.

The goal is to repeat the proof of the Generalized Morley’s Omitting Types Theorem 1, except we restrict our set-up to the \(n\)th approximation \(\mathcal{K}^n\) in stage \(n\). Then when we move to stage \(n+1\), we use the lifting condition Definition 30.([lift-cond]) to lift the set-up to the next level. Crucially, the ‘approximate blueprints’ \(\Phi_n\) have all types of length \(\leq n\) in \(\mathcal{K}^n\) and are not strictly increasing. Instead, the \(\Phi_n\) are increasing on the types \(p\) satisfying \(k_p\leq n\).

At the sage advice of the referee, we repeat the proof here and provide all details so that we can highlight where the different conditions of Definition 30 are used.
Proof: As in the proof of Theorem 1, set \(\daleth_\alpha = \daleth_\alpha^F\), \(g=g^\mathcal{K}\), and \(f=f^{\mathcal{K}, F}\) and we can begin with \(f_\alpha:I_\alpha\to M_\alpha\) for \(\alpha < g(\mu)^+\) so \(I_\alpha\) is \(\daleth_\alpha\)-big and all \(M_\alpha\) realize the same \(0\)-type, \(p^* \in \text{S}^0_\tau\).

We build the following for \(n<\omega\) and \(\alpha<g(\mu)^+\). Note that we have tried to match the corresponding names from the proof of Theorem 1; the \(g^n_\alpha\) functions are new since the \(I^n_\alpha\) are in \(\mathcal{K}^n\), so cannot literally be \(I_{\beta_n(\alpha)}\).

• \(\Phi_n: \text{S}^{inc,\leq n}_{\mathcal{K}^n}\to \text{S}^{\leq n}_\tau\);

• \(\beta_n(\alpha) < g(\mu)^+\);

• \(\gamma_{n+1}(\alpha) < g(\mu)^+\);

• \(\daleth_\alpha\)-big \(I^n_\alpha \in \mathcal{K}^n\);

• \(\mathcal{K}^n\)-embeddings \(h^{n+1}_\alpha:(I^{n+1}_\alpha \upharpoonright n) \to I^n_{\gamma_{n+1}(\alpha)}\);

• \(\mathcal{K}^n\)-embeddings \(g^n_\alpha: I^n_\alpha\to (I_{\beta_n(\alpha)}\upharpoonright n)\); and

• \(f^n_\alpha:I^n_\alpha\to M_{\beta_n(\alpha)}\)

such that

1. \(\beta_0(\alpha) = \alpha\), \(I^0_\alpha = I_\alpha\upharpoonright 0\), \(g^0_\alpha = \textrm{id}_{I^0_\alpha}\), and \(f^0_\alpha = f_\alpha\upharpoonright I^0_\alpha\);

2. for all \(\alpha<g(\mu)^+\), \(i_1<\dots<i_m \in I^n_\alpha\), and \(m \leq n\), we have \[\Phi_n\left(tp_{\mathcal{K}^n}\left(i_1, \dots, i_m;I^n_\alpha\right)\right)=tp_\tau\left(f^n_\alpha(i_1), \dots, f^n_\alpha(i_m); M_{\beta_n(\alpha)}\right)\]

3. the \(\Phi_n\) are coherent in the following sense:

   1. (within \(n\)) if \(p \in \text{S}^{inc, \leq n}_{\mathcal{K}^n}\) and \(s \subseteq\ell(p)\), then \[\Phi_n(p)^s = \Phi_n(p^s)\]

   2. (across \(n\)) if \(p \in \text{S}^{inc,\leq n}_{\mathcal{K}^n}\) has a unique extension to \(p^* \in \text{S}^{inc, \leq n}_{\mathcal{K}}\) with¹³ \(k_{p^*} \leq n\), then \[\Phi_{k_{p^*}}(p \upharpoonright k_{p^*}) = \Phi_n(p)\]

4. for \(\alpha < g(\mu)^+\) and \(n<\omega\),

   1. \(\alpha \leq \beta_n(\alpha)\), \(\alpha \leq \gamma_{n+1}(\alpha)\), and \(\beta_n(\gamma_{n+1}(\alpha)) = \beta_{n+1}(\alpha)\); and

   2. the following diagram commutes: \[\begin{tikzcd} {I_{\beta_{n+1}(\alpha)} \upharpoonright n} &&&& {M_{\beta_{n+1}(\alpha)}} \\ \\ && {I^n_{\gamma_{n+1}(\alpha)}} \\ \\ && {I^{n+1}_\alpha \upharpoonright n} \arrow["{f_{\beta_{n+1}(\alpha)}\upharpoonright\left(I_{\beta_{n+1}(\alpha)} \upharpoonright n\right)}", curve={height=-24pt}, from=1-1, to=1-5] \arrow["{g^n_{\gamma_{n+1}(\alpha)}}"', from=3-3, to=1-1] \arrow["{f^n_{\gamma_{n+1}(\alpha)}}", from=3-3, to=1-5] \arrow["{g^{n+1}_\alpha\upharpoonright\left(I^{n+1}_\alpha \upharpoonright n\right)}", curve={height=-24pt}, from=5-3, to=1-1] \arrow["{f^{n+1}_\alpha\upharpoonright\left(I^{n+1}_\alpha \upharpoonright n\right)}"', curve={height=24pt}, from=5-3, to=1-5] \arrow["{h^{n+1}_\alpha}", from=5-3, to=3-3] \end{tikzcd}\]

This is enough: We want to define our blueprint as the colimit of the \(\Phi_n\)’s, but face the extra difficulty that they are not actually increasing: \(\text{S}^{inc, \leq n}_{\mathcal{K}^n}\) consists of types in a different class then \(\text{S}^{inc, \leq n+1}_{\mathcal{K}^{n+1}}\). Moreover, a type in the first set might have multiple extensions to the second. We solve this problem by using Defintion 30.([type-det-cond]), which says that all types in \(\text{S}^{inc}_{\mathcal{K}}\) are determined at some level.

Fix \(p \in \text{S}^{inc}_\mathcal{K}\). This is determined at some level \(k_p <\omega\). Define \[\Phi(p) := \Phi_{k_p}(p \upharpoonright k_p)\] First, for any \(n \geq k_p\), we claim that \[\Phi_{k_p}(p\upharpoonright k_p) = \Phi_n(p\upharpoonright n)\] This means that we have chosen \(\Phi(p)\) to be the output of the \(\Phi_n\)’s after it has stabilized. We prove this by induction on \(n \geq k_p\) by using condition ([phi-cond39]) of the construction: For \(n=k_p\), it is immediate. So assume we know \(\Phi_n(p\upharpoonright n) = \Phi_{k_p}(p\upharpoonright k_p)\) and we want to prove this for \(n+1\).

To this end, let \(i_1<\dots<i_m\in I^{m+1}_\alpha\) for some \(\alpha<g(\mu)^+\) realize \(p\upharpoonright(n+1)\). By Definition 30.([type-det-cond]), we have \(i_1, \dots, i_m\in \left(I^{n+1}_\alpha\upharpoonright n\right)\), so it is in the domain of \(h^{n+1}_\alpha\). Moreover, \[h^{n+1}_\alpha(i_1), \dots, h^{n+1}_\alpha(i_m)\in I^n_{\gamma_{n+1}(\alpha)}\] realizes \(p\upharpoonright n\). By the lower right triangle in the diagram of condition ([diag-cond39-2]) and condition ([phi-cond39]), we have \[\begin{align} \Phi_{n+1}\left(p\upharpoonright(n+1)\right) &=& tp_\tau\left(f^{n+1}_\alpha(i_1), \dots, f^{n+1}_\alpha(i_m); M_{\beta_{n+1}(\alpha)}\right)\\ &=&tp_\tau\left(f^n_{\gamma_{n+1}(\alpha)}\left(h^{n+1}_\alpha(i_1)\right),\dots,f^n_{\gamma_{n+1}(\alpha)}\left(h^{n+1}_\alpha(i_1)\right);M_{\beta_{n+1}(\alpha)}\right)\\ &=&\Phi_n\left(tp_\tau\left(h^{n+1}_\alpha(i_1), \dots, h^{n+1}_\alpha(i_m);I^n_{\gamma_{n+1}(\alpha)}\right)\right)\\ &=&\Phi_n(p\upharpoonright n)=\Phi_{k_p}(p\upharpoonright k_p) \end{align}\]

Now we want to check the coherence condition from Definition 1. Fix \(p \in \text{S}^{inc,\leq n}_\mathcal{K}\) and \(s \subseteq m=\ell(p)\). By Definition 30.([type-det-cond]).(4), \(k_{p^s} \leq k_p\) and \(p^s \upharpoonright k_{p^s} = \left( p\upharpoonright k_p \right)^s \upharpoonright k_{p^s}\). Then we have \[\begin{align} \Phi(p)^s &=& \Phi_{k_p}(p \upharpoonright k_p)^s\\ &=& \Phi_{k_p}\left((p\upharpoonright k_p)^s \right) \text{ by condition (\ref{coh-cond39-2})}\\ &=& \Phi_{k_{p^s}}\left((p\upharpoonright k_p)^s \upharpoonright k_{p^s} \right) \text{ by condition (\ref{coh-cond39-1})}\\ &=& \Phi_{k_{p^s}}(p^s \upharpoonright k_{p^s}) = \Phi(p^s) \end{align}\]

Construction: \(n=0\): As before, this is determined by condition ([0-cond39]).
\(n+1\): Suppose we have the construction at stage \(n\). The construction is similar to the construction in Theorem 1 in plan, but there are many additional technicalities, so we give the construction in full.

Fix \(\alpha < g(\mu)^+\). We have a \(\mathcal{K}^n\)-map \(g^n_\alpha:I^n_\alpha \to I_{\beta_n(\alpha)}\upharpoonright n\) with \(I^n_\alpha\) being \(\daleth_\alpha\)-big (in \(\mathcal{K}^n\)) and \(I_{\beta_n(\alpha)}\) being \(\daleth_{\beta_n(\alpha)}\)-big (in \(\mathcal{K}\)). By the lifting condition Definition 30.([lift-cond]) and since \(\alpha \leq \beta_n(\alpha)\), there is a lift \[\hat{g}^{n+1}_\alpha:\hat{I}^{n+1}_\alpha \to I_{\beta_n(\alpha)}\upharpoonright(n+1)\] with \(\hat{I}^{n+1}_\alpha \in \mathcal{K}^{n+1}\) being \(\daleth_\alpha\)-big so that \(\hat{I}^{n+1}_\alpha \upharpoonright n = I^n_\alpha\) and \(\hat{g}^{n+1}_\alpha\upharpoonright(I^n_\alpha) = g^n_\alpha\). We have that \(F^*(\daleth_\alpha, n+1) \leq \daleth_{\alpha+1}\). Since \(F^*\) is the function associated with the ‘\(\leq n\)’ partition relation (recall Proposition 13), we color \[c^{n+1}_\alpha:\left[\hat{I}^{n+1}_{\alpha+1}\right]^{\leq n+1} \to \text{S}^{\leq n+1}_\tau\] by, for \(i_1 < \dots <i_m \in \hat{I}^{n+1}_{\alpha+1}\) with \(m \leq n+1\), setting \[c^{n+1}_{\alpha}\left(\{i_1, \dots, i_m\}\right) = tp_\tau\left(f_{\beta_n(\alpha+1)}\circ\hat{g}^{n+1}_{\alpha+1}(i_1), \dots,f_{\beta_n(\alpha+1)}\circ\hat{g}^{n+1}_{\alpha+1}(i_m);M_{\beta_n(\alpha+1)} \right)\] By Proposition 13, we can find \(\daleth_\alpha\)-big \(\bar{I}^{n+1}_\alpha \in \mathcal{K}^{n+1}\) and \[\begin{align} \bar{h}^{n+1}_\alpha&:&\bar{I}^{n+1}_\alpha \to \hat{I}^{n+1}_{\alpha+1}\\ c^{*, n+1}_\alpha&:& \text{S}^{inc, \leq n+1}_{\mathcal{K}^{n+1}} \to \text{S}^{\leq n+1}_\tau \end{align}\] that witness the type-homogeneity, that is, so for all \(i_1<\dots<i_m \in \bar{I}^{n+1}_\alpha\) with \(m \leq n+1\), we have \[c^{n+1}_\alpha\left(\left\{\bar{h}^{n+1}_\alpha(i_1), \dots, \bar{h}^{n+1}_\alpha(i_m)\right\}\right) = c^{*, n+1}_\alpha\left(tp_{\mathcal{K}^{n+1}}\left(i_1, \dots, i_m; \bar{I}^{n+1}_\alpha\right)\right)\]

Now we can thin out and collapse these structures as before: each \(c^{*, n+1}_\alpha\) is a function \(\text{S}^{inc, \leq n+1}_{\mathcal{K}^{n+1}}\to \text{S}^{\leq n+1}_\tau\) and there are less than \(\text{cf }(g(\mu)^+)=g(\mu)^+\) of these, so there is \(X \subseteq g(\mu)^+\) of size \(g(\mu)^+\) and \(c^{*, n+1}:\text{S}^{inc, \leq n+1}_{\mathcal{K}^{n+1}}\to\text{S}^{\leq n+1}_\tau\) such that \(c^{*, n+1} = c^{*, n+1}_\alpha\) for all \(\alpha \in X\).

Set \(\pi:X \cong g(\mu)^+\) to be the collapse. Now define the following:

• \(\Phi_{n+1} = c^{*, n+1}\);

• \(\beta_{n+1}(\alpha) = \beta_n(\pi^{-1}(\alpha)+1)\);

• \(\gamma_{n+1}(\alpha) = \pi^{-1}(\alpha)+1\);

• \(I^{n+1}_\alpha = \bar{I}^{n+1}_{\pi^{-1}(\alpha)} \in \mathcal{K}^{n+1}\) is \(\daleth_{\pi^{-1}(\alpha)}\)-big (and therefore \(\daleth_\alpha\)-big);

• \(h^{n+1}_\alpha = \bar{h}^{n+1}_{\pi^{-1}(\alpha)} \upharpoonright\left(I^{n+1}_\alpha \upharpoonright n\right)\);

• \(g^{n+1}_\alpha = \hat{g}^{n+1}_{\pi^{-1}(\alpha)+1} \circ \bar{h}^{n+1}_{\pi^{-1}(\alpha)}\); and

• \(f^{n+1}_\alpha = f_{\beta_n\left(\pi^{-1}(\alpha)+1\right)}\circ \hat{g}^{n+1}_{\pi^{-1}(\alpha)+1} \circ \bar{h}^{n+1}_{\pi^{-1}(\alpha)}\), where we could have written the first composite as ‘\(f_{\beta_n\left(\pi^{-1}(\alpha)+1\right)}\upharpoonright\left(I_{\beta_n\left(\pi^{-1}(\alpha)+1\right)}\upharpoonright(n+1)\right)\)’ for more precision and more notation.

Now we verify the various conditions of our construction:

1. This is only relevant to the base case.

2. Let \(\alpha < g(\mu)^+\) and \(i_1<\dots<i_m\in I^{n+1}_\alpha=\bar{I}^{n+1}_{\pi^{-1}(\alpha)}\) with \(m \leq n+1\). Then \(\pi^{-1}(\alpha)\in X\), so \(\Phi_{n+1}=c^{*, n+1} = c^{*, n+1}_{\pi^{-1}(\alpha)}\) witnesses the type-homogeneity of \(\bar{I}^{n+1}_{\pi^{-1}(\alpha)}\) for \(c^{n+1}_{\pi^{-1}(\alpha)}\). Thus, we compute \[\begin{align} \Phi_{n+1}\left(tp_{\mathcal{K}^{n+1}}\left(i_1, \dots, i_m; I^{n+1}_\alpha\right)\right) &=& c^{*, n+1}_{\pi^{-1}(\alpha)}\left( tp_{\mathcal{K}^{n+1}}\left(i_1, \dots, i_m; \bar{I}^{n+1}_{\pi^{-1}(\alpha)}\right)\right)\\ &=& c^{n+1}_{\pi^{-1}(\alpha)} \left( \left\{ \bar{h}^{n+1}_{\pi^{-1}(\alpha)}(i_1), \dots,\bar{h}^{n+1}_{\pi^{-1}(\alpha)}(i_m)\right\}\right)\\ &=& tp_\tau\left(f_{\beta_n(\pi^{-1}(\alpha)+1)}\circ\hat{g}^{n+1}_{\pi^{-1}(\alpha)+1}\circ \bar{h}^{n+1}_{\pi^{-1}(\alpha)}(i_1), \dots,\right.\\ & &\left.f_{\beta_n(\pi^{-1}(\alpha)+1)}\circ\hat{g}^{n+1}_{\pi^{-1}(\alpha)+1}\circ \bar{h}^{n+1}_{\pi^{-1}(\alpha)}(i_m);M_{\beta_n(\pi^{-1}(\alpha)+1)} \right)\\ &=& tp_\tau\left(f^{n+1}_\alpha(i_1), \dots, f^{n+1}_{\alpha}(i_m);M_{\beta_{n+1}(\alpha)}\right) \end{align}\] as desired.

3. 1. This follows from condition ([phi-cond39]), but to be explicit: let \(p \in \text{S}^{inc, \leq n+1}_{\mathcal{K}^{n+1}}\) and \(s \subseteq m = \ell(p)\). Fix some/any \(\alpha < g(\mu)^+\) and \(i_1<\dots<i_m \in I^{n+1}_\alpha\) such that \[p=tp_{\mathcal{K}^{n+1}}\left(i_1, \dots, i_m; I^{n+1}_\alpha\right)\] If we write \(s = \{i_{j_1}, \dots, i_{j_\ell}\}\), then \[\begin{align} \Phi_{n+1}(p^s) &=& tp_\tau\left(f_\alpha^{n+1}(i_{j_1}), \dots, f^{n+1}_\alpha(i_{j_\ell}); M_{\beta_{n+1}(\alpha)}\right)\text{ by condition (\ref{phi-cond39})}\\ \Phi_{n+1}(p) &=& tp_\tau\left(f^{n+1}_\alpha(i_1), \dots, f_{\alpha}^{n+1}(i_m) ; M_{\beta_{n+1}(\alpha)}\right) \text{ by condition (\ref{phi-cond39})}\\ \Phi_{n+1}(p)^s &=& tp_\tau\left(f_\alpha^{n+1}(i_{j_1}), \dots, f^{n+1}_\alpha(i_{j_\ell}); M_{\beta_{n+1}(\alpha)}\right)\text{ by definition of this operation} \end{align}\] So \(\Phi_{n+1}(p^s) = \Phi_{n+1}(p)^s\) as desired.

   2. Suppose \(p \in \text{S}^{inc, \leq n+1}_{\mathcal{K}^{n+1}}\) has a unique extension to \(p^* \in \text{S}_\mathcal{K}^{inc, \leq n+1}\) with \(k_{p^*}\leq n+1\).
      If \(k_{p^*} = n+1\), then \[\Phi_{k_{p^*}}(p\upharpoonright k_{p^*}) = \Phi_{n+1}\left(p \upharpoonright(n+1)\right) = \Phi_{n+1}(p)\] If \(k_{p^*} \leq n\), then \(p^*\) is also the unique extension of \(p\upharpoonright n\). By induction, we have \[\Phi_{k_{p^*}}((p\upharpoonright n)\upharpoonright k_{p^*}) = \Phi_{k_{p^*}}(p\upharpoonright k_{p^*}) = \Phi_n(p\upharpoonright n)\] Let \(\alpha<g(\mu)^+\) and \(i_1<\dots<i_m \in I^{n+1}_\alpha\) such that \[p =tp_{\mathcal{K}^{n+1}}(i_1, \dots,i_m; I^{n+1}_\alpha)\] Since \(k_{p^*}\leq n\), \(i_1, \dots,i_m\in I^{n+1}_\alpha\upharpoonright n\) by Definition 30.[endex-def-colimit].(c). Thus, \(h_\alpha^{n+1}(i_1), \dots, h_\alpha^{n+1}(i_m)\in I^n_{\gamma_{n+1}(\alpha)}\). Then we have \[\begin{align} p\upharpoonright n &=& tp_{\mathcal{K}^n} (i_1, \dots, i_m; I_\alpha^{n+1}\upharpoonright n)\\ &=& tp_{\mathcal{K}^n}(h^{n+1}_\alpha(i_1), \dots, h_\alpha^{n+1}(i_m); I^n_{\gamma_{n+1}(\alpha)}) \end{align}\] Thus, by condition ([phi-cond39]) applied at \(n\) and \(n+1\) (since we have already proved it in this induction), we have \[\begin{align} \Phi_n(p\upharpoonright n) &=&tp_\tau\left(f^n_{\gamma_{n+1}(\alpha)}\left(h^{n+1}_\alpha(i_1)\right), \dots, f^n_{\gamma_{n+1}(\alpha)}\left(h^{n+1}_\alpha(i_m)\right);M_{\beta_{n}\left(\gamma_{n+1}(\alpha)\right)}\right)\\ \Phi_{n+1}(p) &=& tp_\tau \left(f_\alpha^{n+1}(i_1), \dots,f_\alpha^{n+1}(i_m); M_{\beta_{n+1}(\alpha)}\right) \end{align}\] These types on the right-hand side are the same: \(M_{\beta_{n+1}(\alpha)}=M_{\beta_n\left(\gamma_{n+1}(\alpha)\right)}\) by construction and by (the independently proven) condition ([diag-cond39]).([diag-cond39-2]), \[f^{n+1}_\alpha = f^n_{\gamma_{n+1}(\alpha)}\circ h^{n+1}_\alpha \text{ on }I^{n+1}_\alpha \upharpoonright n\] Thus we have shown the desired equality \[\Phi_{n+1}(p) = \Phi_n(p\upharpoonright n) = \Phi_{k_{p^*}}(p\upharpoonright k_{p^*})\]

4. for \(\alpha < g(\mu)^+\) and \(n<\omega\),

   1. we have \[\begin{align} \beta_{n+1}(\alpha) &=& \beta_{n}\left(\pi^{-1}(\alpha)+1\right) \geq \pi^{-1}(\alpha)+1>\alpha\\ \gamma_{n+1}(\alpha) &=& \pi^{-1}(\alpha)+1 > \alpha \end{align}\]

   2. to show the diagram commutes, we repeat the desired diagram and make substitutions for the definitions above \[\begin{tikzcd} {I_{\beta_{n}(\pi^{-1}(\alpha)+1)} \upharpoonright n} &&&& {M_{\beta_{n}(\pi^{-1}(\alpha)+1)}} \\ \\ && {I^n_{\pi^{-1}(\alpha)+1}} \\ \\ && {\bar{I}^{n+1}_{\pi^{-1}(\alpha)} \upharpoonright n} \arrow["{f_{\beta_{n}(\pi^{-1}(\alpha)+1)}\upharpoonright\left(I_{\beta_{n}(\pi^{-1}(\alpha)+1)} \upharpoonright n\right)}", curve={height=-24pt}, from=1-1, to=1-5] \arrow["{g^n_{\pi^{-1}(\alpha)+1}}"', from=3-3, to=1-1] \arrow["{f^n_{\pi^{-1}(\alpha)+1}}", from=3-3, to=1-5] \arrow["{\left(\hat{g}^{n+1}_{\pi^{-1}(\alpha)+1} \circ \bar{h}^{n+1}_{\pi^{-1}(\alpha)}\right) \upharpoonright\left(\bar{I}^{n+1}_{\pi^{-1}(\alpha)} \upharpoonright n\right)}", curve={height=-24pt}, from=5-3, to=1-1] \arrow["{\left(f_{\beta_n(\pi^{-1}(\alpha)+1)}\circ \hat{g}^{n+1}_{\pi^{-1}(\alpha)+1}\circ \bar{h}^{n+1}_{\pi^{-1}(\alpha)}\right)\upharpoonright\bar{I}^{n+1}_{\pi^{-1}(\alpha)}}"', curve={height=24pt}, from=5-3, to=1-5] \arrow["{\bar{h}^{n+1}_{\pi^{-1}(\alpha)} \upharpoonright\bar{I}^{n+1}_{\pi^{-1}(\alpha)}}", from=5-3, to=3-3] \end{tikzcd}\] First note that the upper triangle commutes by the inductive assumption and the outer triangle commutes by definition. The lower left triangle commutes by the lifting property: \[\hat{g}^{n+1}_{\pi^{-1}(\alpha)+1} \upharpoonright\left(I^n_{\pi^{-1}(\alpha)+1}\right) = g^{n}_{\pi^{-1}(\alpha)+1}\] Since the other parts of the diagram commute, the commutation of the lower right triangle follows (although it could be shown directly).

Thus, while we have no combinatorial partition result for \(\mathcal{K}^{\omega-tr}\), it is an Erdős-Rado class.

Proof: By Theorem 7 applied to Proposition 31.

6 Applications↩︎

6.1 Unsuperstability in Abstract Elementary Classes↩︎

In countable first-order theories, strict stability can detected by counting types at cardinals \(\lambda\) satisfying \(\lambda<\lambda^\omega\):

This is done by building what is called a ‘Shelah tree’ [43]. This is a way of embedding the \(\omega+1\)-height tree \({}^{\leq \omega}\lambda\) into a model of \(T\) so the types of branches are differentiated over their initial segments. In the context of nonelementary classes, Baldwin and Shelah [18] generalized this to atomic classes by use of \(\mathcal{K}^{\omega-tr}\)-indiscernibles.

Here, we generalize this to tame Abstract Elementary Classes with amalgamation. Note that we break our convention of always using types over the empty set here. In fact, we will consider types over arbitrary sets. Given \(N \in \mathbb{K}\), \(a \in N\), and \(B \subseteq N\), we write \[tp_\mathbb{K}(a/B; N)\] for the equivalence class of triples where the equivalence relation in Definition 4 is required to fix the parameter set \(B\) as well. The presence of amalgamation means that we can always witness \(\mathbb{K}\)-type equality with \(n=1\) in Definition 4.(1). Since we lack a monster model, we fix an ambient model \(N\) to give meaning to \(B\). Then \(\text{S}_{\mathbb{K}}(B; N)\) is the collection of all Galois types over \(B\) as seen as a set in \(N\) and we write \(\text{S}_\mathbb{K}(N)\) for \(\text{S}_\mathbb{K}(N;N)\). We say that \(\mathbb{K}\) is Galois stable in \(\lambda \geq \text{LS}(\mathbb{K})\) iff for every \(M \in \mathbb{K}_\lambda\), we have \(|\text{S}_\mathbb{K}(M)|\leq \lambda\) and Galois unstable in \(\lambda\) for the negation of that statement. We omit other basics of Abstract Elementary Classes, but the key definitions can be found in one of [15], [44], [45].

The first case roughly corresponds to Galois superstability, while the second is not superstable. However, the necessary involvement of \(\|M\|^{<\kappa}\) in the type counting (as opposed to just \(\|M\|\)) makes comparison with other results awkward. Here we state two corollaries that rephrase the result directly in terms of Galois stability:

The subscript ‘\(\left(2^{\kappa+\text{LS}(\mathbb{K})}\right)^+\)’ can be replaced by the relevant undefinability of well-ordering number. This fits into the project summarized in [46]: while superstability for arbitrary Abstract Elementary Classes seems poorly behaved (exhibiting what Shelah terms ‘schizophrenia’ [17]), superstability in the context of tame Abstract Elementary Classes with amalgamation is much better behaved. Vasey [47] computes stability spectra of Abstract Elementary Classes. For tame classes with amalgamation, [47] uses a technical analysis of nonsplitting to show that failure of ‘\(\mathbb{K}\) is Galois stable on a tail’ implies \(\chi(\mathbb{K}) > \omega\) and [47] shows that for ‘most \(\lambda\),’ \(\text{cf }\lambda < \chi(\mathbb{K})\) implies \(\mathbb{K}\) is Galois unstable in \(\lambda\); ‘most \(\lambda\)’ means all sufficiently large, almost \(\lambda(\mathbb{K})\)-closed cardinals. Theorem 8 offers a tighter bound on when the tail of stability must start and also a better condition on where the instability must happen.

Allowing for \(\kappa \leq \text{LS}(\mathbb{K})\), especially the case \(\kappa = \omega\) is important because of the requirement that \(\lambda^{<\kappa}=\lambda\) in (1) of Theorem 8. This allows us to recover comparisons to first-order results and [18].

Our proof follows [18], but adapts the argument to Abstract Elementary Classes. The following notion of type fragments will make our argument smoother. These are essentially the partial Galois types that allow us to specify extending or not extending small Galois types. This is motivated by the idea that small Galois types should occasionally be able to stand in for formulas in tame AECs (e.g., [48] or Vasey’s Galois Morleyization [49]).

We fix some important notation for this section: given \(q\in \text{S}_\mathbb{K}(A; N)\), we write \[\begin{align} q^0 := q \\ q^1 := \neg q \end{align}\]

In the following, we will want consider the number of types of length \(<\kappa\) over the empty set. We have \[\text{S}_{\mathbb{K}}^{<\kappa}(\emptyset) = \bigcup_{M \in \mathbb{K}_{\kappa^*}} \text{S}_{\mathbb{K}}^{<\kappa}(\emptyset; M)\] and can bound it’s size by \[|\text{S}_{\mathbb{K}}^{<\kappa}(\emptyset)| \leq \left(2^{\kappa^*}\right)^{<\kappa}\]

The following is similar to an argument of Baldwin-Kueker-VanDieren [50] (see [15]), generalizing first-order arguments of Morley. It will give us more than we need.

Proof: If not, then for every \(B \in \mathcal{P}_\kappa A\), there is a unique \(q_B \in \text{S}_\mathbb{K}(B; N)\) that has many extensions to \(\Gamma\). Then every \(p \in \Gamma\) falls into one of two categories:

1. \(p \geq q_B\) for all \(B \in \mathcal{P}_\kappa A\); or

2. there is \(B \in \mathcal{P}_\kappa A\) such that \(p \not \geq q_B\).

By tameness, there is at most one type of the first kind. For each \(B\), there are \(\leq |A|^{<\kappa}\)-many types of the second kind by the choice of \(q_B\) and there are \(|A|^{<\kappa}\)-many such \(B\)’s. Thus, there are \(\leq |A|^{<\kappa}\)-many types of the second kind, which contradicts that there are at least \((|A|^{<\kappa})^+\)-many types in \(\Gamma\).

Proof: We will construct

1. a tree \(T \subseteq{}^{\leq\mu} 2\);

2. types \(\{q_\eta(x; X) \in \text{S}^{<\kappa}_\mathbb{K}(\emptyset) : \eta \in T\}\);

3. sets \(\{A^\eta \in \mathcal{P}_\kappa M:\eta \in T\}\); and

4. type fragments¹⁴ \[\Sigma_\eta := \{q_{\eta \upharpoonright j}(x; A^{\eta\upharpoonright j})^{\eta(j)} : j < \ell(\eta)\}\] for \(\eta \in T\)

such that for each \(i \leq \mu\):

1. every level \(T_i\) of \(T\) is nonempty (in particular, there is a branch \(\eta \in T_\mu\));

2. if \(\eta \in T_i\), then the type fragment \(\Sigma_{\eta}\) is contained in at least \(\left(\|M\|^{<\kappa}\right)^+\)-many of the types in \(\Gamma\); and

3. every node on level \(T_i\) splits.

This is enough: Pick \(\eta \in T_\mu\). Since \(\mu > |\text{S}_{\mathbb{K}}^{<\kappa}(\emptyset)|\), there is some \(X \in [\mu]^\mu\), \(q \in \text{S}^{<\kappa}_\mathbb{K}(\emptyset)\), and \(k \in 2\) such that \(q = q_{\eta\upharpoonright j}\) and \(\eta(j) = k\) for all \(j \in X\). Write \(\pi:X \to \mu\) for the Mostowski collapse and set \[A^i:=A^{\eta\upharpoonright\pi^{-1}(i)}\] If \(k = 0\), we are in the first case; if \(k = 1\), we are in the second case. We give the details of the first case, and the second is similar. Suppose \(k=0\) and fix \(j_1<\mu\). We define the node just off the branch \(\eta\) at height \(\pi^{-1}(j_1)\) \[\nu = \left(\eta \upharpoonright\pi^{-1}(j_1)\right){}^\frown\langle 1 \rangle \in {}^{\pi^{-1}(j_1)+1} 2\] We have that \(\eta \upharpoonright\pi^{-1}(j_1) \in T\), so \(\nu \in T\) by condition ([split-cond]). Thus, the fragment \(\Sigma_\nu\) is contained in at least \((\|M\|^{<\kappa})^+\)-many types in \(\Gamma\) by condition ([frag-con]). The goal now is to show that the condition in item (1) of the lemma statement are contained in the fragment \(\Sigma_\nu\).

If \(j_0<j_1\), then \(\eta\upharpoonright\pi^{-1}(j_0) = \nu\upharpoonright\pi^{-1}(j_0)\), so \[q_{\eta\upharpoonright\pi^{-1}(j_0)}(x; A_{\eta \upharpoonright\pi^{-1}(j_0)})^{\eta(\pi^{-1}(j_0))} = q(x; A_{j_0})^0 = q(x; A_{j_0})\in \Sigma_\nu\] For \(j_1\), we similarly have \[q_{\eta\upharpoonright\pi^{-1}(j_1)}(x; A_{\eta \upharpoonright\pi^{-1}(j_1)})^{\nu(\pi^{-1}(j_1))} = q(x; A_{j_1})^1 = \neg q(x; A_{j_1})\in \Sigma_\nu\]

Construction: We work by induction on levels \(i \leq \mu\). At each, we will also guarantee that \(\Sigma_{\eta^\frown\langle 0 \rangle}\) and \(\Sigma_{\eta^\frown\langle 1 \rangle}\) satisfy condition ([frag-con]) since they are defined at that stage.

For \(i = 0\), we apply Lemma 1 to \(\Gamma\) to find \(A^\emptyset\in \mathcal{P}_\kappa M\) and \(q_\emptyset(x; A^\emptyset)\neq r(x;A^\emptyset) \in \text{S}_\mathbb{K}(A^\emptyset; M)\) such that both types extend to at least \((\|M\|^{<\kappa})^+\)-many types in \(\Gamma\). Then we have that \(\Sigma_{\langle 0 \rangle} = \{q_\emptyset(x; A^\emptyset)\}\) and \(\Sigma_{\langle 1 \rangle} = \{ \neg q_\emptyset(x; A^\emptyset)\}\), with the latter satisfying our conditions because every type extending \(r\) extends \(\Sigma_{\langle 1 \rangle}\).

For \(i = j+1\), for each \(\eta \in T_i\) we follow the same strategy except we apply Lemma 1 to the elements of \(\Gamma\) extending \(\Sigma_\eta\). This gives \(A^\eta \in \mathcal{P}_\kappa M\) and \(q_\eta(x; A^\eta) \neq r(x;A^\eta) \in \text{S}_\mathbb{K}(A^\eta)\) that satisfy the requirements of the construction.

At limit stage \(i\), we note that every type \(p_\alpha\) (or more generally, every \(p \in \text{S}_\mathbb{K}(M)\)) extends one of our type fragments \(\Sigma_\eta\) for \(\eta \in {}^i 2\). There are \(\leq2^i\) many branches at this stage, and at least \(\left(\|M\|^{<\kappa}\right)^+>2^\mu\geq 2^i\)-many \(p_\alpha\)’s, so there must be some \(\eta \in {}^i 2\) so many of them extend \(\Sigma_\eta\); then set \(T_i\) to be the collection of all such \(\eta\). Once again, we apply Lemma 1 to the elements of \(\Gamma\)-extending \(\Sigma_\eta\) to define \(A^\eta\) and \(q_\eta\).

The following lemma is the key inductive step that allows us to build our tree of types.

Proof: We do this by induction. For the base case \(n=0\), we pick \(M_0 \prec_\mathbb{K}M\) and \(A^{\langle \rangle} \in \mathcal{P}^*_\kappa M_0\) arbitrarily, then use the pigeonhole principle to find \(q_{\langle \rangle} \in \text{S}_\mathbb{K}(M_0)\) with at least \(\left(\|M\|^{<\kappa}\right)^+\)-many extensions of \(\text{S}_{\mathbb{K}}(M)\).

Given stage \(n\), we know that each \(q_\nu\) for \(\nu \in {}^n \mu\) has at least \(\left(\|M\|^{<\kappa}\right)^+\)-many extensions to \(\text{S}_\mathbb{K}(M)\) and \(\|M\| \geq 2^\mu\). So we can apply Lemma 2 to get \(q(x;Y) \in \text{S}_\mathbb{K}^{<\kappa}(\emptyset)\) and \(\{A^i_\nu \in \mathcal{P}_\kappa M: i < \mu\}\) and \(\ell_\nu \in \{0,1\}\) such that

Set \(A_{\nu^\frown\langle i \rangle} = A^i_\nu\).

Let \(M_{n+1} \prec M\) contain \(M_n\) and \(\bigcup_{\rho \in {}^{n+1}\mu} A_\rho\) of size \(\mu\). For each \(i < \mu\), set \[\Sigma'_{\nu, i}:= q_\nu \cup\{q(x; A^{i})^{1-\ell_\nu}, q(x; A^{j})^{\ell_\nu} : j < i\}\] This is a consistent type fragment over \(M\) by definition that can be extended to at least \(\left(\|M\|^{<\kappa}\right)^+\)-many types over \(M\). Since there are at most \(2^\mu\) extensions of \(\Sigma'_{\nu, i}\) to \(\text{S}_{\mathbb{K}}(M_{n+1})\) and \(2^\mu < \left(\|M\|^{<\kappa}\right)^+\), the pigeonhole principle says we can extend \(\Sigma'_{\nu, i}\) to a type \(q_{\nu^\frown\langle i \rangle} \in \text{S}_\mathbb{K}(M_{n+1})\) that can be extended to at least \(\left(\|M\|^{<\kappa}\right)^+\)-many types over \(M\).

By the saturation of \(\hat{M}\), we can find \(a_\nu \in \hat{M}\) realizing \(p_\nu\) for each \(\nu \in {}^{<\omega}\mu\).
The following is an easy but useful fact before we begin the proof of the main theorem of this section.

Recall Shelah’s Presentation Theorem ([10] or [51] for a longer discussion). Given an AEC \(\mathbb{K}\), it expands the lanuage by functions indexed by \(\text{LS}(\mathbb{K})\times\omega\) and gives an infinitary theory \(T\) in the expanded langauge that captures both membership in \(\mathbb{K}\) and the strong substructure relation \(\prec\). However, it behaves like a Skolemization and can’t necessarily capture every strong substructure relation simultaneously (although you can do so with a given chain). In the following proof, we have a vast array of strong substructures that we want to code into the language by use of presentation functions. We resolve this tension by introducing disjoint copies of this expanded language (often with parameters) to capture the different strong substructure relations we need. We use the phrase ‘a collection of presentation functions witnessing \(M\prec N\)’ to refer to a collection of functions (possibly with constant parameters) indexed by \(\kappa^*\times \omega\) such that

• the expansion by these functions satisfies the translation of the presentation theory \(T\) to this language; and

• the models mentioned are closed under the functions.

This will ensure that any model of the translated theory (including generalized EM models, following the proof in Theorem 2) will satisfy the appropriate strong substructure relations.
Proof of Theorem 8: Recall \(\kappa^* = \kappa +\text{LS}(\mathbb{K})\) and Hypothesis 33. For the proof, suppose that (1) fails. Then, for every \(\alpha < (2^{\kappa_*})^+\), there is \(M^\alpha \in \mathbb{K}_{\geq \beth_{\alpha+1}}\) such that \[|\text{S}_\mathbb{K}(M^\alpha)| \geq \left(\|M^\alpha\|^{<\kappa}\right)^+\] We are going to build a blueprint \(\Upsilon^{\omega-tr}[\mathbb{K}]\) in the language \[\tau_+:=\tau(\mathbb{K}) \cup\{f_\gamma, H, F_{k, \beta}, G_{k, \beta}, G_{0, \beta, k}, G_{1, \beta, k}, h_0\mid \gamma < \kappa, k<\omega, \beta<\kappa_*\}\] such that the \(f_\gamma\) and \(H\) are unary; the \(G_{1, \beta, k}\) are binary; \(h_0\) is ternary; the \(F_{\beta, k}\) are \(k\)-ary; the \(G_{\beta, k}\) are \((k+1)\)-ary; and the \(G_{0, \beta, k}\) are \((k+2)\)-ary.

Now we build, for each \(\alpha < (2^{\kappa_*})^+\), the \(\tau_+\)-structure \(M^\alpha_+\) which will satisfy \(M^\alpha \prec \left(M^\alpha_+\upharpoonright\tau(\mathbb{K})\right)\) (and much more). Towards this end, fix \(\alpha < (2^{\kappa_*})^+\) and set \(\mu_\alpha = \beth_\alpha\); WLOG, \(\mu_\alpha > |\text{S}^{<\kappa}_{\mathbb{K}}(\emptyset)|\). We can use amalgamation to find \(\hat{M}^\alpha \succ M^\alpha\) that is \(\mu_\alpha^+\)-saturated; this will be the restriction of \(M^\alpha_+\) to \(\tau(\mathbb{K})\). Now we can apply Lemma 3 to find \(\prec\)-increasing models \(\{M^\alpha_n\in \mathbb{K}_{\mu_\alpha} : n <\omega\}\); types \(\{q^\alpha_\nu \in \text{S}_\mathbb{K}(M^\alpha_n): n<\omega, \nu \in{}^n \mu_\alpha\}\); sets \(\{A^\alpha_\nu \in \mathcal{P}_\kappa M^\alpha_n : n<\omega, \nu \in {}^n \mu_\alpha\}\); and elements \(\{a^\alpha_\nu \in \hat{M}^\alpha : \nu \in {}^{<\omega}\mu_\alpha\}\) such that

1. \(M^\alpha_n \prec M^\alpha\) for all \(n<\omega\);

2. each \(q^\alpha_\nu\) has at least \((\|M^\alpha\|^{<\kappa})^{+}\)-many extensions to \(\text{S}_\mathbb{K}(M^\alpha)\) with \(a^\alpha_\nu \vDash q^\alpha_\nu\);

3. if \(\nu < \eta\), then \[q^\alpha_\nu \leq q^\alpha_\eta\]

4. if \(\nu\in {}^{<\omega}\mu\) and \(i<j<\mu\), then \[q^\alpha_{\nu{}^\frown \{i\}} \upharpoonright A^\alpha_{\nu{}^\frown \{i\}} \ne q^\alpha_{\nu{}^\frown\{j\}}\upharpoonright A^\alpha_{\nu{}^\frown\{i\}}\]

Now we will define some auxilliary models and functions. For the most part, we are defining small witnesses for the various phenomena listed above, and then adding parameterized presentation functions to capture those structures in the blueprint. When we define the expansions, we define them partially to capture the structure we want, and then implicitly expand their domain arbitrarily.

1. For each \(\nu \in {}^{<\omega}\mu_\alpha\), pick an arbitray element \(b^\alpha_\nu \in M^\alpha_{\ell(\nu)}\).

2. Define \(\{f^\alpha_\gamma(b^\alpha_\nu):\gamma < \kappa\}\) to be an enumeration of \(A^\alpha_\nu\) (with repetition); \(H^\alpha(b^\alpha_\nu) = a^\alpha_\nu\); and \(\{F^\alpha_{\beta, k}:\beta<\kappa^*, k<\omega\}\) be a collection of presentation functions such that

   1. each \(M^\alpha_n\) and \(M^\alpha\) are closed under them (which witnesses \(M^\alpha_n\prec M^\alpha \prec \hat{M}^\alpha\)); and

   2. each \(M^\alpha_n\) is the closure under \(\{b^\alpha_\nu:\nu\in {}^n \mu_\alpha\}\) under these functions.

3. For each \(\nu \in {}^{<\omega}\mu_\alpha\), find \(\bar{M}^\alpha_\nu \prec \hat{M}^\alpha\) of size \(\mu_\alpha\) containing \(a^\alpha_\nu\) and \(M^\alpha_\ell(\nu)\). Thus \[\begin{align} q^\alpha_\nu = tp_\mathbb{K}(a^\alpha_\nu/M^\alpha_{\ell(\nu)}; \hat{M}^\alpha) = tp_\mathbb{K}(a^\alpha_\nu/M^\alpha_{\ell(\nu)}; \bar{M}^\alpha_\nu) \end{align}\] Then set \(\{G^\alpha_{\beta,k}(\boldsymbol{x}, b^\alpha_\nu):\beta<\kappa^*, k<\omega\}\) to be presentation functions witnessing that \(\bar{M}^\alpha_\nu \prec \hat{M}^\alpha\).

4. For each \(\nu < \eta \in {}^{<\omega}\mu_\alpha\), we have \[\begin{align} q^\alpha_\nu &=& q^\alpha_\eta\upharpoonright M^\alpha_{\ell(\nu)}\\ tp_\mathbb{K}(a^\alpha_\nu/M^\alpha_{\ell(\nu)}; \bar{M}^\alpha_\nu) &=&tp_\mathbb{K}(a^\alpha_\eta/M^\alpha_{\ell(\nu)}; \bar{M}^\alpha_\eta) \end{align}\] By Proposition 35, there is \(\bar{M}_{0,(\nu, \eta)}\prec\hat{M}^\alpha\) of size \(\mu_\alpha\) containing \(a^\alpha_\nu\) and \(M^\alpha_\nu\) and \(h^\alpha_{0, (\nu, \eta)}: \bar{M}^\alpha_\eta \to\bar{M}^\alpha_{0,(\nu, \eta)}\) that fixes \(M^\alpha_{\ell(\nu)}\) and so \(h^\alpha_{0, (\nu, \eta)}(a^\alpha_\eta) = a^\alpha_\nu\). Define \[h^\alpha(x, b^\alpha_\nu, b^\alpha_\eta) := h^\alpha_{0, (\nu, \eta)}(x)\] and \(\{G^\alpha_{0, \beta, k}(\boldsymbol{x}, \eta, \nu):\beta<\kappa^*, k<\omega\}\) be presentation functions witnessing \(h^\alpha_{0, (\nu, \eta)}(\bar{M}^\alpha_\eta)\prec\bar{M}^\alpha_{0, (\nu, \eta)} \prec \hat{M}^\alpha\) (note that \(\bar{M}^\alpha_\nu\prec\bar{M}^\alpha_{0, (\nu, \eta)}\) will be guaranteed by the presentation functions \(G^\alpha_{\beta,k}(\boldsymbol{x}, b^\alpha_\nu)\) and coherence).

5. For each \(\nu \neq \eta \in {}^n\omega_\alpha\) with \(\rho = \nu\upharpoonright(n-1)=\eta\upharpoonright(n-1)\) and \(\nu(n-1)<\eta(n-1)\), we know that \[tp_\mathbb{K}(a^\alpha_\nu/A^\alpha_\nu; \hat{M}^\alpha) \neq tp_\mathbb{K}(a^\alpha_\eta/A^\alpha_\nu; \hat{M}^\alpha)\] Fix \(\bar{M}^\alpha_{1, (\eta, \nu)} \prec \hat{M}^\alpha\) of size \(\kappa^*\) that contains \(a^\alpha_\eta, a^\alpha_\nu\) and \(A^\alpha_\nu\) and is closed under the functions \(F^\alpha_{\beta,k}\) for \(\beta<\kappa^*\), \(k<\omega\). Define \(\{G^\alpha_{1,\beta, k}(b^\alpha_\nu, b^\alpha_\eta):\beta<\kappa^*, k<\omega\}\) to be an enumeration of \(\bar{M}^\alpha_{1, (\nu, \eta)}\).

Now we define the expansion \(M^\alpha_+\) of \(\hat{M}^\alpha\) to the language \(\tau_+\): the expansion is the one suggested by the notation \[\begin{align} f^{M^\alpha_+}_\gamma &:=& f^\alpha_\gamma\\ H^{M^\alpha_+} &:=& H^\alpha\\ &\text{etc.}& \end{align}\] along with any necessary expansion of these to be full functions (rather than partial).

Now for each \(\alpha <(2^{\kappa^*})^+\), we have a \(\tau_+\)-structure \(M^\alpha_+\) along with an embedding \[\begin{align} {}^{<\omega}\beth_\alpha &\to& M^\alpha_+\\ \nu &\mapsto& b^\alpha_\nu \end{align}\] Since \(\mathcal{K}^{\omega-tr}\) is a cofinal Erdős-Rado Class (Corollary 2), we can build a blueprint \(\Phi \in \Upsilon^{\omega-tr}_{\kappa^*}[\mathbb{K}]\) that is modeled off this embedding. Given \(\lambda\geq \kappa^*=\kappa+\text{LS}(\mathbb{K})\), set \(T^\lambda\) to be the \(\mathcal{K}^{\omega-tr}\)-structure built on \({}^{<\omega} \lambda\) in the normal way. We then read off the various structures we have built:

1. \(N^\lambda_+:= EM(T^\lambda, \Phi)\)

2. \(\hat{N}^\lambda = EM_{\tau(\mathbb{K})}(T^\lambda, \Phi) \in \mathbb{K}\)

3. \(N^\lambda_n\) is the substructure of \(N^\lambda\) generated by \(\{\nu: \nu\in {}^n \lambda\}\) with \(N^\lambda_n\prec \hat{N}^\lambda\)

4. \(N^\lambda_\omega = \bigcup_{n<\omega} N^\lambda_n \prec \hat{N}^\lambda\)

5. For \(\nu \in {}^{<\omega}\lambda\), set \[B^\lambda_\nu:=\{f^{N^\lambda_+}_\gamma(\nu):\gamma<\kappa^*\}\]

First, note that \(\|N^\lambda_n\| = \lambda+\kappa^*=\lambda\) since it is generated by \(\lambda\)-many elements under \(\kappa^*\)-many functions. Then \(\|N^\lambda_\omega\|=\lambda\) as well. Now we wish to construct our \(\lambda^\omega\)-many distinct types. Unsurprisingly, they will come from the branches of the tree \({}^{<\omega}\lambda\). As we do so, remember that the elements of \({}^{<\omega}\lambda\) are also elements of \(N^\lambda_+\) and generate that model under the functions of \(\Phi\).

For each \(\rho \in {}^{<\omega}\lambda\), define \[p^\lambda_\rho:=tp_\mathbb{K}\left(H^{N^\lambda_+}(\rho)/N_n^\lambda; \hat{N}^\lambda\right)\] We have two key claims, both of which are guaranteed by coding the necessary information in the \(\tau_+\)-structure.

Claim 1: Given \(\nu < \eta \in {}^{<\omega} \lambda\), \[p^\lambda_\nu = p^\lambda_\eta \upharpoonright N^\lambda_{\ell(\nu)}\] Proof:. Define \(\tau(\mathbb{K})\)-structures as given by their universes below \[\begin{align} \bar{N}^\lambda_\nu&:=& \left\{G^{N^\lambda_+}_{\beta, k}\left(\boldsymbol{m}, \nu\right):\beta<\kappa^*, k<\omega, \boldsymbol{m}\in \left(\left\{H^\lambda(\nu)\right\}\cup N^\lambda_{\ell(\nu)}\right)\right\}\prec N^\lambda\\ \bar{N}^\lambda_{0, (\nu, \eta)}&:=&\left\{G^{N^\lambda_+}_{0,\beta, k}\left(\boldsymbol{m}, \nu, \eta\right):\beta<\kappa^*, k<\omega, \boldsymbol{m}\in \left(\left\{H^\lambda(\nu)\right\}\cup N^\lambda_{\ell(\nu)}\right)\right\}\prec N^\lambda\\ h^\lambda_{0, (\nu, \eta)}(x)&:=&h^{N^\lambda_+}(x, \nu, \eta) \end{align}\] By the modeling property, since they are true at each \(\alpha < (2^{\kappa^*})^+\), we have

1. \(N^\lambda_{\ell(\nu)} \prec \bar{N}^\lambda_\nu \prec \bar{N}^\lambda_{0, (\nu, \eta)}\)

2. \(N^\lambda_{\ell(\nu)}\prec \bar{N}^\lambda_{\eta}\)

3. \(h^\lambda_{0, (\nu, \eta)}: \bar{N}^\lambda_\eta \to \bar{N}^\lambda_{0, (\nu, \eta)}\) is a \(\mathbb{K}\)-embedding that fixes \(N^\lambda_\ell(\nu)\) and so \(h^\lambda_{0, (\nu, \eta)}(H^{N^\lambda_+}(\eta)) = H^{N^\lambda_+}(\nu)\).

This directly witnesses the type equality.

\[\begin{tikzcd} & {N^\lambda_+} & \\ & {\bar{N}^\lambda_{0,(\nu, \eta)}} \\ {\bar{N}^\lambda_\nu} && {\bar{N}^\lambda_\eta} \\ & {N^\lambda_{\ell(\nu)}} \arrow[from=2-2, to=1-2] \arrow[from=3-1, to=2-2] \arrow["{\bar{h}_{0,(\nu, \eta)}}"', from=3-3, to=2-2] \arrow[from=4-2, to=3-1] \arrow[from=4-2, to=3-3] \end{tikzcd}\]

Claim 2: Given \(\rho \in {}^{<\omega}\lambda\) and \(i < j < \lambda\), write \(\nu = \rho{}^\frown\{i\}\) and \(\eta = \rho{}^\frown\{j\}\), so \[p^\lambda_{\nu} \upharpoonright B^\lambda_\nu \neq p^\lambda_\eta\upharpoonright B^\lambda_\nu\] Proof: This claim is trickier than above since we have to transfer type inequality (which is a statement about lack of structure) rather than type equality (which is a statement about the existence of structure that can included in the language \(\tau_+\)). We can do this because the structures defining the types are generated by finitely many elements of \(T^\lambda\), which in turn is possible since \(\mathbb{K}\) is \(<\kappa\)-tame with \(\kappa\leq|\tau(\Phi)|\); we give the details.

Define the \(\tau(\mathbb{K})\)-structures given by the universe \[N^\lambda_{1, (\nu, \eta)} =\left\{G^{N^\lambda_+}_{1,\beta, k}(\nu, \eta):\beta<\kappa^*, k<\omega\right\}\prec N^\lambda\] Suppose for contradiction that \[p^\lambda_\nu \upharpoonright B^\lambda_\nu = p^\lambda_\eta\upharpoonright B^\lambda_\nu\] This can be rewritten as \[\begin{align} tp_\mathbb{K}\left(H^{N^\lambda_+}(\nu)/B^\lambda_\nu; N^\lambda_{1, (\nu, \eta)}\right) &=& tp_\mathbb{K}\left(H^{N^\lambda_+}(\eta)/B^\lambda_\nu; N^\lambda_{1, (\nu, \eta)}\right)\\ tp_\mathbb{K}\left(H^{N^\lambda_+}(\nu)/\left\{f^{N^\lambda_+}_\gamma(\nu):\gamma<\kappa^*\right\}; \left\{G^{N^\lambda_+}_{1, \beta, k}(\nu, \eta):\beta<\kappa^*, k<\omega\right\}\right)\\&=&\\tp_\mathbb{K}\left(H^{N^\lambda_+}(\eta)/\left\{f^{N^\lambda_+}_\gamma(\nu):\gamma<\kappa^*\right\}; \left\{G^{N^\lambda_+}_{1, \beta, k}(\nu, \eta):\beta<\kappa^*, k<\omega\right\}\right) \end{align}\] If these types are equal, then there are \(N^+ \in \mathbb{K}_{\kappa^*}\) and \(f_\ell:N^\lambda_{1,(\nu, \eta)}\to N^+\) for \(\ell = 0,1\) such that \(f_0 \upharpoonright B^\lambda_\nu = f_1\upharpoonright B^\lambda_\nu\) and \[f_0\left(H^{N^\lambda_+}(\nu)\right)=f_0\left(H^{N^\lambda_+}(\eta)\right)\] By the modeling property (recall Definition 20.([erc2-item])), there is \(\alpha < (2^{\kappa^*})^+\) and \(\nu', \eta' \in {}^{<\omega}\mu_\alpha\) such that \[\begin{align} tp_{\omega-tr}(\nu', \eta'; T^{\mu_\alpha}) &=& tp_{\omega-tr}(\nu, \eta; T^\lambda)\\ tp_{\tau_+}(b^\alpha_{\nu'},b^\alpha_{\eta'}; M^\alpha_+) &=& tp_{\tau_+}(\nu, \eta; N^\lambda_+) \end{align}\] In particular, this \(\tau_+\)-quantifier free type includes the isomorphism type of the model \(N^\lambda_{1, (\lambda, \eta)}\). Thus, the map \[G^{N^\lambda_+}_{1, \beta, k}(\nu, \eta) \mapsto G^{M^\alpha_+}_{1, \beta, k}(\nu', \eta')\] is an isomorphism \(g:N^\lambda_{1, (\nu, \eta)} \cong M^\alpha_{1,(\nu', \eta')}\) that sends \(A^\alpha_{\nu'}\) to \(B^\lambda_\nu\) and sends \(H^{N^\lambda_+}(\nu), H^{N^\lambda_+}(\eta)\) to \(a^\alpha_{\nu'}, a^\alpha_{\eta'}\). Thus, composing everything, we have \[\begin{tikzcd} & {N^\lambda_{1, (\nu, \eta)}} & {N^+} \\ {M^\alpha_{1,(\nu',\eta')}} && {N^\lambda_{1, (\nu,\eta)}} \\ {A^\alpha_{\nu'}} & {M^\alpha_{1,(\nu', \eta')}} \arrow["{f_0}", from=1-2, to=1-3] \arrow["{g^{-1}}", from=2-1, to=1-2] \arrow["{f_1}"', from=2-3, to=1-3] \arrow[from=3-1, to=2-1] \arrow[from=3-1, to=3-2] \arrow["{g^{-1}}"', from=3-2, to=2-3] \end{tikzcd}\]

so that the maps agree on \(A^\alpha_{\nu'}\) and send \(a^\alpha_{\nu'}\) to \(a^\alpha_{\eta'}\). This gives \[tp_\mathbb{K}(a^\alpha_{\nu'}/A^\alpha_{\nu'}; M^{\alpha}_{1, (\nu', \eta')})=tp_\mathbb{K}(a^\alpha_{\eta'}/A^\alpha_{\eta'};M^\alpha_{1,(\nu', \eta')})\] However, since \(\nu, \eta\) and \(\nu', \eta'\) have the same type, we have that \(\rho'=\nu'\upharpoonright(n-1)=\eta'\upharpoonright(n-1)\) and \(\nu'(n-1)<\eta'(n-1)\). Thus, by construction, we have \[tp_\mathbb{K}(a^\alpha_{\nu'}/A^\alpha_{\nu'}; \hat{M}^{\alpha})=tp_\mathbb{K}(a^\alpha_{\eta'}/A^\alpha_{\eta'};\hat{M}^\alpha)\] which is a contradiction since \(M^\alpha_{1,(\nu', \eta')} \prec \hat{M}^\alpha\).\({}_{\text{Claim 2}}\)
Putting these together completes the proof.

Claim 3: \(|\text{gS}_\mathbb{K}(N^\lambda_\omega)| \geq \lambda^\omega\)
Proof: For each \(\eta \in {}^{\omega}\lambda\), the sequence \(\{p^\lambda_{\eta\upharpoonright n}:n<\omega\}\) is an increasing chain by Claim 1. By the \(\omega\)-compactness of AECs with amalgamation (see [15]), there is \(p_\eta \in \text{gS}_\mathbb{K}(N^\lambda_\omega)\) that extends all of them. By Claim 2, each \(p_\eta\) is distinct.

6.2 Indiscernible Collapse in Nonelementary Classes↩︎

One of the uses of generalized indiscernibles in first-order is to characterize various dividing lines via indiscernible collapse. An old result of Shelah [8] says that a theory \(T\) is stable iff any order indiscernibles in a model of \(T\) are in fact set indiscernibles. Scow [9] proved that \(T\) is NIP iff any ordered graph indiscernibles in a model of \(T\) are in fact order indiscernibles. In each of these cases, there are abstract (Ramsey) classes \(\mathcal{K}_0\) and \(\mathcal{K}\) with \(\mathcal{K}_0\) a reduct of \(\mathcal{K}\) where some property of \(T\) can be detected by whether or not there are \(\mathcal{K}\)-indiscernibles that are not \(\mathcal{K}_0\)-indiscernibles (after reducting the index). Guingona, Hill, and Scow [36] have formalized this notion of indiscernible collapse and given several more examples.

Following this work, we can give definitions of several dividing lines in Abstract Elementary Classes making use of the fact that the determining classes are Erdős-Rado classes in addition to being Ramsey classes. Unfortunately, at this time, we don’t know of any indiscernible collapses characterizing dividing lines that start with an Erdős-Rado class (other than order indiscernibles, but this collapse result is already known for Abstract Elementary Classes). [36] uses \(\mathcal{K}^{n-mlo}\) and [36] uses a class of trees that doesn’t restrict the height (in a similar way that \(\mathcal{K}^{ceq}\) generalizes \(\mathcal{K}^{\chi-or}\)), but neither of these are known to be Erdős-Rado classes. [36] characterizes \(NTP_2\) theories via a collapse of \(\mathcal{K}^{ceq}\)-indiscernibles, but involves notions of formulas dividing that does not easily generalize to Abstract Elementary Classes. This leads us to the following question:

Recall that it is consistently not a combinatorial Erdős-Rado class by Example 21. However, this does not rule out the possibility it is an Erdős-Rado class. A positive answer for this question would give a prospective definition for the notion of NIP for Abstract Elementary Classes.

This has advantages over other prospective definitions in that no amalgamation, tameness, etc. assumption is necessary. Of course, it has the disadvantage that it needs more results to be viable. This is being explored further in [52]

6.2.1 Category theoretic interpretation of indiscernible collapse↩︎

We can build on the category theoretic interpretation of indiscernibles from Section 5.2 to give the same gloss to indiscernible collapse in terms of injectivity conditions ([37] gives this background). In general, if \(f:A \to B\) is a morphism, then another object \(C\) is injective with respect to \(f\) iff every \(g:A \to C\) can be lifted along \(f\) to a \(g':B \to C\) so \(g = g' \circ f\). Then Shelah’s result [8] can be rephrased as follows.

Proof: First, assume \(\mathbb{K}\) is stable and let \(G:\mathcal{K}^{or} \to \mathbb{K}\). By Theorem 5, we may assume that \(G\) comes from a blueprint \(\Phi\) for order-indiscernibles. By [8], \(\Phi\) gives rise to a blueprint \(\Psi\) for set indiscernibles. Then, using Theorem 5 again, \(\Psi\) gives rise to the desired \(G'\).

Second, suppose that \(\mathbb{K}\) is injective in this sense. Then any order indiscernibles are set indiscernibles. By [8], \(\mathbb{K}\) is stable.
Other indiscernible collapses can be phrased similarly.

6.3 Interpretability Order↩︎

Finding generalized indiscernibles in nonelementary classes can give stronger negative results in the interpretability order even for comparing first-order theories. The interpretability order is a three-parameter order \(\triangleleft^*_{\lambda, \chi, \kappa}\) on complete first-order theories introduced by Shelah [53] in the vein of Keisler’s order. It would say that \(T_0\) is less complicated than \(T_1\) iff every time a first-order theory interprets both \(T_0\) and \(T_1\), if the interpretation of \(T_1\) is saturated, then so is the interpretation of \(T_0\). [53] gives the full definition, but we only need a particular instance, \(\triangleleft^*_1\), which we weaken to \(\triangleleft^{*, \kappa}_1\). Moreover, we allow the \(\chi\)-parameter to be arbitrarily large (rather than countable as in most instances in [54]) to strengthen our results. Since this application is not central, we omit some of the definitions, but a good exposition (and the results we reference) can be found in Malliaris and Shelah [54].

So \(\triangleleft^{*, \kappa}_1\) differs from \(\triangleleft^*_1\) in that it allows for infinitary theories to do the interpreting. In particular, the statement that \(\neg(T_0 \triangleleft^{*,\kappa}_1 T_1)\) is a stronger statement than \(\neg(T_0 \triangleleft^*_1 T_1)\). In [54], Malliaris and Shelah show several positive and negative instances of the interpretability order. The negative instances are proved by using various Ramsey classes to build generalized blueprints that saturate \(T_1\) without saturating \(T_0\). When these Ramsey classes are in fact Erdős-Rado classes, the stronger negative instance can be shown. In the following statement, \(T_{DLO}\) is the theory of dense linear orders and \(T_{RG}\) is the theory of the random graph.

Proof: We rely heavily on citations from [54]. Note their \(\mathcal{K}= \mathcal{K}_{\lambda}\) is essentially our \(\mathcal{K}^{\lambda-color}\), which is Erdős-Rado by Example 15 and Corollary 1. Also, they use \(GEM\) to emphasize that the Ehrenfeucht-Mostowski construction uses a generalized blueprint. We adopt [54] with our infinitary change, so

1. \(\lambda = \lambda^{<\mu} \geq 2^\mu\);

2. \(T_*\) is a skolemized \(\mathbb{L}_{\kappa, \omega}\)-theory with \(|T_*| \leq \lambda\) that interprets \(T_{RG}\) by \(R_{RG}\) and interprets \(T_{DLO}\) by \(<_{DLO}\).

Note that they point out that their results in this area work for uncountable languages as well.

Since \(\mathcal{K}\) is a combinatorial Erdős-Rado class, there is \(\Phi \in\Upsilon^{\mathcal{K}}[T_*]\). By [54], we can find \(\Psi\) extending \(\Phi\) such that for every separated \(I \in \mathcal{K}\), \(EM_{RG}(I, \Psi)\) is \(\mu\)-saturated. Note that, since \(\Psi\) agrees with \(\Phi\) on \(\tau(T_*)\), \(\Psi\) is still in \(\Upsilon^{\mathcal{K}}[T_*]\). By [54], if \(J\) is a separated linear order, then for any \(\Phi^* \in \Upsilon^{\mathcal{K}}[T_*]\), \(EM_{DLO}(J, \Phi^*)\) is not \(\kappa^+\)-saturated. Thus, by taking \(I\) separated with a \((\kappa, \kappa)\)-cut, we have \(EM_{RG}(I, \Psi)\) is \(\mu\)-saturated, but \(EM_{DLO}(I, \Psi)\) is not \(\kappa^+\)-saturated, as desired.

References↩︎

---

1. The notation \[\alpha \xrightarrow{} (\beta)^r_\gamma\] means that for any coloring \(c:[\alpha]^r \to \gamma\), there is \(X \subseteq\alpha\) of type \(\beta\) such that \(c"[X]^r\) is a single element; such an \(X\) is called homogeneous. Hajnal and Larson [2] point out “[t]here are cases in mathematical history when a well-chosen notation can enormously enhance the development of a branch of mathematics and a case in point is the ordinary partition symbol."↩︎

2. Indiscernibles over a set of parameters can be recovered by adding those parameters to the language. The exception to this rule is Section 6.1, which deals with a specific application to Abstract Elementary Classes, and uses types over parameter sets and other techniques.↩︎

3. This is a proper class, but we can use Scott’s trick (see [22]) or some other method to only deal with sets.↩︎

4. A more mathematically complex example of a bidimensional theory is the theory \(Th( \oplus \mathbb{Z}(p^\infty))\) of the direct sum of countably many copies of the Prüfer p-group. The same analysis applies there.↩︎

5. \(\Upsilon^{2-or}\) is \(\Upsilon^{\mathcal{K}^{2-or}}\), and this class is consists of two disjoint linear orders; see Example 3.↩︎

6. For a more accessible reference, see [27].↩︎

7. By inspection, Proposition 15 gives a stronger result, but we use this weakening for easier comparison with other structural partition relations since \[\beth_{1}\left(\beth_{n(n+1)}(\kappa)^+\right)^+ \leq \beth_{1}\left(\beth_{n(n+1)+1}(\kappa)\right)^+ = \beth_{n(n+1)+2}(\kappa)^+\]↩︎

8. Importantly, this fails if we allow \(\gamma = \gamma'\). This is the reason for the complicated subscript in the definition of \(\chi\otimes X\).↩︎

9. Shelah [29] mentions the result, which appears with proof in [8]. There, the threshold cardinal on the left-hand side is mentioned to be some polynomial \(k(n,m)\) in the height \(n\) of the tree and size \(m\) of the tuples being colored. Alternate proofs appear in [30] and [16], with the later lowering the bound on \(k(n,n)\) from \(2^n+n+1\) to \(n^2\). Our method to remove the well-ordering assumption raises the threshold, so we’re not concerned about finding the optimal value.↩︎

10. \(\daleth\) (‘daleth’) is the fourth letter of the Hebrew alphabet and is chosen to follow in the line of the well-known \(\aleph\) and \(\beth\) functions and the less well-known \(\gimel\) function (see, e.g., [22]↩︎

11. A more detailed version of this technique is given at the end of the induction step of the construction.↩︎

12. Note that this condition follows from the previous one.↩︎

13. This implies that \(p=p^*\upharpoonright n\) is the unique extension of \(p\upharpoonright k_{p^*}=p^*\upharpoonright k_{p^*}\).↩︎

14. Note that this type fragment is actually determined by the other objects in the construction.↩︎