COFINALITY QUANTIFIERS IN ABSTRACT ELEMENTARY CLASSES AND BEYOND

Abstract

The cofinality quantifiers were introduced by Shelah as an example of a compact logic stronger than first-order logic. We show that the classes of models axiomatized by these quantifiers can be turned into an Abstract Elementary Class by restricting to positive and deliberate uses. Rather than using an ad hoc proof, we give a general framework of abstract Skolemizations. This method gives a uniform proof that a wide rang of classes are Abstract Elementary Classes.

1 Introduction

Abstract Elementary Classes (AECs, introduced by Shelah [17]) are the primary framework to do classification theory beyond first-order logic. They are defined as a collection $(\mathbb {K}, \prec _{\mathbb {K}})$ of structures $\mathbb {K}$ and a strong substructure relation $\prec _{\mathbb {K}}$ satisfying a certain set of axioms; see [1] for an introduction to these axioms and the basic properties of AECs. These axioms are designed to be broad enough to contain classes axiomatized by $\mathbb {L}_{\lambda , \omega }$ and some extensions, but provide enough structure to do classification theory. Beyond AECs, $\mu $ -AECs (introduced by Boney, Grossberg, Lieberman, Rosicky, and Vasey [7]) can capture classes axiomatized in $\mathbb {L}_{\lambda , \mu }$ , but at the loss of the development of their classification theory.

The primary extension of $\mathbb {L}_{\lambda , \omega }$ that form AECs are extensions by cardinality quantifiers $Q_{\alpha }$ (although Baldwin, Ekloff, and Trlifaj [2] provide an extension in a different direction). Here, the cardinality quantifier is interpreted, so $Q_{\alpha } x \phi (x, \mathbf {y})$ is true (in some structure) iff there are at least $\aleph _{\alpha }$ -many x that make $\phi (x, \mathbf {y})$ true. Then classes axiomatized in $\mathbb {L}_{\lambda , \omega }(Q_{\alpha })$ form an AEC, although the strong substructure relation must be strengthened. ¹ Most logics extending $\mathbb {L}_{\lambda , \omega }$ that axiomatize AECs work by adding quantifiers that have a similar “feel” to the cardinality quantifiers, for instance, the Ramsey or Magidor–Malitz quantifiers [15] or the structure quantifiers [6].

We show how extension by another type of quantifier—the cofinality quantifiers introduced by Shelah [16] (see Section 2)—can be made an AEC. Cofinality quantifiers, given a set of regular cardinals $\mathcal {C}$ , $Q^{\text {cof}}_{\mathcal {C}}$ are a binary quantifier, where

$$ \begin{align*}Q^{\text{cof}}_{\mathcal{C}} x,y \, \phi(x,y, \mathbf{z}) \end{align*} $$

means that $\phi (x,y, \mathbf {z})$ is a linear order whose cofinality is in C. Among the many properties of cofinality quantifiers, perhaps the most surprising is that $\mathbb {L}(Q^{\text {cof}}_{\mathcal {C}})$ is fully compact (see [16] or Fact 2.2)! This is a rarity among extensions of first-order logic: Lindström’s theorem [14] says that any extension of first-order logic must sacrifice either compactness or the downward Löwenheim–Skolem property, but in practice most extensions of first-order logic become incompact. This makes cofinality quantifiers particularly intriguing to capture by an AEC since even small fragments of compactness can greatly advance the classification theory (see [5] for a survey).

In order to make cofinality quantifiers an AEC, we must make certain changes to the class. We give more details in Section 3, but the essential issue is that the cofinality of a linear order is not preserved under increasing unions. This necessitates two changes:

• • Like cardinality quantifiers, the strong substructure relation must preserve the cofinality of linear orders with a positive instance of the cofinality quantifier. This manifests by not allowing end extensions of such linear orders.

• • We have the additional issue that the cofinality can decrease following an increasing union. This requires that we restrict to what we call positive, deliberate uses of the cofinality quantifier.

Definition 3.1 makes these ideas precise.

Given a positive $\mathbb {L}(Q^{\text {cof}}_{\mathcal {C}})$ -theory T, we form an AEC $\mathbb {K}_T^+$ through the deliberate use of these quantifiers (Definition 3.1), and we briefly explore the properties of this AEC. An unfortunate consequence of the changes to strong substructure is that many of the nice properties of elementary classes that follow from compactness (amalgamation, etc.) do not hold in these AECs, although these AECs do have some nice properties. We discuss how some of these issues have their roots in the models produced by the compactness theorem for cofinality quantifiers. Still, there are some general results that hold for any classes of models that can be made into an AEC with some strong substructure relation (existence of EM models, undefinability of well-order, etc.), and these apply to our classes. Moving beyond AECs, classes axiomatized by cofinality quantifiers naturally form a $\mu $ -AEC without the changes above; here, $\mu $ is the successor of the supremum ² of $\mathcal {C}$ for $Q^{\text {cof}}_{\mathcal {C}}$ . This follows from the fact that the cofinality quantifier $Q^{\text {cof}}_{\mathcal {C}}$ is expressible in $\mathbb {L}_{\infty , \mu }$ .

Rather than proving that $\mathbb {K}_T^+$ forms an AEC through an ad hoc method, we present a general framework of finitary abstract Skolemizations (Definition 4.1). This captures the essence of Shelah’s Presentation Theorem [17], but with a tighter connection to the syntax used to define the AEC. This is a rather broad method and is able to encompass most known quantifiers that define AECs (see Example 4.7).

2 Cofinality quantifiers and background

Background on abstract logics and quantifiers is given in [3], but is not really necessary here. The reader unfamiliar with these ideas can always replace an abstract logic $\mathcal {L}$ by, depending on the circumstance, one of: finitary first-order logic $\mathbb {L} = \mathbb {L}_{\omega , \omega }$ ; infinitary logic $\mathbb {L}_{\lambda , \omega }$ ; or a mild extension of $\mathbb {L}_{\lambda , \omega }$ by cardinality quantifiers. For completeness, the logic $\mathbb {L}_{\lambda , \mu }$ (for regular $\lambda \geq \mu $ ) extends first-order logic by closing formula formation under ${<}\lambda $ -sized disjunctions and conjunctions, and existential and universal quantification of ${<}\mu $ -sized sequences of free variables, with the obvious semantics.

Cofinality quantifiers were introduced by Shelah [16] to answer questions of Keisler and Friedman on compact logics stronger than first-order. We gave an informal description in the Introduction, but give a formal definition here.

Definition 2.1. Fix a logic $\mathcal {L}$ , a class of regular ³ cardinals $\mathcal {C}$ , and a language $\tau $ .

