Universal abstract elementary classes and locally multipresentable categories
Michael Lieberman Jiří Rosický Sebastien Vasey
math.LO math.CT 03C48 (Primary), 18C35, 03C52, 03C55, 03C75 (Secondary)



  We exhibit an equivalence between the model-theoretic framework of universal classes and the category-theoretic framework of locally multipresentable categories. We similarly give an equivalence between abstract elementary classes (AECs) admitting intersections and locally polypresentable categories. We use these results to shed light on Shelah's presentation theorem for AECs.
 

A Locally Adapting Technique for Boundary Detection using Image Segmentation
    Marylesa Howard howardmm@nv.doe.gov 

       Signal Processing and Applied Mathematics

       Nevada National Security Site

       P.O. Box 98521, M/S NLV078, Las Vegas, NV 89193-8521, USA
       Margaret C. Hock hockmc@nv.doe.gov 

       Signal Processing and Applied Mathematics

       Nevada National Security Site

       P.O. Box 98521, M/S NLV078, Las Vegas, NV 89193-8521, USA


       Department of Mathematical Sciences

       University of Alabama in Huntsville

       301 Sparkman Drive, 258A, Huntsville, AL 35899, USA
       B. T. Meehan meehanbt@nv.doe.gov

       Signal Processing and Applied Mathematics

       Nevada National Security Site

       P.O. Box 98521, M/S NLV078, Las Vegas, NV 89193-8521, USA
       Leora Dresselhaus-Cooper lacooper@mit.edu

       Department of Physical Chemistry, Institute for Soldier Nanotechnology

       Massachusetts Institute of Technology

       77 Massachusetts Avenue, NE47-593, Cambridge, MA 02139, USA
    December 30, 2023
================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================







§ INTRODUCTION


Abstract elementary classes (AECs) <cit.> were introduced by Shelah in the late seventies as a purely semantic framework in which to study the model theory of infinitary logics such as _∞, ω. At about the same time, Lair <cit.> introduced the notion of an accessible category (which he called a “catégorie modelable”) and proved that accessible categories are exactly those that can be sketched. Independently, the second author showed in his doctoral thesis <cit.> that accessible categories correspond to classes of models of an _∞, ∞-sentence, thus exhibiting an explicit connection with model theory. Later Makkai and Paré <cit.> independently rediscovered these results and showed that they say essentially the same thing in different languages. The connection between AECs and accessible categories was then studied more closely by the first author <cit.> and independently by Beke and the second author <cit.>. These works characterized AECs as special kinds of accessible categories with all directed colimits and whose morphisms are monomorphisms.

In recent joint work with Boney and Grossberg <cit.> the authors introduced μ-AECs, a generalization of AECs where only closure under μ-directed colimits is required. It was shown that μ-AECs correspond exactly to accessible categories whose morphisms are monomorphisms (the correspondence is given in terms of an equivalence of categories: see Fact <ref> for a more precise statement). This gives evidence that these frameworks are natural.

One of the questions that motivated Shelah's introduction of AECs is the eventual categoricity conjecture: an AEC categorical in a single high-enough cardinal (i.e. with a unique model of that cardinality, up to isomorphism) should be categorical in all high-enough cardinals. This conjecture has profoundly shaped the development of the field (see the introduction of <cit.> for a survey and history of the conjecture). Note that Shelah's eventual categoricity conjecture can be rendered as a purely category-theoretic statement, with cardinalities replaced by presentability ranks—see <cit.>)—and hence can be posed in relation to general accessible categories. 

Recently, the third author <cit.> proved that the conjecture holds in the more restricted framework of universal classes: classes of structures closed under isomorphism, substructures, and union of chains. Universal classes had previously been studied by, among others, Tarski <cit.> and Shelah <cit.>.

In this paper, we show (Theorem <ref>) that universal classes have a natural category-theoretic analog: the locally ℵ_0-multipresentable categories (whose morphisms are monomorphisms) introduced by Diers <cit.>. They can be characterized as the ℵ_0-accessible categories that have all connected limits, i.e. those generated from equalizers and wide pullbacks (see Fact <ref>). More generally, we prove that μ-universal classes (where we allow the relations and functions to have arity strictly less than μ) correspond to locally μ-multipresentable categories.

After the initial submission of this paper, Hyttinen and Kangas <cit.> have continued the work of the third author by proving that, in a technical model-theoretic sense, the big-enough models in an eventually categorical universal classes look like either vector spaces or sets. In light of the present paper, it would be interesting to know whether their result has a category-theoretic analog.

Another type of AEC that was studied in the third author's proof of the categoricity conjecture for universal classes are those which admit intersections. They were introduced by Baldwin and Shelah <cit.> and can be characterized as the AECs admitting a certain closure operator. Any universal class admits intersections and the third author has shown <cit.> that the categoricity conjecture holds in AECs admitting intersections if we assume a large cardinal axiom. We suggest that such AECs are also natural by characterizing them (Theorem <ref>) as the locally ℵ_0-polypresentable categories of Lamarche <cit.>. These are the ℵ_0-accessible categories with wide pullbacks (see Fact <ref>).  Indeed, this result generalizes as well: per Theorem <ref>, any μ-AEC admitting intersections is a locally μ-polypresentable category. Examples of locally multi- and polypresentable categories arise naturally in areas such as functional analysis, algebra, and even computer science, see Example <ref>. 

