Restriction categories. I: Categories of partial maps

2-category associated idempotent category of partial maps category of semilattices cocompleteness completeness degree of partiality equivalence of 2-categories formal system restriction category universal realization

Mathematics Subject Classification ID

Preorders, orders, domains and lattices (viewed as categories) (18B35) Categorical semantics of formal languages (18C50) Semantics in the theory of computing (68Q55)

Abstract: A restriction category is an abstract formulation for a category of partial maps, defined in terms of certain specified idempotents called the restriction idempotents. All categories of partial maps are restriction categories; conversely, a restriction category is a category of partial maps if and only if the restriction idempotents split. Restriction categories facilitate reasoning about partial maps as they have a purely algebraic formulation. In this paper we consider colimits and limits in restriction categories. As the notion of restriction category is not self-dual, we should not expect colimits and limits in restriction categories to behave in the same manner. The notion of colimit in the restriction context is quite straightforward, but limits are more delicate. The suitable notion of limit turns out to be a kind of lax limit, satisfying certain extra properties. Of particular interest is the behaviour of the coproduct both by itself and with respect to partial products. We explore various conditions under which the coproducts are ``extensive in the sense that the total category (of the related partial map category) becomes an extensive category. When partial limits are present, they become ordinary limits in the total category. Thus, when the coproducts are extensive we obtain as the total category a lextensive category. This provides, in particular, a description of the extensive completion of a distributive category.

Review text

Given a category with a stable system of monics, one can form the corresponding category of partial maps. To each map in this category there is, on the domain of the map, an associated idempotent, which measures the degree of partiality. This structure is captured abstractly by the notion of a restriction category, in which every arrow is required to have such an associated idempotent. Categories with a stable system of monics, functors preserving this structure, and natural transformations which are cartesian with respect to the chosen monics, form a 2-category which we call \({\mathcal {MC}}at.\) The construction of categories of partial maps provides a 2-functor \({\mathcal P}ar: {\mathcal {MC}}at \rightarrow {\mathcal C}at\). We show that \({\mathcal P}ar\) can be made into an equivalence of 2-categories between \({\mathcal {MC}}at\) and a 2-category of restriction categories. NEWLINENEWLINENEWLINEThe underlying ordinary functor \({\mathcal P}ar_{0}: {\mathcal {MC}}at_{0} \rightarrow {\mathcal C}at_{0}\) of the above 2-functor \({\mathcal P}ar\) turns out to be monadic, and, from this, we deduce the completeness and cocompleteness of the 2-categories of \({\mathcal M}\)-categories and of restriction categories. We also consider the problem of how to turn a formal system of subobjects into an actual system of subobjects. A formal system of subobjects is given by a functor into the category \(s{\mathcal L}at\) of semilattices. This structure gives rise to a restriction category which, via the above equivalence of 2-categories, gives an \({\mathcal M}\)-category. This \({\mathcal M}\)-category contains the universal realization of the given formal subobjects as actual subobjects.

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

This page was built for publication: Restriction categories. I: Categories of partial maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958307)