Theory and Applications of Categories, Vol. 16, No. 15, 2006, pp. 307–341.

STABLE MEET SEMILATTICE FIBRATIONS AND FREE RESTRICTION CATEGORIES

J.R.B. COCKETT AND XIUZHAN GUO

Abstract. The construction of a free restriction category can be broken into two steps: the construction of a free stable semilattice fibration followed by the construction of a free restriction category for this fibration. Restriction categories produced from such fibrations are “unitary”, in a sense which generalizes that from the theory of inverse semigroups. Characterization theorems for unitary restriction categories are derived. The paper ends with an explicit description of the free restriction category on a directed graph.

1. Introduction

A restriction on a category C is an assignment of a map \overline{f} : X → X to each map f : X → Y. When a category has a restriction which satisfies the following four axioms:

[R.1] f\overline{f} = f for all map f,

[R.2] \overline{f}\overline{g} = \overline{g}\overline{f} whenever dom(f) = dom(g),

[R.3] \overline{g\overline{f}} = \overline{g}\overline{f} whenever dom(f) = dom(g),

[R.4] \overline{g}f = f\overline{gf} whenever cod(f) = dom(g),

it is called a restriction category [3].

A functor F : C → D between two restriction categories is said to be a restriction functor if F (\overline{f}) = \overline{F (f)} for any map f in C. Restriction categories and restriction functors form a category, denoted by rCat_{0}. Clearly, there is a forgetful functor to the category of categories, U_{r} : rCat_{0} → Cat_{0}, which forgets restriction structure. U_{r} has a left adjoint F_{r} given by the free restriction category on a category which was described in [3].

Also in [3], quite separately, a way to freely add subobjects determined by a fibration was given. It was not realized at that time that the two constructions were actually related. One of the objectives of this paper is to fill out this relationship as, realigned in this way, the free construction factors though the construction which freely adds subobjects specified by a stable meet semilattice fibration.

Breaking the construction of the free restriction category down into two separate steps is useful: for example, this approach was key to understanding the construction of free range restriction categories [2]. Furthermore, the intermediate step of adding subobjects is of independent interest and leads one to consider the question of how one may characterize the rather special restriction categories which arise from these constructions. This question, it turns out, is a generalization of a question which had already arisen in the study of inverse semigroups (see [8, 11]) for the categories which arise in this manner are “unitary” (or “proper”) restriction categories.

Both authors partially supported by NSERC, Canada.

Received by the editors 2005-04-01 and, in revised form, 2006-07-21.

Transmitted by S. Lack. Published on 2006-08-10.

2000 Mathematics Subject Classification: 18D99.

Key words and phrases: Restriction categories, fibrations, semigroups.

\begin{matrix}c \\ ◯ \end{matrix} J.R.B. COCKETT and XIUZHAN GUO, 2006. Permission to copy for private use granted.

This realization led us to seek characterization theorems analogous to those for unitary inverse semigroups. This is the content of the second section below which, incidentally, can be skipped by readers primarily interested in the free construction. While we do provide characterization theorems, any reader familiar with the theory for inverse semigroups will notice that we do not present a parallel to the McAlister triple and, in fact, we do not know whether there is an appropriate generalization of this notion. Instead we use, as our point of generalization, the analogue of an F -inverse semigroup (see [8, 11]) which we propose is a bounded unitary restriction category (see Subsection 3.23). We also found it very natural to cast the development in the language of fibrations which perspective, we feel, is also useful in explaining the significance of the original development of E-unitary inverse semigroups.

For further connections to semigroup theory, see the discussion in Manes [9]. In particular, there he points out that the untyped version of the restriction identities had already been considered in, for example, John Fountain’s work [5] and, even more explicitly, in Jackson and Stokes’s paper [7].

Restriction categories were introduced to model partial maps and in this regard they are complete in the sense that every restriction category occurs as a full subcategory of a partial map category. There is an extensive literature on partial map categories, see for example [4], [12], [13], and [14], however, much of this literature considers categories with more structure (e.g. partial products) than is being considered here.

That there are free restriction categories is of some interest especially as they have a relatively simple form. We end this paper by describing a particularly simple construction: the free restriction category on a graph. This bears a close relationship to the construction of the free inverse semigroup due to Munn [10]. Free restriction categories on graphs are completely decidable and, thus, allow one to determine what is and is not true in general restriction categories relatively easily.

In Section 2 we introduce stable meet semilattice fibrations and show that each restriction category has functorially associated to it such a fibration. Furthermore, we show how such a fibration can be used to construct a restriction category and that this construction provides a left adjoint to the previous construction. In the next section we characterize the restriction categories which arise from such fibrations and show that this adjunction is both monadic and comonadic. This leads into a discussion of unitary restriction categories. In the last section we note that every category gives rise freely to a stable meet semilattice fibration. Thus the category of stable meet semilattice fibrations acts as a stepping-stone between the category of restriction categories and the category of categories. The composite of the adjoint of this section and the second section produces the Cockett-Lack free restriction category functor.

STABLE MEET SEMILATTICE FIBRATIONS AND FREE RESTRICTION CATEGORIES 309

2. Stable Meet Semilattice Fibrations

Recall that a stable homomorphism (that is a pullback preserving homomorphism) of meet semilattices preserves binary meets but crucially does not necessarily preserve the empty meet (i.e. the top element).

2.1. Definition. A stable meet semilattice fibration is a fibration δ_{X} : X̃ → X in which each fiber is a meet semilattice and in which for each map f : X → Y, the inverse image functor f^{∗} : δ_{X}^{−1}(Y) → δ_{X}^{−1}(X) is a stable meet semilattice homomorphism.

Stable meet semilattice fibrations δ_{X} : X̃ → X are equivalently, using the Grothendieck construction [1], those fibrations given by the indexed categories X^{op} → StabMSLat_{0}, where StabMSLat_{0} is the category of meet semilattices with stable homomorphisms.

2.2. Restriction Categories to Stable Meet Semilattice Fibrations. To each restriction category C one can associate a stable meet semilattice fibration ∂ : r(C) → C. The category r(C) has objects (X, e_{X}), where e_{X} is a restriction idempotent over X, namely, a map e_{X} : X → X satisfying \overline{e_{X}} = e_{X}, and maps f : X → Y such that e_{X} = \overline{e_{Y} f}e_{X} as maps from (X, e_{X}) to (Y, e_{Y}). The obvious forgetful functor ∂_{C} : r(C) → C is a stable meet semilattice fibration as shown in the following lemma:

2.3. Lemma. If C is a restriction category, then the forgetful functor ∂_{C} : r(C) → C is a stable meet semilattice fibration.

Proof. Note that each fiber

∂_{C}^{−1}(X) = {(X, e_{X}) | e_{X} : X → X is a restriction idempotent on X}

is a meet semilattice with the order given by (X, e_{X}) ≤ (X, e′_{X}) ⇔ e_{X} = e′_{X}e_{X}, with the binary meet given by (X, e_{X}) ∧ (X, e′_{X}) = (X, e_{X}e′_{X}), and with (X, 1_{X}) as the top element.

For any map f : X → Y in C and any object (Y, e_{Y}) ∈ ∂_{C}^{−1}(Y), f : (X, \overline{e_{Y} f}) → (Y, e_{Y}) is a map of r(C) since \overline{e_{Y} f}^{2} = \overline{e_{Y} f}. Moreover, it is straightforward to see that f : (X, \overline{e_{Y} f}) → (Y, e_{Y}) is the cartesian lifting of f : X → Y at (Y, e_{Y}). Hence ∂_{C} : r(C) → C is a fibration.

Obviously, for any map f : X → Y, f^{∗} : ∂_{C}^{−1}(Y) → ∂_{C}^{−1}(X), sending (Y, e_{Y}) to (X, \overline{e_{Y} f}), the functor introduced by cartesian lifting, is a stable homomorphism since \overline{e′_{Y} f} \overline{e_{Y} f} = \overline{e_{Y} f\overline{e_{Y} f}} = \overline{e′_{Y} \overline{e_{Y}} f} = \overline{e′_{Y} e_{Y} f}. Hence ∂_{C} : r(C) → C is a stable meet semilattice fibration.

The category sFib_{0} of stable meet semilattice fibrations may be formed as follows:

objects: stable meet semilattice fibrations: (δ_{X} : X̃ → X),

maps: a map from (δ_{X} : X̃ → X) to (δ_{Y} : Ỹ → Y) is a pair (F, F′), where F : X → Y and F′ : X̃ → Ỹ are functors such that

\xymatrix{X̃ \ar[r]^{F′} \ar[d]_{δ_{X}} & Ỹ \ar[d]^{δ_{Y}} \\ X \ar[r]^{F} & Y}

commutes and for any map f : A → B in X and any σ, σ′ ∈ δ_{X}^{−1}(B), the following conditions are satisfied:

[sfM.1] F′(⊤_{δ_{X}^{−1}(A)}) = ⊤_{δ_{Y}^{−1}(F (A))},

[sfM.2] F′(σ ∧ σ′) = F′(σ) ∧ F′(σ′),

[sfM.3] F′(f^{∗}(σ)) = (F (f))^{∗}(F′(σ)),

composition: for any maps (F, F′) : (δ_{X} : X̃ → X) → (δ_{Y} : Ỹ → Y) and (G, G′) : (δ_{Y} : Ỹ → Y) → (δ_{Z} : Z̃ → Z), (G, G′)(F, F′) = (GF, G′F′),

identities: 1_{(δ_{X}:X̃→X)} = (1_{X}, 1X̃).

Note that each map (F, F′) : δ_{X} → δ_{Y} is a morphism of fibrations in the sense of preserving Cartesian liftings, due to [sfM.3], but it also preserves finite limits on the fibers due to [sfM.1] and [sfM.2].

We can now define a functor R : rCat_{0} → sFib_{0} by setting R(X) = ∂_{X} : r(X) → X. If F : X → Y is a restriction functor, then we have a functor r(F) : r(X) → r(Y) given by sending f : (A, e_{A}) → (B, e_{B}) to F (f) : (F (A), F (e_{A})) → (F (B), F (e_{B})) and a commutative diagram

\xymatrix{r(X) \ar[d]_{∂_{X}} \ar[r]^{r(F)} & r(Y) \ar[d]^{∂_{Y}} \\ X \ar[r]^{F} & Y}

2.4. Lemma. R : rCat_{0} → sFib_{0}, taking F : X → Y in rCat_{0} to (F, r(F)) : (∂_{X} : r(X) → X) → (∂_{Y} : r(Y) → Y) in sFib_{0}, is a functor.

Proof. We have

r(F)(⊤_{∂_{X}^{−1}(A)}) = r(F)(A, 1_{A})
= (F (A), F (1_{A}))
= (F (A), 1_{F (A)})
= ⊤_{∂_{Y}^{−1}(F (A))},

r(F)((B, e_{B})(B, e′_{B})) = r(F)(B, e_{B}e′_{B})
= (F (B), F (e_{B}) · F (e′_{B}))
= (F (B), F e_{B})(F (B), F (e′_{B}))
= r(F)(B, e_{B}) · r(F)(B, e′_{B}),

and, for any map f : A → B in X,

r(F)(f^{∗}(B, e_{B})) = r(F)(A, \overline{e_{B}f})
= (F (A), F (\overline{e_{B}f}))
= (F (A), \overline{F (e_{B}) · F (f)})
= (F (f))^{∗}(F (B), F (e_{B}))
= (F (f))^{∗}(r(F)(B, e_{B})).

Hence the conditions [sfM.1], [sfM.2], and [sfM.3] are satisfied and therefore

(F, r(F)) : (∂_{X} : r(X) → X) → (∂_{Y} : r(Y) → Y)

is a map in sFib_{0}.

For any restriction functors F : X → Y and G : Y → Z, we have

R(GF) = (GF, r(GF)) = (GF, r(G)r(F)) = (G, r(G))(F, r(F)) = R(G)R(F).

Clearly, R(1_{X}) = (1_{X}, 1_{r(X)}). Hence R is a functor.

2.5. Stable Meet Semilattice Fibrations to Restriction Categories. Suppose that δ_{X} : X̃ → X is a stable meet semilattice fibration, then we can form the category S(δ_{X}) with:

objects: A ∈ obX,

maps: (f, σ) : A → B, where f : A → B is a map in X and σ ∈ δ_{X}^{−1}(A) is such that σ ≤ f^{∗}(⊤_{δ_{X}^{−1}(B)}),

composition: For any map (f, σ_{1}) : A → B and (g, σ_{2}) : B → C, (g, σ_{2})(f, σ_{1}) = (gf, σ_{1} ∧ f^{∗}(σ_{2})),

identities: 1_{A} = (1_{A}, ⊤_{δ_{X}^{−1}(A)}).

