Elementary toposes and abelian categories as first-order structures, 1:
I was thinking about definable sets in groupoids earlier today, and ended up considering categories in general. (And then things got out of hand, and I ended up writing this.) In what follows, I define categories as first-order structures and analyze what sorts of category-theoretic notions are captured by their first-order theory. Surprisingly (because you can ignore the product-exponential adjunction and consider power objects instead), toposes are first-order definable, and since the \(\mathbf{Ab}\)-enriched structure on an abelian category follows from much more elementary properties, abelian categories are too.
As Hrushovski pointed out, categories can naturally be interpreted as two-sorted first-order structures.
Definition 1. We work in the two-sorted language \(\mathcal{L}\) with sorts \(\operatorname{Ob}\) and \(\operatorname{Mor}\). We have functions \(\operatorname{dom}\) and \(\operatorname{cod}\) going \(\operatorname{Mor} \to \operatorname{Ob}\). There is a partial binary composition function, whose graph relation we add to the language \(\circ(-,-,-) \subseteq \operatorname{Mor} \times \operatorname{Mor} \times \operatorname{Mor}\). A category is an \(\mathcal{L}\)-structure satisfying the following axioms, which state that composition is only defined on arrows with compatible domains and codomains, that composition is associative, and that there are left- and right-identities for composition:
\(\forall f \forall g, [\operatorname{cod}(f) \neq \operatorname{dom}(f) \rightarrow \forall h \left(\neg \circ(f,g,h)\right)].\)
\(\forall f \forall g \forall h, [\circ(f,g,h) \longleftrightarrow\) \([\forall h’ \left( \circ(f,g,h’) \rightarrow h = h’ \right) \land \operatorname{dom}(h) = \operatorname{dom}(g) \land \operatorname{cod}(h) = \operatorname{cod}(f)]].\)
\(\forall f \forall g \forall h, \circ(f, \circ(g,h)) = \circ(\circ(f,g), h).\)
\(\forall a \in \operatorname{Ob} \exists e_a \in \operatorname{Mor},\)\( (\operatorname{cod}(e_a) = \operatorname{dom}(e_a) = a \land\)\(\forall f \left(\operatorname{dom}(f) = a \rightarrow \circ (f,e_a,f) \land \operatorname{cod}(f) = a \rightarrow \circ(e_a,f,f) \right)).\)
As usual, we write \(\circ\) infix whenever it is defined as a function, and write \(f : X \to Y\) to denote that \(f\) has domain \(X\) and codomain \(Y\). Identity maps are necessarily unique, so the function \(\operatorname{id} : \operatorname{Ob} \to \operatorname{Mor}\) taking objects to their identity maps is zero-definable (so we may as well treat it as part of our language).
So we have these structures. What are their first-order definable (maybe with parameters) sets?
Example 1. Initial and terminal objects: consider \(\mathsf{isInitial}(x) \overset{\operatorname{df}}{\equiv} \forall y \in \operatorname{Ob}, \exists! f : x \to y\); dually for final.
Example 2. Slice and co-slice categories: fix a base \(b \in \operatorname{Ob}\). For the objects of the slice category, take \(\operatorname{Ob}(\mathbf{C}/b) \overset{\operatorname{df}}{=} \{f \in \operatorname{Mor} \operatorname{ | } \operatorname{cod}(f) = b\}\). For morphisms, take \(\operatorname{Mor}(\mathbf{C}/b) \overset{\operatorname{df}}{=} \{f \in \operatorname{Mor} \operatorname{ | } f : \operatorname{dom}(g) \to \operatorname{dom}(h) \text{ for } g,h \in \operatorname{Ob}(\mathbf{C}/b)), h \circ f = g\}\). Composition is just induced by restriction of composition in \(\mathbf{C}\). Dually for co-slices.
(Note that, in the same way algebraic groups are group objects in the category of algebraic varieties, this defines a category object, i.e. an internal category in the category of definable sets (i.e. the syntactic category) of the first-order theory of \(\mathbf{C}\)).
Example 3. Limits and colimits of arbitrary finite diagrams: if \(\mathbf{D}\) is a diagram with finitely many objects \(d_1, \dots, d_n\) with finitely many morphisms between them, a limit to \(\mathbf{D}\) is just a tuple \((x, \pi_1, \dots, \pi_n)\), where \(x\) is an object and the \(\pi_i\) are morphisms \(x \to d_i\), such that:
whenever \(f : d_i \to d_j \in \mathbf{D}, f \circ \pi_i = \pi_j\), and
for any other tuple \((y, \pi_1′, \dots, \pi_n’)\) satisfying the above conditions, there exists a unique map \(y \overset{u}{\to} x\) such that \(\pi_i’ = \pi_i \circ u\) for all \(i\).
(Alternately, we can just modify our realization of slice and co-slice categories as definable categories in \(\mathbf{C}\) to realize cone and co-cone categories as definable categories in \(\mathbf{C}\). Then limits and colimits are just terminal and initial objects in those definable categories, thus definable.)
Example 4. Limits and colimits of arbitrary definable diagrams construed as definable subcategories: (Instead of capturing the entire diagram in a sentence, as is possible when \(\mathbf{D}\) is finite, we only need to check that certain subtriangles of our diagram commute, as long as the legs of the triangle belong to something we can safely quantify over, it doesn’t matter if there are infinitely many things to check.)
Definition 2. If \((O_1, M_1)\) and \((O_2, M_2)\) are internal categories in \(\mathbf{C}\), an internal functor between them is just a pair of definable maps \(O_1 \to O_2\), \(M_1 \to M_2\) which behaves like a functor with respect to the internal composition, domain, and codomain maps of either internal category. If \(F_1, F_2\) are two internal functors between two internal categories, an internal natural transformation \(F_1 \overset{\eta}{\to} F_2\) is a definable function \(O_1 \overset{\eta}{\to} M_2\), such that \(\operatorname{dom}(\eta(x)) = F_1(x)\) and \(\operatorname{cod}(\eta(x)) = F_2(x)\), such that all naturality squares commute.
Example 5. Change-of-base functors between slice categories: a morphism between category objects in a category is just a morphism in the ambient category that makes all the right diagrams (expressing associativity, etc) commute. Here this means: a definable function from objects to objects and morphisms and morphisms, which is functorial with respect to either internal category’s domain, codomain, and composition operation. Since pullbacks don’t exist in general, the best we can do is to define this partially in the way we defined our composition operation: whenever applicable, functoriality holds.
Example 6. Epimorphisms, monomorphisms, and subobject classifiers: to be a monomorphism \(f : X \to Y\) means that the definable map \(f \circ - : \operatorname{Hom}(-, X) \to \operatorname{Hom}(-,Y) = f \circ - : \operatorname{cod}^{-1}(X) \to \operatorname{cod}^{-1}(Y)\) is injective. To be a monomorphism \(f : X \to Y\) means that the definable map \(- \circ f : \operatorname{Hom}(-, Y) \to \operatorname{Hom}(-, X)\) is injective. To have a subobject classifier is to say, “there exists a terminal object \(\mathbf{1}\) and a monomorphism \(\operatorname{true}: \mathbf{1} \to \Omega\) for some object \(\Omega\) such that for every object \(X\) and every monomorphism \(S \hookrightarrow X\), there exists a unique classifying map \(X \to \Omega\) such that \(S \hookrightarrow X\) is the pullback of \(\operatorname{true}\) along that classifying map \(X \to \Omega\).”
Example 7. Power objects of a fixed object X: “there exists an object \(\Omega^X\) and a monomorphism \(\in_X \hookrightarrow X \times \Omega^X\) such that for any other object \(Y\) and every monomorphism \(S \hookrightarrow X \times Y\), there is a unique classifying map \(X \times Y \to X \times \Omega^C\) such that \(S \hookrightarrow X \times Y\) is the pullback of \(\in_X \hookrightarrow X \times \Omega^X\) along that unique classifying map (and that, of course, the necessary pullbacks and products exist).”
Exercise 1. (For the masochistic.) Write out Examples 4, 5, 6, and 7 explicitly.
Remark 1. I don’t think arbitrary limits and colimits are definable. So, to-do: construct two categories with equivalent first-order theories, but which realize some limit or colimit differently.
Remark 2. Maybe I should’ve read about internal categories in toposes from Johnstone’s text before starting this post.
Remark 3. What about internal adjunctions? Recall that \(F \operatorname{\dashv} G\) if there exists a system of bijections, natural in \(X\) and \(Y\), between the hom-sets \[\operatorname{Hom}_{\operatorname{dom}(F)}(X, RY) \simeq \operatorname{Hom}_{\operatorname{dom}(G)}(LX, Y).\] If \(F\) and \(G\) are between two internal categories \(\mathbf{D}, \mathbf{E}\), the data of that system of natural bijections can be expressed a function \[\operatorname{Ob}(\mathbf{D}) \times \operatorname{Ob}(\mathbf{E}) \to \operatorname{Hom}_{\mathbf{Set}} \left( \bigsqcup_{X \in \mathbf{D}, Y \in \mathbf{E}} \operatorname{Hom}_{\mathbf{D}}(X, RY), \bigsqcup_{X \in \mathbf{D}, Y \in \mathbf{E}} \operatorname{Hom}_{\mathbf{E}}(LX,Y) \right).\] By the product-hom adjunction in \(\mathbf{Set}\), this is the same as a function \[\operatorname{Ob}(\mathbf{D}) \times \operatorname{Ob}(\mathbf{E}) \times \bigsqcup_{X \in \mathbf{D}, Y \ in \mathbf{E}} \operatorname{Hom}_{\mathbf{D}}(X,RY) \to \bigsqcup_{X \in \mathbf{D}, Y \in \mathbf{E}} \operatorname{Hom}_{\mathbf{E}}(LX,Y)\] (satisfying, of course, the necessary properties.)
Exercise 2. Check that \(\bigsqcup_{X \in \mathbf{D}, Y \in \mathbf{E}} \operatorname{Hom}_{\mathbf{D}}(X, RY)\) is definable in the parameters of \(\mathbf{D}, \mathbf{E}\) and \(R\).
Proposition 1. If \(F : \mathbf{D} \to \mathbf{E}\) and \(G : \mathbf{E} \to \mathbf{D}\) are internal functors between two categories internal to \(\mathbf{C}\), and \(\eta\) is a definable function of the above form, then the statement that \(F\) is left-adjoint to \(G\) witnessed by \(\eta\) is first-order expressible in the parameters of \(F\), \(G\) and \(\eta\).
Proof. With everything we have so far, we just need that checking naturality is first-order expressible. We’re essentially checking that we have a natural transformation between hom-functors, whose action on morphisms is induced by composition in \(\mathbf{D}\) and \(\mathbf{E}\), which is definable since \(\mathbf{D}\) and \(\mathbf{E}\) are internal.
Definition 3. An elementary topos is an \(\mathcal{L}\)-structure with all finite limits and power objects (for all objects).
Definition 4. An abelian category is an \(\mathcal{L}\)-structure such that:
There is an object which is both initial and terminal.
It has all products and coproducts.
Every morphism has a kernel and cokernel.
Every monomorphisms (resp. epimorphism) arises as an equalizer (resp. coequalizer.)
Remark 4. I find it interesting that while power objects are first-order expressible, adjunctions appear not to be. Perhaps something special happens when you have all products, so that having an exponential is akin to finding the right adjoint to an internal endofunctor \(X \mapsto X^Y\). Hence,
Question 1. If \(F\) is a functor internal to \(\mathbf{C}\), and \(F\) has an adjoint \(G\), then is \(G\) also internal (up to isomorphism) to \(\mathbf{C}\)?
Question 2. What do monster models of toposes and saturated abelian categories look like?
Question 3. Do sufficiently saturated models of abelian categories contain enough injectives?
In future posts for this series, I’ll try to answer these questions.