In the final section of this paper, we present a generalization of Shelah's presentation theorem <cit.> to all accessible categories with arbitrary μ-directed colimits whose morphisms are monomorphisms: we show (Theorem <ref>) that any such category is the essential image by a faithful functor of a μ-universal class. This generalizes the category-theoretic presentation theorem of the first and second authors <cit.> as well as Boney's presentation theorem for metric AECs <cit.>.  (Recall that metric AECs are an analogue of AECs in which the structures have underlying complete metric spaces, rather than sets: see <cit.> or <cit.>.) We give one more characterization of the μ-AECs admitting intersections as those classes for which the functor is, in a sense, close to being full (see Definition <ref> and Theorem <ref>).

Throughout this paper, we assume the reader is familiar with basic category theory as presented e.g. in <cit.>. We also assume some familiarity with μ-AECs and their relationship with accessible categories <cit.>.

We use the following notational conventions: we write K for a class of τ-structures and  (boldface) for a pair (K, ), where  is a partial order. We write  (script) for a category. We will abuse notation and write M ∈ instead of M ∈ K. For a structure M, we write U M for its universe, and |U M| for the cardinality of its universe. We write M ⊆ N to mean that M is a substructure of N. For α an ordinal, we let <αA [resp. αA] denote the set of sequences of length less than [resp. exactly] α with elements from the set A. We will abuse this notation as well, writing <αM in place of <αU M.

The authors would like to thank Will Boney for comments that helped improve the presentation of this paper.



§ UNIVERSAL CLASSES OR CLASSES WITH INTERSECTIONS


The following concept was introduced by Tarski for finite vocabularies <cit.> and by Shelah for infinite (but still finitary) vocabularies <cit.>. In this paper, we study it for potentially infinitary vocabularies:


  Let μ be a regular cardinal. K is a μ-universal class if:

  
  
  * K is a class of structures in a fixed μ-ary vocabulary τ = τ (K).
  
  * K is closed under isomorphism, unions of μ-directed systems of τ-substructure inclusions, and τ-substructures.
  

  When μ = ℵ_0, we omit it and just say that K is a universal class.


We say that an _∞, ∞-sentence is universal if it has the form ∀ϕ, where ϕ is quantifier-free. We say that a theory is universal if it consists only of universal sentences. Tarski has shown <cit.> that a universal class in a finite (and finitary) vocabulary is the class of models of a universal _ω, ω-theory. The proof generalizes without difficulties to infinitary logics:

[Tarski's presentation theorem]
  Let μ be a regular cardinal and K be a class of structures in some μ-ary vocabulary τ. The following are equivalent:

  
  
  *  There is a set Γ of quantifier-free _∞, μ-types such that K is the class of all τ-structures omitting Γ.
  
  *  K is the class of models of a universal _∞, μ theory.
  
  *  K is a μ-universal class.
  


  That (<ref>) implies (<ref>) and (<ref>) implies (<ref>) can be easily verified. To see that (<ref>) implies (<ref>), let K_0 be the class of τ-structures that are generated by a set of size less than μ and are not contained in any member of K. Let Γ be the set of types that code each structure in K_0, and use a μ-directed system argument to see that K is the set of τ-structures omitting Γ.


Recall from <cit.> that a (μ-ary) abstract class is a pair = (K, ≤) such that K is a class of structures is a fixed μ-ary vocabulary τ = τ (), and ≤ is a partial order on K that respects isomorphisms and extends the τ-substructure relation. We say that such a  is a μ-universal class if K is a μ-universal class and = ⊆.

In any abstract class , there is a natural notion of morphism: we say that f: M → N is a -embedding if f is an isomorphism from f onto f[M] and f[M]  N. We can see an abstract class and its -embeddings as a category. In fact (see <cit.>), an abstract class is a replete and iso-full subcategory of the category of τ-structures with injective homomorphisms.



We now recall the definition of a μ-AEC from <cit.>:


  Let μ be a regular cardinal. An abstract class  is a μ-abstract elementary class (or μ-AEC for short) if it satisfies the following three axioms:

  
  
  * Coherence: for any M_0, M_1, M_2 ∈, if M_0 ⊆ M_1  M_2 and M_0  M_2, then M_0  M_1.
  
  * Chain axioms: if M_i : i ∈ I is a μ-directed system in , then:
    
    
  * M := ⋃_i ∈ I M_i is in .
    
  * M_i  M for all i ∈ I.
    
  * If M_i  N for all i ∈ I, then M  N.
    
  
  * Löwenheim-Skolem-Tarski (LST) axiom: there exists a cardinal λ = λ^<μ≥ |τ ()| + μ such that for any M ∈ and any A ⊆ U M, there exists M_0 ∈ with M_0  M, A ⊆ U M_0, and |U M_0| ≤ |A|^<μ + λ. We write () for the least such λ.
  


Note that when μ = ℵ_0, we recover Shelah's definition of an AEC from <cit.>. Note, too, that a μ-universal class, equipped with the τ-substructure relation, is a μ-AEC. In this case, we may call it a universal μ-AEC. Equivalently, a universal μ-AEC is a μ-AEC  such that for any N ∈, M ⊆ N implies that M ∈ and M  N.

More general than μ-universal classes are μ-AECs admitting intersections. AECs admitting intersections were introduced in <cit.> and further studied in <cit.>.


  A μ-AEC  admits intersections if for any N ∈ and any A ⊆ U N, the set

  
    ^N (A) = ^N (A) := ⋂{M ∈| M  N, A ⊆ U M}

is the universe of a -substructure of M. In this case, we abuse notation and write ^N (A) for this substructure as well.


Note that any universal μ-AEC  admits intersection, since ^N (A) is a substructure of N and  is closed under substructures. On the other hand, the AEC of algebraically closed fields admits intersections but is not a universal class (ℚ is a subfield of an algebraically closed field, but it is not algebraically closed).

Many of the properties of AECs admitting intersections proven in <cit.> can be generalized to μ-AECs: it suffices to replace ℵ_0 by μ in the proofs. For example:


  Let  be a μ-AEC that admits intersection.

  
  
  * If M  N and A ⊆ U M, then ^M (A) = ^N (A).
  
  * Local character: If B ⊆^N (A) and |B| < μ, then there exists A_0 ⊆ A such that |A_0| < μ and B ⊆^N (A_0).
  


We will use these facts without much comment in the sequel.

Similarly to <cit.>, one can define the notion of a pseudo-universal μ-AEC:


  A μ-AEC  is pseudo-universal if it admits intersections and whenever f, g: M → N are -embeddings and A ⊆ U M is such that f  A = g  A, then f ^M (A) = g ^M (A).


  A universal μ-AEC is pseudo-universal: since ^M (A) is just the closure of A under the functions of M, any -embedding with domain ^M (A) is determined by its restriction to A.


Some motivation may be in order: consider the class of groups in the language containing a symbol for multiplication, identity, and inverse. Then this is a universal class. On the other hand, if we look at the class of groups in the language containing only multiplication and identity, then it is not universal: substructures need not be closed under inverses. However it will still be pseudo-universal, since inverses are definable from the rest. In fact, we will see shortly (Theorem <ref>) that this is how all pseudo-universal classes look: any such class admits a functorial expansion to a universal one.

Although we will not need it in this paper, we also note that we can imitate the proof of <cit.> to show that any pseudo-universal μ-AEC is fully (<μ)-tame and short over ∅.

We now show that pseudo-universal μ-AECs are the same as universal μ-AECs, up to extension of the vocabulary. Recall from <cit.> the notion of a functorial expansion of an abstract class : roughly, it is an abstract class  in an expansion of τ () such that the reduct map is an isomorphism of concrete categories. We show that every pseudo-universal class (that does not contain the empty structure) can be functorially expanded to a universal class. This result is not needed in the rest of this paper, where we deal with equivalence of categories, but shows that every pseudo-universal class is isomorphic (not just equivalent) to a universal class.


  Let  be a pseudo-universal μ-AEC that does not contain the empty structure. Then there is a functorial expansion  of  which is a universal μ-AEC. Moreover, |τ ()| ≤ 2^ ().


  Any abstract class admits a notion of type, called Galois (or orbital) types in the literature. They can be defined as the finest notion of type preserving -embeddings (see <cit.> for a formal definition). The proof, in short, is to take the (<μ)-Galois Morleyization (i.e. expand the language with a symbol for every type of length less than μ, see <cit.>) and then add Skolem functions. This works since types are able to code the closure operator. We now give a self-contained implementation of this proof.

  We will write ^M () instead of ^M () (here  denotes the range of , i.e. the set of elements in the sequence ) and b for the concatenation of the sequence  with the element b. For M_1, M_2 ∈, _ℓ∈<μM_ℓ, ℓ = 1,2, write (_1, M_1) ≡ (_2, M_2) if there exists an isomorphism f: ^M_1 (_1) ≅^M_2 (_2) such that f (_1) = _2. Note that ≡ is an equivalence relation with at most 2^ ()-many classes. We say that an equivalence class C codes closure if C = [( b, M)]_≡ implies that b ∈^M (). Note that if C codes closure, C = [( b, M)]_≡, and ( b', M) ≡ ( b, M), then b' = b. Indeed, by definition there is an isomorphism f: ^M ( b) ≅^M ( b') such that f ( b) = f ( b'). This is in particular an isomorphism f: ^M () ≅^M () sending  to . The identity is another such isomorphism, hence by pseudo-universality f must be the identity.

  Fix a well-ordering ≼ on the set of equivalence classes coding closure. Let  consist of τ () together with a new α-ary function symbol f_C for each C coding closure with C = [( b, M)]_≡, ℓ () = α. For each M ∈, define a -expansion  by setting f_C^ () to be the unique b ∈^M () such that C = [( b, M)]_≡, provided it exists. Otherwise, let D be ≼-least coding closure such that there exists b' ∈ M with D = [(b', M)]_≡ and set f_C^ () = b'. Note that such a D always exists as ^M (∅) ≠∅ (we are assuming the empty structure is not part of ).

  Let K := {| M ∈}. It is easy to check that K is a functorial expansion of  (see also <cit.>), hence we can let := (K, ), where M  N if and only if M ⊆ N and M τ ()  N τ (). We claim that  is a universal μ-AEC. It is enough to show that for any N ∈, M ⊆ N implies that M  N. Indeed, noting that , and hence , admits intersections, it suffices to show that ^N (M) = M. In what follows, we do not distinguish between ≡ computed in  and  and between the closure operations _ and _: since  is a functorial expansion of , they are the same up to expansion of the language.

  Clearly, M ⊆^N (M), so let us check that ^N (M) ⊆ M. Let b ∈^N (M). By local character (Fact <ref>), there exists A ⊆ U M of size less than μ such that b ∈^N (A). Let  be an enumeration of A. Let C := [( b, N)]_≡. Then C codes closure and b ∈ N, hence we must have that f_C^N () = b. Since M ⊆ N, b = f_C^N () = f_C^M (), so b ∈ U M, as desired.



  The restriction that  does not contain the empty structure is essential, as otherwise one would not be able to add constant symbols to the vocabulary to code the closure of the empty set. This is, nonetheless, not a serious restriction: given any μ-AEC  there is a μ-AEC ' that is isomorphic to  as a category and does not contain the empty structure: for each M ∈, expand M to a (τ () ∪{c})-structure M' ∈', where c is a new constant symbol, such that c^M'∉ U M, U M' = {c^M'}∪ U M, and a relation R^M' () holds if and only if either c^M'∈ran () or c^M'∉ran () and R^M ().  For any function symbol f∈τ (), define f^M' () = c^M' if c^M'∈ran () and f^M' () = f^M () otherwise. Finally, for M_1', M_2' ∈', let M_1 ' M_2 if and only if M_1  M_2 and c^M_1' = c^M_2'.
  