1. (1) The logic $\mathcal {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )$ is an extension of $\mathcal {L}$ where we add a formulation rule where if $\phi (\mathbf {x}, \mathbf {y}, \mathbf {z})$ is a formula of $\mathcal {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )(\tau )$ (with $\ell (\mathbf {x}) = \ell (\mathbf {y})$ finite), then so is

   $$ \begin{align*}Q^{\text{cof}}_{\mathcal{C}} \mathbf{x},\mathbf{y} \phi(\mathbf{x}, \mathbf{y}, \mathbf{z})\end{align*} $$
   with $\mathbf {z}$ the remaining free variables. The semantics of this formula are given by, if M is a $\tau $ -structure and $\mathbf {c} \in M$ , then
   $$ \begin{align*}M\vDash Q^{\text{cof}}_{\mathcal{C}} \mathbf{x}, \mathbf{y} \phi(\mathbf{x}, \mathbf{y}, \mathbf{c})\end{align*} $$
   iff the relation $\phi (\mathbf {x}, \mathbf {y}, \mathbf {c})$ is a linear order without the last element of the set $I:=\{\mathbf {a} \in M :\text { there is }\mathbf {b} \in M, M\vDash \phi (\mathbf {a}, \mathbf {b}, \mathbf {c}) \}$ and that the cofinality of this linear order is in C.

2. (2) A fragment $\mathcal {F}$ of $\mathcal {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )(\tau )$ is a collection $\mathcal {F} \subset \mathcal {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )(\tau )$ of formulas that is closed under subformulas.

When we have a singleton $\mathcal {C} = \{\kappa \}$ , we write $Q^{\text {cof}}_{\kappa }$ in place of $Q^{\text {cof}}_{\{\kappa \}}$ ; there is no risk of confusion because we never place finite cardinals in $\mathcal {C}$ .

Note that the assertion that “ $\phi (\mathbf {x}, \mathbf {y}, \mathbf {z})$ is a linear order without last element” is expressible by a single first-order sentence, and it is the assertion about the cofinality that makes this quantifier inexpressible in first-order logic. Also, due to the requirement that $\phi (\mathbf {x}, \mathbf {y}, \mathbf {c})$ forms a linear order, we have several equivalent ways to define the set underlying set I:

$$ \begin{align*} \{\mathbf{a} \in M :\text{ there is }\mathbf{b} \in M, M\vDash \phi(\mathbf{a}, \mathbf{b}, \mathbf{c}) \} &= \{\mathbf{b} \in M :\text{ there is }\mathbf{a} \in M, M\vDash \phi(\mathbf{a}, \mathbf{b}, \mathbf{c}) \}\\ &= \{\mathbf{a} \in M : M\vDash \phi(\mathbf{a}, \mathbf{a}, \mathbf{c}) \}. \end{align*} $$

The last is compactly denoted $\phi (M, M, \mathbf {c})$ and is how we will most often refer to the underlying set.

The most common of the cofinality quantifiers used is $Q^{\text {cof}}_{\omega }$ . Perhaps the most useful fact about cofinality quantifiers is that first-order logic augmented by a single cofinality quantifier is compact; recall a logic $\mathcal {L}$ is compact iff given any theory $T \subset \mathcal {L}(\tau )$ , T has a model iff every finite subset has a model.

Fact 2.2 [16], [9, Corollary 4.4].

For every class $\mathcal {C}$ of regular cardinals, $\mathbb {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )$ is compact.

Remark 2.3.

1. (1) In keeping with Lindström’s theorem[14], $\mathbb {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )$ fails the countable downward Löwenheim–Skolem property. For instance, the $\mathbb {L}\left (Q^{\text {cof}}_{\omega }\right )(\{<\})$ -sentence

   $$ \begin{align*} \kern-20pt \text{"}x < y\text{ is a linear order of the universe with no last element"} \wedge \neg Q^{\text{cof}}_{\omega} x,y (x < y)\end{align*} $$
   has no countable model.

2. (2) Casanovas and Ziegler [9] have recently provided an excellent and self-contained exposition of Fact 2.2. A reader surprised to learn about the full compactness of $\mathbb {L}(Q^{\text {cof}}_{\mathcal {C}})$ is not alone; the exposition by Casanovas and Ziegler [9] was apparently inspired by a referee of Casanovas and Shelah [8] who did not believe this was a ZFC result.

For future reference, it is helpful to understand the basic structure of the proof of Fact 2.2. First note that $Q^{\text {cof}}_{\mathcal {C}}$ is not interesting if $\mathcal {C}$ is empty or all regular cardinals; in the former, it is always false and, in the latter, it reduces to the first-order statement that the formula gives a linear order without last element.

Thus, at the start two cardinals are fixed: $\kappa \in \mathcal {C}$ and $\lambda \not \in \mathcal {C}$ (if $\mathcal {C}$ is empty or all regular cardinals, then $Q^{\text {cof}}_{\mathcal {C}}$ is not interesting ⁴ ). Then T is expanded to definably link all definable linear orders that are positively quantified by $Q^{\text {cof}}_{\mathcal {C}}$ in one group and all definable linear orders that are negatively quantified by $Q^{\text {cof}}_{\mathcal {C}}$ in another group. Then we find a model of the first-order part of T in which all definable linear orders have cofinality $\max \{\kappa , \lambda \}$ . This is iteratively extended by end-extending all of one group of the linear orders while fixing the other group using the Extended Omitting Types Theorem[10, Theorem 2.2.19]. We continue this iteration for $\min \{\kappa , \lambda \}$ -many steps to achieve the desired cofinalities.

The key take away from this proof is that always produces models where the definable linear orders have one of exactly two cofinalities: $\kappa $ for the definable linear orders satisfying $Q^{\text {cof}}_{\mathcal {C}}$ and $\lambda $ for the definable linear orders not satisfying $Q^{\text {cof}}_{\mathcal {C}}$ .

Finally, we give an explicit example showing that $Q^{\text {cof}}$ is stronger than $\mathbb {L}_{\infty , \omega }$ .

Example 2.4. Recall that two structures are back and forth equivalent to each other if and only if they are $\mathbb {L}_{\infty , \omega }$ equivalent. It is routine to show that $(\mathbb {Q}, <)$ is back-and-forth equivalent to $(\mathbb {Q} \times \omega _1, <)$ . However, $(\mathbb {Q},<)$ satisfies $Q^{\text {cof}}_{\omega } x,y (x < y)$ while $(\mathbb {Q} \times \omega _1, <)$ does not.

We also provide the basics of AECs (and $\mu $ -AECs); [1, 11] provide further background.

Definition 2.5. Fix an infinite cardinal $\mu $ . A $\mu $ -Abstract Elementary Class (or $\mu $ -AEC for short) is a pair $\left (\mathbb {K}, \prec _{\mathbb {K}}\right )$ where $\mathbb {K}$ is a collection of structures in a fixed $<\mu $ -ary language $\tau _{\mathbb {K}}$ satisfying the following axioms:

1. (1) $\prec _{\mathbb {K}}$ is a partial order on $\mathbb {K}$ that is stronger than $\subset _{\tau _{\mathbb {K}}}$ .