2.6. Remark. Let f : A → B be a map in X. The condition that σ ≤ f^{∗}(⊤_{δ_{X}^{−1}(B)}) holds for a map (f, σ) : A → B in S(δ_{X}) is to ensure the identity law holds:

(1_{B}, ⊤_{δ_{X}^{−1}(B)})(f, σ) = (f, σ ∧ f^{∗}(⊤_{δ_{X}^{−1}(B)})) = (f, σ)

and

(f, σ)(1_{A}, ⊤_{δ_{X}^{−1}(A)}) = (f, ⊤_{δ_{X}^{−1}(A)} ∧ (1_{A})^{∗}(σ)) = (f, σ).

2.7. Proposition. For each stable meet semilattice fibration δ_{X}, S(δ_{X}) is a restriction category with the restriction given by \overline{(f, σ)} = (1_{A}, σ) for any map (f, σ) : A → B.

Proof. Clearly, (1_{A}, σ) : A → A is a map in S(δ_{X}). So it suffices to check that \overline{(f, σ)} = (1_{A}, σ) satisfies the four restriction axioms.

[R.1] For any map (f, σ) : A → B,

(f, σ)\overline{(f, σ)} = (f, σ)(1_{A}, σ) = (f, σ ∧ 1_{A}^{∗}(σ)) = (f, σ ∧ 1_{δ_{X}^{−1}(A)}(σ)) = (f, σ).

[R.2] For any maps (f, σ_{1}) : A → B and (g, σ_{2}) : A → C,

\overline{(f, σ_{1})} \overline{(g, σ_{2})} = (1_{A}, σ_{1})(1_{A}, σ_{2})
= (1_{A}, σ_{1} ∧ σ_{2})
= (1_{A}, σ_{2} ∧ σ_{1})
= (1_{A}, σ_{2})(1_{A}, σ_{1})
= \overline{(g, σ_{2})} \overline{(f, σ_{1})}.

[R.3] For any maps (f, σ_{1}) : A → B and (g, σ_{2}) : A → C,

\overline{(g, σ_{2})\overline{(f, σ_{1})}} = \overline{(g, σ_{2})(1_{A}, σ_{1})}
= \overline{(g, σ_{1} ∧ 1_{A}^{∗}(σ_{2}))}
= \overline{(g, σ_{1} ∧ σ_{2})}
= (1_{A}, σ_{1} ∧ σ_{2})
= (1_{A}, σ_{2})(1_{A}, σ_{1})
= \overline{(g, σ_{2})} \overline{(f, σ_{1})}.

[R.4] For any maps (f, σ_{1}) : A → B and (g, σ_{2}) : B → C,

\overline{(g, σ_{2})}(f, σ_{1}) = (1_{B}, σ_{2})(f, σ_{1}) = (f, σ_{1} ∧ f^{∗}(σ_{2})),

and

(f, σ_{1})\overline{(g, σ_{2})(f, σ_{1})} = (f, σ_{1})\overline{(gf, σ_{1} ∧ f^{∗}(σ_{2}))}
= (f, σ_{1})(1_{A}, σ_{1} ∧ f^{∗}(σ_{2}))
= (f, σ_{1} ∧ f^{∗}(σ_{2}) ∧ 1_{A}^{∗}(σ_{1}))
= (f, σ_{1} ∧ f^{∗}(σ_{2})).

Hence \overline{(g, σ_{2})}(f, σ_{1}) = (f, σ_{1})\overline{(g, σ_{2})(f, σ_{1})}.

2.8. Examples.

1. Suppose that C is any category, then S(1_{C}) = C, which is the restriction category with the trivial restriction structure (\overline{f} = 1_{A} for each map f : A → B).

2. For each restriction category C, S(∂_{C}) is the restriction category with the same objects as C while a map from A to B in S(∂_{C}) is a pair (f, e) with a map f : A → B in C and a restriction idempotent e ≤ \overline{f} over A in C, the composition is given by (g, e_{B})(f, e_{A}) = (gf, e_{A} ∧ \overline{e_{B}f}) = (gf, \overline{e_{B}f}e_{A}) for any maps (f, e_{A}) : A → B and (g, e_{B}) : B → C, and the restriction is given by \overline{(f, e_{A})} = (1_{A}, e_{A}). So S(∂_{C}) and C are different in general.

3. Each meet semilattice L can be viewed as a category with elements of L as objects and with maps l_{1} → l_{2} given by l_{1} ≤ l_{2} so that L : L → 1 is a stable meet semilattice fibration. In this case, S(L) is the one object category with maps l : ∗ → ∗ given by elements l of L and with the composition given by l_{1}l_{2} = l_{1} ∧ l_{2}. Note that if we split the restriction idempotents of this category then the subcategory of total maps is precisely L.

Shortly we will see that S, sending (F, F′) : (δ_{X} : X̃ → X) → (δ_{Y} : Ỹ → Y) to S(F, F′) : S(δ_{X}) → S(δ_{Y}), is a functor, where S(F, F′) : S(δ_{X}) → S(δ_{Y}) is given by sending (f, σ) : A → B to (F (f), F′(σ)) : F (A) → F (B), and, in fact, the left adjoint of R. We shall establish this by exhibiting the universal property of S (see Lemma 2.11 below).

2.9. The Universality of the Construction S. Let δ_{X} : X̃ → X be a stable meet semilattice fibration, Y a restriction category, and (F, F′) : (δ_{X} : X̃ → X) → (∂_{Y} : r(Y) → Y) a map in sFib_{0}. For any object A ∈ X and any object σ ∈ δ_{X}^{−1}(A), F′(σ) ∈ r(Y) can be written as (F (A), e_{σ}^{F}), where e_{σ}^{F} is a restriction idempotent over F (A) in Y. In order to prove the universal property of S, we need the following technical lemma.

2.10. Lemma. Let δ_{X} : X̃ → X be a stable meet semilattice fibration and (F, F′) : (δ_{X} : X̃ → X) → (∂_{Y} : r(Y) → Y) a map in sFib_{0}. Then

(i) For any object A ∈ X and any σ_{1}, σ_{2} ∈ δ_{X}^{−1}(A), e_{⊤_{δ{−1 \atop X}(A)}}^{F} = 1_{F (A)} and e_{σ_{1}∧σ_{2}}^{F} = e_{σ}^{F} ∧ e_{σ_{2}}^{F};

(ii) For any map f : A → B in X and σ ∈ δ_{X}^{−1}(B), e_{f^{∗}(σ)}^{F} = \overline{e_{σ}^{F} (F (f))};

(iii) For any map (f, σ) : A → B in S(δ_{X}), e_{σ}^{F} = \overline{F (f)}e_{σ}^{F}.

Proof.

(i) By [sfM.1], (F (A), e_{⊤_{δ{−1 \atop X}(A)}}^{F}) = F′(⊤_{δ_{X}^{−1}(A)}) = ⊤_{δ_{Y}^{−1}(F (A))} = (F (A), 1_{F (A)}). Hence e_{⊤_{δ{−1 \atop X}(A)}}^{F} =

1_{F (A)}. By [sfM.2], (F (A), e_{σ_{1}∧σ_{2}}^{F}) = F′(σ_{1}∧σ_{2}) = F′(σ_{1})∧F′(σ_{2}) = (F (A), e_{σ_{1}}^{F})(F (A), e_{σ_{1}}^{F}) = (F (A), e_{σ_{1}}^{F}e_{σ_{1}}). Hence e_{σ_{1}∧σ_{2}}^{F} = e_{σ_{1}}^{F}e_{σ_{1}}^{F}.

(ii) By [sfM.3], (F (A), e_{f^{∗}(σ)}^{F}) = F′(f^{∗}(σ)) = (F (f))^{∗}(F′(σ)) = (F (f))^{∗}(F (B), e_{σ}^{F}) = (F (A), \overline{e_{σ}^{F} (F (f))}). Hence e_{f^{∗}(σ)}^{F} = \overline{e_{σ}^{F} (F (f))}.

(iii) For any map (f, σ) : A → B in S(δ_{X}), since σ ≤ f^{∗}(⊤_{δ_{X}^{−1}(A)}), we have the following commutative diagram in X̃:

\xymatrix{ & f^{∗}(⊤_{δ_{X}^{−1}(B)}) \ar@{-->}[dr]^{ϑ_{f}} \\ σ \ar[rr] \ar[ur]^{≤} &  & ⊤_{δ_{X}^{−1}(B)}}

where ϑ_{f} is the cartesian lifting of f at ⊤_{δ^{−1}(B)}. Applying F̃, we have the following commutative diagram:

\xymatrix{ & (F (A), e_{f^{∗}(⊤_{δ{−1 \atop X}(B)})}) \ar@{-->}[dr]^{F (f)} \\ (F (A), e_{σ}) \ar[ur]^{1_{F (A)}} \ar[rr]^{F (f)} &  & (F (B), 1_{F (B)})}

Hence F (f) : (F (A), e_{σ}^{F}) → (F (B), 1_{F (B)}) is a map in r(Y) and therefore e_{σ}^{F} = \overline{F (f)1_{F (B)}}e_{σ}^{F} = \overline{F (f)}e_{σ}^{F} .

For a given stable meet semilattice fibration δ_{X} : X̃ → X, we have a functor I_{X} : X → S(δ_{X}) by sending f : A → B to (f, f^{∗}(⊤_{δ_{X}^{−1}(B)})) : A → B. Also, we can define I_{X}^{δ_{X}} : X̃ → r(S(δ_{X})) by taking f : U → V to (δ_{X}(f), (δ_{X}(f))^{∗}(⊤_{δ_{X}^{−1}(δ_{X}(V))})) : (δ_{X}(U), (1_{δ_{X}(U)}, U)) → (δ_{X}(V), (1_{δ_{X}(V)}, V)). Clearly, η = (I_{X}, I_{X}^{δ_{X}}) is a map from (δ_{X} : X̃ → X) to (∂_{S(δ_{X})} : r(S(δ_{X})) → S(δ_{X})) in sFib_{0}. This map turns out to be the unit of the adjunction S ⊣ R.

2.11. Lemma. Let δ_{X} : X̃ → X be a stable meet semilattice fibration and let Y be a restriction category. If (F, F′) : (δ_{X} : X̃ → X) → (∂_{Y} : r(Y) → Y) is a map in sFib_{0}, then there is a unique restriction functor F^{δ_{X}} : S(δ_{X}) → Y sending (f, σ) : A → B to (F (f))e_{σ}^{F} : F (A) → F (B) such that

\xymatrix{(δ_{X} : X̃ → X) \ar[dr]_{(F,F′)} \ar[r]^{(I_{X},I_{X}^{δ_{X}})} & R(S(δ_{X} : X̃ → X)) \ar[d]^{R(F^{δ_{X}})} & S(δ_{X} : X̃ → X) \ar@{.>}[d]_{∃!}^{F^{δ_{X}}} \\  & R(Y) & Y}

commutes, where the restriction idempotent e_{σ}^{F} is determined by F′(σ) = (F (A), e_{σ}^{F}) ∈ r(Y).

Proof. Clearly, by [sfM.1] and Lemma 2.10 (i),

F^{δ_{X}}(1_{A}) = F^{δ_{X}}(1_{A}, ⊤_{δ_{X}^{−1}(A)}) = F (1_{A}) · e_{⊤_{δ{−1 \atop X}(A)}}^{F} = F (1_{A}) · 1_{F (A)} = 1_{F (A)}.

For any maps (f, σ) : A → B and (g, σ′) : B → C in S(δ_{X}), we have

F^{δ_{X}}((g, σ′)(f, σ)) = F^{δ_{X}}(gf, σ ∧ f^{∗}(σ′))
= F (gf) · e_{σ∧f^{∗}(σ′)}^{F}
= F (g) · F (f) · e_{σ}^{F} ∧ e_{f^{∗}(σ′)}^{F} (by Lemma 2.10 (i)),

and

F^{δ_{X}}(g, σ′)F^{δ_{X}}(f, σ) = (F (g) · e_{σ′}^{F})(F (f) · e_{σ}^{F})
= (F (g) · F (f))\overline{e_{σ}^{F} (F (f))}e_{σ}^{F} (by [R.4])
= (F (g) · F (f))e_{f^{∗}(σ′)}^{F}e_{σ}^{F} (by Lemma 2.10 (ii)).

Hence F^{δ_{X}}((g, σ′)(f, σ)) = F^{δ_{X}}(g, σ′)F^{δ_{X}}(f, σ). Therefore F^{δ_{X}} is a functor. Since

F^{δ_{X}}(\overline{(f, σ)}) = F^{δ_{X}}(1_{A}, σ)
= F (1_{A}) · e_{σ}^{F}
= e_{σ}^{F}
= \overline{F (f)}e_{σ}^{F} (by Lemma 2.10(iii))
= \overline{(F (f))e_{σ}^{F}} (by [R.3])
= \overline{F^{δ_{X}}(f, σ)},