§ ACCESSIBLE CATEGORIES


To present category-theoretic equivalents of μ-universal classes and μ-AECs admitting intersections, we require the notion of an accessible category (see <cit.> or <cit.>).


  Let  be a category and let λ be a regular cardinal.

  
  
  * An object M is λ-presentable if its hom-functor (M,-):→ preserves λ-directed colimits. Put another way, M is λ-presentable if for any morphism f:M→ N with N a λ-directed colimit ⟨ϕ_α:N_α→ N⟩, f factors essentially uniquely through one of the N_α, i.e. f=ϕ_α f_α for some f_α:M→ N_α.
  
  *  is λ-accessible if it has λ-directed colimits and  contains a set S of λ-presentable objects such that every object of  is a λ-directed colimit of objects in S.
  
  *  is accessible if it is λ'-accessible for some regular cardinal λ'.
  


Intuitively, an accessible category is a category with all  sufficiently directed colimits and such that every object can be written as a highly directed colimit of “small” objects.  Here “small” is interpreted in terms of presentability, a notion of size that makes sense in any (possibly non-concrete) category. In the category of sets, of course, a set is λ-presentable if and only if its cardinality is less than λ; in an AEC , the same is true for all λ>().  

From <cit.>, we have that μ-AECs are the same as accessible categories whose morphisms are monomorphisms, up to equivalence of categories:


  If  is a μ-AEC, then it is an ()^+-accessible category with all μ-directed colimits whose morphisms are monomorphisms. Conversely, any μ-accessible category whose morphisms are monomorphisms is equivalent to a μ-AEC.


In general, a μ-AEC need not be a μ-accessible category and, in fact, the least cardinal λ such that  is λ-accessible cannot be bounded by a function of μ: this is the case, in short, because the index of accessibility is determined as much by the parameter () as by μ. For example, given a regular cardinal λ, the (ℵ_0-)AEC  of sets of cardinality at least λ (ordered by subset inclusion) contains no λ-presentable objects, hence cannot be ℵ_0-accessible or even λ-accessible.  It is, however, λ^+-accessible, as ()=λ. We can show, though, that μ-AECs admitting intersections are μ-accessible:


  If  is a μ-AEC admitting intersections, then  is μ-accessible.


  By definition of a μ-AEC,  has all μ-directed colimits. It remains to exhibit a set of μ-presentable objects in  such that every element of  is a μ-directed colimit thereof.

  Let us call M ∈ μ-generated if there exists a set A ⊆ U M with |A| < μ such that M = ^M (A). Clearly, there is only a set of isomorphism types of μ-generated objects. Moreover by the local character property of the closure operator (Fact <ref>), it follows that any N ∈ can be written as ⋃_A ⊆ U N, |A| < μ^N (A). In other words, every N is a μ-directed colimit of μ-generated objects. Moreover it is easy to check that μ-generated objects are μ-presentable. This completes the proof.




§ AXIOMATIZABILITY OF ACCESSIBLE CATEGORIES