2. (2) $\mathbb {K}$ and $\prec _{\mathbb {K}}$ are closed under isomorphisms.

3. (3) (Coherence) If $M_0, M_1, M_2 \in \mathbb {K}$ such that $M_0 \prec _{\mathbb {K}} M_2$ , $M_1 \prec _{\mathbb {K}} M_2$ , and $M_0 \subset _{\tau _{\mathbb {K}}} M_1$ , then $M_0 \prec _{\mathbb {K}} M_1$

4. (4) (Closure under $\mu $ -directed limits) Given a $\mu $ -directed system $\{M_i \in \mathbb {K} : i \in I\}$ , we have that the colimit of this system $\displaystyle \bigcup _{i \in I}M_i$ computed in the category of $\tau $ -structures is also the colimit in $\mathbb {K}$ .

5. (5) (Lowenheim–Skölem–Tarksi number) There ⁵ is a cardinal $\text {LS}(\mathbb {K})$ such that, for all $M \in \mathbb {K}$ and $A \subset M$ , there is $M_0 \prec _{\mathbb {K}} M$ such that $A \subset M_0$ and $\|M_0\| = |A|^{<\mu }+\text {LS}(\mathbb {K})$ .

When clear, we often use $\mathbb {K}$ to refer to the pair $(\mathbb {K}, \prec _{\mathbb {K}})$ .

By far the most common (and important) case is $\mu = \omega $ , where we omit $\mu $ and just call it an Abstract Elementary Class (or AEC).

AECs were introduced by Shelah [17], and generalized to $\mu $ -AECs in [7]. They are the most common framework to develop classification theory for nonelementary classes.

3 $\mathbb {L}(Q^{\text {cof}}_{\mathcal {C}})$ as an Abstract Elementary Class

Fix a set of regular cardinals $\mathcal {C}$ and a theory T in some fragment $\mathcal {F}$ of $\mathbb {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )(\tau )$ . Recall that a fragment $\mathcal {F}$ is a subset of $\mathbb {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )(\tau )$ that is closed under subformulas. To build a notion of strong substructure that makes $\operatorname {\mathrm {Mod}} T$ an Abstract Elementary Class, we will develop the notion of positive, deliberate uses of the cofinality quantifier (Definition 3.1).

The main problem with making $\operatorname {\mathrm {Mod}} T$ an AEC (or $\mu $ -AEC) is smoothness under unions of chains (Definition 2.5(4)): If ${\langle {I_{\alpha } : \alpha < \lambda } \rangle }$ is a sequence of linear orders such that $I_{\alpha }$ is end-extended by $I_{\alpha +1}$ , then $\displaystyle \bigcup _{\alpha < \lambda } I_{\alpha }$ has cofinality $\text {cf} \, \lambda $ regardless of the cofinalities of the $I_{\alpha }$ . This necessitates two changes:

1. (1) If $M\vDash Q^{\text {cof}}_{\mathcal {C}} x,y \phi (x,y)$ , then we should not allow end extensions of this definable linear order in strong extensions; note this is similar to the condition on strong extensions when using the cardinality quantifiers.

2. (2) If $M \vDash \neg Q^{\text {cof}}_{\mathcal {C}} x,y \phi (x,y)$ , then we similarly worry about end extensions. However, disallowing any end extensions of any definable linear order would be too restrictive, ⁶ so we will only allow positive instances of the cofinality quantifier. This doesn’t solve the problem completely because definable linear orders that are not put under the $Q^{\text {cof}}_{\mathcal {C}}$ quantifier will “accidentally” end up with a cofinality in $\mathcal {C}$ after the appropriate unions. So, via a Morleyization, we avoid this accidental occurrence by deliberately tagging formulas that we wish to be affected by the cofinality restriction.

We detail the construction of positive, deliberate uses of the cofinality quantifier that will form the strong substructure of an AEC (we deal with positive, deliberate uses of quantifiers in more generality in Section 4). We work in some degree of generality, allowing for an arbitrary logic $\mathcal {L}$ to be expanded by cofinality quantifiers, but this will most often be first-order logic $\mathbb {L}$ with possible extension by infinitary conjunction or cardinality quantifiers. Note that this expansion is similar to the formation of weak models in [12], but with only one direction of implication.

Definition 3.1. Fix a language $\tau $ and a logic $\mathcal {L}$ .

1. (1) Define $\tau ^{\mathcal {L}}_{*}$ to be

   $$ \begin{align*}\tau \cup \{R_{\phi}(\mathbf{z}) :\phi(\mathbf{x}, \mathbf{y}, \mathbf{z}) \in \mathcal{L}(\tau)\},\end{align*} $$
   where each $R_{\phi }$ is new.

2. (2) Fix a base theory in $\mathbb {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )(\tau ^{\mathcal {L}}_*)$ ,

   $$ \begin{align*}T^{\text{cof}}_{\tau, \mathcal{L}} := \left\{\forall \mathbf{z} \left(R_{\phi}(\mathbf{z}) \to Q^{\text{cof}}_{\mathcal{C}} \mathbf{x}, \mathbf{y} \phi(\mathbf{x}, \mathbf{y}, \mathbf{z})\right) : \phi(\mathbf{x}, \mathbf{y}, \mathbf{z}) \in \mathcal{L}(\tau)\right\}.\end{align*} $$

3. (3) Let $T \subset \mathcal {L}(Q^{\text {cof}}_{\mathcal {C}})(\tau )$ be a theory where $Q^{\text {cof}}_{\mathcal {C}}$ only appears positively. ⁷ Define two theories $T^* \subset \mathcal {L}(\tau ^{\mathcal {L}}_*)$ and $T^+ \subset \mathcal {L}(Q^{\text {cof}})(\tau ^{\mathcal {L}}_*)$ by

   $$ \begin{align*} T^* &\text{ is} \text{ the result of replacing each use of "}Q^{\text{cof}} \mathbf{x}, \mathbf{y}\phi(\mathbf{x}, \mathbf{y}, \mathbf{z})\text{" with }\\ & \text{"}R_{\phi}(\mathbf{z})\text{" in the inductive construction of each } \psi \in T,\\ T^+ &:= T^* \cup T^{\text{cof}}_{\tau,\mathcal{L}}. \end{align*} $$

4. (4) Given two $\tau ^{\mathcal {L}}_*$ -structures $M \subset N$ , define the relation

   $$ \begin{align*}M\prec_{\mathcal{L}(+)} N\end{align*} $$
   iff $M \prec _{\mathcal {L}} N$ and, for all $\mathbf {a} \in M$ , if $M \vDash R_{\phi }(\mathbf {a})$ , then $\phi (M,M, \mathbf {a})$ is cofinal in $\phi (N, N, \mathbf {a})$ .

With this definition in hand, we can be explicit about what is meant by positive and deliberate:

