Re: partial categories

[Claudio Hermida <claudio.hermida@gmail.com>]

>
> On Wed, Sep 28, 2011 at 4:34 PM, Emily Riehl <eriehl@math.harvard.edu>wrote:
>
>> A colleague of mine is wondering if anyone has studied "partial
>> categories," by which she means directed graphs with identities but with
>> only some compositions (including all identity compositions) defined.
>>
>> A partial category can be thought of as a category enriched in pointed
>> sets (with smash product as tensor and S^0 as unit). The slogan is that
>> the basepoint in each hom-set stands in for "does not exist". But enriched
>> functors don't give the right notion of maps; these should preserve
>> identities and all specified compositions. Enriched functors behave
>> appropriately with regards to the identites but may "forget" extant
>> arrows and in particular need not preserve composites. So perhaps this
>> perspective is not useful.
>>
>> I'll happily pass along any suggestions.
>>
>> Thanks,
>> Emily Riehl
>>
>>
>>

> Dear Emily Riehl,
>
> The notion you seem to refer to is that which has appeared in the
> literature as 'precategory' as used in
>
> - Universal Aspects of Probabilistic Automata
>
      L. Schröder and P. Mateus
      Mathematical Structures in Computer Science, Volume 12 Issue 4, August
2002

    - Precategories for Combining Probabilistic Automata
      P. Mateus, A. Sernadas, C. Sernadas
     *Electronic Notes in Theoretical Computer Science*,
1999, Pages 169-186
     CTCS '99, Conference on Category Theory and Computer Science

Enriching over pointed sets you will end up with functors which must
preserve the undefined composites, something a little awkward to require.
The above treatment does not do that, but the concepts are developed ad hoc
from scratch.

A more sophisticated notion of 'partial category' is that of *paracategory*,
introduced by P. Freyd. Here, the partial composites must satisfy a certain
'saturation' condition. The general context for such a theory is that
of *partial
algebras*, which admit an abstract notion of *saturation*. In this context,
saturation is equivalent to a representation result which embeds any partial
algebra in a total one (using the notion of Kleene morphism, which reflect
definedness of composites, rather than preserving them) . This theory is
given in
*
- *Paracategories I: Internal Paracategories and Saturated Partial Algebras
  C. Hermida, P. Mateus
*Theoretical Computer
Science*<http://www.sciencedirect.com/science/journal/03043975>
Volume 309, Issues
1-3, 2 December 2003, Pages 125-156

Such a general theory can then be instantiated in various contexts:
categories, multicategories and indexed categories are treated in

- Paracategories II: adjunctions, fibrations and examples from probabilistic
automata theory
   C. Hermida, P. Mateus
   *Theoretical Computer
Science*<http://www.sciencedirect.com/science/journal/03043975>
Volume 311, Issues
1-3, 23 January 2004, Pages 71-103

which develops the basic 2-category theory of paracategories, inlcuding
adjunctions, limits, etc. The most relevant example (for which
paracategories were introduced) is that of bivariant functors and dinatural
transformations, which constitute a cartesian closed paracategory.

Finally, I'd like to mention that paracategories have been used to study
certain models of quatum compuation in the thesis of O. Malherbe:

Categorical models of computation: Partially traced categories and presheaf
models of quantum computation   by *Malherbe, Octavio, * Ph.D., *UNIVERSITY
OF OTTAWA , 2010, 215 pages; NR73903 *   Sincerely,

Claudio Hermida


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]