For completeness, we recall that accessible categories can be presented syntactically. For an _∞, ∞-sentence ϕ, we denote by (ϕ) the category of models of ϕ with homomorphisms (i.e. mappings preserving all functions and relations). We say that a category  is axiomatizable by ϕ if  is equivalent to the category (ϕ). We call ϕ basic if it is a conjunction of sentences of the form ∀ (ϕ_1 →ϕ_2), where ϕ_1 and ϕ_2 are positive existential formulas. Following <cit.>, let us call a category (∞, μ)-elementary if it is axiomatizable by a basic _∞, μ-sentence (this is the same as the category of models of an arbitrary _∞, μ-sentence ordered by elementarity according to a suitable fragment, see <cit.>). 

A theorem of the second author <cit.> asserts that accessible categories are precisely the (∞, ∞)-elementary ones. More precisely, by <cit.> we have:

   
  
  * Any (∞, μ)-elementary category is accessible and has all μ-directed colimits.
  
  * Any μ-accessible category is (∞, μ)-elementary.
  


In this paper, we are interested in abstract classes where the morphisms are substructure embeddings. For ϕ an _∞, ∞-sentence, denote by (ϕ) the category of models of T with substructure embeddings (i.e. injective mappings preserving all functions and relations and reflecting all relations). Thus the difference between  and  when all morphisms are mono is the same as the difference between graphs ordered by the subgraph relation and graphs ordered by the induced subgraph relation. From the point of view of category theory, this is not a serious difference:


  Let μ be an infinite cardinals and let  be a category. The following are equivalent:

  
  
  *   is equivalent to (ϕ), for ϕ a basic _∞, μ-sentence, and all the morphisms of  are monomorphisms.
  
  *   is equivalent to (ϕ), for ϕ a basic _∞, μ-sentence.
  


  Assume (<ref>). Add a sort for each relation symbol and code relations as sets of tuples. Let ϕ' describe this. Then (ϕ) and (ϕ') are isomorphic. Therefore (<ref>) holds. Conversely, assume (<ref>). For each relation symbol R, add a relation symbol R coding the negation of R. Also add a relation symbol ≠ coding non-equality. Once again, we obtain a sentence ϕ' such that (ϕ') is isomorphic to (ϕ). Therefore (<ref>) holds.


It follows, for example, (see Lemma <ref> and Fact <ref>) that μ-AECs admitting intersections are equivalent to the category of models of an _∞, μ-sentence. Note that the stronger statement that every μ-AEC admitting intersections is directly axiomatizable (without changing the category) by an _∞, μ-sentence is false. Indeed, the AEC whose models are equivalence relations all of whose classes are countably infinite, ordered by the relation “equivalence classes do not grow,” is not the class of models of an _∞, ω-sentence.

Similarly, it is not known whether any AEC is directly _∞,  ()^+-axiomatizable, but by Fact <ref>, it is equivalent to a category of models of an _∞,  ()^+-sentence.

It is also not known whether there is a natural category-theoretic definition of the (∞, μ)-elementary categories (see the discussion after <cit.>). In fact, it is not known whether all μ-AECs are (∞, μ)-elementary (this question was posed in <cit.> in relation to accessible categories with all morphisms monomorphisms).



§ LOCALLY MULTI- AND POLYPRESENTABLE CATEGORIES


The concept of a locally presentable category is originally due to Gabriel and Ulmer <cit.>. We will use the following definition: 


  For μ a regular cardinal, we say that a category  is locally μ-presentable if it is μ-accessible and has all (small) colimits. We say it is locally presentable if it is μ'-locally presentable for some μ'.


Examples include the category of groups with group homomorphisms or any Grothendieck topos. Although we will move quickly to other characterizations, the initial definitions of, and motivations for, locally multipresentable and locally polypresentable categories arise from mathematically natural weakenings of the notion of colimit.  Just as colimits go back to initial objects, one can define a notion of multicolimit that goes back to a multiinitial object. This is a set  of objects of a category  such that for every object M of  there is a unique i ∈ and a unique morphism f_i : i → M. For example, the category of fields and field homormorphisms does not have an initial object, but does have a multiinitial object: the prime fields in each characteristic. 

There is also the still weaker notion of a polyinitial object. This is a set  of objects of a category  such that for every object M in :



  * There is a unique i ∈ having a morphism i → M.

  * For each i ∈, given f,g:i → M, there is a unique (isomorphism) h:i → i with fh=g.


For example, the algebraic closures of the prime fields form a polyinitial object in the category of algebraically closed fields.

The multicolimit of a diagram D in a category  is a multiinitial object in the category of cones on D, i.e. a set of cones such that for any cone on D, there will be a unique induced map from exactly one of the members of the set.  The polycolimit of a diagram is defined similarly.

One then defines locally multi- and polypresentable categories by replacing colimits by multicolimits and polycolimits, respectively:


  For μ a regular cardinal, we say that a category  is locally μ-[multi/poly]presentable if it is μ-accessible and has all [multi/poly]colimits. Locally [multi/poly]presentable means locally μ'-[multi/poly]presentable for some μ'.  


  The set  in the definition of a multiinitial object is allowed to be empty. Thus in a locally μ-multipresentable category, a diagram of the form

  
    @=3pc
        M_1    
    
        M_0  [u]  [r]    
        M_2

