Wanted: Theorem about Cocomplete Categories

I’m pretty sure that a certain theorem about cocomplete categories must be true, and I’m even pretty sure that I know how to write down a proof. (Famous last words, I know.) But I have the feeling that the result is already known, and I just haven’t seen it. I thought I would state the result here (in somewhat vague terms), and hopefully someone can point me to the result, if it already exists.

Every cocomplete category that is co-well-powered and has a set of generators can be constructed explicitly as follows. Each object X can be represented as:

  1. A family of sets, X_i. This family is always a set. Each set represents a different sort, in the sense of multisorted algebras.
  2. A family of relations, R_j defined on the X_i. The relations can be of arbitrary arity and signature (so you can have relations on X_1 x X_2, etc.) Infinite arities are allowed. The number of relations of a fixed arity and signature is a set, but the family of all relations can be a proper class.
  3. A family of partially-defined operations. Each operation has as its domain all tuples that satisfy a certain relation.
  4. The relations are required to satisfy a collection of specified Horn clauses. The left-hand side of the Horn clauses can contain infinite conjunctions.

The arrows of this category are all families of functions X_i -> X’_i that preserve the R_j and the partial operations.

An easy example of this is the category of small categories. Here X_1 is the set of objects, X_2 is the set of arrows. It has four operations: the id operation that sends an object to its identity element, the dom operation that sends an arrow to its domain, the cod operation that sends an arrow to its codomain, and the partial operation of composition, which is defined for all f and g such that cod f = dom g. The Horn clause it satisfies is the requirement that the identity arrow is an identity under composition. (This example is unusual in that the relation is an equality between two operations; the relations can be arbitrary in general.)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>