partial categories

partial categories

[Emily Riehl]

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


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

Re: partial categories

[Claudio Hermida]

>
> 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/ ]

Reference requested

[Peter May]

I have a reference question.  Who first coined the term
``chaotic category'' for a groupoid with a unique morphism
between each pair of object, and in what context?  It is a
ridiculously elementary concept, but one that is extremely
useful in  work on equivariant bundle theory that is needed
for equivariant infinite loop space theory and equivariant
algebraic K-theory.

Peter May






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

Re: Reference requested

[Ronnie Brown]

Why not use the term `indiscrete groupoid' for the functor that gives a
right adjoint to the  functor Ob: Groupoids \to Sets?   The left adjoint
is then of course the `discrete groupoid'.  This agrees with the
terminology for discrete and indiscrete topologies.

I confess to have used different  terminology in various places.

Of course one use of these notions is to show that the functor Ob
preserves limits and colimits, which is  a start on constructing them.

It is not surprising that this concept occurs widely. In groupoids there
is a notion of covering morphism and the universal cover of a group G
is of course an indiscrete groupoid G'; this groupoid is by no means
`trivial' since it comes equipped with a covering morphism  p: G' \to
G.  This approach to covering space theory is given in my book `Topology
and groupoids'.

Ronnie



Ronnie

On 29/09/2011 02:35, Peter May wrote:
> I have a reference question.  Who first coined the term
> ``chaotic category'' for a groupoid with a unique morphism
> between each pair of object, and in what context?  It is a
> ridiculously elementary concept, but one that is extremely
> useful in  work on equivariant bundle theory that is needed
> for equivariant infinite loop space theory and equivariant
> algebraic K-theory.
>
> Peter May
>
>
>

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

Re: Reference requested

[jpradines]

The use of a lot of terminologies stemming from topology for describing 
purely algebraic properties seems to be widespread  and fashionable among  an 
important part of the community of categorists.
This may be a convenient source of intuition and analogies by giving a 
topological or geometrical fragrance to such algebraic concepts.
However the considerable drawback is that this habit is a source of 
unsolvable clashes for people who are currently using topological or more 
specially Lie groupoids, more generally structured (in Ehresmann's sense), 
i. e. internal, groupoids, who are obliged to create alternative 
terminologies.
For the special case of the duet discrete/undiscrete (or indiscrete, or 
sometimes coarse) I'm personally using presently null/banal (there are a lot 
of different terminologies used by various authors).
(As to the term "chaotic", I prefer to avoid comments, being afraid to 
perturb the beautifully non chaotic weather we are presently enjoying in our 
region).

Jean Pradines

----- Message d'origine ----- 
De : "Ronnie Brown" <ronnie.profbrown@btinternet.com>
À : "Peter May" <may@math.uchicago.edu>
Cc : <categories@mta.ca>
Envoyé : jeudi 29 septembre 2011 15:41
Objet : categories: Re: Reference requested


> Why not use the term `indiscrete groupoid' for the functor that gives a
> right adjoint to the  functor Ob: Groupoids \to Sets?   The left adjoint
> is then of course the `discrete groupoid'.  This agrees with the
> terminology for discrete and indiscrete topologies.
>
> I confess to have used different  terminology in various places.
>
> Of course one use of these notions is to show that the functor Ob
> preserves limits and colimits, which is  a start on constructing them.
>
> It is not surprising that this concept occurs widely. In groupoids there
> is a notion of covering morphism and the universal cover of a group G
> is of course an indiscrete groupoid G'; this groupoid is by no means
> `trivial' since it comes equipped with a covering morphism  p: G' \to
> G.  This approach to covering space theory is given in my book `Topology
> and groupoids'.
>
> Ronnie
>
>

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

Re: Reference requested

[Peter May]

Thanks everybody for comments, although I guess the use
goes so far back into antiquity that the request for an original
reference is unanswerable.  For context, with two young
collaborators (Bertrand Guillou and Mona Merling), I
have a draft in progress tentatively entitled ``Chaotic
categories and equivariant classifying spaces''.