F^{δ_{X}} is a restriction functor. Obviously, (F^{δ_{X}}, r(F^{δ_{X}}))(I_{X}, I_{X}^{δ_{X}}) = (F, F′). If G : S(δ_{X} : X̃ → X) → Y is a restriction functor such that (G, r(G))(I_{X}, I_{X}^{δ_{X}}) = (F, F′), then GI_{X} = F and r(G)I_{X}^{δ_{X}} = F′. Hence for any map f : A → B in X, G must map A to F (A) and must map (f, f^{∗}(⊤_{δ_{X}^{−1}(B)})) : A → B to F (f) : F (A) → F (B) and therefore G(f, f^{∗}(⊤_{δ_{X}^{−1}(B)})) = F (f) = F^{δ_{X}}(f, f^{∗}(⊤_{δ_{X}^{−1}(B)})) since e_{f^{∗}(⊤_{δ{−1 \atop X}(B)})}^{F} = \overline{F (f)}. For any map (f, σ) : A → B in S(δ_{X}),

(F (A), e_{σ}^{F}) = F′(σ) = r(G)(I_{X}^{δ_{X}})(σ) = r(G)(A, (1_{A}, σ)) = (G(A), G(1_{A}, σ))

and so G(1_{A}, σ) = e_{σ}^{F}. Since (f, σ) = (f, f^{∗}(⊤_{δ_{X}^{−1}(B)}))(1_{A}, σ) and G is a restriction functor,

G(f, σ) = G(f, f^{∗}(⊤_{δ_{X}^{−1}(B)}))G(1_{A}, σ) = F (f)e_{σ} = F^{δ_{X}}(f, σ).

Then G = F^{δ_{X}} and so the uniqueness of F^{δ_{X}} follows.

2.12. Theorem. There is an adjunction: \xymatrix{rCat_{0} \ar[r]_{R}|{⊥} & sFib_{0} \ar[l]_{S}} with R and S faithful functors.

Proof. By Lemma 2.11, S ⊣ R. Clearly, the counit ε of S ⊣ R is given by ε_{C} : S(R(C)) → C sending (f, e_{A}) : A → B to fe_{A} : A → B, where e_{A} is a restriction idempotent such that e_{A} ≤ \overline{f}, for each restriction category C. We define λ_{C} : C → S(R(C)) by taking f : A → B to (f, \overline{f}) : A → B. It is easy to check that λ_{C} is a functor such that ε_{C}λ_{C} = 1_{C} in Cat_{0}. Hence ε_{C} is an epic in rCat_{0} and therefore is faithful.

On the other hand, the unit of S ⊣ R is given by (I_{X}, I_{X}^{δ_{X}}). Clearly, I_{X} is faithful and each I_{X}^{δ_{X}}|_{δ_{X}} is faithful. By Lemma 2.13 below, S is faithful.

2.13. Lemma. Let (F, G) : (δ_{X} : X̃ → X) → (δ_{Y} : Ỹ → Y) be a morphism of fibrations:

\xymatrix{X̃ \ar[d]_{δ_{X}} \ar[r]^{G} & Ỹ \ar[d]^{δ_{Y}} \\ X \ar[r]^{F} & Y}

If F is faithful and for each object X in X, G|_{δ_{X}^{−1}(X)} : δ_{X}^{−1}(X) → Ỹ is faithful, then G is faithful.

Proof. For any f, g ∈ mapX̃(U, V) with G(f) = G(g), we have δ_{Y}(G(f)) = δ_{Y}(G(g)) which is F (δ_{X}(f)) = F (δ_{X}(g)). Since F is faithful, δ_{X}(f) = δ_{X}(g). By noticing both Cartesian liftings of δ_{X}(f) and δ_{X}(g):

\xymatrix{ & U \ar@{.>}[dl]_{f′} \ar[dr]^{f} &  &  & U \ar@{.>}[dl]_{g′} \ar[dr]^{g} \\ W \ar[rr]_{δ_{X}(f)^{∗}} &  & V & W \ar[rr]_{δ_{X}(g)^{∗}} &  & V}

where W = (δ_{X}(f))^{∗}(V) = (δ_{X}(g))^{∗}(V), we have

G(f) = G(δ_{X}(f)^{∗}f′) = (F (δ_{X}(f)))^{∗}G(f′)

and

G(g) = G(δ_{X}(g)^{∗}g′) = (F (δ_{X}(g)))^{∗}G(g′).

Hence G(f′) = G(g′) and therefore, by the faithfulness of G|_{δ_{X}^{−1}(U)}, f′ = g′. Then f = δ_{X}(f)^{∗}f′ = δ_{X}(g)^{∗}g′ = g and so G is faithful.

3. Restriction Fibered and Unitary Restriction Categories

In Subsection 2.9, we proved that there is an adjunction S ⊣ R : sFib_{0} → rCat_{0} between the category of stable meet semilattice fibrations and the category of restriction categories and, furthermore, that the functor S is faithful. This section studies the special properties of restriction categories which arise as the image of this functor. A complete description of these restriction categories is provided both from the fibrational and (in the last subsection) from the unitary point of view. Furthermore we show how to use these descriptions to show that S is comonadic and R is monadic.

Restriction categories which arise as S(δ_{X}) have the peculiar property that f = g whenever \overline{f} = \overline{g} and fe = ge for some restriction idempotent. A restriction category satisfying this condition is called unitary: this directly generalizes the notion of an E-unitary inverse semigroup. These categories are introduced in the last subsection below and given an alternate view (and a generalization) of the main development path we follow using fibrations

In any unitary restriction category the compatibility relation f ⌣ g (⇔ f\overline{g} = g\overline{f}) is a congruence, this allows all parallel compatible maps to be viewed as a single “base” map. For a fibration the resulting functor to the category of base maps is just ε : S(δ_{X}) → X and we shall speak of the base of a unitary restriction category as the generalization of this situation. In particular, this congruence turns restricted isomorphisms into actual isomorphisms and so it turns a unitary inverse category (a restriction category in which all maps are restricted isomorphisms) into a groupoid. In the one object case this is the observation that the base of an E-unitary inverse monoid is a group which provides an important interface between semigroup theory and group theory. A nice example of this is given by the E-unitary inverse monoid of Möbius functions on the complex plane (described in [8]).

In many unitary restriction categories each equivalence class of compatible maps contains an upper bound. However, the composite of two bounding maps may not necessarily be bounding. In the inverse semigroup literature the corresponding semigroups are called F - unitary: we have chosen to depart slightly from this terminology using instead bounded unitary. A bounded unitary restriction category is strictly bounded in case the composition of any two bounding maps is itself bounding. Strictly bounded unitary restriction categories are precisely the categories in the image of S.

As mentioned in the introduction of this paper, while we have managed to show that every unitary restriction category can be embedded in a bounded unitary restriction category (which can be constructed from a lax fibration), we have not generalized the notion of McAlister triple – a useful tool of semigroup theory.

3.1. Restriction Fibered Categories. We shall call a restriction category of the form S(δ_{X}) which arises from a fibration δ_{X} a restriction fibered category. The purpose of this subsection is to provide an alternative description of these rather special restriction categories.

We begin with a general fact about restriction categories:

3.2. Lemma.

(i) Any restriction category is poset-enriched with respect to f ≤ g ⇔ f = g\overline{f}.

(ii) f ≤ g ⇒ \overline{f} ≤ \overline{g}.

Proof.

(i) Clearly, f = f\overline{f} gives f ≤ f. If f ≤ g and g ≤ h, then f = g\overline{f} and g = h\overline{g} and so, by [R.3], f = g\overline{f} = h\overline{g}\overline{f} = h\overline{g\overline{f}} = h\overline{f}. Hence f ≤ h. If f ≤ g and g ≤ f, then f = g\overline{f} and g = f\overline{g} and so, by [R.3], \overline{f} = \overline{g\overline{f}} = \overline{g}\overline{f} = \overline{f}\overline{g} = \overline{f\overline{g}} = \overline{g}. Hence, by [R.1], f = g\overline{f} = g\overline{g} = g, as desired. Therefore, map_{C}(A, B) is a poset.

Let f, g : A → B and f′, g′ : B → C be maps. If f ≤ g and f′ ≤ g′, then f = g\overline{f} and f′ = g′\overline{f′}. Hence

g′g\overline{f′f} = g′g\overline{f′f\overline{f}} = g′g\overline{f} \overline{f′f} = g′f\overline{f′f} = g′\overline{f′}f = f′f

and therefore f′f ≤ g′g. Thus, any restriction category is poset-enriched with respect to f ≤ g ⇔ f = g\overline{f}.

(ii) f ≤ g gives f = g\overline{f}. Hence \overline{f} = \overline{g\overline{f}} = \overline{g}\overline{f} = \overline{g}\overline{\overline{f}} and therefore \overline{f} ≤ \overline{g}.

Now, for a pair of objects A, B in a restriction category C, we define

map_{C}^{max}(A, B) = {f ∈ map_{C}(A, B) | f ≤ h implies h = f in map_{C}(A, B)}.

We shall call a restriction category C a lax restriction fibered category if it satisfies the following condition:

[M.1] For any objects A, B and any f ∈ map_{C}(A, B), there is a unique m_{f} ∈ map_{C}^{max}(A, B) such that f ≤ m_{f}.

A lax restriction fibered category is a restriction fibered category if it satisfies in addition

[M.2] For any objects A, B, C, f ∈ map_{C}^{max}(A, B), and g ∈ map_{C}^{max}(B, C), gf ∈ map_{C}^{max}(A, C).

Clearly, for any map f : A → B in a lax fibered restriction category C, m\overline{f} = 1_{A} since \overline{f} ≤ 1_{A} and 1_{A} ≤ g ⇔ g = 1_{A} in map_{C}(A, A). Since m_{1_{A}} = 1_{A}, 1_{A} ∈ map_{C}^{max}(A, A). Note that, for any maps f : A → B and g : B → C,

m_{gf} = m_{m_{g}m_{f}} ,

since f ≤ m_{f} and g ≤ m_{g} imply gf ≤ m_{g}m_{f} ≤ m_{m_{g}m_{f}} and both m_{gf} and m_{m_{g}m_{f}} are maximum above gf.

A restriction functor F : C → D between two lax restriction fibered categories is called a restriction fibered functor if it preserves maximal maps, namely, F (f) ∈ map_{D}^{max}(F (A), F (B)) for each f ∈ map_{C}^{max}(A, B). All lax restriction fibered categories and restriction fibered functors between them form a category, denoted by lrfCat_{0}. All restriction fibered categories and restriction fibered functors between them form a subcategory of lrfCat_{0}, denoted by rfCat_{0}.

STABLE MEET SEMILATTICE FIBRATIONS AND FREE RESTRICTION CATEGORIES 319

3.3. Lemma. For any stable meet semilattice fibration δ_{X} : X̃ → X, the restriction category S(δ_{X}) is a restriction fibered category. Proof. For any objects A, B,

map_{S(δ_{X})}(A, B) = {(f, σ) | f ∈ map_{X}(A, B) and σ ∈ δ_{X}^{−1}(A) with σ ≤ f^{∗}(⊤_{δ_{X}^{−1}(B)})}. and observe that (f, σ) ≤ (g, σ′) if and only if f = g and σ ≤ σ′. This implies that (f, f^{∗}(⊤_{δ_{X}^{−1}(B)})) is the unique maximal element above (f, σ). So [M.1] is satisfied.

For any (f, f^{∗}(⊤_{δ_{X}^{−1}(B)})) ∈ map_{S(δ_{X})}^{max}(A, B) and (g, g^{∗}(⊤_{δ_{X}^{−1}(C)})) ∈ map_{S(δ_{X})}^{max}(B, C), we have

(g, g^{∗}(⊤_{δ_{X}^{−1}(C)}))(f, f^{∗}(⊤_{δ_{X}^{−1}(B)})) = (gf, f^{∗}(⊤_{δ_{X}^{−1}(B)}) ∧ f^{∗}g^{∗}(⊤_{δ_{X}^{−1}(C)}))
= (gf, f^{∗}g^{∗}(⊤_{δ_{X}^{−1}(C)}))
= (gf, (gf)^{∗}(⊤_{δ_{X}^{−1}(C)}))
∈ map_{S(δ_{X})}^{max}(A, C).

Hence [M.2] is also satisfied. Thus, S(δ_{X}) is a restriction fibered category.

Let C be a lax restriction fibered category. We define C_{max} by following data: objects: the same as the objects of C, maps: for any objects A, B, map_{C_{max}}(A, B) = map_{C}^{max}(A, B), composition: gf = m_{m_{g}m_{f}} = m_{gf}. Then C_{max} is a category. Now, we define C̃_{max} to be the category given by objects: (A, e_{A}), where e_{A} is a restriction idempotent over A in C, maps: a map f from (A, e_{A}) to (B, e_{B}) is a map f ∈ map_{C}^{max}(A, B) such that e_{A} = \overline{e_{B}f}e_{A}, composition: the same as in C_{max}. Obviously, there is a forgetful functor ∂_{C_{max}} : C̃_{max} → C_{max}, which forgets restriction idempotents. 3.4. Lemma. For any restriction fibered category C, the forgetful functor ∂_{C_{max}} : C̃_{max} → C_{max} is a stable meet semilattice fibration.

