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?
Best Answer
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.
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ω,ω.