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

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?

-
Thanks for the invitation from over there (mathoverflow.net/questions/12180). – Hans Stricker Jan 28 '10 at 9:58
To clarify one point: "If Mod(T) is uncountable, then it must be a proper class:" to be strictly correct, you should say, "If Mod(T) has uncountably many isomorphism classes, then it contains a proper class of isomorphism classes," unless by Mod(T) you mean the "embeddability skeleton" containing one representative from each isomorphism class. – John Goodrick Jan 28 '10 at 17:55
Also, this is an excellent question, one I've thought a lot about myself (in the case where morphisms are elementary maps, rather than arbitrary L-homomorphisms). I wish I had a snappy answer to it by now, but it seems to be a tricky question! – John Goodrick Jan 28 '10 at 17:57
@John. Yes, I agree that I should mean isomorphism classes in that remark. And I'm interested in both versions of the question, either with homomorphisms or elementary embeddings. The latter is more natural in logic and model theory, but the former includes the most canonical category examples, with groups, rings and sets. – Joel David Hamkins Jan 28 '10 at 18:32
Just for clarification/making the question more concrete, what exactly do you mean by "In other words, is being Mod(T) a category-theoretic concept?". That is, what is it about something like "There exists a first-order theory (equivalently, a Boolean logos) T such that C is equivalent to Mod(T)?" that would make it not immediately a category-theoretic concept? [It is, after all, a property of categories which is preserved by categorical equivalence] – Sridhar Ramesh Feb 10 '10 at 7:05

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ω,ω.

-
Thanks very much for this answer! But am I to understand you correctly that, ultimately, accessibility is neither necessary nor sufficient as a criterion to answer my specific question? After all, if it works for infinitary languages also, then it would seem to admit instances that are not Mod(T) for any first order theory. And your final remark says that Mod(T) is not always accessible? Could you explain your final remark about VP a bit more? If large cardinals come in here, that would be great. – Joel David Hamkins Jan 28 '10 at 13:18
I deleted that confusing short paragraph and, in exchange, I added a considerable amount of details, including the relationship with VP. – François G. Dorais Jan 29 '10 at 3:43
I guess the key about VP is that if k is sufficiently large then k-directed colimits in Mod(T) can be computed in Mod(0). For the reverse direction, it is the graph theoretic interpretation of VP which is key. – François G. Dorais Jan 29 '10 at 15:03

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.

-
John, this looks like a really interesting research direction. I had meant my use of Mod(T) to be somewhat ambiguous between homomorphisms and elementary embeddings, and actually like you I am more interested in the elementary embedding case, but thought that the category theorists would usually care more about homomorphisms, which seem to give category-theoretic concepts greater traction (e.g. products would have more of a chance...). – Joel David Hamkins Jan 28 '10 at 18:40

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(-)).

-
I don't think your equivalence in the second paragraph is correct since the functor category you describe should have finite limits. Maybe you're thinking of the category of Boolean-valued models of the theory T? In any case, how do you construct the classifying Boolean logos of an arbitrary theory T? – François G. Dorais Feb 11 '10 at 13:14
The category I describe won't necessarily have finite limits: for example, consider the four-element Boolean algebra, viewed as a preorder category. This is a Boolean logos, and the functors from it to Set preserving Boolean logos structure are those which send its top element to 1 (by virtue of being a terminal object), its bottom element to 0 (by virtue of its arrow into the top element being the bottom subobject of the top element), one of the middle elements to 1 and the other to 0 (by virtue of their arrows into the top element being complementary subobjects). – Sridhar Ramesh Feb 11 '10 at 18:31
There are precisely two of these, and neither has a natural transformation into the other; thus, the category lacks a terminal object. – Sridhar Ramesh Feb 11 '10 at 18:31
As for how to construct the classifying logos of an arbitrary theory T, take as objects the definable predicates (of any arity) in the theory, with morphisms being definable, provably functional relations on the extensions of those predicates up to provable equivalence. I.e., a morphism from D(X) to R(Y) is a predicate F(X, Y) such that the theory proves "For all X and Y, F(X, Y) implies (D(X) and R(Y)), and for all X such that D(X), there exist unique Y such that F(X, Y).", where X is a tuple of variables of any length and similarly for Y. – Sridhar Ramesh Feb 11 '10 at 18:41
And composition is straightforward: the binary composition of F(X, Y) and G(Y, Z) is the predicate H(X, Z) := There exist Y such that F(X, Y) and G(Y, Z). And the identity morphisms are given by equality predicates [or, technically, given the description as I've stated it so far, the identity morphism on A(X) is the predicate F(X_1, X_2) := A(X_1) & A(X_2) & (X_1 = X_2)]. – Sridhar Ramesh Feb 11 '10 at 18:47