Can we recognize when a category is equivalent to the category of models of a first order theory?

Question

Many of the most canonical early examples of categories arise as the collection of models of a fixed first order theory, with the related model-theoretic concept of homomorphism. For example, the category of Groups, the category of Rings and the category Set, with their usual morphisms, each arise this way. More generally, for any first order theory T in a first order language L, the collection Mod(T) of all models of T is a central focus of model theory, known as an elementary class, and it is naturally a category with the model-theoretic concept of L-homomorphism. A closely related category, which is very natural in many model-theoretic uses, has the same objects, but requires morphisms to be elementary embeddings.

My question is:

• Can we tell by looking at a category (viewing it only as dots-and-arrows), whether it is equivalent as a category to Mod(T) for some first order theory T? In other words, is being Mod(T) a category-theoretic concept?

Please note that Mod(T) is not the same concept as concrete category, although every Mod(T) is of course concrete.

The question invites a natural restriction to countable languages. In this case, there are some easy necessary conditions on the category. The Lowenheim Skolem theorem shows that if a theory in a countable language has an infinite model, then it has models of every cardinality. Thus, if Mod(T) is uncountable, it must be proper class. So if your category is uncountable, but not a proper class, it cannot be Mod(T) for any countable T. A similar observation applies for any cardinal κ bound on the language, showing that if there are at least κ⁺ many objects in Mod(T), then there must be a proper class of objects in Mod(T).

Another restriction arises from the elementary chain concept, which tells us that the category must admit certain limits, if it wants to be Mod(T).

The ideal answer would be a fully category-theoretic necessary and sufficient criterion.

Finally, a toy version of the question asks only about finite categories. Which finite categories are equivalent to Mod(T) for some first order theory T?

Answer 1

The categories of models with elementary embeddings are accessible categories. (The cardinal κ is related to the size of the language via Löwenheim-Skolem; the κ-presentable, aka κ-compact, objects are models of size less than κ.) Michael Makkai and Bob Paré originally describe this idea in Accessible categories: the foundations of categorial model theory (Contemporary Mathematics 104, AMS, 1989). However, still more can be found in later works such as Adámek and Rosický, Locally presentable and accessible categories (LMS Lecture Notes 189, CUP, 1994).

More generally, abstract elementary classes can also be viewed as accessible categories. Thus accessible categories include categories of models of infinitary theories, theories with generalized quantifiers, etc. In fact, accessible categories can always be attached to such structures, but I don't know the exact characterization of the categories that arise from models of theories of first-order logic. The Yoneda embedding can sometimes be used to attach first-order models to accessible categories, such as when the accessible category is strongly categorical (Rosický, Accessible categories, saturation and categoricity, JSL 62, 1997). On the other hand, you can reformulate a lot of model theoretic concepts in general accessible categories. There are more than a few kinks along the way and not all of it has been done, but the more I learn the more I find that this is actually a very interesting and powerful way to approach model theory.

---

Let me try to explain the situation in greater detail. I guess the correspondences are better explained in terms of sketches. (This nLab page needs expansion; Adámek and Rosický give a nice account of sketches; another account can be found in Barr and Wells.) A sketch asserts the existence of certain limits and colimits, or just limits in the case of a limit sketch, taken together these assertions can be formulated as a sentence in L_∞,∞ (sketchy details below). Like such sentences, every sketch S has a category Mod(S) of models. Sketches and accessible categories go hand in hand.

• If S is a sketch, then Mod(S) is an accessible category, and every accessible category is equivalent to the category of models of a sketch.

• If S is a limit sketch, then Mod(S) is a locally presentable category, and very locally presentable category is equivalent to the category of models of a limit sketch.

When translated into L_∞,∞, a limit sketch becomes a theory with axioms of the form

$\forall\bar{x}(\phi(\bar{x})\to\exists!\bar{y}\psi(\bar{x},\bar{y})),$

where $\phi$ and $\psi$ are conjunction of atomic formulas (and the variable lists $\bar{x}$ and $\bar{y}$ can be infinite). When the category is locally finitely presentable, then these axioms can be stated in L_ω,ω. Theories with axioms of this type are essentially characterized by the fact that Mod(T) has finite limits.

• If T is a theory in L_ω,ω and Mod(T) which is closed under finite limits (computed in Mod(∅)), then Mod(T) is locally finitely presentable category (and hence finitely admissible).

• Every locally finitely presentable category is equivalent to a category Mod(T) where T is a limit theory in L_ω,ω (i.e. with axioms as described above).

It is natural to conjecture that this equivalence continues when ω is replaced by ∞. Adámek and Rosický have shown in A remark on accessible and axiomatizable theories (Comment. Math. Univ. Carolin. 37, 1996) is that for a complete category being equivalent equivalent to a (complete) category of models of a sentence in L_∞,∞ and being accessible are equivalent provided that Vopenka's Principle holds. In fact, this equivalence is itself equivalent to Vopenka's Principle. (It is apparently unknown whether accessible can be strengthened to locally presentable.)

Now, if T is a sentence in L_∞,∞, then the category Elem(T) (models of T under elementary embeddings) is always an accessible category. The category Mod(T) is unfortunately not necessarily accessible. When translated into L_∞,∞ sketches become sentences of a special form. A formula in L_∞,∞ is positive existential if it has the form

$\bigvee_{i \in I} \exists\bar{y}_i \phi_i(\bar{x},\bar{y}_i)$

where each $\phi_i$ is a conjunction of atomic formulas. A basic sentence in L_∞,∞ is conjunction of sentences of the form

$\forall\bar{x}(\phi(\bar{x})\to\psi(\bar{x}))$