may not even be completable: there might not exist morphisms  M_ℓ→ N making the diagram commute. In model-theoretic terms, the category may not have the amalgamation property (see <cit.> for examples of universal classes failing the amalgamation property in non-trivial ways).

   
  
  * As noted above, the category of all fields with field homomorphisms is locally ℵ_0-multipresentable.  It is not locally ℵ_0-presentable as it cannot have an initial object—a consideration of characteristics makes clear that no single field can map into all of the others.  There is, however, an initial object relative to the fields of each fixed characteristic, which together form the multiinitial family (<cit.>).
  
  * The category of linearly ordered sets with order-preserving maps is locally ℵ_0-multipresentable, with multiinitial family consisting of two objects, one for the connected linear orders and one for the disconnected (<cit.>).
  
  * The category of pre-Hilbert spaces (i.e. we do not require completeness) with linear orthogonal maps is locally ℵ_0-multipresentable, while the category of Hilbert spaces with linear orthogonal maps is locally ℵ_1-multipresentable (<cit.>).
  
  * As noted above, the category of algebraically closed fields with fields homomorphisms is locally ℵ_0-polypresentable (<cit.>).  Here the polyinitial family consists of the closures of the prime fields.
  
  * Lamarche's categories of aggregates <cit.> and Coquand's categories of embeddings <cit.> are examples of, respectively, locally ℵ_0-multipresentable and locally ℵ_0-polypresentable categories whose morphisms are monomorphisms.  Both notions arise in theoretical computer science, as efforts to model the phenomenon of polymorphism in type theory.
  


We can also characterize each of these categories in terms of limits:


  Let  be a μ-accessible category.

  
  
  * <cit.>  is locally μ-polypresentable if and only if  has wide pullbacks (that is, limits over diagrams A_i→ A, i∈ I, where I is a set).
  
  * <cit.>, <cit.>  is locally μ-multipresentable if and only if  has all connected limits.
  
  * <cit.>, <cit.>  is locally μ-presentable if and only if  has all limits.
  


Note that the locally presentable categories whose morphisms are monomorphisms are not very interesting: since they have coequalizers, it must be the case that any two morphisms f, g : M → N are equal! In other words, between any two objects there is at most one morphism. Thus locally presentable categories whose morphisms are monomorphisms are exactly the complete lattices. In particular, they are small and their objects are rigid.

However, the situation is different for locally multi- and polypresentable categories:


  Let  be a μ-AEC. If  admits intersections, then  is locally μ-polypresentable. If in addition  is pseudo-universal, then  is locally μ-multipresentable.

 
  By Lemma <ref>,  is μ-accessible. It is easy to check that having wide pullbacks in a μ-AEC is the same as admitting intersections. Therefore  has wide pullbacks and hence by Fact <ref> is locally μ-polypresentable.

  Assume now that  is pseudo-universal. We check that  has connected limits, which is enough by Fact <ref>. To see that  has connected limits, it suffices to check that  has wide pullbacks and equalizers (this is similar to the proof that having arbitrary limits is the same as having products and equalizers <cit.>). We have already checked that  has wide pullbacks. As for equalizers this is implied by the definition of a pseudo-universal class: assume we have two -embeddings f, g: M → N. Let A := {x ∈ U M | f (x) = g (x)}. By definition of A, f  A = g  A. By the definining condition of pseudo-universality, f ^M (A) = g ^M (A). Therefore A = ^M (A), so A  M. Therefore h := f  A is a -embedding and hence the equalizer of f and g.


We obtain the following characterization of μ-AECs admitting intersections:


  Let  be a category and let μ be a regular cardinal. The following are equivalent:

  
  
  *  is locally μ-polypresentable and all its morphisms are monomorphisms.
  
  *  is equivalent to a μ-AEC which admits intersections.
  


  If  is equivalent to a μ-AEC which admits intersections, then by Lemma <ref>,  is locally μ-polypresentable. Conversely, assume that  is locally μ-polypresentable and all its morphisms are mono. By Fact <ref>,  is equivalent to a μ-AEC . Since  has wide pullbacks,  has wide pullbacks, hence  must admit intersections.


For locally μ-multipresentable categories, we give a syntactic description. Johnstone <cit.> has shown (for μ = ℵ_0) that they can be axiomatized by disjunctive theories (see the proof below), and we can then Skolemize to obtain a universal class.

 If  is a locally μ-multipresentable category with all morphisms monomorphisms, then  is axiomatizable by a universal _∞, μ-theory.