1. (1) “Positive” refers to the fact that the $Q^{\text {cof}}$ quantifiers are required to appear positively in the theory T that we start with.

2. (2) “Deliberate” refers to the aim to make the cofinality restriction a particular choice about a tuple, rather than something that can be turned on or off as we move to, e.g., unions. The predicates $R_{\phi }(\mathbf {z})$ are used to “tag” the parameters where we want to enforce a particular cofinality for $\phi (\mathbf {x}, \mathbf {y}, \mathbf {z})$ . On the other hand, if $\neg R_{\phi }(\mathbf {z})$ holds, then this has no other implications: the cofinality could “accidentally” be in $\mathcal {C}$ or it could not, and this could change as a result of moving to $\prec _{\mathcal {L}(+)}$ -extensions.

The reason to jump through all of these hoops is the following result.

Theorem 3.2. Fix a set of regular cardinal $\mathcal {C}$ and set $\mathcal {L} = \mathbb {L}$ , finitary first-order logic. Let $T \subset \mathcal {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )(\tau )$ be a theory where all instances of cofinality quantifiers appear positively. Then

$$ \begin{align*}\mathbb{K}_{T}^+ := \left(\operatorname{\mathrm{Mod}} T^+, \prec_{\mathcal{L}(+)}\right)\end{align*} $$

is an Abstract Elementary Class with $\text {LS}(\mathbb {K}_{T}^+) = |\tau |+(\sup \mathcal {C})^+$ .

Proof This is a corollary of the more general result Theorem 4.12.

Remark 3.3. Theorem 3.2 remains true if $\mathcal {L}$ is replaced by $\mathbb {L}_{\lambda , \omega }$ , $\mathbb {L}\left (Q_{\alpha }\right )$ , or any other logic that axiomatizes Abstract Elementary classes (with the appropriate modification to the substructure relation and the Löwenheim–Skolem number).

Now that we have an AEC $\mathbb {K}^+_T$ axiomatized in the fully compact logic $\mathbb {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )$ , we might hope that several nice consequences of compactness (amalgamation, tameness, etc.) follow directly. However, this is not the case. The reason has to do with a disconnect between $\mathbb {L}(Q^{\text {cof}}_{\mathcal {C}})$ -elementary diagrams and the strong substructure $\prec _{\mathbb {K}^+_T}$ .

Recall that the $\mathcal {L}$ -elementary diagram $\text {ED}_{\mathcal {L}}(M)$ of a $\tau $ -structure M is the collection of all $\mathcal {L}\left (\tau \cup \{c_m : m \in M\}\right )$ -sentences that are true in M when we interpret $c_m^M = m$ . For first-order logic or any fragment of infinitary $\mathbb {L}_{\lambda ,\kappa }$ , we have an equivalence between “there exists an $\mathcal {L}$ -elementary embedding $M \to N$ ” and “ $N \vDash \text {ED}_{\mathcal {L}}(M)$ .”

However, this does not hold for $\mathbb {K}^+_T$ : modeling $\text {ED}_{\mathbb {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )}(M)$ is not sufficient to guarantee a $\mathbb {K}^+_T$ -embedding since it does not guarantee that the $R_{\phi }$ -tagged linear orders of M are cofinal in N (Condition 3.1(4)). In the desired uses of compactness, it is routine to find a model of some $\mathcal {L}$ -elementary diagram and turn that into an extension of the desired models; this is not possible. However, we have some results.

Use $\mathbb {L}^+(Q^{\text {cof}}_{\mathcal {C}})$ to denote the $\mathbb {L}(Q^{\text {cof}}_{\mathcal {C}})$ -formulas where $Q^{\text {cof}}_{\mathcal {C}}$ only appears positively.

Proposition 3.4. Let T be an $\mathbb {L}^+(Q^{\text {cof}}_{\mathcal {C}})$ -theory and define $\mathbb {K}_T^+$ as in Theorem 3.2.

1. (1) $\mathbb {K}_T^+$ has arbitrarily large models.

2. (2) Suppose $M \in \mathbb {K}$ has size $\kappa $ and all $R_{\phi }$ -tagged linear orders have cofinality $\kappa $ ; that is, if $M \vDash R_{\phi }(\mathbf {a})$ , then $\phi (M, M, \mathbf {a})$ has cofinality $\kappa $ . Then M has a proper $\prec _{\mathbb {K}_T^+}$ -extension in $\mathbb {K}_T^+$ .

Proof The first follows easily from the compactness of $\mathbb {L}(Q^{\text {cof}}_{\mathcal {C}})$ since it doesn’t mention $\prec _{\mathbb {K}_T^+}$ . For the second, we use the notation and results of [9]. Pick some $\psi $ that is not definably connected to the $R_{\phi }$ -tagged linear orders in M. Then, by [9, Corollary 3.2], we can find an $\mathbb {L}(Q^{\text {cof}}_{\mathcal {C}})$ -elementary extension N of M that extends $\psi $ , but in which every $R_{\phi }$ -tagged order has M cofinal.

3.1 $\mathbb {L}\left (Q^{\text {cof}}_{\omega }\right )$ as an $\omega _1$ -Abstract Elementary Class

Above, there was much effort put into finding precisely the right condition to form an AEC out of $\operatorname {\mathrm {Mod}} T$ , and the end result was a rather restrictive solution. Here, we describe a more uniform and natural approach with the drawback that the resulting class is not an Abstract Elementary Class, but instead a $\mu $ -Abstract Elementary Class.

While $Q^{\text {cof}}_{\omega }$ is not axiomatizable in $\mathbb {L}_{\infty ,\omega }$ (recall Example 2.4), it is axiomatizable in $\mathbb {L}_{\omega _1, \omega _1}$ . More generally, for any bounded set of regular cardinals $\mathcal {C}$ , $Q^{\text {cof}}_{\mathcal {C}} \mathbf {x}, \mathbf {y} \phi (\mathbf {x}, \mathbf {y}, \mathbf {z})$ is expressible by the first-order statement that $\phi $ defines a linear order without last element and the $\mathbb {L}_{(\mu +|\mathcal {C}|)^+,\mu ^+}$ assertion

$$ \begin{align*}\bigvee_{\lambda \in \mathcal{C}} \exists {\langle {\mathbf{x}_i : i < \lambda} \rangle} \left( \bigwedge_{i<j<\lambda} \phi(\mathbf{x}_i, \mathbf{x}_j, \mathbf{z}) \wedge \forall \mathbf{w} \bigvee_{i<\lambda} \phi(\mathbf{w}, \mathbf{x}_i, \mathbf{z})\right),\end{align*} $$

where $\mu = \sup \mathcal {C}$ . The logics $\mathbb {L}_{\lambda ,\kappa }$ come with a well-known notion of elementarity.