Proof. As in Lemma 2.3, For any map f : A → B in C_{max} and any (B, e_{Y}) ∈ ∂_{C_{max}}^{−1}(B), f : (A, \overline{e_{B}f}) → (B, e_{B}) is the cartesian lifting of a map f : A → B at (B, e_{B}). Note that each fiber

∂_{C_{max}}^{−1}(A) = {(A, e_{A}) | e_{A} : A → A is a restriction idempotent on A}

is a meet semilattice with the order given by (A, e_{A}) ≤ (A, e′_{A}) ⇔ e_{A} = e′_{A}e_{A}, with the binary meet given by (A, e_{A}) ∧ (A, e′_{A}) = (A, e_{A}e′_{A}), and with (A, 1_{A}) as the top element. Obviously, for any map f : A → B, f^{∗} : ∂_{C_{max}}^{−1}(B) → ∂_{C_{max}}^{−1}(A), sending (B, e_{B}) to (A, \overline{e_{B}f}), is a stable meet semilattice homomorphism. Hence ∂_{C_{max}} : C̃_{max} → C_{max} is a stable meet semilattice fibration.

3.5. Lemma. For any restriction fibered category C, S(∂_{C_{max}}) ≅ C.

Proof. Define the functor E : S(∂_{C_{max}}) → C by sending (f, (A, e_{A})) : A → B to fe_{A} : A → B. It is easy to check that E is a restriction functor.

For any map f : A → B in C, by [M.1], there is a unique m_{f} ∈ map_{max}(A, B) such that f ≤ m_{f}. Then \overline{f} ≤ \overline{m_{f}} = m_{f}^{∗}(⊤_{∂_{Cmax}^{−1}(B)}) and so (m_{f}, (A, \overline{f})) : A → B is a map in S(∂_{C_{max}}).

Now, we define the functor F : C → S(∂_{C_{max}}) by sending f : A → B to (m_{f}, (A, \overline{f})) : A → B. Note that F (\overline{f}) = (m\overline{f}, (A, \overline{\overline{f}})) = (1_{A}, (A, \overline{f})) = \overline{(m\overline{f}, (A, \overline{f}))} = \overline{F (f)}. Then F is a restriction functor. For any map f : A → B in C, (EF)(f) = E(m_{f}, (A, \overline{f})) = m_{f} \overline{f} = f. Hence EF = 1_{C}.

On the other hand, for any map (f, (A, σ_{A})) : A → B in S(∂_{C_{max}}), σ_{A} ≤ f^{∗}(⊤_{∂_{Cmax}^{−1}(B)}) =

\overline{f}. Then σ_{A} = \overline{f}σ_{A} = \overline{fe_{A}} and so fe_{A} = f\overline{fe_{A}} which gives fe_{A} ≤ f. Since f ∈ map_{C}^{max}(A, B), we have m_{fe_{A}} = f. Hence (F E)(f, (A, e_{A})) = F (fe_{A}) = (m_{fe_{A}}, (A, \overline{fe_{A}})) = (f, (A, e_{A})), and therefore F E = 1_{S(∂_{Cmax})}. Thus, S(∂_{C_{max}}) ≅ C.

Lemmas 3.3 and 3.5 immediately yield the following proposition.

3.6. Proposition. C is a restriction fibered category if and only if there is a stable meet semilattice fibration δ_{X} : X̃ → X such that C ≅ S(δ_{X}).

Now let’s look at which restriction functors between restriction fibered categories are in the image of S.

3.7. Proposition. Let C and D be two restriction fibered categories and F : C → D a functor. Then F is of form S(G, H) for some map (G, H) in sFib if and only if F is a restriction fibered functor.

Proof. If F : C → D is a restriction fibered functor, then we have two functors F_{1} : C_{max} → D_{max} and F_{2} : C̃_{max} → D̃_{max}, where F_{1} is the restriction of F on the max maps and F_{2} is the functor introduced by F_{1} on the restriction idempotents. By Lemma 3.5, we have

C ≅ S(∂_{C_{max}}) and D ≅ S(∂_{D_{max}})

and a commutative diagram:

\xymatrix{C̃_{max} \ar[d]_{∂_{C}} \ar[r]^{F_{2}} & D̃_{max} \ar[d]^{∂_{D}} \\ C_{max} \ar[r]^{F_{1}} & D_{max}}

Now, it is easy to check that (F_{1}, F_{2}) : ∂_{C_{max}} → ∂_{C_{max}} is a map in sFib_{0} and S(F_{1}, F_{2}) ≅ F.

Conversely, if F ≅ S(G, F) for some map (G, H) : (δ_{X} : X̃ → X) → (δ_{Y} : Ỹ → Y) in sFib_{0}, then, for each (f, σ) ∈ max_{S(δ_{X})}(A, B), S(G, H)(f, σ) = (G(f), H(σ)) ∈ max_{S(δ_{Y})}(G(A), G(B)). Hence S(G, H) : S(δ_{X}) → S(δ_{Y}) is a restriction fibered functor.

By Propositions 3.6 and 3.7, we have immediately:

3.8. Theorem. S : sFib_{0} → rfCat_{0} is an equivalence of categories.

3.9. Monadicity of R and Comonadicity of S. Theorem 3.8 gives us a characterization of the image of S. A natural question, therefore, is: what does the image of R look like? The image of R was characterized in [6] as the restriction fibrations:

3.10. Definition. A stable meet semilattice fibration δ : D → C is called a restriction fibration if for each object E ∈ D, there is a map ε_{E} : δ(E) → δ(E) in C satisfying

[rF.1] ε_{⊤_{δ^{−1}(δ(E))}} = 1_{δ(E)},

[rF.2] ε_{E}^{∗}(⊤_{δ^{−1}(δ(E))}) = E, where ϑ_{ε_{E}} : ε_{E}^{∗}(⊤_{δ^{−1}(δ(E))}) → ⊤_{δ^{−1}(δ(E))} is the cartesian lifting of ε_{E} at ⊤_{δ^{−1}(δ(E))},

[rF.3] ε_{E}ε_{E′} = ε_{E∧E′},

[rF.4] ε_{F} f = fε_{f^{∗}(F)},

for all map f : δ(E) → Y in C, E′ ∈ δ^{−1}(δ(E)), and F ∈ δ^{−1}(Y).

A map from a restriction fibration (δ : D → C) to a restriction fibration (δ′ : D′ → C′) is given by a pair (F, F′), where F : C → C′ and F′ : D → D′ are functors such that

\xymatrix{D \ar[r]^{F′} \ar[d]_{δ} & D′ \ar[d]^{δ′} \\ C \ar[r]^{F} & C′}

commutes and for any map f : X → Y in C and any E ∈ δ^{−1}(X), W ∈ δ^{−1}(Y), the following conditions are satisfied:

[pR.1] F′(⊤_{δ^{−1}(X)}) = ⊤_{(δ′)^{−1}(F (X))},

[pR.2] F (ε_{E}) = ε_{F′(E)},

[pR.3] F′(f^{∗}(W)) = (F (f))^{∗}(F′(W)).

We have:

3.11. Theorem. If δ : D → C is a restriction fibration, then it is isomorphic to R(C), where C is the restriction category with the restriction \overline{f} = ε_{f^{∗}(⊤)}, called the restriction category induced by δ : D → C. Furthermore, a restriction fibration map (F, F′) : (δ : D → C) → (δ′ : D′ → C′) induces a restriction functor F : C → C′.

Sketch of Proof: First of all, it is easy to check that if δ : D → C is a restriction fibration then C is the restriction category with the restriction \overline{f} = ε_{f^{∗}(⊤)} and that for a given restriction category X the forgetful functor ∂_{X} : r(X) → X is a restriction fibration.

Let δ : D → C be a restriction fibration and C the restriction category with the restriction structure induced by δ. Then we have a restriction fibration map (1_{C}, 1_{δ}) : δ → ∂_{C}, where 1_{δ} : D → r(C) is given by sending f : D_{1} → D_{2} to δ(f) : (δ(D_{1}), ε_{E_{1}}) → (δ(D_{2}), ε_{E_{2}}). On the other hand, we have a restriction fibration map (1_{C}, G) : ∂_{C} → δ, where G : r(C) → D is given by sending f : (C_{1}, ε_{E_{1}}) → (C_{2}, ε_{E_{2}}) in r(C) to lift(f) = ϑ_{f,E_{2}} ∘ leq : E_{1} → E_{2}, here ϑ_{f,E_{2}} is the cartesian lifting of f at E_{2} and leq is the map E_{1} ≤ f^{∗}(E_{2}). Now it is routine to verify that (1_{C}, 1_{δ})(1_{C}, G) = 1_{∂_{C}} and (1_{C}, G)(1_{C}, 1_{δ}) = 1_{δ}. Hence δ ≅ ∂_{C}.

If (F, F′) : (δ : D → C) → (δ′ : D′ → C′) is a restriction fibration map, then, clearly, F : C → C′ is a restriction functor since F (\overline{f}) = F (ε_{f^{∗}(⊤_{δ^{−1}(Y )})}) = ε_{(F (f))^{∗}(⊤_{(δ′)^{−1}(F Y )})} = \overline{F (f)}. □

The above result can be used to show the monadicity and comonadicity of the adjunction

\xymatrix{rCat_{0} \ar[r]_{R}|{⊥} & sFib_{0} \ar[l]_{S}} . We have the very strong result:

3.12. Theorem. R is monadic and S is comonadic.

To prove that R is monadic, we use a technical lemma which states that a retraction of a restriction fibration in sFib_{0} is a restriction fibration.

3.13. Lemma. Let δ_{i} : D_{i} → C_{i} be stable meet semilattice fibrations such that (F, F′)(S, S′) = 1_{δ_{2}} for some maps (F, F′) : δ_{1} → δ_{2} and (S, S′) : δ_{2} → δ_{1} in sFib_{0}. If δ_{1} is a restriction fibration, then so is δ_{2}.

Proof. Suppose that δ_{1} is the restriction fibration with the map ε_{U} for each object U in δ_{1}^{−1}(O). It is clear that each fiber δ_{2}^{−1}(X) is a stable meet semilattice in which E_{1} ≤ E_{2} if and only if there is a map from E_{1} to E_{2}. In order to prove that δ_{2} is a restriction fibration with the map ε′_{E} = F (ε_{S′(E)}), it suffices to check the four conditions [rF.1], [rF.2], [rF.3], and [rF.4]. For any map f : X → Y in C_{2}, any E, E′ ∈ δ_{2}^{−1}(X) and any I ∈ δ_{2}^{−1}(Y), we have:

[rF.1]

ε′_{⊤_{δ{−1 \atop 2}(X)}} = F (ε_{S′(⊤_{δ{−1 \atop 2}(X)})})
= F (ε_{⊤_{δ{−1 \atop 2}(T (X))}}) (by [sfM.1])
= F (1_{T (X)}) (by [rF.1])
= 1_{F T (X)}
= 1_{X}.

[rF.2]

ε_{E}^{′∗}(⊤_{δ_{2}^{−1}(X)}) = (F (ε_{S′(E)}))^{∗}(⊤_{δ_{2}^{−1}(X)})
= (F (ε_{S′(E)}))^{∗}(F′⊤_{δ_{1}^{−1}(SX)}) (by [sfM.1])
= F′(ε_{S′(E)}^{∗})(⊤_{δ_{1}^{−1}(SX)}) (by [sfM.3])
= F′(S′(E)) (by [rF.2])
= E.

[rF.3] ε′_{E}e′_{E′} = F (ε_{S′(E)})F (ε_{S′(E′)}) = F (ε_{S′(E)}ε_{S′(E′)}) = F (ε_{S′(E)∧S′(E′)}) = F (ε_{S′(E∧E′)}) = ε′_{E∧E′}.

[rF.4]

ε′_{I}f = F (ε_{S′(I)})f
= F (ε_{S′(I)}T (f))
= F (T (f)ε_{T (f)^{∗}(S′(I))}) (by [rF.4])
= fF (ε_{T (f)^{∗}(S′(I))})
= fF (ε_{S′(f^{∗}(I))}) (by [sfM.3])
= fε′_{f^{∗}(I)}.

