nLab
paracategory

Idea

A paracategory is a category where composition is only partially defined.

The definition is “unbiased” in that it comes with basic (partial) nn-ary composition operations for all nn, and unlike in the total case these cannot always be reduced to binary and nullary operations. A paracategory in which all the composites are generated from binary and nullary ones is sometimes called a precategory.

Definition

A paracategory is a quiver C 1C 0C_1 \rightrightarrows C_0 together with the following structure. We write C nC_n for the iterated pullback C 1× C 0× C 0C 1C_1 \times_{C_0} \dots\times_{C_0} C_1, the set of length-nn strings of composable arrows.

  • Partial functions n:C nC 1\circ_n \colon C_n ⇀ C_1, over C 0×C 0C_0\times C_0

  • 0:C 0C 1\circ_0 \colon C_0 \to C_1 is total, so all identity arrows exist.

  • 1:C 1C 1\circ_1\colon C_1 \to C_1 is the identity.

  • If ny\circ_n \vec{y} is defined, then m+1+k(x, ny,z)= m+n+k(x,y,z)\circ_{m+1+k}(\vec{x},\circ_n \vec{y},\vec{z}) = \circ_{m+n+k}(\vec{x},\vec{y},\vec{z}) (the equality being Kleene equality).

A functor between paracategories is a quiver morphism f:CDf\colon C\to D such that if nx\circ_n \vec{x} is defined, then so is nf(x)\circ_n \vec{f(x)} and it equals f( nx)f(\circ_n \vec{x}). A Kleene functor is a functor such that if nf(x)\circ_n \vec{f(x)} is defined, then so is nx\circ_n \vec{x}; this is equivalently a quiver morphism such that nf(x)=f( nx)\circ_n \vec{f(x)}=f(\circ_n \vec{x}) is a Kleene equality.

Examples

  • If DD is any category and CC is a subclass of arrows in DD containing all the identities, then CC becomes a paracategory whose objects are the objects of DD, whose arrows are the arrows in CC, and where the composite of a string of arrows is defined iff the composite of that string in DD happens to lie in CC.

  • extranatural transformations and dinatural transformations form paracategories, since they are not always composable. This is exploited in the definition of extraordinary 2-multicategory?. This example can also be regarded as a case of the previous example, where the ambient category DD consists of “unnatural transformations.”

  • In fact, if Cat PCat_P denotes the category of categories equipped with a subclass of arrows containing the identities, then the functor Cat PParCatCat_P \to ParCat defined above is actually a coreflection, i.e. it has a fully faithful left adjoint. In particular, any paracategory is isomorphic to one obtained from a class of arrows in some category, and moreover in a universal way.

Paracategories as generalized multicategories

Paracategories, and more general “partial algebras,” can be considered as a special case of generalized multicategories; see the papers of Hermida.

References

The definition is due to Peter Freyd in apparently unpublished work. It has been studied further in the papers:

  • Hermida and Mateus, “Paracategories I: Internal Paracategories and Saturated Partial Algebras”

  • Hermida and Mateus, “Paracategories II: Adjunctions, fibrations and examples from probabilistic automata theory”

Revised on July 5, 2010 16:01:54 by Mike Shulman (67.52.155.121)