Definition 3.5. Let $\mathcal {C}$ be a set of regular cardinals, $\tau $ be a language, and $\mathcal {F}$ be a fragment of $\mathbb {L}(Q^{\text {cof}}_{\mathcal {C}})$ .

1. (1) Setting $\mu = \sup \mathcal {C}$ , let $\mathcal {F}^*$ be the fragment of $\mathbb {L}_{(\mu +|\mathcal {C}|)^+,\mu ^+}(\tau )$ that is formed by replacing each instance of $Q^{\text {cof}}_{\mathcal {C}}$ by the formulation listed above (including the first-order part) and closing under subformula, etc.

2. (2) Given $\tau $ -structures M and N, set $M \prec ^*_{\mathcal {F}} N$ iff $M \prec _{\mathcal {F}^*} N$ .

Theorem 3.6. Fix a set $\mathcal {C}$ of regular cardinals and set $\mu = \sup \mathcal {C}$ . For any theory T in $\mathbb {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )(\tau )$ , $\mathbb {K}^*_T$ is a $\mu ^+$ -Abstract Elementary Class with $LS(\mathbb {K}^*_T) = \left (|\tau | + \mu ^+ +|\mathcal {C}|\right )^{<\mu }$ . This AEC has arbitrarily large models (if nonempty) and satisfies the undefinability of well-ordering.

Proof Classes axiomatized by $\mathbb {L}_{(\mu +|\mathcal {C}|)^+,\mu ^+}$ are the prototypical examples of $\mu ^+$ -AECs (see [7, Example (3), p. 3052]).

Remark 3.7. As with Theorem 3.2, the above can be naturally generalized to logics of the form $\mathbb {L}_{\lambda , \kappa }\left (Q^{\text {cof}}_{\mathcal {C}}\right )$ .

Crucially, we have removed any restriction to positive or deliberate uses of the cofinality quantifier. Note that additional model theoretic properties (amalgamation, etc.) still do not hold because, while $\mathbb {L}\left (Q^{\text {cof}}_{\mathcal {C}}\right )$ is compact, elementarity in this class is according to $\mathbb {L}_{(\mu +|\mathcal {C}|)^+,\mu ^+}$ , which is still not compact.

4 Abstract Skolemizations and a sufficient criteria to be an AEC

We collect here two related and helpful results: a handy criteria for a class to be an Abstract Elementary Class (Corollary 4.5) and an application of this to show generally that positive, deliberate uses of infinitary quantification forms an Abstract Elementary Class (Theorem 4.12).

We begin by discussing the general motivation of this result to help the reader understand the series of abstract definitions that are forthcoming. There are two related issues that the results of this section are intended to solve.

The first issue begins with the observation that Abstract Elementary Classes are given through an entirely semantic set of axioms (recall Definition 2.5), so don’t seem to have an explicit connection to the syntax normally central to model theory. Shelah’s Presentation Theorem [17] forms a connection by showing that every AEC can be expanded by functions to a language where it omits an axiomatization in terms of $\mathbb {L}_{\lambda , \omega }$ (or, equivalently, by omitting types). In a sense (see the discussion around [4, Section 3.1]), these additional functions act like Skolem functions. Beyond strengthening the philosophical ties to model theory and syntax, Shelah’s Presentation Theorem is useful in proving certain results about AECs, e.g., computing Hanf numbers, finding indiscernibles, and using large cardinals.

However, Shelah’s Presentation Theorem often feels unsatisfactory in that the axiomatization it produces feels unnatural in part because it has to deal with such a wide range of AECs. Even if the class has a very nice $\mathbb {L}_{\lambda , \omega }$ -axiomatization (or even first-order!), the axiomatization given by Shelah’s Presentation Theorem looks entirely different: it just says that the models of AECs don’t contain any substructures that don’t appear in the AEC. So there can be a large gap between the axioms we use to define the class and the axioms coming from Shelah’s Presentation Theorem.

The second issue is more practical, but also highlights the problems with the gap above. While the definition of AECs is abstract and asyntactic, the actual examples of AECs that people give and use are very syntactically based. Most examples of AECs that occur are given by axiomatizations in some fragment of $\mathbb {L}_{\lambda , \omega }$ , with the vast majority occurring in some mild extension of that logic via quantifiers, such as “there exists uncountably many” or the cofinality quantifier (see Example 4.7). The only two examples the author knows of that don’t fit into those frameworks are the modules studied in [2] (specifically coming from the strong substructure relation) and saturated models of superstable theories. In particular, each of these quantifiers admits a Skolemization to $\mathbb {L}_{\lambda , \omega }$ that shows that it is an AEC and gives rise to the strong substructure relation that is used.

The results of this section address both of these situations by providing a more natural and satisfying Skolemization that is built to more accurately track the syntax that defines the majority of examples of AECs.

First, we define an abstract notion of Skolemization, that is, an expansion by functions that turns the class into one axiomatizable by a universal theory in $\mathbb {L}_{\infty ,\omega }$ . The goal of this notion is to capture the way in which various extensions of $\mathbb {L}_{\lambda , \omega }$ by different quantifiers have been turned into AECs.

Below, the dot in “ $\cdot \upharpoonright \tau $ ” indicates the place to put the argument of the map; that is, given a model M, the output of the map is $M \upharpoonright \tau $ . This notation is a little clunky in the abstract, but allows us to use the normal notation for restrictions of models.

Definition 4.1. Fix $(\mathbb {K}, \prec _{\mathbb {K}})$ , where $\mathbb {K}$ is a class of $\tau $ -structures and $\prec _{\mathbb {K}}$ is a partial order on $\mathbb {K}$ . A (finitary) abstract Skolemization (to a universal theory in $\mathbb {L}_{\infty ,\omega }$ ) of $(\mathbb {K}, \prec _{\mathbb {K}})$ is an expansion of the language $\tau ^* := \tau \cup \{F_i : i \in I\}$ by finitary function symbols and a universal theory $T^* \subset \mathbb {L}_{\infty , \omega }(\tau ^*)$ such that the restriction map

$$ \begin{align*}\cdot \upharpoonright \tau :\left(\operatorname{\mathrm{Mod}} T^*, \subset\right) \to \left(\mathbb{K}, \prec_{\mathbb{K}}\right)\end{align*} $$

satisfies the following properties:

1. (1) (capturing) The restriction map is a functor that is surjective on objects and arrows .

2. (2) (lifting) Every map $f:M \to N$ in $\mathbb {K}$ has a lift ⁸ $f^*:M^* \to N^*$ in $\operatorname {\mathrm {Mod}} T^*$ . Moreover, given any lift $M^*$ of the model M and any map $f:M\to N$ in $\mathbb {K}$ , there is a lift $f^*:M^* \to N^*$ in $\operatorname {\mathrm {Mod}} T^*$ with the prescribed domain.

3. (3) (coherence/local testability) Given $M_0 \subset M_1 \subset N$ , if there are separate lifts $M_0^* \subset N^{*0}$ and $M_1^* \subset N^{*1}$ , then there are lifts $M_0^{**} \subset M_1^{**} \subset N^{**}$ .