Proof of Theorem 3.12. To show that R is monadic, we need to prove that R reflects isomorphisms and that rCat_{0} has coequalizers of reflexive R-split coequalizer pairs and R preserves them. Let F : X → Y be a restriction functor such that R(F) : R(X) → R(Y) is an isomorphism in sFib_{0}. Then there is a map (N, N′) : R(Y) → R(X) such that (N, N′)R(F) = 1_{R(X)} and R(F)(N, N′) = 1_{R(Y)}. Thus, NF = 1_{X} and F N = 1_{Y}. For any map f : A → B in Y, we have N(\overline{f}) = N(\overline{F (N(f))}) = N(F (\overline{(N(f))})) = \overline{N(f)}. Hence N is a restriction functor and therefore N is an isomorphism in rCat_{0}. Thus, R reflects isomorphisms. By Corollary 2.4 in [3], rCat_{0} is cocomplete. Suppose that F, G : X → Y is a reflexive R-split coequalizer pair and that \xymatrix{∂_{X} \ar[r]^{(F,r(F))} \ar[r]_{(G,r(G))} & ∂_{Y} \ar[r]^{(U,U′)} & δ_{U}} is the split coequal-

izer diagram in sFib_{0}. Let \xymatrix{X \ar[r]^{F} \ar[r]_{G} & Y \ar[r]^{C} & C} be a coequalizer diagram in rCat_{0}. Then

monadicity of R amounts to checking that \xymatrix{∂_{X} \ar[r]^{(F,r(F))} \ar[r]_{(G,r(G))} & ∂_{Y} \ar[r]^{(C,r(C))} & ∂_{C}} is a coequalizer diagram in

sFib_{0}. Since δ_{U} is a retraction of a restriction fibration ∂_{Y}, by Lemma 3.13 δ_{U} is a restriction

fibration and so δ_{U} ≅ ∂_{Z} for some restriction category Z. Note that \xymatrix{X \ar[r]^{F} \ar[r]_{G} & Y \ar[r]^{U} & Z} is

a split coequalizer diagram in Cat_{0}. Since the forgetful functor rCat_{0} → Cat_{0} is monadic (Theorem 2.28, [3]), C ≅ Z, as desired.

On the other hand, for the comonadicity of S, we first note that S reflects isomorphisms. For any map (F, F′) : δ_{X} → δ_{Y} in sFib_{0} such that S(F, F′) : S(δ_{X}) → S(δ_{Y}) is an isomorphism in rCat_{0}, there is a restriction functor M : S(δ_{Y}) → S(δ_{X}) such that MS(F, F′) = 1_{S(δ_{X})} and S(F, F′)M = 1_{S(δ_{Y})}. Clearly, M preserves max maps so that M is a map in rfCat_{0}. Hence (F, F′) is an isomorphism in sFib_{0} since S : sFib_{0} → rfCat_{0} is an equivalence of categories.

For any maps (F, F′), (G, G′) : (δ_{X} : X̃ → X) → (δ_{Y} : Ỹ → Y) in sFib_{0}, the equalizer of (F, F′) and (G, G′) is given by (I, I′) : (δ_{E} : Ẽ → E) → (δ_{X} : X̃ → X), where I′ : Ẽ → X̃ and I : E → X are equalizers of F′, G′ : X̃ → Ỹ and F, G : X → Y in Cat_{0}, respectively. So sFib_{0} has equalizers.

Suppose that (F, F′), (G, G′) : δ_{X} → δ_{Y} is a reflexive S-split equalizer pair in sFib_{0}

