# Expressive power of first-order category theory

Given the signature $\lbrace \mathsf{dom}, \mathsf{cod}, \mathsf{id},\circ \rbrace$ and the axioms of category theory – which are expressible in the signature's first-order (FO) language – I wonder

• which (relevant) properties of categories as a whole
• which properties of and relations between individuals (= objects and morphisms) inside a category
• which other concepts and constructions

are expressible in category theory's first-order language – and which are genuinely not.1

(For graph theory there is a highly elaborate investigation of expressibility of properties in different languages - FO, SO, MSO - basically driven by Bruno Courcelle.)

The following properties are easily seen to be FO-expressible:

• being a initial/terminal object

• being a product/coproduct

• being a monic/epic (morphism)

• being a groupoid (category)

What - among other things - is not clear to me is how being a subobject of $A$ might be FO-expressible? Officially a subobject of a given object $A$ is a specific equivalence class of morphisms with codomain $A$ (as a subclass of individuals this is not an FO-definable individual) which corresponds naturally to an isomorphism class of objects (ditto). But maybe being an element of this isomorphism class is FO-expressible, eventually?

This becomes interesting when we ask if being connected is a FO-expressible property of objects (= graphs) in the category of finite graphs:

Connected graphs are the noninitial objects in the category of finite graphs that can not be expressed as a coproduct of two nonempty subobjects.

(Note: As a property of graphs as a whole connectedness is provably not expressible by a closed formula in the FO-language of graphs with signature $\lbrace R\ \rbrace$)

On the other hand:

Is the property of being a category of finite graphs expressible by a closed formula in the FO-language of categories?

1 Properties of categories "as a whole" are expressed by closed formulas. $n$-ary relations between individuals are expressed by formulas with $n$ free individual variables.

• On the last question: the category of finite graphs has a small infinite skeleton, so we may take ultrapowers of it to get categories that are elementarily equivalent but not equivalent. (The ultrapower will contain non-standard objects.) – Zhen Lin Feb 27 '14 at 10:55
• Does "C is a category of finite graphs" mean "the objects of C may be identified with a set of finite graphs, and the morphisms of C may be identified with graph morphisms, in a way such that the standard relations apply"? And are you allowing graphs with loops or not? Or do you mean "the category of finite graphs", as in the comment? – Matt F. Feb 27 '14 at 22:30
• I mean the category of graphs, for which the quoted characterization of connected graphs is true. (To be honest, I am not sure if this is the category with or without loops.) – Hans-Peter Stricker Feb 28 '14 at 7:33

• @Neil Strickland: That is an interesting question, but I think the answer is still no. Here is a sketch: Let C be the category of finite graphs. Suppose phi is a formula where M satisfies phi iff M is equivalent to C. Then psi holds in C iff phi implies psi. So the formulas valid in C are recursively enumerable. But for any polynomial $p(x,y...)$, we can code the sentence $\forall x,y...\in N, p(x,y...)\neq0$ as a statement in this language. And a recursive enumeration of the true sentences of that form would solve Hilbert's tenth problem recursively, which is impossible. – Matt F. Mar 1 '14 at 19:52