We can also define a $<\mu $ -ary abstract Skolemization (to a universal theory in $\mathbb {L}_{\infty , \mu }$ ) by allowing the function symbols to be $<\mu $ -ary and the universal theory $T^*$ to be in $\mathbb {L}_{\infty , \mu }$ .

We could also speak of abstract Skolemizations to theories in (fragments of) logics different than universal theories, but we don’t have use for that here.

We often omit “finitary” and “to a universal theory in $\mathbb {L}_{\infty , \omega }$ .”

We do not explicitly mention it in the definition, but the restriction functor as above is faithful (injective on arrows).

Proposition 4.2. Any restriction functor between classes of substructures with arrows extending embeddings (such as the one above) is faithful.

Proof In both categories, the arrows between structures are determined by their value on the underlying sets.

Crucially, we should mention that the expansion given by these abstract Skolemizations is not a functorial expansion [18, Definition 3.1]. That is, just like in the original Shelah’s Presentation Theorem and (concrete) Skolemizations, choices must be made in the expansion, and different choices lead to incompatible choices. A functorial expansion (such as a Morleyization) would mean that the lifting property Definition 4.1(2) was strengthened to “…every $f:M \to N$ in $\mathbb {K}$ has a unique lift $f^*:M^* \to N^*\dots $ .”

The following sequence of results connects AECs to abstract Skolemizations (one direction is Shelah’s Presentation Theorem).

Theorem 4.3. If $(\mathbb {K}, \prec _{\mathbb {K}})$ has an abstract Skolemization, then $(\mathbb {K}, \prec _{\mathbb {K}})$ is an AEC with Löwenheim–Skolem number $|\tau ^*|$ , where $\tau ^*$ is the language in the witnessing expansion.

Proof Let $\{F_i : i \in I\}$ and $T^* \subset \mathbb {L}_{\infty , \omega }\left (\tau \cup \{F_i:i\in I\}\right )$ witness the abstract Skolemization. Most of the AEC axioms (recall Definition 2.5 when $\mu =\omega $ ) follow immediately. We comment on the three axioms that tend to cause issues for classes being AECs: coherence, smoothness, and Löwenheim–Skolem.

Coherence: This is directly addressed by the “coherence/local testability” property of the expansion. If we have $M_0 \subset M_1$ , $M_0 \prec _{\mathbb {K}} M_2$ , and $M_1 \prec _{\mathbb {K}} M_2$ , the surjectivity of the restriction gives lifts $M_0^* \subset M_2^{*0}$ and $M_1^* \subset M_2^{*1}$ . This is precisely the setup to give lifts $M_0^{**} \subset M_1^{**} \subset M_2^{**}$ . By applying the restriction functor, we have $M_0 \prec _{\mathbb {K}} M_1$ , as desired.

Smoothness: This is the key use of the condition (2). Let $\langle M_i \in \mathbb {K} : i < \alpha \rangle $ be a continuous, $\prec _{\mathbb {K}}$ -increasing chain of structures with $\alpha $ limit. We define a continuous, $\subset $ -increasing chain $\langle M_i^* \vDash T^* : i < \alpha \rangle $ such that $M_i^*$ is a lift of $M_i$ . To do this, start by letting $M_0^*$ be any lift of $M_0$ . For successors $i = j+1$ , we have a lift $M^*_j$ of $M_j$ and $M_j \prec _{\mathbb {K}} M_i$ , so condition (2) guarantees a lift $M^*_i$ of $M_i$ such that $M^*_j \subset M^*_i$ . For limits, we can take unions since the restriction functor preserves unions.

In the end, we have that

$$ \begin{align*}\bigcup_{i < \alpha} M_i = \left(\bigcup_{i<\alpha} M_i^*\right) \upharpoonright \tau,\end{align*} $$

so this union is in $\mathbb {K}$ and is the least upper bound of the chain.

Löwenheim–Skolem: Let $A \subset M \in \mathbb {K}$ and let $M^*$ be a lift of M. Then, since the restriction functor doesn’t change the universe, $A \subset M^*$ . Set $M^*_0$ to be the closure of A under the $\tau \cup \{F_i : i \in I\}$ -functions of M. Since $T^*$ is universal, $M^*_0 \vDash T^*$ , so $M^*_0 \upharpoonright \tau \prec _{\mathbb {K}} M$ , contains A, and has size $\leq |A|+|\tau \cup \{F_i:i\in I\}|$ .

Theorem 4.4. If $(\mathbb {K}, \prec _{\mathbb {K}})$ is an AEC, then the expansion given in Shelah’s Presentation Theorem is an abstract Skolemization.

The following proof assumes familiarity with the proof and the idea of Shelah’s Presentation Theorem; see [4, Section 3.1] for an exposition.

Proof Shelah’s Presentation Theorem presents $(\mathbb {K}, \prec _{\mathbb {K}})$ by an expansion to $\tau ^*=\tau (\mathbb {K}) \cup \{F^n_{\alpha } : n < \omega , \alpha < \text {LS}(\mathbb {K})\}$ that omit a collection $\Gamma $ of quantifier-free types. We can express this omission through the following $\mathbb {L}_{\infty , \omega }$ sentence:

$$ \begin{align*}\bigwedge_{p \in \Gamma} \forall \mathbf{x} \bigvee_{\phi \in p} \neg \phi(\mathbf{x}).\end{align*} $$

The statement of Shelah’s Presentation Theorem ([4, Fact 3.1.1] is perfect for our purposes) gives everything we need except for the coherence/local testability condition. But this holds exactly because the starting class $(\mathbb {K}, \prec _{\mathbb {K}})$ is an AEC and, therefore, satisfies coherence.

Corollary 4.5. Given a pair $(\mathbb {K}, \prec _{\mathbb {K}})$ in a finitary language, we have that $(\mathbb {K}, \prec _{\mathbb {K}})$ is an AEC iff it has a finitary abstract Skolemization to a universal theory in $\mathbb {L}_{\infty , \omega }$ .

Proof The two directions are Theorems 4.3 and 4.4.

We can also generalize this result to $\mu $ -AECs, which we state without proof (the proof is the same).

Theorem 4.6. Given a pair $(\mathbb {K}, \prec _{\mathbb {K}})$ in a $<\mu $ -ary language, we have that $(\mathbb {K}, \prec _{\mathbb {K}})$ is a $\mu $ -AEC iff it has a ${<}\mu $ -ary abstract Skolemization to a universal theory in $\mathbb {L}_{\infty , \mu }$ .

Now we turn to the question of how to find abstract Skolemizations. As we mentioned at the beginning of this section, our motivation for abstract Skolemizations is to use syntactic axiomatizations of mild extensions of $\mathbb {L}_{\lambda , \omega }$ to show that those logics axiomatize Abstract Elementary classes.