where $\phi$ and $\psi$ are positive existential formulas.

• A category is accessible if and only if it is equivalent to a category Mod(T) where T is a basic sentence in L_∞,∞.

It would be great if one could simply replace accessible by finitely accessible and sentence in L_∞,∞ by theory in L_ω,ω, as in the locally presentable case above. Unfortunately, this is simply not true. The category of models of the basic sentence $\forall x\exists y(x \mathrel{E} y)$ in the language of graphs is accessible but not finitely accessible. A counterexample in the other direction is the category of models of $\bigvee_{n<\omega} f^{n+1}(a) = f^n(a)$, which is finitely accessible but not axiomatizable in L_ω,ω.

Answer 2

For a long time, I've been thinking about this question for the category Mod*(T) of all models of T with elementary maps as morphisms (I'm putting an asterisk to distinguish it from Mod(T) in the original question). I still have more conjectures than answers about these categories, but I can say a few things about them. For example:

Proposition: If Mod*(T) is "linearly ordered" -- i.e. for any two M, N in Mod*(T), either M is embeddable into N, or vice-versa -- then Mod*(T) must have the Schroeder-Bernstein property (any two bi-embeddable models are isomorphic).

[Sketch of proof: First, note T must be complete. By a result of Shelah, T must be superstable -- otherwise, one of his constructions gives that there are many pairs of "incomparable" models neither of which can be embedded into the other. By some other results of Shelah from Classification Theory, we can deduce that T must be unidimensional (it cannot have a pair of orthogonal regular types) and omega-stable. But any omega-stable, unidimensional theory is categorical in aleph_1, and hence categorical in any uncountable cardinal by Morley's Theorem. By the Baldwin-Lachlan analysis of such theories, any model of T is determined up to isomorphism by a single cardinal-valued "dimension," and bi-embeddable models must have the same dimension, QED.]

I strongly suspect that there is some dichotomy result for Mod*(T) (and probably also for Mod(T)) saying that either it is extremely wild (e.g. as when T is unstable) or relatively "tame" (such as when T is uncountably categorical, and Mod*(T) is just a big tower, modulo isomorphisms). But I'm not sure what's the best way to make this precise.

As an example of the kind of dichotomy that may be true: I conjecture that if Mod*(T) does not have the Schroeder-Bernstein property, then in fact Mod*(T) contains an infinite collection of models which are pairwise bi-embeddable but pairwise nonisomorphic. I can prove this in some special cases (e.g. when T is weakly minimal) but not in general.

Answer 3

I'm not sure if this is exactly the sort of thing you are looking for, but call a category a "Boolean logos" just in case it has finite limits, the subobjects of any object form a Boolean algebra under inclusion, and pullback along any morphism induces a homomorphism of such Boolean algebras with left and right adjoints. [Much of this definition is redundant, but no matter]. Boolean logoses, functors between them which preserve all the defining structure, and arbitrary natural transformations between those comprise a two-category, which I'll call BoolLog.

Up to equivalence, the categories of all models of some theory in multi-sorted classical first-order logic with equality and the elementary embeddings between them are precisely those of the form BoolLog[B, Set]. That is, a category C is equivalent to one of the form Mod*(T) just in case there is some Boolean logos B such that C is equivalent to the full subcategory of Set^B consisting of those functors which preserve Boolean logos structure.

This isn't really saying much (the definition of a Boolean logos is a very straightforward categorical rendering of the definition of multi-sorted classical first-order logic with equality [although, like I said, it could be pared down a bit. And, of course, we can easily tweak the former definition around a little to correspond to variants on the latter (e.g., the single-sorted case, the intuitionistic case, etc.)]), but, perhaps such categorical rendering is all you were looking for (although, re-reading the reply you gave to my comment above, I suspect you were after a different sort of answer. Oh well.)

EDIT: I may as well add a paring down of the definition now. Another (equivalent) way to define a Boolean logos is as a category with finite limits, a right adjoint to pullback of subobjects along any morphism, and an initial object, such that certain maps constructed out of this structure have inverses (explained below). The category BoolLog has these as 0-cells, functors preserving finite limits, initial objects, and right adjoints to subobject-pullback as 1-cells, and arbitrary natural transformations as 2-cells; as before, the Hom-categories BoolLog[B, Set] are the categories of models of B and elementary embeddings between them. The requirement for preservation of initial objects destroys many of the completeness/cocompleteness properties for models which we might otherwise have expected from universal algebra; e.g., there won't necessarily be finite limits of models or "free" (i.e., initial) models.

There are two isomorphism conditions to complete this definition of a Boolean logos: 1) the unique maps from an initial object to its product with any other object should be isomorphisms [i.e., products distribute over 0-ary coproducts], and 2) from the previous structure, it follows that the subobjects of any object form a cartesian closed preorder with an initial object. In these preorders, the initial objects should be dualizing [which suffices to make these Boolean algebras].

I didn't add conditions to force Boolean logoses to represent complete theories, but that's easy enough: this happens just in case the only subobjects of the terminal object are the unique maps into it from itself and the initial object. And, of course, consistency amounts to asking for these two maps to be distinct; equivalently, the terminal category is the unique Boolean logos representing an inconsistent theory.

EDIT2: Whoops, also, in both definitions, I forgot to add the Beck-Chevalley condition: for every object A, the right adjoint to subobject pullback along the projection A x - $\rightarrow$ - should be a natural transformation (from Sub(A x -) to Sub(-)).

Answer 4

It seems that such category is equivalent to an accessible one. See http://archive.numdam.org/article/DIA_1981__6__A5_0.pdf and also http://www.numdam.org/article/DIA_1982__7__A4_0.pdf