Consider the canonical embedding E:→^^ where  is the representative full subcategory of μ-presentable objects in . Then E preserves μ-directed colimits and μ-presentable objects. Following <cit.>,  is equivalent to a μ-cone-orthogonality class in ^^ and the latter category can be viewed as an equational variety of many-sorted universal algebras. Thus  can be axiomatized by a disjunctive theory in the corresponding unary vocabulary τ (see <cit.>). Recall that this theory consists of sentences

    (∀)(φ()→(∃ !) ⋁_i∈ Iψ_i(,))∧(∀,)⋁_i≠ j∈ I(ψ_i(,)∧ψ_j(,)

where φ and ψ_i are conjunctions of atomic formulas and , are strings of variables. The use of ∃ ! can be eliminated by introducing a new relation symbol R (,) such that R(,) if and only if 
⋁_i∈ Iψ_i(,) and then adding Skolem functions. Thus  can be axiomatized by a universal _∞, μ-theory.


We obtain the following characterization of universal classes:


  Let  be a category and let μ be a regular cardinal. The following are equivalent:

  
  
  *   is locally μ-multipresentable and all its morphisms are monomorphisms.
  
  *   is equivalent to (T), for some universal _∞, μ-theory T.
  
  *   is equivalent to a universal μ-AEC.
  
  *   is equivalent to a pseudo-universal μ-AEC.
  


  (<ref>) implies (<ref>) is Lemma <ref> combined with Lemma <ref>. (<ref>) implies (<ref>) is Fact <ref>. (<ref>) implies (<ref>) is Remark <ref>. Finally, (<ref>) implies (<ref>) is Lemma <ref>.


Note that a syntactic characterization of locally polypresentable classes (in terms of models of a pullback theory) is also known <cit.> (see also Rabin's characterization of first-order theories with intersections <cit.>).



 §.§ Summary

We have the following hierarchy of categories whose morphisms are monomorphisms, for μ a fixed regular cardinal:



  * Locally μ-multipresentable.

  * Locally μ-polypresentable.

  * Accessible.


Each level is properly contained in the next and each level admits a characterization in terms of abstract classes (see Theorem <ref>, Theorem <ref>, and Fact <ref>):



  * Universal μ-AEC.

  * μ-AEC admitting intersections.

  * μ'-AEC, for some μ'.


Each level also has a known syntactic characterization (see Theorem <ref>, <cit.>, and Fact <ref>):



  * (T), for T a universal _∞, μ-theory.

  * (T), for T a pullback _∞, μ-theory.

  * (T), for T a basic _∞, ∞-theory.


We do not know where μ-AECs (for fixed μ) stand in this hierarchy:


  Is every accessible category with μ-directed colimits and all morphisms monomorphisms equivalent to a μ-AEC?




§ MORE ON SHELAH'S PRESENTATION THEOREM


Shelah's presentation theorem <cit.> says that any AEC is the reduct of a class of models of an _ω, ω theory omitting a set of types. Moreover the reduct map is functorial. The proof generalizes to μ-AECs <cit.>. In <cit.>, the following category-theoretic analog was proven (for μ = ℵ_0, but the proof generalizes).


  A functor is called essentially surjective if every object of its codomain is isomorphic to an object in its range.



  Let  be an accessible category with μ-directed colimits and all morphisms monomorphisms. Then there is a μ-accessible category  whose morphisms are monomorphisms and an essentially surjective faithful functor F: → preserving μ-directed colimits.


Fact <ref> says that accessible categories with μ-directed colimits and all morphisms mono are, while not necessarily μ-accessible, functorial images of μ-accessible categories. This cannot be obtained directly from Shelah's presentation theorem, since we do not know whether accessible categories with μ-directed colimits are μ-AECs (the problem is that we are fixing μ, see Question <ref>). 

In this section, we combine Fact <ref> with the proof of Shelah's presentation theorem <cit.> to obtain the following common generalization:


  Let  be an accessible category with μ-directed colimits whose morphisms are monomorphisms. Then there is a universal μ-AEC  and an essentially surjective faithful functor F: → preserving μ-directed colimits.


Note that Theorem <ref> is indeed a generalization of Fact <ref>, since universal μ-AECs are μ-accessible (Lemma <ref>). Moreover, Theorem <ref> is a generalization of Shelah's presentation theorem: by Tarski's presentation theorem (Fact <ref>) every universal μ-AEC is a class of models omitting a set of quantifier-free _∞, μ-types. Theorem <ref> also generalizes Boney's presentation theorem for metric AECs <cit.>.

In Shelah's presentation theorem the functor F from Theorem <ref> is the reduct map, as we now establish by imitating Shelah's proof:


  Let  be a μ-AEC which does not contain the empty structure. There exists an expansion τ' of τ := τ () and a universal μ-AEC ' in the vocabulary τ' such that the reduct map ' → is a faithful functor preserving μ-directed colimits which is surjective on objects. Moreover, |τ'| = |τ| +  ().


  Let τ' := τ∪{f_i^α : i <  (), α < μ}, where each f_i^α is a new α-ary function symbol. Let:

  
    ' := {M' ∈ (τ') | M' τ∈∀ A ⊆ U M' . ^M' (A) τ M' τ}


  Here, (τ') is the class of τ'-structure and ^M' (A) denotes the closure of A under the functions of M'. It is easy to check that ' is a μ-universal class and that the reduct map is a faithful functor from ' to  preserving μ-directed colimits. We show that it is onto: let M ∈, and pick a μ-directed system {M_s : s ∈ [M]^<μ} (where [M]^<μ denotes the set of subsets of U M of cardinality strictly less than μ) such that |U M_s| ≤ (), s ⊆ U M_s, and s ⊆ t implies that M_s  M_t. For each s ∈ [M]^<μ, let {c_i^s : i <  ()} be an enumeration (possibly with repetitions) of U M_s. Finally, for ∈αM, α < μ, and i <  (), define (f_i^α)^M' () := c_i^ (). This works: check that for any A ⊆ U M', ^M' (A) = ⋃_s ∈ [^M' (A)]^<μ M_s and use the chain axioms of μ-AECs.



  By Fact <ref>, there is a μ-accessible category _0 (whose morphisms are monomorphisms) and an essentially surjective faithful functor F_0 : _0 → preserving μ-directed colimits. By Fact <ref>, _0 is equivalent via a functor G to a μ-AEC _0 (G may not be surjective but it will be essentially surjective) and without loss of generality (see Remark <ref>) _0 does not contain the empty structure. By Lemma <ref>, there is a universal μ-AEC  such that the reduct functor F_1 : →_0 is a faithful functor preserving μ-directed colimits. Let F := F_1 G F_0.



If we ask for the functor F from Theorem <ref> to be full, then it will be an equivalence of categories, so  will be equivalent to a μ-universal class. On the other hand, the reduct functor F from Lemma <ref> is always surjective on morphisms (that is, if f: A → B, then there exists f̅: A' → B' such that F (f̅) = f). Consider now the following intermediate weakening of fullness:


  A functor F: → is pullback-full if for any sequence f̅_i: B_i → C | i ∈ I of morphisms in  and any sequence g_i : A → F B_i | i ∈ I of morphisms in , if (F f̅_i) g_i =  (F f̅_j) g_j for all i, j ∈ I, then there exists an object A' in  and morphisms g̅_i: A' → B_i | i ∈ I such that F g̅_i = g_i for all i ∈ I.


When is the functor F from Theorem <ref> pullback-full? The answer yields yet another characterization of μ-AECs admitting intersections:


  Let  be a μ-AEC. The following are equivalent:

  
  
  *   admits intersections.
  
  *  There is a universal μ-AEC  and an essentially surjective pullback-full and faithful functor F: → preserving μ-directed colimits.
  
  *  There is a μ-AEC admitting intersections  and an essentially surjective pullback-full and faithful functor F: → preserving μ-directed colimits.
  

   
  
  * (<ref>) implies (<ref>): Trivial.
  
  * (<ref>) implies (<ref>):
    By Fact <ref>, it suffices to check that  has wide pullbacks. Observe that the definition of pullback-fullness (taken with I a singleton set and f̅_i = 𝕀_C) implies that whenever g : A → F C, there exists g̅ : A' → C such that F g̅ = g. The proof is now routine using the fact that  has wide pullbacks, together with the pullback-fullness and faithfulness of F.
  
  * (<ref>) implies (<ref>):
    In the proof of Lemma <ref>, let ” be the class of members M' of ' such that ^M' (M_0) = M_0 for all M_0  M' τ. The reduct map from ” to  is a faithful functor from ” to  preserving μ-directed colimits. As in the proof of <cit.>, this functor is onto, and we show that it is also pullback-full.

    Let A, C, B_i, f̅_i, g_i | i ∈ I be as in the definition of being pullback-full. For i ∈ I, let h_i := (F f̅_i) g_i. By hypothesis, h_i = h_j for all i, j ∈ I, so let h := h_i. First observe that h [U A] induces a substructure C_0 of C, because h[A]  C τ = F C and so by definition of ”, ^C (h [U A]) = h[U A]. We can find a τ'-expansion A' of A such that h induces a τ'-isomorphism from A' onto C_0. Thus h will induce a ”-embedding h̅ from A' into C.

    We now claim that for all i ∈ I, g_i induces a ”-embedding g̅_i from A' into B_i. This is enough to prove what we want. To prove the claim, it is enough to see that for any α-ary τ'-function symbol ρ and any ∈αA', g_i (ρ^A' ()) = ρ^B_i (g_i ()). Now by the previous paragraph h (ρ^A' ()) = ρ^C (h ()). Since C_0 = h[U A] = h[U A'], ρ^C (h ()) = ρ^C' (h ()) = ρ^f̅_i[B_i] (h ()). By definition of h, the latter is equal to ρ^f̅_i[B_i] (f̅_i g_i ()) = f̅_i (ρ^B_i (g_i ()). Putting these calculations together, we have obtained the equality h (ρ^A' ()) = f̅_i (ρ^B_i (g_i ())). Since (as a concrete function) h = f̅_i g_i and f̅_i is a monomorphism, we conclude that g_i (ρ^A' ()) = ρ^B_i (g_i ()), as desired.
  


Note that (<ref>) implies (<ref>) holds more generally when we start with an accessible category with μ-directed colimits. We do not know whether (<ref>) implies (<ref>) also holds at that level of generality.

amsalpha