In each example below, the quantifiers are expressible in a fragment of $\mathbb {L}_{\infty , \infty }$ whose only use of infinitary quantification was a single existential quantifier at the very beginning. We highlight these examples to develop a common framework to encompass all of them in Definition 4.8.

Example 4.7. Below, we axiomatize several quantifiers often used in axiomatizing examples of Abstract Elementary Classes: $Q^{\text {cof}}_{\kappa }$ is the cofinality quantifier we have seen; $Q_{\alpha }$ is the quantifier “there exists $\geq \aleph _{\alpha }$ -many”; and $Q^{ec}_{\alpha }$ is the quantifier that says the formula is a definable equivalence class with at least $\alpha _{\alpha }$ -many equivalence classes. In the axiomatization of $Q^{\text {cof}}_{\kappa }$ and $Q^{ec}_{\alpha }$ , “its domain” refers to the set $\{\mathbf {a} : \phi (\mathbf {a}, \mathbf {a}, \mathbf {z})\}$ .

$$ \begin{align*} Q^{\text{cof}}_{\kappa} \mathbf{x}, \mathbf{y} \phi(\mathbf{x}, \mathbf{y}, \mathbf{z}) &\iff \exists \langle \mathbf{x}_i : i < \kappa \rangle \left(\vphantom{\bigvee_{i < \kappa}}"\phi(\mathbf{x}, \mathbf{y}, \mathbf{z}) \text{ defines a linear order on its} \right.\\&\qquad\quad \left. \text{domain with no last element"} \wedge \forall \mathbf{x}' \bigvee_{i < \kappa} \phi(\mathbf{x}', \mathbf{x}_i, \mathbf{z})\right),\\Q_{\alpha} \mathbf{x} \phi(\mathbf{x}, \mathbf{y}) &\iff \exists \langle \mathbf{x}_i : i < \aleph_{\alpha}\rangle \left(\bigwedge_{i < \aleph_{\alpha}} \phi(\mathbf{x}_i, \mathbf{y}) \wedge \bigwedge_{i<j<\aleph_{\alpha}} \mathbf{x}_i \neq \mathbf{x}_j \right), \\\neg Q_{\alpha+1} \mathbf{x} \phi(\mathbf{x}, \mathbf{y}) &\iff \exists \langle \mathbf{x}_i :i < \aleph_{\alpha}\rangle \forall \mathbf{z}\left(\phi(\mathbf{z}, \mathbf{y}) \to \bigvee_{i<\aleph_{\alpha}} \mathbf{z} = \mathbf{x}_i \right),\\Q^{ec}_{\alpha} \mathbf{x}, \mathbf{y} \phi(\mathbf{x}, \mathbf{y}, \mathbf{z}) &\iff \exists \langle\mathbf{x}_i : i < \aleph_{\alpha}\rangle \left(\!\vphantom{\bigwedge_{i < j < \aleph_{\alpha}}}"\phi(\mathbf{x}, \mathbf{y}, \mathbf{z})\text{ defines an equivalence relation} \right.\\&\qquad\quad \left. \text{ on its domain"} \bigwedge_{i < j < \aleph_{\alpha}} \neg\phi(\mathbf{x}_i, \mathbf{x}_j, \mathbf{z}) \right),\\\neg Q^{ec}_{\alpha+1} \mathbf{x}, \mathbf{y} \phi(\mathbf{x}, \mathbf{y}, \mathbf{z}) &\iff \exists \langle \mathbf{x}_i : i < \aleph_{\alpha}\rangle \left(\!\vphantom{\bigvee_{i<\aleph_{\alpha}}}"\phi(\mathbf{x}, \mathbf{y}, \mathbf{z})\text{ defines an equivalence relation} \right.\\&\qquad\quad \left. \text{on its domain"} \wedge \forall \mathbf{x}' \left( \phi(\mathbf{x}', \mathbf{x}', \mathbf{z}) \to \bigvee_{i<\aleph_{\alpha}} \phi(\mathbf{x}_i, \mathbf{x}', \mathbf{z})\right)\!\right). \end{align*} $$

The Ramsey/Magidor–Malitz quantifiers [15] could be similarly expressed in this way. Moreover, the strong substructure relation is exactly elementarity according to the fragment of $\mathbb {L}_{\infty , \infty }$ containing the right-hand sides.

This form is exactly what allows for a finitary abstract Skolemization to $\mathbb {L}_{\infty , \omega }$ (which can then be further Skolemized to a universal theory). Note that the fact that both the positive and negative instances of cardinality quantifiers ⁹ have this nice form is what accounts for not needing to worry about deliberate uses of this quantifier.

We now make this connection precise, beginning with some definitions.

Definition 4.8. Say that a quantifier Q is $\kappa $ -existentially definable in $\mathcal {L}_1$ over $\mathcal {L}_0$ iff, for each language $\tau $ , there is a map

$$ \begin{align*}\phi(\mathbf{x}, \mathbf{y}) \in \mathcal{L}_0(\tau) \mapsto \Psi_{\phi}(\mathbf{x}_i : i < \kappa, \mathbf{y}) \in \mathcal{L}_1(\tau)\end{align*} $$

such that the following holds:

$$ \begin{align*}\vDash \forall \mathbf{y} \left[\left(Q\mathbf{x}\phi(\mathbf{x}, \mathbf{y})\right) \leftrightarrow \left( \exists \{\mathbf{x}_i : i < \kappa\} \bigwedge_{\psi \in \Psi_{\phi}} \psi(\mathbf{x}_i : i<\kappa, \mathbf{y})\right) \right].\end{align*} $$

The following definition only makes sense due to a subtle (and often overlooked) feature of $\mathbb {L}_{\infty , \omega }$ : the formation of infinitary conjuncts and disjuncts is only allowed if the resulting formula has only finitely many free variables. We relax this to form $\mathbb {L}_{(\infty , \omega )}$ .

Definition 4.9. The logic $\mathbb {L}_{(\lambda , \omega )}$ is exactly like $\mathbb {L}_{\lambda , \omega }$ except without the restriction to finitely many free variables in conjunctions and disjunctions.

Since the distinction is subtle, we give an example involving well-ordering to emphasize the differences. As is well-known, $\mathbb {L}_{\omega _1, \omega }$ cannot define well-ordering, while the stronger logic $\mathbb {L}_{\omega _1, \omega _1}$ can (by the sentence $\Phi $ below). We consider three related formulas and discuss how they affect the logics

$$ \begin{align*}\mathbb{L}_{\omega_1, \omega} \subset \mathbb{L}_{(\omega_1, \omega)} \subset \mathbb{L}_{\omega_1, \omega_1}.\end{align*} $$

Example 4.10.