I prefer `chaotic' to `indiscrete' not just because
of the `coarse' implications of the latter, but because
indiscrete spaces are boring, `null or banal', whereas
chaotic categories have genuinely significant applications.
They are quite surprisingly central to the theory of universal
bundles, equivariant or not.

Via the (product-preserving) classifying space construction
from categories (especially categories internal to spaces)
to spaces, they provide a rich source of contractible spaces
that can very easily be given interesting additional structure.
That is just what one wants when constructing universal bundles.

More fun, it is just what one wants to construct an E infinity
operad of G-categories that defines `genuine' symmetric
monoidal G-categories (which are not merely symmetric
monoidal categories on which a group G acts in the obvious
`naive' way).   These which give rise to `genuine' G-spectra.
Genuine G-spectra that define equivariant algebraic K-theory
arise in precisely this way.    All starting from chaotic trivialities.


Cheers,

Peter


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

Re: partial categories

[Peter Selinger]

Dear Emily,

one notion of "partial category" that has been studied is Freyd's
notion of "paracategory". It differs from what you wrote below as
follows: instead of taking compositions of two arrows as the primitive
operation, one takes compositions of n arrows as primitive operations,
for all n. So if f1, ..., fn are n arrows (so that the codomain of
each is the domain of the next), then [f1, ..., fn] is their
composition, which may be defined or undefined.

In the case of (total) categories, adding n-ary compositions makes no
difference, since they are already definable in terms of identities
and binary composition. But in the partial case, it does make a
difference, as it is possible, for example, that [f,g,h] is defined,
but [f,g] and [g,h] are undefined.

The axioms are:

(a) [] : A -> A is defined (the composition of the empty path from A to A)
(b) [f] is defined and equal to f, for all arrows f,
(c) if ff, gg, hh are are (composable) paths, and if [gg] is defined,
     then [ff,[gg],hh] is defined if and only if [ff,gg,hh] is defined,
     and in this case, they are both equal.

The main representation theorem is:

Every reflexive subgraph of a category is a paracategory; conversely,
every paracategory can be faithfully completed to a category.

It is not the only possible notion of partial category, and may not
always be the notion that one wants.

-- Peter

Emily Riehl 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
>


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

Re: partial categories

[Lutz Schröder]

I studied these things in my PhD work. The thesis itself is in German, 
I'm afraid, but there's a series of papers based on it which you can 
find on my homepage. Maybe the most interesting one for you might be the 
paper with Mateus on probabilistic automata (which form a certain type 
of partial category) in MSCS 12 (2002), pp. 481–512.

Regards,

Lutz



Am 28.09.2011 22:34, schrieb Emily Riehl:
> 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
>

-- 
--------------------------------------
Prof. Dr. Lutz Schröder
Senior Researcher
DFKI Bremen	
Safe and Secure Cognitive Systems
Cartesium, Enrique-Schmidt-Str. 5
D-28359 Bremen

phone: (+49) 421-218-64216
Fax:   (+49) 421-218-9864216
mail: Lutz.Schroeder@dfki.de
www.dfki.de/sks/staff/lschrode
--------------------------------------


-------------------------------------------------------------
Deutsches Forschungszentrum für Künstliche Intelligenz GmbH
Firmensitz: Trippstadter Strasse 122, D-67663 Kaiserslautern

Geschäftsführung:
Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster (Vorsitzender)
Dr. Walter Olthoff

Vorsitzender des Aufsichtsrats:
Prof. Dr. h.c. Hans A. Aukes

Amtsgericht Kaiserslautern, HRB 2313
-------------------------------------------------------------




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

Re: Reference requested

[David Roberts]

Or codiscrete groupoid?

David

On 29 September 2011 23:11, Ronnie Brown
<ronnie.profbrown@btinternet.com> wrote:
> Why not use the term `indiscrete groupoid' for the functor that gives a
> right adjoint to the  functor Ob: Groupoids \to Sets?   The left adjoint
> is then of course the `discrete groupoid'.  This agrees with the
> terminology for discrete and indiscrete topologies.
>
> I confess to have used different  terminology in various places.
>
> Of course one use of these notions is to show that the functor Ob
> preserves limits and colimits, which is  a start on constructing them.
...

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