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.

  • 1
    $\begingroup$ 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.) $\endgroup$ – Zhen Lin Feb 27 '14 at 10:55
  • $\begingroup$ 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? $\endgroup$ – Matt F. Feb 27 '14 at 22:30
  • $\begingroup$ 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.) $\endgroup$ – Hans-Peter Stricker Feb 28 '14 at 7:33

No, being the category of finite graphs can not be expressed by a formula, or even a set of formulas, in the FO language of category theory. Any set of formulas satisfied by that category also has models of other cardinalities, by the Lowenheim-Skolem theorem.

  • 3
    $\begingroup$ This argument seems to show that "being isomorphic to the category of finite graphs" is inexpressible, but "being equivalent to the category of finite graphs" is more interesting, and equivalent categories can have different cardinalities. $\endgroup$ – Neil Strickland Mar 1 '14 at 11:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Matt F. Mar 1 '14 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.