$$ \begin{align*} \phi(x_n : n< \omega)&:= "\bigwedge_{n < \omega} x_{n+1}<x_n,\text{"}\\ \psi(x_n : n < \omega) &:= "\phi(x_n:n<\omega) \to \exists y \bigwedge y < x_n\text{"}\\ \Phi &:= "\exists \langle x_n : n<\omega\rangle \phi(x_n : n < \omega).\text{"} \end{align*} $$

• • $\underline {\mathbb {L}_{\omega _1, \omega }:}$ None of the formulas $\phi (\mathbf {x}), \psi (\mathbf {x}), \Phi \not \in \mathbb {L}_{\omega _1, \omega }$ are in $\mathbb {L}_{\omega _1, \omega }$ and this logic cannot talk about well-ordering in any way. As a further example, we can build models $M \prec _{\mathbb {L}_{\omega _1, \omega }} N$ with an ill-founded sequence in M such that a lower bound is added in N.

• • $\underline {\mathbb {L}_{\omega _1, \omega }:}$ The formulas $\phi (\mathbf {x}), \psi (\mathbf {x})$ are in this logic, but it does not contain the full sentence $\Phi $ that asserts the relation is well-ordered. This gives it a limited ability to discuss well-ordering. Thus, in contrast with $\mathbb {L}_{\omega _1, \omega }$ , if we are given $M \prec _{\mathbb {L}_{(\omega _1, \omega )}} N$ , then any ill-founded sequence from M with a lower bound in N must have already had a lower bound in M (by applying the elementarity to $\psi (\mathbf {a})$ ). However, we can still build models $M' \prec _{\mathbb {L}_{(\omega _1, \omega )}} N'$ such that $M'$ is well-ordered but $N'$ is not well-ordered.

• • $\underline {\mathbb {L}_{\omega _1, \omega _1}:}$ . All the formulas $\phi (\mathbf {x}), \psi (\mathbf {x}),$ and $\Phi $ are in this logic, and well-ordering is definable. Thus, if $M' \prec _{\mathbb {L}_{\omega _1, \omega _1}} N'$ , then $M'$ is well-ordered iff $N'$ is well-ordered.

Definition 4.8 captures the quantifiers listed above.

Proposition 4.11. All quantifiers in Example 4.7 are $\kappa $ -existentially definable in $\mathbb {L}_{(\lambda +\kappa , \omega )}$ over $\mathbb {L}_{\lambda , \omega }$ for the appropriate $\kappa $ .

Proof The required maps are exactly given in Example 4.7.

Theorem 4.12. If Q is $\kappa $ -existentially definable in $\mathbb {L}_{(\mu , \omega )}$ over $\mathbb {L}_{\lambda , \omega }$ , then classes axiomatized by positive, deliberate uses of Q in $\mathbb {L}_{\lambda , \omega }$ have finitary abstract Skolemizations.

Furthermore, the same holds if $\mathbb {L}_{\lambda , \omega }$ is extended by some collection of quantifiers that are $\kappa $ -existentially definable in $\mathbb {L}_{(\mu , \omega )}$ over $\mathbb {L}_{\lambda , \omega }$ .

Proof Let Q be $\kappa $ -existentially definable in $\mathbb {L}_{(\mu , \omega )}$ over $\mathbb {L}_{\lambda , \omega }$ via the map $\phi (\mathbf {x}, \mathbf {y}) \mapsto \Psi (\mathbf {x}_i : i<\kappa , \mathbf {y})$ . Following Definition 3.1, an axiomatization via positive, deliberate uses of Q in $\mathbb {L}_{\lambda , \omega }$ consists of:

• • $T \subset \mathbb {L}_{\lambda , \omega }\left (Q\right )(\tau )$ with Q only occurring positively;

• • $\tau ^* = \tau \cup \{R_{\phi }(\mathbf {y}) : \phi (\mathbf {x}, \mathbf {y}) \in \mathbb {L}_{\lambda , \omega }(\tau )\}$ ;

• • $T^* \subset \mathbb {L}_{\lambda , \omega }(\tau )$ is the result of inductively replacing instances of “ $Q\mathbf {x} \phi (\mathbf {x}, \mathbf {y})$ ” in T by “ $R_{\phi }(\mathbf {y})$ ”; and

• • $T^+ = T^* \cup \left \{\forall \mathbf {y}\left ( R_{\phi }(\mathbf {y}) \to Q \mathbf {x} \phi (\mathbf {x}, \mathbf {y}) \right ) : \phi (\mathbf {x}, \mathbf {y}) \in \mathbb {L}_{\lambda , \omega } \right \}.$

Then $\mathbb {K} := \operatorname {\mathrm {Mod}}(T^+)$ is the class we need to provide the Skolemization for. We describe the Skolemization in two steps.

For the first step, for each $\phi (\mathbf {x}, \mathbf {y})$ , add functions

$$ \begin{align*}\left\{ F^{Q, \phi}_{i, j}(\mathbf{y}) : i < \kappa, j < \ell(\mathbf{x})\right\}\end{align*} $$

and set

$$ \begin{align*}T^{++} = T^* \cup \left\{ \forall \mathbf{y}\left( R_{\phi}(\mathbf{y}) \to \Psi_{\phi}\left(F^{Q, \phi}_{i,j}(\mathbf{y}) : j < \ell(\mathbf{x}), i<\kappa, \mathbf{y}\right)\right) : \phi(\mathbf{x}, \mathbf{y}) \in \mathbb{L}_{\lambda, \omega} \right\}.\end{align*} $$

Crucially, $T^{++}$ is an $\mathbb {L}_{\lambda +\mu ,\omega }$ -theory. So this gives a Skolemization of $T^+$ to a (non-universal) theory in $\mathbb {L}_{\lambda +\mu , \omega }$ . It is a standard result (see, e.g., [13, Theorem 17] for the case $\mathbb {L}_{\omega _1, \omega }$ ) that $\mathbb {L}_{\infty , \omega }$ theories have finitary Skolemizations to universal theories in $\mathbb {L}_{\infty , \omega }$ ; the second step is to do this Skolemization.

Putting these steps together, we have a finitary Skolemization of $\mathbb {K}$ to a universal theory in $\mathbb {L}_{\infty , \omega }$ ; we can define $\prec _{\mathbb {K}}$ by setting $M \prec _{\mathbb {K}} N$ iff there are lifts $M^*$ and $N^*$ such that $M^* \subset N^*$ .

Corollary 4.13. All of the quantifiers listed in Example 4.7 form AECs when used positively and deliberately over $\mathbb {L}_{\infty , \omega }$ and can be mixed together.

Note that the strong substructure relation $\prec _{\mathbb {K}}$ in Definition 4.1 can be recovered from the expansion $T^*$ . Chasing through the definitions, the appropriate strong substructure relation in the cases above is elementarity according to the fragment of $\mathbb {L}_{\infty , \infty }$ needed to define the quantifiers; this corresponds exactly to the seemingly ad hoc notions given for cardinality and cofinality quantifiers.