nLab
protocategory

Protocategories

Idea

A protocategory is a way to present a category that makes formal the idea that a single datum (a “protomorphism”) can represent many different morphisms with different sources and targets. For instance, in material set theory, a given set of ordered pairs can represent functions with many different codomains.

As compared to the definition of category with one set of objects and one set of morphisms, a protocategory removes the requirement that each morphism have a unique source and target. As compared to the definition of category with separate hom-sets hom(A,B)\hom(A,B) for each pair of objects, a protocategory requires all these homsets to be (not necessarily disjoint) subsets of one set of all “protomorphisms”.

It is important to recognize, however, that unlike those two definitions of category, a protocategory is not a definition of a category. It retains information about “which morphisms in distinct hom-sets are ‘equal’”, which is not relevant category-theoretic information: in a true category it is never ‘meaningful’ to compare two morphisms for equality unless one already knows for other reasons that their domains and codomains coincide. A protocategory is rather a way of presenting a category, analogous to a group presentation, formalizing the fact that in some cases morphisms in different hom-sets can be “equal” until we “forget about that fact” in a structured way.

Definition

A protocategory consists of:

  • Two collections of objects and protomorphisms
  • A ternary “source-target relation” relating two objects and one protomorphism, written “f:ABf : A\to B” and read as “ff represents a morphism from AA to BB
  • A ternary “composition predicate” relating three protomorphisms, written “h=gfh = g \circ f” and read as “hh is a possible composite of ff and gg”.

satisfying the axioms

  • If f:ABf:A\to B and g:BCg:B\to C, there is exactly one hh satisfying h:ACh:A\to C and h=gfh = g\circ f.
  • If we define the set of morphisms hom(A,B)\hom(A,B) to be the set of protomorphisms ff satisfying f:ABf:A\to B, then the composition operation given by the previous axiom results in a category (i.e. it is associative and has identities).

Examples

  • Let the objects be the sets in material set theory (such as ZFC), and let the protomorphisms be sets ff of ordered pairs such that for any xx there is at most one yy such that (x,y)f(x,y)\in f. The domain of such an ff is the set of all xx such that there is such a yy, and its range is the set of all yy such that there exists an xx with (x,y)f(x,y)\in f. We say f:ABf:A\to B if AA is the domain of ff and BB is a superset of the range of ff. With a suitable definition of composition, this yields a protocategory that generates the category Set.

  • More generally, if we take the protomorphisms to be all sets of ordered pairs, and f:ABf:A\to B to mean that AA is a superset of the domain of ff in addition to BB being a superset of the codomain of ff, then we get a protocategory that generates the category Rel.

  • Let the objects be groups, let the protomorphisms be functions, and say that f:GHf:G\to H when ff is a function between the underlying sets of GG and HH that is a group homomorphism. This protocategory generates the category Grp.

  • Any category can be presented by a protocategory in a trivial way, by taking the protomorphisms to be the disjoint union of all the sets of morphisms (i.e. the set C 1C_1 in the one-set-of-morphisms definition of category), with the source-target relation being simply a function from protomorphisms to pairs of objects.

Remark

It may seem that, at least in a material set theory, we should be able to modify the previous example by taking a non-disjoint union of the sets of morphisms (assuming given a category in the many-sets-of-morphisms definition). However, this is not true, because the composition predicate in a protocategory makes no reference to objects. For example, consider the following category:

  • objects 0,1,2,0,1,20,1,2,0',1',2'
  • hom(0,1)=hom(0,1)={f}\hom(0,1) = \hom(0',1') = \{f\}, hom(1,2)=hom(1,2)={g}\hom(1,2)=\hom(1',2')=\{g\}, hom(0,2)=hom(0,2)={h,h}\hom(0,2)=\hom(0',2')=\{h,h'\}, no other nonidentity morphisms, all identity morphisms distinct
  • g 0,1,2f=hg\circ_{0,1,2} f = h and g 0,1,2f=hg\circ_{0',1',2'} f = h'.

Then if we take unions of homsets we have gf=hg\circ f = h and also gf=hg\circ f = h', but then the protocategory composition axiom fails: we have f:01f:0\to 1 and g:12g:1\to 2, but there does not exist a unique kk such that k:02k:0\to 2 and gf=kg \circ f = k.

References

Last revised on April 16, 2018 at 05:34:17. See the history of this page for a list of all contributions to it.