Maths & Stats / Seminars / AusCat Seminar / 980520rc

A characterization of categories of partial maps

Robin Cockett
Dept. Computer Science
University of Calgary
Calgary, Alberta
CANADA

Sydney category seminar: 21 May 1998.

The talk described work in progress with Steve Lack .

Abstract:

This work was motivated by he problem of obtaining a conceptual description of the extensive completion of a distributive category. It traces the ideas from the concrete description of the extensive completion through to a more abstract description using copy categories. Here certain idempotents played a crucial role. Finally it described a very fundamental characterization of categories of partial maps purely in terms of idempotent structure.

There is no claim that these results are altogether original! The basic ideas occur in the work of various authors (Rossolini and Robinson, Heller, Jay, Carboni): our aim is to use these ideas to elucidate various constructions (and it helps to talk about them!)

Summary:

The extensive completion of a distributive category:

    Let X be a distributive category then Cp(X) the extensive completion of X is the following category:

    • Objects: p: A -> 1+1
    • Maps: f: p1 -> p2 where p1: A -.>1+1, p2: B -> 1+1, and f: A -> B+1 such that p1;<f |false> = p2 and p1 = f;!+1.

    To prove this is actually what I claim takes work (of course) and we would like a more conceptual approach.

    First we note that the maps look rather like maps in the Kleisli category of the exception monad. This allows a first reformulation in terms of Ex(X), which we may view as "pointed sets":

    • Objects: p: A -> 1
    • Maps: f: p1 -> p2 where f;p2 = p1 and f;! = p1.

    This looks a little clearer but the second condition is really not very clear ... !:B -> 1+1 in X is the map !;true. What role does this play? To answer this question we must understand the structure of the category Ex(X) better.

    As the exception monad is a monoidal monad the Kleisli category is equipped with a symmetric tensor. Furthermore, the copy map lifts up as a natural transformation into the Kleisli category. This suggests we can abstract the problem to categories with these properties.

Copy categories:

    A copy category is a symmetric monoidal category X with a monoidal transformation

    D: X -> X * X

    which turns each object into a commutative cosemi-group (that is a monoid without a unit).

    In a copy category each object either has a unit or it does not: an object with a unit is called total. A map is called total if it is between total objects and it preserves the units. Clearly the total maps of a copy category form a cartesian (i.e. has products)category.

    Any p: A -> T (where T is the tensor unit) induces an idempotent e_p:A -> A by

    A -D-> A * A -p*1-> T * A -u-> A

    which we shall call a copy restriction (idempotent). now these copy restrictions allows us to re-express the completion Cp(X) we discussed above as follows:

    With respect to the copy restrictions we may form the Karoubi envelope (a restricted Cauchy completion) call this Kr(X) this is clearly a copy category. Out of this category we may take the subcategory of total maps: this is Cp(X). Clearly this category is cartesian

    The construction of the extensive completion may then be viewed as a consequence of this construction. In particular, we have the following theorem:

    Theorem: For any distributive copy category X with a zero, Cp(X) is extensive.

    By a distributive copy category I simply mean a copy category with coproducts which are preserved by the tensor in each argument. To have a zero is to have an initial object which is also a final object.

    Now before continuing it is perhaps worth considering some examples of copy categories and the copy completion construction.

    1. An idempotent commutative monoid M is an copy category: there is only one object so the tensor is determined on objects on maps f * g = f;g (commutativity gives the middle four interchange). The copy map is the identity. Cp(M) is simply the meet semi-lattice regarded as a poset. Thus, one might say that we are just exploring this very well-known construction ....
    2. In any symmetric monoidal category the cocommutative semi-groups from a copy category. If the original category has coproducts (which distribute over the tensor0 then the cocommutative semi-groups are a distributive copy category. Further, it the category has a zero then the result will satisfy the theorem. now this raises an interesting question as these constructions applied to any commutative monoid enriched category monoidal category (e.g. Rel, Mod_R, SupLat,...) gives an extensive diatributive category. OPEN QUESTION: what do these look like?
    3. If M is any stable system of monics in a category X we may form the category of partial maps with respect to those monics Par_M(X). If X has products then Par_M(X) is a copy category.

    The last example raises a number of questions relating to partial map classification and I will end by giving a classification theorem for these partial map categories which underlies many results in this area.

Categories with a restriction:

    A category X has a restriction if to each f: A -> B there is an associated idempotent {f}:A -> A (here laziness is stopping me from using Ross Street's suggestion of an overbar) which satisfies five conditions:

      • {f};f = f
      • {f};{g} = {g};{f}
      • {f;g} = {f;{g}}
      • {{f};g} = {f};{g}
      • f;{g} = {f;g};f

    We say the restriction is split if all the idempotents of the form {f} split. A map in a category with a restriction is total in case {f} = 1. The total maps form a subcategory which includes all the monics.

    Any total copy category has a natural restriction given by {f} = e_f;!. Furthermore, the natural functors between copy categories (comonoidally preseving copy structure) preserves the restriction structure. Thus, there is a 2-functor from the 2-category of copy categories to the 2-category of categories with restrictions:

    Copy --> rCat

    where rCat is defined by:

    • 0-cells: categories with a split restriction
    • 1-cells: functors which preserve restrictions, that is {F f} = F{f}.
    • 2-cells: natural transformations whose components are total.

    The 2-functor takes a copy category splits the restriction idempotents (this gives a total copy category )... which is by the above a restriction category.

    Now let MCat be the 2-category:

    • 0-cells: a category X together with a stable system of monics M
    • 1-cells: functors which preserve the systems of monics and pullbacks along these monics.
    • 2-cells: natural transformations who naturallity squares at M-maps are pullbacks.

    We now have the observation that:

    Theorem: MCat is isomorphic to rCat.

    In particular, a category X with split restriction has the class of monics which split a restricion a stable system of monics in Total(X) and Par_M(Total(X)) is just X. However, the theorem provides more: as restriction preserving functors preserve certain pullbacks and the natural transformations are automatically cartesian over certain maps.

Is there more?

    We hope so!!

    In particular, we plan to answer the following:

    1. When does a restriction category with coproducts have its total category extensive ... and indeed when is the system M of monics precisely the detachable maps (coproduct embeddings).
    2. What do partial map classifiers look like in these situations.
    3. How does one introduce functorial structure in the presence (or indeed to generate) restriction structures. E.g. can one get a slick version of the "shape" functors (Barry Jay) using the restriction structures?

Other talks by the same speaker.
Back to titles of seminars.

Steve Lack
Last modified: Fri May 22 10:23:46 EST 1998