* partial categories @ 2011-09-28 20:34 Emily Riehl [not found] ` <CADxNEA2=AdiLetth8HkP0LK2Y8chP0kfrTjyQ5bP1OTA3h5Fig@mail.gmail.com> ` (4 more replies) 0 siblings, 5 replies; 9+ messages in thread From: Emily Riehl @ 2011-09-28 20:34 UTC (permalink / raw) To: categories 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/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
[parent not found: <CADxNEA2=AdiLetth8HkP0LK2Y8chP0kfrTjyQ5bP1OTA3h5Fig@mail.gmail.com>]
* Re: partial categories [not found] ` <CADxNEA2=AdiLetth8HkP0LK2Y8chP0kfrTjyQ5bP1OTA3h5Fig@mail.gmail.com> @ 2011-09-29 1:11 ` Claudio Hermida 0 siblings, 0 replies; 9+ messages in thread From: Claudio Hermida @ 2011-09-29 1:11 UTC (permalink / raw) To: Emily Riehl; +Cc: categories > > 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/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Reference requested 2011-09-28 20:34 partial categories Emily Riehl [not found] ` <CADxNEA2=AdiLetth8HkP0LK2Y8chP0kfrTjyQ5bP1OTA3h5Fig@mail.gmail.com> @ 2011-09-29 1:35 ` Peter May 2011-09-29 13:41 ` Ronnie Brown [not found] ` <11E807BD-8A2D-423D-8D1B-117BC99B7CF8@mq.edu.au> 2011-09-29 2:18 ` partial categories Peter Selinger ` (2 subsequent siblings) 4 siblings, 2 replies; 9+ messages in thread From: Peter May @ 2011-09-29 1:35 UTC (permalink / raw) Cc: categories 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/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Reference requested 2011-09-29 1:35 ` Reference requested Peter May @ 2011-09-29 13:41 ` Ronnie Brown 2011-09-30 7:34 ` jpradines [not found] ` <11E807BD-8A2D-423D-8D1B-117BC99B7CF8@mq.edu.au> 1 sibling, 1 reply; 9+ messages in thread From: Ronnie Brown @ 2011-09-29 13:41 UTC (permalink / raw) To: Peter May; +Cc: categories 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/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Reference requested 2011-09-29 13:41 ` Ronnie Brown @ 2011-09-30 7:34 ` jpradines 0 siblings, 0 replies; 9+ messages in thread From: jpradines @ 2011-09-30 7:34 UTC (permalink / raw) To: Ronnie Brown, Peter May; +Cc: categories 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/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
[parent not found: <11E807BD-8A2D-423D-8D1B-117BC99B7CF8@mq.edu.au>]
* Re: Reference requested [not found] ` <11E807BD-8A2D-423D-8D1B-117BC99B7CF8@mq.edu.au> @ 2011-09-30 13:56 ` Peter May 0 siblings, 0 replies; 9+ messages in thread From: Peter May @ 2011-09-30 13:56 UTC (permalink / raw) Cc: categories 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/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: partial categories 2011-09-28 20:34 partial categories Emily Riehl [not found] ` <CADxNEA2=AdiLetth8HkP0LK2Y8chP0kfrTjyQ5bP1OTA3h5Fig@mail.gmail.com> 2011-09-29 1:35 ` Reference requested Peter May @ 2011-09-29 2:18 ` Peter Selinger 2011-09-29 12:24 ` Lutz Schröder 2011-09-30 7:38 ` Reference requested David Roberts 4 siblings, 0 replies; 9+ messages in thread From: Peter Selinger @ 2011-09-29 2:18 UTC (permalink / raw) To: eriehl; +Cc: categories 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/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: partial categories 2011-09-28 20:34 partial categories Emily Riehl ` (2 preceding siblings ...) 2011-09-29 2:18 ` partial categories Peter Selinger @ 2011-09-29 12:24 ` Lutz Schröder 2011-09-30 7:38 ` Reference requested David Roberts 4 siblings, 0 replies; 9+ messages in thread From: Lutz Schröder @ 2011-09-29 12:24 UTC (permalink / raw) To: Emily Riehl, categories 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/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Reference requested 2011-09-28 20:34 partial categories Emily Riehl ` (3 preceding siblings ...) 2011-09-29 12:24 ` Lutz Schröder @ 2011-09-30 7:38 ` David Roberts 4 siblings, 0 replies; 9+ messages in thread From: David Roberts @ 2011-09-30 7:38 UTC (permalink / raw) To: categories@mta.ca list 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/ ] ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2011-09-30 13:56 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-09-28 20:34 partial categories Emily Riehl [not found] ` <CADxNEA2=AdiLetth8HkP0LK2Y8chP0kfrTjyQ5bP1OTA3h5Fig@mail.gmail.com> 2011-09-29 1:11 ` Claudio Hermida 2011-09-29 1:35 ` Reference requested Peter May 2011-09-29 13:41 ` Ronnie Brown 2011-09-30 7:34 ` jpradines [not found] ` <11E807BD-8A2D-423D-8D1B-117BC99B7CF8@mq.edu.au> 2011-09-30 13:56 ` Peter May 2011-09-29 2:18 ` partial categories Peter Selinger 2011-09-29 12:24 ` Lutz Schröder 2011-09-30 7:38 ` Reference requested David Roberts
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).