and that \xymatrix{M \ar@{^{(}->}[r]^{M} & S(δ_{X}) \ar[r]^{S(F,F′)} \ar[r]_{S(G,G′)} & S(δ_{Y})} is the split equalizer diagram in rCat_{0}. Then M

a restriction fibered category and M preserves max maps so that the last equalizer di-

agram is an equalizer diagram in rfCat_{0}. Let \xymatrix{δ_{E} \ar[r]^{(E,E′)} & δ_{X} \ar[r]^{(F,F′)} \ar[r]_{(G,G′)} & δ_{Y}} be an equalizer dia-

gram in sFib_{0}. Then \xymatrix{S(δ_{E}) \ar[r]^{S(E,E′)} & S(δ_{X}) \ar[r]^{S(F,F′)} \ar[r]_{S(G,G′)} & S(δ_{Y})} is an equalizer diagram in rfCat_{0} since

S : sFib_{0} → rfCat_{0} is an equivalence of categories. Hence M ≅ S(δ_{E}) and therefore

\xymatrix{S(δ_{E}) \ar[r]^{S(E,E′)} & S(δ_{X}) \ar[r]^{S(F,F′)} \ar[r]_{S(G,G′)} & S(δ_{Y})} is an equalizer diagram in rCat_{0}.

3.14. Lax Restriction Fibered Categories. Our next aim is to characterize lax restriction fibered categories. As shown in Subsection 3.1, restriction fibered categories are essentially the same as the stable meet semilattice fibrations. We now show that the lax restriction fibered categories have an analogous description via lax fibrations. In particular, we show something even more general (whose ramifications we still do not fully understand) that a lax restriction functor into the dual of stable meet semilattices can be used as the basis of a construction analogous to S. This construction in particular generates all the lax fibered restriction categories.

STABLE MEET SEMILATTICE FIBRATIONS AND FREE RESTRICTION CATEGORIES 325

A graph map between two restriction categories is called a lax restriction semi-functor in case: [lr.1] \overline{F (x)} ≤ F (\overline{x}), [lr.2] F (y)F (x) = F (yx)\overline{F (y)F (x)}. [lr.3] x ≤ y ⇒ F (x) ≤ F (y) A lax restriction functor also requires that 1_{F (A)} ≤ F (1_{A}), and this forces F (1_{A}) = 1_{F (A)} as we now see: 3.15. Lemma.

(i) If F is a lax restriction semi-functor then F preserves restriction idempotents, that is \overline{F (\overline{f})} = F (\overline{f}).

(ii) The condition [lr.3] can be replaced by

[lr.3a] F (y\overline{x}) = F (y)F (\overline{x}). (iii) If a lax restriction semi-functor is a lax functor, that is 1_{F (A)} ≤ F (1_{A}), then F (1_{A}) =

1_{F (A)}. Proof.

(i) \overline{F (\overline{x})} = F (\overline{x}) follows from [lr.1] as \overline{F (\overline{x})} ≤ F (\overline{x}) so that \overline{F (\overline{x})} = F (\overline{x})\overline{F (\overline{x})} = F (\overline{x}). (ii) Suppose that [lr.3] holds. Then F (y\overline{x}) ≤ F (y) implies F (y\overline{x}) = F (y)\overline{F (y\overline{x})} ≤

F (y)F (\overline{y\overline{x}}) ≤ F (y)F (\overline{x}). Furthermore, [lr.2] gives F (y)F (\overline{x}) ≤ F (y\overline{x}). So that F (y)F (\overline{x}) = F (y\overline{x}) and [lr.3a] follows. Conversely, assume [lr.3a]. Then x ≤ y gives x = y\overline{x} and so F (x) = F (x)\overline{F (x)} = F (y\overline{x})\overline{F (x)} = F (y)F (\overline{x})\overline{F (x)} = F (y)\overline{F (x)}. Hence F (x) ≤ F (y).

(iii) If 1 ≤ F (1) then F is normal since F (1) = \overline{F (1)} ≤ 1.

The category of stable meet semilattices opposite, StabMSLat_{0}^{op}, is a restriction category. The (co)restriction of a map f : X → Y in StabMSLat_{0} is given by setting \overline{f}(y) = f(⊤_{X}) ∧ y.

Given a lax restriction functor F : C → StabMSLat_{0}^{op}, we may construct L(F) as follows:

objects: A ∈ obC,

maps: (f, e) : A → B, where f : A → B is a map in C and e ∈ F (A) with e ≤ F (f)(⊤_{F (B)}),

composition: For any map (f, e) : A → B and (g, e′) : B → C, (g, e′)(f, e) = (gf, e ∧ F (f)(e′)),

identities: 1_{A} = (1_{A}, ⊤_{F (A)}),

restriction: \overline{(f, e)} = (\overline{f}, e).

3.16. Lemma. L(F) is a restriction category.

Proof. Since ⊤_{F (A)} = F (1_{A})(⊤_{F (A)}), the identities are well-defined. If e ≤ F (f)(⊤_{F (B)}) and e′ ≤ F (g)(⊤_{F (C)}), then

e ∧ F (f)(e′) ≤ F (f)(F (g)(⊤_{F (C)})) ≤ F (gf)(⊤_{F (C)})

and so the composition is well-defined too.

For any map (f, e) : A → B in L(F), we must show that \overline{(f, e)} = (\overline{f}, e) is well-defined. That is we need e ≤ F (\overline{f})(⊤_{F (A)}). It suffices to show that F (\overline{f})(e) = e (which will be useful later):

e ≤ F (f)(⊤_{F (B)})
= F (f\overline{f})(⊤_{F (B)})
= \overline{F (\overline{f})}(F (f)(⊤_{F (B)})) (by [lr.3a])
= F (\overline{f})(⊤_{F (A)}) ∧ F (f)(⊤_{F (B)})
≤ F (\overline{f})(⊤_{F (A)})

so e = F (\overline{f})(⊤_{F (A)}) ∧ e = F (\overline{f})(e).

Note that

(1_{B}, ⊤_{F (B)})(f, e) = (f, e ∧ F (f)(⊤_{F (B)})) = (f, e)

and

(f, e)(1_{A}, ⊤_{F (A)}) = (f, ⊤_{F (A)} ∧ F (1_{A})(e)) = (f, F (1_{A})(e)) = (f, e).

Then the identity laws hold.

For any maps (f, e) : A → B, (g, e′) : B → C, and (h, e′′) : C → D in L(F), Since F (f)F (g) ≤ F (gf), we have F (f)F (g)(e′′) = \overline{F (f)F (g)}F (gf)(e′′) = F (f)F (g)(⊤_{F (C)}) ∧ F (gf)(e′′). Then

((h, e′′)(g, e′))(f, e) = (hg, e′ ∧ F (g)(e′′))(f, e)
= ((hg)f, e ∧ F (f)(e′) ∧ F (f)F (g)(e′′))
= (h(gf), e ∧ F (f)(e′) ∧ F (f)F (g)(⊤_{F (C)}) ∧ F (gf)(e′′))
= (h(gf), e ∧ F (f)(e′) ∧ F (gf)(e′′))
= (h, e′′)(gf, e ∧ F (f)(e′))
= (h, e′′)((g, e′)(f, e))

and so the associative law holds. Thus, L(F) is a category.

To prove that L(F) is restriction category with \overline{(f, e)} = (\overline{f}, e), we need to check the four restriction axioms.

[R.1] (f, e)\overline{(f, e)} = (f, e)(\overline{f}, e) = (f, e ∧ F (\overline{f})(e)) = (f, e).

[R.2] \overline{(f_{1}, e_{1})} \overline{(f_{2}, e_{2})} = (\overline{f_{1}}, e_{1})(\overline{f_{2}}, e_{2}) = (\overline{f_{1}} \overline{f_{2}}, e_{2} ∧ F (\overline{f_{2}})e_{1}) = (\overline{f_{2}} \overline{f_{1}}, e_{2} ∧ \overline{F (\overline{f_{2}})}e_{1}) = (\overline{f_{2}} \overline{f_{1}}, e_{2} ∧ F (\overline{f_{2}})(⊤) ∧ e_{1}) = (1, e_{2} ∧ e_{1}) = \overline{(f_{2}, e_{2})} \overline{(f_{1}, e_{1})}.

[R.3] \overline{(g, e′)\overline{(f, e)}} = \overline{(g, e′)(\overline{f}, e)} = \overline{(g\overline{f}, e ∧ F (\overline{f})(e′))} = (\overline{g\overline{f}}, e ∧ F (\overline{f})(e′)) = (\overline{g}\overline{f}, e ∧ e′) =

\overline{(g, e′)} \overline{(f, e)}.

[R.4]

\overline{(g, e′)}(f, e) = (\overline{g}, e′)(f, e)
= (\overline{g}f, e ∧ F (f)(e′))
= (f\overline{gf}, e ∧ F (f)(e′) ∧ F (\overline{g})(F (\overline{f})(e))) (since F (\overline{f})(e) = e)
= (f\overline{gf}, e ∧ F (f)(e′) ∧ F (\overline{f} \overline{gf})(e))
= (f\overline{gf}, e ∧ F (f)(e′) ∧ F (\overline{gf})(F (\overline{f})(e)))
= ((f\overline{gf}, e ∧ F (f)(e′) ∧ F (\overline{gf})(e))
= (f, e)(\overline{gf}, e ∧ F (f)(e′))
= (f, e)\overline{(g, e′)(f, e)}.

Hence L(F) is restriction category with \overline{(f, e)} = (\overline{f}, e).

3.17. Remarks.

1. Given a lax restriction functor F : C → StabMSLat_{0}^{op}, we obtain an obvious forgetful restriction functor F̃ : L(F) → C which sends (f, e) : A → B to f : A → B. This functor is induced by a congruence on L(F) : (f, e) ∼ (g, e′) ⇔ f = g, which has the property that congruent maps are “compatible”. See Subsection 3.23 below for the link to unitary restriction categories.

2. Given a lax restriction semi-functor F : X → Y, we can construct a lax restriction functor e(F) : X → im(F), sending f : X → Y to F (1_{Y})F (f) : X → Y and a faithful restriction semi-functor m(F) : im(F) → Y, sending g : X → Y to g : F (X) → F (Y):

[figure: X; F; e(F); F̂; ≤; Y; im(F); m(F)]

where F̂ = m(F) ∘ e(F) ≤ F as m(F)(e(F)(f)) = F (1_{Y})F (f) and im(F) is the following category:

objects: X ∈ obX,

maps: maps from X to Y are given by maps from F (X) to F (Y) in Y which can be written in the form

F (1_{Y})F (f_{1}) ⋯ F (f_{n}) ∏_{i} \overline{F (1)F (g_{m_{i}i}) ⋯ F (g_{1i})},

where g_{1i} ⋯ g_{m_{i}i} : X → Z_{i} and f_{1} ⋯ f_{n} : X → Y are maps in X,

identities: 1_{X} = F (1_{X}),

composition and restriction: same as in Y.

The semi-functor m(F) can then be further factorized as a restriction functor to K_{r}(Y) followed by the couniversal (idempotent forgetting) restriction semi-functor K_{r}(Y) → Y. If Y is split, which is the case when Y = StabMSLat_{0}^{op}, then this gives a lax restriction functor to Y itself. Thus, this allows the construction above to be performed on any lax restriction semi-functor with F = F̂.

The remainder of this section, will be concerned with lax restriction functors F : C → StabMSLat_{0}^{op} where C is a mere category (so we regard C as being a restriction category in which all maps are total). In this case, L(F) is lax restriction fibered category with \overline{(f, e)} = (1, e) and with m_{(f,e)} = (f, F (f)(⊤_{F (B)})) for any map (f, e) : A → B. As C is a mere category, we do not need the condition [lr.3]. This means such a lax functor may be described more concretely as follows:

[lax.1] For each object A in C, F (1_{A}) = 1_{F (A)},

[lax.2] For any maps f : A → B and g : B → C, and element c ∈ F (C), F (f)(F (g)(⊤_{F (C)})) ∧ F (gf)(c) = F (f)F (g)(c).

Notice that the condition \overline{F (x)} ≤ F (\overline{x}) reduces to \overline{F (x)} ≤ 1, which is always true as all x are total. The condition [lr.2] translates straight into the condition [lax.2]. Notice also we may equivalently express [lax.2] as:

[lax.2a] For any maps f : A → B and g : B → C, and elements c ∈ F (C) and b ∈ F (B) with b ≤ F (g)(⊤_{F (C)}), we have F (f)(b) ∧ F (gf)(c) = F (f)(b) ∧ F (f)F (g)(c).

We shall use this form in the proofs below.

A transformation between two lax functors F : X → StabMSLat_{0}^{op} and G : Y → StabMSLat_{0}^{op} is a pair (W, ω), where W : X → Y is a functor and ω : GW → F is a transformation such that each ω_{A} preserves the top element: ω_{A}(⊤_{F (A)}) = ⊤_{GW (A)}.

All lax functors to StabMSLat_{0}^{op} and transformations between them form a category, denoted by laxFun_{0}.

Let F : C → StabMSLat_{0}^{op} and G : D → StabMSLat_{0}^{op} be two lax functors and (W, ω) : F → G is a map in laxFun_{0}. Then we define a restriction fibered function L(W, ω) : L(F) → L(G) given by taking (f, e) : A → B to (W (f), ω_{A}(e)) : W (A) → W (B), here, L(W, ω) preserving identities follows from each ω_{A} preserving the top element and L(W, ω) preserving composition follows from the naturality of ω. Clearly, L(W, ω) preserves restriction and maximal maps. So, we have a functor L : laxFun_{0} → lrfCat_{0}.

Let C be a lax restriction fibered category. Then we have a category C_{max} and a functor M : C → C_{max} given by taking f : A → B to m_{f} : A → B. On the other hand, M : C → C_{max} gives arise to, as the next lemma will show, a lax functor M(C) : C_{max} → StabMSLat_{0}^{op} given by sending each f : A → B in C_{max} to f^{∗} : E(B) → E(A); e ↦ \overline{ef} in StabMSLat_{0} (where E(B) and E(A) are the meet semilattice of all restriction idempotents over B and A respectively).

3.18. Lemma. For any lax restriction fibered category C, M(C) : C_{max} → StabMSLat_{0}^{op}, as above, is a lax functor.

Proof. We need to check the conditions [lax.1] and [lax.2].

[lax.1] Clearly, M(C)(1_{A}) = 1_{E(A)} = 1_{M(C)(A)}.

[lax.2] For any maps f : A → B, g : B → C in C_{max}, and any restriction idempotent e′′ on C,we have: M(C)(f)(M(C)(g)(⊤)) ∧ M(C)(gf)(e′′) = \overline{\overline{g}f} \overline{e′′m_{gf}} = \overline{e′′m_{gf}} \overline{gf} = \overline{e′′m_{gf} \overline{gf}} = \overline{e′′gf} since gf ≤ m_{gf}. Finally, \overline{e′′gf} = \overline{\overline{e′′g}f} = M(C)(f)(M(C)(g)(e′′)) so that [lax.2] follows.

Hence M(C) : C_{max} → StabMSLat_{0}^{op} is a lax functor.

If F : C → D is a restriction fibered functor, then we have a map (F_{M}ω^{F}) : M(C) → M(D) in laxFun_{0}, where ω_{A}^{F} : E(A) → E(F (A)) is given by ω_{A}^{F}(e) = F (e). So, we have a functor M : lrfCat → laxFun_{0}, which sends F : C → D to (F_{M}, ω^{F}) : M(C) → M(D).

3.19. Lemma. For any lax restriction fibered category C, L(M(C)) ≅ C.

Proof. L(M(C)) is the category with the same objects as C and with maps (f, e) : A → B, where f : A → B is a maximal map in C and e is an idempotent over A such that e ≤ \overline{f}. Define functors S : L(M(C)) → C by S(f, e) = fe and T : C → L(M(C)) by T (f) = (m_{f}, \overline{f}). Clearly,

ST (f) = S(m_{f}, \overline{f}) = m_{f} \overline{f} = f

and

T S(f, e) = T (fe) = (m_{fe}, \overline{fe}) = (f, \overline{f}e) = (f, e).

Hence L(M(C)) ≅ C.

3.20. Lemma. For a given lax functor F : C → StabMSLat_{0}^{op}, M(L(F)) ≅ F.

Proof. For a given lax functor F : C → StabMSLat_{0}^{op}, L(F) is the lax restriction fibered category with the same objects as C, with maps (f, e) : A → B, e ∈ F (A), with the maximal maps: m_{(f,e)} = (f, ⊤_{F (A)}), and with the restriction given by \overline{(f, e)} = (1_{A}, e). (L(F))_{max} is the category with the same objects as C, with the maps (f, ⊤_{F (A)}) : A → B and with the composition (g, ⊤_{F (B)})(f, ⊤_{F (A)}) = (gf, ⊤_{F (A)}). Clearly, (L(F))_{max} ≅ C and M(L(F)) : (L(F))_{max} → StabMSLat_{0}^{op} is the lax functor given by sending (f, ⊤_{F (A)}) : A → B to (f, ⊤_{F (A)})^{∗} : E(B) → E(A) in StabMSLat_{0}, where E(B) = {(1_{B}, e) | e ∈ F (B)\} and (f, ⊤_{F (A)})^{∗}(1_{B}, e) = \overline{(1_{B}, e)(f, ⊤_{F (A)})} = \overline{(f, ⊤_{F (A)} ∧ F (f)e)} = (1_{A}, F (f)e). Hence M(L(F)) ≅ F with the obvious isomorphisms.

Combining Lemmas 3.19 and 3.20 yields immediately:

3.21. Theorem. L : laxFun_{0} → lrfCat_{0} is an equivalence of categories.

3.22. Remark. Since each stable meet semilattice fibration gives rise to a lax functor by the Grothendieck construction, we have the following commutative diagram:

\xymatrix{sFib_{0} \ar[r]^{S} \ar@{^{(}->}[d] & rfCat_{0} \ar@{^{(}->}[d] \\ _{laxFun_{0}} \ar[r]^{L} & _{lrfCat_{0}}}

3.23. Unitary Restriction Categories. We now show how this whole development can be approached from a completely different perspective, as was outlined in the introduction.

A restriction category is unitary (or proper) ^{1} if for any maps f, g and any restriction idempotent e, fe = ge and \overline{f} = \overline{g} imply f = g. All unitary restriction categories and restriction functors between them form a subcategory of rCat_{0}, denoted by urCat_{0}. Our first observation is:

1John Fountain pointed out to the first author that historically the correct term is actually “proper”

as the unitary condition (as originally defined) was not the one given above but xy = x ⇒ y = y^{2}. For inverse categories, this is equivalent to our notion, but for restriction categories (and Fountain’s left ample semigroups) it is not.

3.24. Proposition. Lax restriction fibered categories are unitary.

Proof. Let C be a lax restriction fibered category and suppose that f, g are two maps in C such that \overline{f} = \overline{g} and fe = ge for some restriction idempotent e. Now fe ≤ f ≤ m_{f} and ge ≤ g ≤ m_{g}; so since fe = ge we have m_{f} = m_{g}, but this means f = m_{f} \overline{f} = m_{g}\overline{g} = g.

Not only is a restriction category a partial order enriched category with the order ≤ on each hom-set given by

f ≤ g ⇔ f = g\overline{f}

but also a compatibility relation ⌣ enriched category, where ⌣ is given by

f ⌣ g ⇔ g\overline{f} = f\overline{g}.

A set S of maps is compatible if for any s, s′ ∈ S, s ⌣ s′. Clearly, each subset of a compatible set is also compatible.

An equivalence relation ∼ on the class of maps in a restriction category X is a restriction congruence if for any maps x : X → A, f : A → B, g : A → B, y : B → Y in X,

(i) f ∼ g ⇔ yfx ∼ ygx,

(ii) f ∼ g ⇒ \overline{f} ∼ \overline{g}.

A unitary restriction category can be characterized by how the relation ⌣ behaves:

3.25. Lemma. Let X be a restriction category then the following are equivalent:

(i) X is unitary.

(ii) f ⌣ g if and only if there is a restriction idempotent e such that fe = ge.

(iii) ⌣ is a restriction congruence on X.

Proof. (i) ⇒ (ii) If f ⌣ g, then f\overline{g} = g\overline{f} and so fe = ge with e = \overline{f}\overline{g}.

Conversely, if fe = ge for some restriction idempotent e, then f\overline{g}\overline{f}\overline{g}e = g\overline{f} \overline{f}\overline{g}e. Since \overline{f\overline{g}} = \overline{f}\overline{g} = \overline{g\overline{f}} and X is unitary, we have f\overline{g} = g\overline{f}. Hence f ⌣ g.

(ii) ⇒ (iii) ¿From (ii) it is easy to see that ⌣ is an equivalence relation on parallel maps. Reflexivity and symmetry are immediate while transitivity follows by composing the mediating restrictions. The additional two requirement of a congruence are, in fact, always true for the compatibility relation of any restriction category. In a unitary restriction category this can proved more simply. If f ⌣ g, then there is a mediating restriction idempotent e such that fe = ge and so xfey = xgey, which implies that xfy\overline{ey} = xgy\overline{ey} whence, by (ii), xfy ⌣ xgy. On the other hand, f ⌣ g ⇒ f\overline{g} = g\overline{f} ⇒ \overline{f} \overline{\overline{g}} = \overline{g} \overline{\overline{f}} ⇒ \overline{f} ⌣ \overline{g}. Thus, ⌣ is a restriction congruence on X.

(iii) ⇒ (i) Let f, g be maps in X such that fe = ge and \overline{f} = \overline{g} for some restriction idempotent e. Then f ⌣ fe = ge ⌣ g and so, by (iii), f ⌣ g. Hence f\overline{g} = g\overline{f} and therefore f = f\overline{f} = f\overline{g} = g\overline{f} = g\overline{g} = g. Thus, X is unitary, as desired.

This result means that for each unitary restriction category X there is a base functor B : X → X/ ⌣. A map f : X → Y in a restriction category is a restricted isomorphism in case there is a (necessarily unique) f^{(−1)} : Y → X such that \overline{f} = f^{(−1)}f and \overline{f^{(−1)}} = ff^{(−1)} (see [3]). As restriction idempotents are exactly the endo-maps which are compatible with the identity map we immediately have:

3.26. Corollary.

(i) In a unitary restriction category, if f : X → Y is a restricted isomorphism then B(f) is an isomorphism.

(ii) Any unitary inverse category X has X/ ⌣ a groupoid.

An inverse category is a restriction category in which all maps are restricted isomorphisms (see [3]). This direct relation between unitary inverse monoids and groups is one reason why this theory has particular importance in semigroup theory.

We shall say a unitary restriction category is bounded in case each equivalence class of compatible maps has a maximal element (called the bound). A unitary restriction category is said to be strictly bounded in case the composite of any two bounds is itself a bound. Clearly any bounded unitary restriction category satisfies [M.1] and, as we have seen above, any lax restriction fibered category is unitary so the two notions are the same. Similarly, to say a unitary restriction category is strictly bounded is precisely to say [M.2] is satisfied:

3.27. Corollary.

(i) A bounded unitary restriction category is precisely a lax restriction fibered category.

(ii) A strictly bounded unitary restriction category is precisely a restriction fibered category.

This therefore gives an alternative, and perhaps more gentle, nomenclature for these categories.

Clearly any restriction subcategory of a unitary restriction category is necessarily unitary. Our purpose now is to prove that every unitary restriction category occurs as a subcategory of a bounded unitary restriction category. This result allows us to replace the base of the fibration X_{max} by X/ ⌣ in the unitary case. However, we still need to construct for any unitary category a lax fibered or strictly bounded unitary extension. To bridge this gap we need to briefly introduce join restriction categories:

3.28. Definition. A restriction category C is called a join restriction category if for each pair of objects A and B and each compatible subset S ⊆ C(A, B) there is ⋁_{s∈S} s : A → B such that

• ⋁_{s∈S} s is the join with respect to the partial order ≤ on C(A, B),

• \overline{⋁_{s∈S} s} = ⋁_{s∈S} \overline{s}, and for any f ∈ C(B, Y) and g ∈ C(X, A),

• f(⋁_{s∈S} s) = ⋁_{s∈S}(fs),

STABLE MEET SEMILATTICE FIBRATIONS AND FREE RESTRICTION CATEGORIES 333

• (⋁_{s∈S} s)g = ⋁_{s∈S}(sg).

For any subset S of a poset (X, ≤), write

↓S = {x ∈ X | ∃s ∈ S such that x ≤ s}.

We say a subset S of a poset (X, ≤) is down closed if ↓S = S. The operator ↓( ) is a closure operator.

Given any restriction category X, we construct a category X̂ with objects: X ∈ X; maps: S : A → B are given by nonempty, down closed, and compatible sets S ⊆ X(A, B); identities: 1_{A} =↓\{1_{A}\} = \{e|e = \overline{e} : A → A in X\}; composition: for any maps S : A → B and T : B → C in X̂, T S = {ts|s ∈ S, t ∈ T }; restriction: \overline{S} = \{\overline{s}|s ∈ S\}; join: ⋁_{i∈Γ} S_{i} = ⋃_{i∈Γ} S_{i}, where {S_{i}}_{i∈Γ} is a compatible set in X̂. For any maps S : A → B and T : B → C in X̂, T S = {ts|s ∈ S, t ∈ T } is down closed as if f ≤ ts then f = t · s\overline{f} but s\overline{f} ∈ S, t ∈ T. To show the join in X̂ is well-defined, the following observation is crucial: 3.29. Lemma. For any map S, T : A → B in X̂, S ⌣ T in X̂ if and only if s ⌣ t in X for all s ∈ S and t ∈ T. Proof. If S ⌣ T in X̂, then S\overline{T} = T \overline{S}. For any s ∈ S and t ∈ T, since s\overline{t} ∈ S\overline{T} = T \overline{S}, there are s′ ∈ S, t′ ∈ T such that s\overline{t} ≤ t′\overline{s′}. Hence, by using t ⌣ t′, that is t\overline{t′} = t′\overline{t},

s\overline{t} = t′\overline{s′}\overline{s\overline{t}} = t′\overline{s′}\overline{s}\overline{t} = t′\overline{t} \overline{s′}\overline{s} = t\overline{t′} \overline{s′}\overline{s} = t\overline{s}(\overline{t′} \overline{s′}) ≤ t\overline{s}.

By symmetry, we have t\overline{s} ≤ s\overline{t}, t\overline{s} = s\overline{t} and s ⌣ t.

Conversely, if for any s ∈ S, t ∈ T, s ⌣ t, then s\overline{t} = \overline{s}t and so

S\overline{T} = \{s\overline{t} | s ∈ S, t ∈ T \} = \{t\overline{s} | s ∈ S, t ∈ T \} = T \overline{S}.

Thus, S ⌣ T in X̂, as desired.

It now is straightforward to verify that X̂ is indeed a join restriction category and that X can be embedded into X̂ with the faithful functor I : X → X̂ given by sending f : A → B to ↓{f} : A → B. Moreover, when X is a unitary restriction category X̂ is lax fibered as shown in the following proposition.

3.30. Proposition. If X is a unitary restriction category, then X̂ is a bounded unitary restriction category and X̂_{max} = X/ ⌣

Proof. For any map S : A → B in X̂, write

M_{S} = {down closed and compatible X ⊆ X(A, B) with S ⊆ X}.

If X_{1}, X_{2} ∈ M_{S}, then, for each x_{1} ∈ X_{1}, x_{2} ∈ X_{2}, x_{1} ⌣ s and x_{2} ⌣ s for some s ∈ S and so x_{1} ⌣ x_{2}. Hence X_{1} ⌣ X_{2} and therefore M_{S} is compatible in X̂. Thus ⋁_{X∈M_{S}} X = ⋃_{X∈M_{S}} X exists in X̂. Now it is routine to check that m_{S} = ⋃_{X∈M_{S}} X. So [M.1] is satisfied. Hence X̂ is a bounded unitary restriction category.

For the last observation a maximal map in X̂ is a maximal compatible set which in a unitary restriction category is a ⌣-equivalence class.

3.31. Theorem. A restriction category is unitary if and only if it is a restriction subcategory of a lax restriction fibered category (or a bounded unitary category).

Proof.

(⇐) By Proposition 3.24.

(⇒) Let X be a unitary restriction category. Since the functor I : X → X̂, given by sending f : A → B to ↓{f} : A → B, is faithful, X is a subcategory of X̂. But X̂ is lax fibered by Proposition 3.30. Hence X is a restriction subcategory of a lax restriction fibered category X̂.

4. Free Restriction Categories

In this section, we return to the consider the construction of a free restriction category from a category. We start by filling in a missing step: namely generating a free stable semilattice fibration from a category. The section ends with an explicit description of the free restriction category on a graph.

4.1. The Free Stable Meet Semilattice Fibration on a Category. The objective of this subsection is to provide a left adjoint to U_{f} : sFib_{0} → Cat_{0}, the base functor, which sends (F, F′) : (δ_{X} : X̃ → X) → (δ_{Y} : Ỹ → Y) to F : X → Y.

Each category gives rise to a canonical stable meet semilattice fibration. In order to see this, we first recall Cockett-Lack’s closure operator ⇓( ). Let C be a category, K = {f_{i} : X → Z_{i} | i ∈ I} a set of maps with domain X, and g : Y → X a map. Then we write Kg for the set {f_{i}g | i ∈ I}, and ⇓(K) for the set {f : X → Z | uf = f_{i} for some i ∈ I and some u : Z → Z_{i}}. Suppose that K and L are sets of maps with domain X. Clearly, if K ⊆ L then ⇓(K) ⊆ ⇓(L).

4.2. Lemma. For any category, ⇓( ) is a Kuratowski closure operator on the maps with domain X. Namely, if K, K_{1}, and K_{2} are sets of maps with domain X, then

⇓(∅) = ∅, ⇓(K_{1} ∪ K_{2}) = ⇓(K_{1}) ∪ ⇓(K_{2}), K ⊆ ⇓(K), ⇓(⇓(K)) = ⇓(K).

Proof. See [3].

To form the category s(C) below, we need:

4.3. Lemma. If ⇓(K) = ⇓(K′), then ⇓(Kf) = ⇓(K′f).

Proof. If x ∈ ⇓(Kf), then ux = kf for some u and k ∈ K. As certainly k ∈ ⇓(K) there is a v such that vk ∈ K′ but then vux = vkf so that x ∈ ⇓(K′f). Hence ⇓(Kf) ⊆ ⇓(K′f). Similarly, ⇓(K′f) ⊆ ⇓(Kf). Therefore, ⇓(Kf) = ⇓(K′f).

Remark. In particular, by Lemma 4.3, ⇓((⇓(K))f) = ⇓(Kf) and so ⇓(f) : Y/C → X/C given by h ↦ hf, is a continuous function, corresponding to topology provided by ⇓( ). Hence ⇓( ) : C^{op} → Top is a functor.

Now, we form s(C) by the following data:

objects: (X, ⇓{x_{1}, ⋯, x_{m}}), where X ∈ ob(C) and {x_{1}, ⋯, x_{m}} ⊆ ob(X/C),

maps: a map from (X, ⇓{x_{1}, ⋯, x_{m}}) to (Y, ⇓{y_{1}, ⋯, y_{n}}) is a map f : X → Y in C such that ⇓{y_{1}f, ⋯, y_{n}f} ⊆ ⇓{x_{1}, ⋯, x_{m}},

composition and identities are formed as in C.

By Lemma 4.3, s(C) is a category. Clearly, there is a forgetful functor Δ_{C} : s(C) → C, which forgets the sieves ⇓(K).

4.4. Lemma. Let C be a category. Then the forgetful functor Δ_{C} : s(C) → C is a stable meet semilattice fibration.

Proof. For any map f : X → Y in C and any object (Y, ⇓{y_{1}, ⋯, y_{n}}) ∈ Δ_{C}^{−1}(Y), clearly f : (X, ⇓{y_{1}f, ⋯, y_{n}f}) → (Y, ⇓{y_{1}, ⋯, y_{n}}) is a map of s(C). Moreover,

f : (X, ⇓{y_{1}f, ⋯, y_{n}f}) → (Y, ⇓{y_{1}, ⋯, y_{n}})

is the cartesian lifting of a map f : X → Y at (Y, ⇓{y_{1}, ⋯, y_{n}}). Hence Δ_{C} : s(C) → C is a fibration. Note that each fiber

Δ_{C}^{−1}(X) = {(X, ⇓{x_{1}, ⋯, x_{m}}) | {x_{1}, ⋯, x_{m}} ⊆ map(X/C)}

is a meet semilattice with the order given by

(X, ⇓{x_{1}, ⋯, x_{m}}) ≤ (X, ⇓{x′_{1}, ⋯, x′_{l}}) ⇔ ⇓{x′_{1}, ⋯, x′_{l}} ⊆ ⇓{x_{1}, ⋯, x_{m}},

with the binary meet given by

(X, ⇓{x_{1}, ⋯, x_{m}}) ∧ (X, ⇓{x′_{1}, ⋯, x′_{l}}) = (X, ⇓{x_{1}, ⋯, x_{m}, x′_{1}, ⋯, x′_{l}}),

and with (X, ⇓{1_{X}}) as the top element. Clearly, for any map f : X → Y in C, f^{∗} : Δ_{C}^{−1}(Y) → Δ_{C}^{−1}(X), which takes (Y, ⇓{y_{1}, ⋯, y_{n}}) to (X, ⇓{y_{1}f, ⋯, y_{n}f}), is a stable meet semilattice homomorphism. Therefore, Δ_{C} : s(C) → C is a stable meet semilattice fibration.

In order to prove the universal property of U_{f}, we need:

4.5. Lemma. For any stable meet semilattice fibration δ_{X} : X̃ → X and any functor G : C → X, there is a unique functor G′ : s(C) → X̃ such that (G, G′) : Δ_{C} → δ_{X} is a map in sFib_{0}.

Proof. For any map f : (C, ⇓{c_{1}, ⋯, c_{m}}) → (D, ⇓{d_{1}, ⋯, d_{n}}) in s(C), where c_{i} : C → X_{i} and d_{j} : D → Y_{j} are maps in C, i = 1, ⋯, m, j = 1, ⋯, n, we have ⇓{d_{1}f, ⋯, d_{n}f} ⊆ ⇓{c_{1}, ⋯, c_{m}} and the following commutative diagram:

\xymatrix{ & (C, ⇓\{c_{1}, ⋯, c_{m}\}) \ar[dl]_{1_{C}} \ar[dr]^{f} \\ (C, ⇓\{d_{1}f, ⋯, d_{n}f\}) \ar[rr]^{f} &  & (D, ⇓\{d_{1}, ⋯, d_{n}\})}

where (C, ⇓{d_{1}f, ⋯, d_{n}f}) = f^{∗}(D, ⇓{d_{1}, ⋯, d_{n}}). Now we define the functor G′ : s(C) → X̃ by sending

f : (C, ⇓{c_{1}, ⋯, c_{m}}) → (D, ⇓{d_{1}, ⋯, d_{n}})

to

ϑ_{G(f)} ≤: ∧_{i=1}^{m}(G(c_{i}))^{∗}⊤_{δ_{X}^{−1}(G(X_{i}))} → ∧_{j=1}^{n}(G(d_{j}))^{∗}⊤_{δ_{X}^{−1}(G(Y_{j}))},

which is given by the following commutative diagram in X̃:

\xymatrix{ & ∧_{i=1}^{m}(G(c_{i}))^{∗}⊤_{δ_{X}^{−1}(G(X_{i}))} \ar@{-->}[dl]_{≤} \ar@{-->}[dr]^{G′(f)} \\ (G(f))^{∗}(∧_{j=1}^{n}(G(d_{j}))^{∗}⊤_{δ_{X}^{−1}(G(Y_{j}))}) \ar[rr]^{ϑ_{G(f)}} &  & ∧_{j=1}^{n}(G(d_{j}))^{∗}⊤_{δ_{X}^{−1}(G(Y_{j}))}}

It is routine to check that (G, G′) : Δ_{C} → δ_{X} satisfies the conditions [sfM.1], [sfM.2], and [sfM.3] and it is a map in sFib_{0}.

Assume that G′′ : s(C) → X̃ is a functor such that (G, G′′) : Δ_{C} → δ_{X} is a map in sFib_{0}. Let f : (C, ⇓{c_{1}, ⋯, c_{m}}) → (D, ⇓{d_{1}, ⋯, d_{n}}) be a map in s(C). By [sfM.1], G′′(C, ⇓{1_{C}}) = G′′(⊤_{Δ_{C}^{−1}(C)}) = ⊤_{δ_{X}^{−1}(G(C))}. By [sfM.3],

G′′(C, ⇓{c_{1}}) = G′′(c_{1}^{∗}(X_{1}, ⇓{1_{X_{1}}})) = (G(c_{1}))^{∗}(G′′(X_{1}, ⇓{1_{X_{1}}})) = (G(c_{1}))^{∗}⊤_{δ_{X}^{−1}(G(X_{1}))}.

By [sfM.2],

G′′(C, ⇓{c_{1}, ⋯, c_{m}}) = G′′(∧_{i=1}^{m}(C, ⇓{c_{i}}))
= ∧_{i=1}^{m}G′′(C, ⇓{c_{i}})
= ∧_{i=1}^{m}(G(c_{i}))^{∗}⊤_{δ_{X}^{−1}(G(X_{i}))}.

Hence G′′(C, ⇓{c_{1}, ⋯, c_{m}}) = G′(C, ⇓{c_{1}, ⋯, c_{m}}). Similarly,

G′′(D, ⇓{d_{1}, ⋯, d_{n}}) = G′(D, ⇓{d_{1}, ⋯, d_{n}}).

Since

\xymatrix{s(C) \ar[d]_{Δ_{C}} \ar[r]^{G′′} & X̃ \ar[d]^{δ_{X}} \\ C \ar[r]_{G} & X}

commutes, for any map f : (C, ⇓{c_{1}, ⋯, c_{m}}) → (D, ⇓{d_{1}, ⋯, d_{n}}) in s(C), we have δ_{X}G′′(f) = GΔ_{C}(f) = G(f). Hence there is a unique map

h : ∧_{j=1}^{n}(G(d_{j}f))^{∗}⊤_{δ_{X}^{−1}(G(Y_{j}))} → ∧_{j=1}^{n}(G(d_{j}f))^{∗}⊤_{δ_{X}^{−1}(G(Y_{j}))}

in δ_{X}^{−1}(G(C)) such that δ_{X}(h) = 1_{G(C)} and ϑ_{G(f)}h = G′′(f). Since δ_{X} is a stable meet semilattice fibration, h =≤. Then, by the definition of G′(f), G′′(f) = ϑ_{G(f)}h = ϑ_{G(f)} ≤= G′(f) and so the uniqueness of G′ follows.

Let F_{f}(C) = Δ_{C} for each category C. Now we are ready to prove F_{f} ⊣ U_{f}.

4.6. Theorem. There is an adjunction: \xymatrix{sFib_{0} \ar[r]_{U_{f}}|{⊥} & Cat_{0} \ar[l]_{F_{f}}} with the identity unit η_{C} = 1_{C}.

Proof. For any category C, clearly U_{f}F_{f}(C) = C. For any stable meet semilattice fibration δ_{X} : X̃ → X and any functor G : C → U_{f}(δ_{C}), by Lemma 4.5 we have a unique map G^{∗} = (G, G′) : Δ_{C} → δ_{X} in sFib_{0} such that

\xymatrix{C \ar[dr]_{G} \ar[r]^{η_{C}=1_{C}} & U_{f}F_{f}(C) \ar[d]^{U_{f} (G^{∗})} & F_{f}(C) \ar@{.>}[d]_{∃!}^{G^{∗}} \\  & U_{f}(δ_{X}) & δ_{X}}

commutes. Hence F_{f} ⊣ U_{f} with the unit η_{C} = 1_{C}.

4.7. The Free Restriction Category on a Category. Recall that there is an evident forgetful functor U_{r} : rCat_{0} → Cat_{0}, which forgets restriction structures. In [3], Cockett and Lack gave the explicit description of the free restriction categories over categories. In this subsection, as an application of Theorems 2.12 and 4.6, we shall reproduce Cockett-Lack’s free restriction category F_{r}(C) using the free stable meet semilattice fibration Δ_{C} for any given category C.

By Theorem 2.12, there is an adjunction: \xymatrix{rCat_{0} \ar[r]_{R}|{⊥} & sFib_{0} \ar[l]_{S}} with a faithful functor R.

By Theorem 4.6, there is an adjunction: \xymatrix{sFib_{0} \ar[r]_{U_{f}}|{⊥} & Cat_{0} \ar[l]_{F_{f}}} with the identity unit η_{C} = 1_{C}.

Given Theorem 2.12 and Theorem 4.6, we define F_{r} to be the composite SF_{f} : Cat_{0} → rCat_{0} and U_{r} to be the composite U_{f}R : rCat_{0} → Cat_{0} which clearly just forgets the restriction structure. So define F_{r} ⊣ U_{r} as adjoints composite.

Explicitly, for a given category C, F_{r}(C) is the category with

• the same objects as C,

• the map from C to D being a pair of (f, ⇓(K)), where f : C → D is a map of C and K is a set of maps in C with domain C such that f ∈ ⇓(K) and |K| < +∞,

• the composition given by

(g, ⇓(L))(f, ⇓(K)) = (gf, ⇓(⇓(K) ∪ (⇓f)⇓(L))) = (gf, ⇓(K ∪ Lf)),

• the identities given by 1_{C} = (1_{C}, ⇓{1_{C}}).

F_{r}(C) is precisely Cockett-Lack’s free restriction category over C as described in [3].

4.8. Theorem. [Cockett-Lack [3]] U_{r} : rCat_{0} → Cat_{0} has a left adjoint.

The free category generated by a graph gives F_{c} ⊣ U_{c} : Cat_{0} → Graph. This, combining with Theorems 2.12 and 4.6, yields immediately the following theorem.

4.9. Theorem. There is a sequence of adjunctions:

\xymatrix{Graph \ar[r]^{F_{c}} & Cat_{0} \ar[r]^{F_{f}} \ar[l]^{U_{c}} & sFib_{0} \ar[r]^{S} \ar[l]^{U_{f}} & rCat_{0} \ar[l]^{R}}

Theorem 2.28 [3] states that U_{f}R : rCat_{0} → Cat_{0} is monadic. In Subsection 3.1, we noticed that R is monadic. We remark here, however, that U_{f} is certainly not monadic since U_{f}F_{f} = 1_{Cat_{0}}.

4.10. The Free Restriction Category on a Graph. By Theorem 4.9, U_{rc} = U_{c}U_{f}R : rCat_{0} → Graph has a left adjoint F_{rc} = SF_{f}F_{c} which is the free restriction category over a graph. In this subsection, we provide an explicit description of this construction. This construction is of some special interest as it is a predecessor to Munn’s description of the free inverse semigroup [10].

Given any graph G, F_{c}(G) is the category with the nodes of G as objects, with paths, p, from node A to node B giving the maps (A, p, B) : A → B, and with the empty path on A giving the identity (A, [ ], A) : A → A. Composition is given by concatenation of paths: (B, q, C)(A, p, B) = (A, qp, C).

Applying F_{f} to F_{c}(G) gives the free stable meet semilattice fibration over F_{c}(G) and applying S to this gives the free restriction category F_{rc}(G) generated by graph G. Explicitly, F_{rc}(G) is the restriction category with:

objects: nodes of G,

maps: a map from A to B is given by a pair (s, S) of a finite prefix closed subset S of paths starting at A and a path s ∈ S ending at B. Explicitly this means pairs (s, S) with S ⊆_{f} F_{c}(G)(A, −) with s ∈ S and s : A → B, where S is prefix closed in the sense that pq ∈ S ⇒ p ∈ S.

composition: (t, T)(s, S) = (ts, S ∪ T s) (Note that S ∪ T s is prefixed closed as if for any p ∈ S ∪ T s and p′ ⪯ p then p ∈ S or p ∈ T s and so in both cases p′ ∈ S ∪ T s since both S and T are prefixed closed.),

identities: 1_{A} = ((A, [ ], A), {(A, [ ], A)}).

The maps, the composition, and restriction of F_{rc}(G) can be described graphically. One can present the maps as a directed trees with a selected node together with a tree map into the graph G. The map starts at the graph node associated with the root of the tree and ends at the graph node associated with the selected node. The composition is given by “gluing” together at the selected node of the first and the root of second in a obvious way and removing repeated branches with the second selected node selected. The identity on a node A is given by the smallest tree starting at A: A . The restriction is given by making the selected node the root.

For example, if G is the graph given by

[figure: A; a; d; B; c; b]

then an example of a composition of a map from A to B and a map from B to B in the free restriction category generated by G is:

[figure: B; B; c; b; A; A; A; d; A; a; d; B; b; c; B; c; b; B; A; d; b; A; a; B; A; A; a; B; B; c; B; b; c; B; B; c; b; A; B; B; c; b; A; A; A; d; a; A; a; d; B; b; c; A; B; c; b; B; c; b; B; A; d; b; A; a; A; A; B] compose

where the tree with selected node B at top-left is a map from A to B in the free restriction category, the tree at top-right is a map from B to B, and the result of the composition is below the line.

The restriction can be displayed as:

[figure: A; A; B; B; A; A; A; B; B; A] restriction

where the top is a map from A to B and its restriction, with the selected node move to the root is below the line.

Notice that in a restriction category generated by a graph, the only total map are the identity maps (X, [ ], X). Thus the only monics are the identities: this is in contrast to the free category (or path category) in which all maps are monic.

References

[1] M. Barr and C. Wells, Category Theory for Computing Science, the Electronic Supplement, 1995 [2] J.R.B. Cockett and Xiuzhan Guo, Introduction to range restriction categories, in

progress.

[3] J.R.B. Cockett and S. Lack, Restriction categories I: Categories of partial maps, Theoret. Comput. Science 270(2002), 223-259.

[4] R.A. Di Paola and A. Heller, Dominical categories: recursion theory without elements, J. Symbolic Logic 52(1987), 595-635.

[5] John Fountain, Adequate semigroups, Proceedings of the Edinburgh Mathematical Society 22(1979), 113-125.

[6] Xiuzhan Guo, Ranges, Restrictions, Partial Maps, and Fibrations, Thesis, University of Calgary, 2004.

[7] M. Jackson and T. Stokes, An invitation to C-semigroups, Semigroup Form 62(2001), 279-310.

[8] Mark Lawson, Inverse Semigroups, World Scientific (1998)

[9] E.G. Manes, Guarded and banded semigroups, preprint, 2004.

[10] W.D. Munn, Free inverse semigroups, Proc. London Math. Soc. (3)29(1974), 385-404.

[11] Mario Petrich, Inverse semigroups, John Wiley (1984)

[12] E.P. Robinson and G. Rosolini, Categories of partial maps, Infom. and Comput. 79(1988), 94-130.

[13] G. Rosolini, Domains and dominical categories, Riv. Mat. Univ. Parma 11(1985), 387-397.

[14] G. Rosolini, Continuity and effectiveness in topoi, D. Phil. Thesis, Oxford University, 1986.

Department of Computer Science University of Calgary 2500 University Drive NW Calgary, Alberta T2N 1N4 Canada

Email: robin@cpsc.ucalgary.ca
      guox@cpsc.ucalgary.ca

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anonymous

ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/16/15/16-15.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@mathstat.uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu

Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca