Theory and Applications of Categories, Vol. 13, No. 4, 2004, pp. 61–85.

UNIVERSAL PROPERTIES OF SPAN

Dedicated to Aurelio Carboni on the occasion of his 60th birthday

R. J. MACG. DAWSON, R. PARÉ, AND D. A. PRONK

Abstract. We give two related universal properties of the span construction. The first involves sinister morphisms out of the base category and sinister transformations. The second involves oplax morphisms out of the bicategory of spans having an extra property; we call these “jointed” oplax morphisms.

Introduction

Even before they were formally introduced in [Ka], the importance of adjoint functors was recognized in many individual cases, e.g., free groups, fraction fields, Stone-Čech compactifications, and adjunctions on linear spaces. Any functor that has an adjoint has many important properties; for instance, a functor with a right adjoint preserves colimits [M2]. Of course, most functors (and even many important ones) have neither left nor right adjoints. This motivates the introduction of profunctors [Bé2]. These are generalizations of functors and in the bicategory Prof of categories with profunctors every functor (viewed as a profunctor) has a right adjoint.

The reader will note that these adjunctions exist in a bicategory different from the 2-category Cat of categories in which adjunctions were originally defined. Indeed, the usual characterization (or definition) of adjunction in terms of unit and counit satisfying the triangle equalities is a 2-categorical concept, and adding the appropriate isomorphisms makes it into a bicategorical one. The idea of an adjunction is fruitful enough to motivate adding a 2-cell structure to an ordinary category, just so that one can consider adjunctions. This has been done in several ways.

Historically, the first instance of this was probably the generalization of the concept of “function” to that of “relation” (before categories were even invented). The idea of relations being ordered by inclusion (i.e., as subsets of the product) also goes back long before the invention of categories, but can be considered as providing a 2-cell structure for the category Rel of sets and relations. In this bicategory, every function determines a relation and as such has a right adjoint, namely the reverse relation. Furthermore, every relation is the composite of one coming from a function with the reverse of one of these, and a relation is that of a function if and only if it has a right adjoint. The notion of relation has been extended to other categories such as groups, to generalize the element level calculation of homology to arbitrary exact categories (cf. [Br, Hi]) and has numerous applications [Lam, M1, P].

All three authors are suppported by NSERC grants.

Received by the editors 2004-04-21 and, in revised form, 2004-05-17.

Published on 2004-12-05.

2000 Mathematics Subject Classification: 18A40, 18D05.

Key words and phrases: Span, Π_{2}, Beck condition, adjoints, universal property, localizations, sinister morphisms, jointed oplax morphisms.

\begin{matrix}c \\ ◯ \end{matrix} R. J. MacG. Dawson, R. Paré, and D. A. Pronk, 2004. Permission to copy for private use granted.

The two constructions which concern us here are rather more general than the above. The first concerns the notion of span, also introduced by Bénabou [Bé1]. (The definition and basic properties will be reviewed at the beginning of Section 1.) Bicategories of spans have been studied in contexts such as input-feedback-output systems [KSW] and the theory of databases [JRW]. For any category A, there is a canonical embedding A → Span(A). It has been known for some time that Span( ) is a free construction subject to the Beck condition. This was made precise by Hermida in [He1, Thm A.2]. In the notation of the present paper, Hermida’s theorem states that there is an equivalence of categories

Hom(Span(A), B) ≃ Beck(A, B).  (1)

The category Hom(Span(A), B) has homomorphisms as objects and oplax transformations as morphisms. The category Beck(A, B) has all sinister morphisms A → B that satisfy the Beck condition as objects, and strong transformations as arrows. (Recall that sinister morphisms were defined in [DPP] as those sending every arrow to a left adjoint.) Moreover, under this equivalence strong transformations in Hom(Span(A), B) correspond to sinister transformations (as in Definition 1.2) in Beck(A, B).

This result can also be viewed as a restriction of the universal property of Π_{2}A, the 2-category obtained by freely adding right adjoints to all arrows in A as defined in [DPP], i.e., there is an equivalence of categories

Hom(Π_{2}A, B) ≃ Sin(A, B),  (2)

where Hom(Π_{2}A, B) is the category of 2-functors and oplax transformations, and Sin(A, B) is the category of sinister functors, and strong transformations. Moreover, under this equivalence strong transformations in Hom(Π_{2}A, B) correspond to sinister transformations in Sin(A, B).

Note that (1) above can be obtained from (2) through restriction of the notion of morphism on the righthand side of the equation. The purpose of this paper is to describe a suitable generalization for the notion of morphism on the lefthand side of the equation, to obtain

JOL(Span(A), B) ≃ Sin(A, B),  (3)

where JOL(Span(A), B) consists of jointed oplax morphisms. These are normal oplax morphisms that preserve certain composites involving adjoints (cf. Definitions 2.4 and 2.14). In future work the universal property (3) will be used to generalize the Span( ) construction to categories that may not have pullbacks, and even to bicategories.

1. Span

Spans were introduced by Bénabou [Bé1] as an example of a bicategory. Let us recall the relevant definitions. Let A be a category with pullbacks. A span \xymatrix{A \ar[r]|{+} & B} in A, i.e., an

arrow in Span(A), is a diagram A ← S → B in A. A 2-cell [figure: A; +; S; +; S′; s⇓; B] is a commutative

diagram

[figure: A; S; s; B; A; S′; B]

Clearly, spans from A to B with 2-cells form a category. The composition T ⊗ S of two spans

\xymatrix{A \ar[r]|{+}^{S} & B \ar[r]|{+}^{T} & C}

is defined using the pullback

\xymatrix{ &  &  & S ×_{B} T \ar[dl] \ar[dr] \\ T ⊗ S = &  & S \ar[dr] \ar[dl] &  & T \ar[dr] \ar[dl] \\  & A &  & B &  & C}

and ⊗ extends to 2-cells in the usual way, using the universal property of pullback. For each A, the span \xymatrix{A & A \ar[l]_{1_{A}} \ar[r]^{1_{A}} & A} is the identity span I_{A}. This defines a bicategory Span(A).

The canonical embedding ( )_{∗} : A → Span(A) is a homomorphism of bicategories where A is considered as a locally discrete bicategory. It is defined as follows: each arrow

f: A → B of A gives a span f_{∗} = ( \xymatrix{A & A \ar[l]_{1_{A}} \ar[r]^{f} & B} ).

The only 2-cells f_{∗} → g_{∗} are identities so ( )_{∗} is locally full and faithful. The span

f^{∗} = \xymatrix{B & A \ar[l]_{f} \ar[r]^{1_{A}} & A} is right adjoint to f_{∗}. Indeed, the adjunctions are

η: I_{A} → f^{∗}f_{∗} and ε: f_{∗}f^{∗} → I_{B}
[figure: A; A; 1_{A}; δ; 1_{A}; A; B; A; f; f; f; B; A; A ×_{B} A; p_{1}; p_{2}; A; B; B; 1_{B}; 1_{B}; B,]

where A ×_{B} A is the pullback of f along itself. The triangle equalities are easily verified. Moreover, every span with a right adjoint is isomorphic to some f_{∗} (cf. [BCSW, CKS]).

Every span \xymatrix{A & S \ar[l]_{p} \ar[r]^{q} & B} is isomorphic to q_{∗} ⊗ p^{∗}; so Span(A) is generated by spans coming from A and their right adjoints, but not freely. In fact, a Beck condition is satisfied: if

\xymatrix{D \ar[d]_{k} \ar[r]^{h} & C \ar[d]^{g} \\ B \ar[r]_{f} & A}

is a pullback, then the canonical morphism

[figure: D; +; k_{∗}; ⇒; C; +; h^{∗}; +; g_{∗}; B; A; +; f^{∗}]

is an isomorphism. Indeed k_{∗} ⊗ h^{∗} can be computed as follows

\xymatrix{ &  & D \ar[dr]^{1} \ar[dl]_{1} \\  & D \ar[dl]_{h} \ar[dr]^{1} &  & D \ar[dl]_{1} \ar[dr]^{k} \\ C &  & D &  & B}

and f^{∗} ⊗ g_{∗} as

\xymatrix{ &  & D \ar[dr]^{k} \ar[dl]_{h} \\  & C \ar[dl]_{1} \ar[dr]^{g} &  & B \ar[dl]_{f} \ar[dr]^{1} \\ C &  & A &  & B.}

To pave the way for our main theorem, we give a universal property for Span(A), which was stated, and a proof sketched, in [He1, Thm A.2] (see also [He2, Thm 2.2]). For our purposes a somewhat different notation will be appropriate, which we shall set out and then use to state the universal property. We shall also give a complete proof, details of which we shall use for our main result. First we recall (cf. [KS]):

1.1. Definition. Let η, ε: f ⊣ u: A → B and η′, ε′: f′ ⊣ u′: A′ → B′ be two pairs of adjoint arrows. Two 2-cells

[figure: A; g; f; ⇓α; A′; f′; A; g; ⇓β; A′; B; h; B′; B; u; h; B′; u′]

are called mates under the adjunctions f ⊣ u and f′ ⊣ u′ if β is the composite

[figure: A; ⇓ε; g; f; ⇓α; A′; f′; ⇓η′; A′; B; u; B; h; B′; u′]

and (consequently) α is the composite

[figure: A; f; ⇓η; A; g; ⇓β; A′; ⇓ε′; f′; B; u; h; B′; u′; B′.]

Note that the notion of mates defines a bijection between 2-cells of the form α and β as in the definition above. In this paper, we will write α^{∗} for β, and β_{∗} for α, when appropriate.

Recall that an oplax transformation t: F → G provides, for each arrow f: A → B, a 2-cell

\xymatrix{F A \ar[d]_{F f} \ar[r]_{⇑tf}^{tA} & GA \ar[d]^{Gf} \\ F B \ar[r]_{tB} & GB.}

satisfying certain conditions described, for instance, in [Ke]. We will see that all the transformations involved in the universal properties of Span which are not strong are at least oplax. So we will write the strong transformations as oplax ones for which the components are isomorphisms.

1.2. Definition. A homomorphism of bicategories F : X → Y is called sinister if for every arrow x: X → X′ in X, the image F (x): F (X) → F (X′) is a left adjoint (i.e., it has a right adjoint F (x)^{∗}). Given two sinister homomorphisms F, G : X → Y, a sinister transformation t : F → G is a strong transformation such that for each arrow x: X → X′ the mates

[figure: F X; tX; ⇓ ((tx)^{−1})^{∗}; GX; F X′; (F x)^{∗}; tX′; GX′; (Gx)^{∗}]

of the naturality isomorphisms of t,

\xymatrix{F X \ar[d]_{F x} \ar[r]_{≅ ⇓ (tx)^{−1}}^{tX} & GX \ar[d]^{Gx} \\ F X′ \ar[r]_{tX′} & GX′,}

are also invertible.

The definition of sinister morphism may seem inadequate in that it might be thought that a functoriality condition on the right adjoints and the adjunctions would be desirable. In fact, as will be shown in Proposition 1.4, this is automatic.

1.3. Definition. For any bicategory B let Map(B) be the bicategory of maps in B, i.e., the objects are the same as those of B and an arrow B → B′ in Map(B) is an adjunction (f, u, ε, η), with f: B → B′, u: B′ → B, ε: fu → 1_{B′}, η: 1_{B} → uf satisfying the usual triangle equalities. A 2-cell (α, β): (f, u, ε, η) → (f̄, ū, ε̄, η̄) is a pair of transformations α: f → f̄, β: ū → u which are mates of each other. Composition of arrows is given by

(f′, u′, ε′, η′)(f, u, ε, η) = (f′f, uu′, ε′ · f′εu′, uη′f · η).

There is an obvious 2-functor Θ: Map(B) → B which is the identity on objects and which is locally fully faithful, so basically an inclusion.

1.4. Proposition. A homomorphism F : A → B is sinister if and only if it factors as

\xymatrix{A \ar[r]^{G} & Map(B) \ar[r]^{Θ} & B}

for some homomorphism G.

Proof. The “if” part is obvious. So assume that F is sinister. For every f: A → A′, pick a right adjoint U(f): F A′ → F A for F (f) and adjunctions ε_{f}: F (f)U(f) → 1_{F A′} and η_{f}: 1_{F A} → U(f)F (f). We let G(f) = (F f, Uf, ε_{f}, η_{f}). On 2-cells there is no problem because Θ is locally fully faithful, i.e., mates are uniquely determined.

As Θ is locally fully faithful, for any \xymatrix{A \ar[r]^{f} & A′ \ar[r]^{f′} & A′′} there is a unique isomorphism ψ_{f′,f}: U(f′f) → U(f′)U(f) making

(φ_{f′,f}, ψ_{f′,f}^{−1}): (F f′, Uf′, ε_{f′}, η_{f′}) · (F f, Uf, ε_{f}, η_{f}) → (F (f′f), U(f′f), ε_{f′f}, η_{f′f})

into an isomorphism

Gf′ · Gf → G(f′f)

in Map(B). Similarly, there is a unique isomorphism 1_{G(A)} → G(1_{A}) projecting to φ_{A} : 1_{F A} → F (1_{A}). Because each component of these isomorphisms uniquely determines the other, the coherence conditions needed for G to be a homomorphism follow from those for F.

Although this proposition presents sinister morphisms in a suitably functorial fashion, sinister transformations t: F → F′ do not lift to transformations μ: G → G′ between the lifted G, G′: A → Map(B). This is because the components t(A) of t need not be left adjoints. To put sinister transformations in the right perspective one needs double categories. We will introduce the double category 𝕄ap(B) in a forthcoming paper.

1.5. Remark. In [DPP] the definition of sinister transformation was wrongly given. What we called sinister there is no condition at all; it follows from strong naturality for 2-functors. What we called strongly sinister there is here called sinister.

Since a sinister morphism sends arrows to left adjoints, the image of a comma object

\xymatrix{X \ar[d]_{p_{2}} \ar[r]_{⇓ ξ}^{p_{1}} & X_{1} \ar[d]^{x_{1}} \\ X_{2} \ar[r]_{x_{2}} & X_{0}}

will have a mate

\xymatrix{F X \ar[r]_{⇓ F (ξ)^{∗}}^{F p_{1}} & F X_{1} \\ F X_{2} \ar[u]^{F p_{2}^{∗}} \ar[r]_{F x_{2}} & F X_{0}. \ar[u]_{F x_{1}^{∗}}}

Explicitly, the cell (F ξ)^{∗} is given by the composite

\xymatrix{F p_{1} · F p_{2}^{∗} \ar[r]^{η_{_{x′}_{1}}·F p_{1}·F p_{2}^{∗}} & F x_{1}^{∗} · F x_{1} · F p_{1} · F p_{2}^{∗} \ar[r]^{−·ϕ^{−1}·−}_{≅} & F x_{1}^{∗} · F (x_{1}p_{1}) · F p_{2}^{∗}}

[figure: −·F (ξ)·−; F x_{1}^{∗} · F (x_{2}p_{2}) · F p_{2}^{∗}; −·ϕ·−; ≅; F x_{1}^{∗} · F x_{2} · F p_{2} · F p_{2}^{∗}; −·ε_{x_{2}}; F x_{1}^{∗} · F x_{2}.]

1.6. Definition. Let F: X → Y be a sinister morphism and assume that X has comma objects. We say that F satisfies the Beck condition if, for every comma object

\xymatrix{X \ar[d]_{p_{2}} \ar[r]_{⇓ ξ}^{p_{1}} & X_{1} \ar[d]^{x_{1}} \\ X_{2} \ar[r]_{x_{2}} & X_{0},}

its mate

\xymatrix{F X \ar[r]_{⇓ F (ξ)^{∗}}^{F p_{1}} & F X_{1} \\ F X_{2} \ar[u]^{F p_{2}^{∗}} \ar[r]_{F x_{2}} & F X_{0} \ar[u]_{F x_{1}^{∗}}}

is invertible. We call F (ξ)^{∗} the Beck morphism of ξ.

1.7. Proposition. Let

\xymatrix{X \ar[d]_{p_{2}} \ar[r]_{⇓ ξ}^{p_{1}} & X_{1} \ar[d]^{x_{1}} \\ X_{2} \ar[r]_{x_{2}} & X_{0}}

be a comma square in X and assume that x_{1} has a right adjoint r; then p_{2} also has a right adjoint s and the square

\xymatrix{X \ar[r]^{p_{1}} & X_{1} \\ X_{2} \ar[u]^{s} \ar[r]_{x_{2}} & X_{0} \ar[u]_{r}}

commutes. The Beck condition for such a comma square is automatically satisfied by any sinister F.

Proof. Take s to be the unique arrow such that ξs = εx_{2}

\xymatrix{X_{2} \ar[ddr]_{1_{X_{2}}} \ar@{.>}[dr]^{s} \ar[r]^{x_{2}} & X_{0} \ar[dr]^{r} \\  & X \ar[d]_{p_{2}} \ar[r]_{⇓ ξ}^{p_{1}} & X_{1} \ar[d]^{x_{1}} \\  & X_{2} \ar[r]_{x_{2}} & X_{0}.}

We see right away that p_{1}s = rx_{2}. Also, p_{2}s = 1_{X_{2}}; and this will be the counit ε_{p_{2}} for the adjunction.

Consider the morphisms \xymatrix{p_{1} \ar[r]^{ηp_{1}} & rx_{1}p_{1} \ar[r]^{rξ} & r_{2}x_{2}p_{2} = p_{1}sp_{2}} and 1_{p_{2}}: p_{2} → p_{2}sp_{2}. x_{1}

times the first and x_{2} times the second commute with ξ in the sense that the outside of the following diagram commutes

[figure: x_{1}p_{1}; ξ; x_{1}ηp_{1}; x_{1}rx_{1}p_{1}; εx_{1}p_{1}; x_{1}rξ; x_{1}rx_{2}p_{2}; εx_{2}p_{2}; x_{1}p_{1}sp_{2}; ξsp_{2}; x_{1}p_{1}; ξ; x_{2}p_{2}; x_{2}p_{2}; 1; x_{2}p_{2}sp_{2}]

Thus, by the two-dimensional universal property of comma squares, there exists a unique η̄: 1_{X} → sp_{2} such that p_{1}η̄ = rξ · ηp_{1} and p_{2}η̄ = 1_{p_{2}}. This last equality is one of the triangle equalities. The other, η̄s = 1_{s}, follows from the fact that

(rξ · ηp_{1})s = rξs · ηp_{1}s = rεx_{2} · ηrx_{2} = (rε · ηr)x_{2} = 1_{p_{1}s}.

As homomorphisms preserve adjoints we can choose F (x_{1})^{∗} to be F (r) and F (p_{2})^{∗} to be F (s) together with F of the corresponding adjunctions. Then the Beck morphism is

[figure: F X; ⇓F ε_{p_{2}}; F p_{2}; F p_{1}; ⇓F ξ; F X_{1}; F x_{1}; ⇓F η_{x_{1}}; F X_{1}; F X_{2}; F s; F X_{2}; F x_{2}; F X_{0} .; F r]

which by definition of ε_{p_{2}} is

[figure: F X_{1}; ⇓F ε_{x_{1}}; F x_{1}; ⇓F η_{x_{1}}; F X_{1}; F X_{2}; F x_{2}; F X_{0}; F r; F X_{0} .; F r]

which is the identity. Other choices for the adjunctions would give an isomorphism.

1.8. Remark. In this paper, we will only use Definition 1.6 for locally discrete X, in which case comma objects are pullbacks.

1.9. Lemma. Let F, G: A → B be homomorphisms of bicategories and t: F → G an oplax transformation. For each adjoint pair of arrows η, ε: f ⊣ u: A → B in A, the mate (tu)_{∗} of tu is the inverse of tf.

Proof. Since f ⊣ u, we also have F (f) ⊣ F (u) and G(f) ⊣ G(u), with adjunctions

\xymatrix{F (f)F (u) \ar[r]^{φ^{−1}} & F (fu) \ar[r]^{F (ε)} & F (1_{B}) \ar[r]^{φ_{B}} & 1_{F B},}

and

\xymatrix{1_{F A} \ar[r]^{φ_{A}^{−1}} & F (1_{A}) \ar[r]^{F (η)} & F (uf) \ar[r]^{φ} & F (u)F (f)} ,

and similarly for G. The composite (tu)_{∗} · tf is given by the following pasting diagram:

[figure: F A; ⇑φ_{A}^{−1}; F A; F (1_{A}); ⇑F η; F A; F (uf); ⇑φ; F f; F B; F u; ⇑tu; t_{B}; GB; Gu; ⇑ψ^{−1}; GB; G(fu); ⇑Gε; GB; G(1_{B}); ⇑ψ_{B}; GB; F A; F A; F A; F A; t_{A}; GA; ⇑tf; Gf; GB; GB; GB; F A; F A; F A; F A; F f; F B; t_{B}; GB; GB; GB.]

By functoriality of t, this pasting is equal to

[figure: F A; ⇑φ_{A}^{−1}; F A; F (1_{A}); ⇑F η; F A; F (uf); ⇑φ; F f; F B; F u; ⇑φ^{−1}; F B; F (fu); ⇑t(fu); t_{B}; GB; G(fu); ⇑Gε; GB; G(1_{B}); ⇑ψ_{B}; GB; F A; F A; F A; F A; F f; F B; t_{B}; GB; GB; GB,]

and by naturality of t, this equals

[figure: F A; ⇑φ_{A}^{−1}; F A; F (1_{A}); ⇑F η; F A; F (uf); ⇑φ; F f; F B; F u; ⇑φ^{−1}; F B; F (fu); ⇑F ε; F B; F (1_{B}); ⇑t(1_{B}); t_{B}; GB; G(1_{B}); ⇑ψ_{B}; GB; F A; F A; F A; F A; F f; F B; F B; t_{B}; GB; GB.]

By the triangle equality, this is equal to

[figure: F A; F f; F B; ⇑φ_{B}^{−1}; F B; F (1_{B}); ⇑t(1_{B}); t_{B}; GB; G(1_{B}); ⇑ψ_{B}; GB; F A; F f; F B; F B; t_{B}; GB; GB]

which equals id_{t_{B}∘F f}. The fact that the other composite tf · (tu)_{∗} is equal to id_{t_{B}∘F f} can be proved in a similar way.

1.10. Proposition. Let A be a category with pullbacks and B any bicategory. Then composition with ( )_{∗}: A → Span(A) induces an equivalence of categories between the category Hom(Span(A), B) of homomorphisms Span(A) → B with oplax transformations, and the category Beck(A, B) of sinister morphisms A → B satisfying the Beck condition with strong transformations as morphisms. Under this equivalence, strong transformations in Hom(Span(A), B) correspond to sinister transformations in Beck(A, B).

Proof. Given a homomorphism F : Span(A) → B, the composite

\xymatrix{A \ar[r]^{( )_{∗}} & Span(A) \ar[r]^{F} & B}

is sinister and satisfies the Beck condition (because ( )_{∗} does and F is a homomorphism). If t: F → G is an oplax transformation, Lemma 1.9 gives that for any arrow f in A, the mate of t(f^{∗}) is the inverse of t(f_{∗}), so t∘( )_{∗} becomes a strong transformation. Moreover, if t: F → G is a strong transformation, Lemma 1.9 implies that the mate of t(f_{∗})^{−1} is t(f^{∗}) and therefore is invertible; so t ∘ ( )_{∗} is sinister.

This gives a functor

Hom(Span(A), B) → Beck(A, B) which we now show to be full and faithful. Let u: F ∘ ( )_{∗} → G ∘ ( )_{∗} be a strong transformation. We wish to extend it to an oplax t: F → G. There is no choice for t on objects nor on morphisms of the form f_{∗}. But t(f^{∗}) must be the inverse of the mate of t(f_{∗})^{−1} and so is also uniquely determined. Finally t(f_{∗} ⊗ g^{∗}) is uniquely determined by pasting t(f_{∗}) with t(g^{∗}), thus

[figure: ≅; ⇑((ug)^{−1})^{∗}; ≅; t(f_{∗} ⊗ g^{∗}) =; ⇑uf; .]

Thus t is defined on all of Span(A). Checking that t is an oplax transformation is a straightforward computation which we omit. If u is sinister, all the 2-cells in this calculation become isomorphisms and consequently t thus defined is a strong transformation.

Finally we must show that every sinister H: A → B satisfying the Beck condition is isomorphic to some F ∘ ( )_{∗}. Define F: Span(A) → B by F (A) = H(A) and F ( \xymatrix{A & S \ar[l]_{p} \ar[r]^{q} & B} ) = H(q)H(p)^{∗}, where H(p)^{∗} is a chosen right adjoint for H(p). Given a 2-cell

\xymatrix{ & S \ar[dl]_{p} \ar[dd]^{s} \ar[dr]^{q} \\ A &  & B \\  & S′ \ar[ul]^{p′} \ar[ur]_{q′} & ,}

F (s) is

\xymatrix{H(q)H(p)^{∗} = H(q′s)H(p′s)^{∗} ≅ H(q′)H(s)H(s)^{∗}H(p′)^{∗} \ar[r]^{H(q′)ε_{s}H(p′)} & H(q′)H(p′).}

That F is functorial on 2-cells is another straightforward calculation involving all the coherence conditions on H. Again, we omit the details. The Beck condition ensures that F is a homomorphism of bicategories.

1.11. Remark. As an application of this proposition we get the fact that a cocomplete S-indexed category can be represented by a homomorphism Span(S) → Cat (cf. [BW]).

2. Jointed Oplax Morphisms

As defined in [DPP], Π_{2}A is the free 2-category generated by A and right adjoints for all

morphisms of A. A special instance of this construction for the category 2= ( \xymatrix{A \ar[r]^{f} & B} ) was presented by Schanuel and Street in [SS]. This example shows very clearly that in general Π_{2}A and Span(A) are not equivalent. The bicategory Span (2) has only three nontrivial arrows, f_{∗}, f^{∗}, and f_{∗}f^{∗} as shown; and one nontrivial 2-cell ε: f_{∗}f^{∗} ⇒ 1_{B}.

[figure: A; f_{∗}; B; f_{∗}f^{∗}; ⇐; f^{∗}]  (4)

However, Π_{2}(2) (which Schanuel and Street call Adj), has, for instance, f^{∗}f_{∗} ≅ 1̸_{A}, and in fact there are infinitely many non-isomorphic arrows and infinitely many 2-cells.

In this paper we are mainly interested in bicategories and only need to work up to the level of bicategorical equivalence. So, while Π_{2}A, like any 2-category, is a bicategory, we may represent it in this context by any equivalent bicategory. Many of the technicalities in the original definition of Π_{2}A were only there to make horizontal composition associative and unitary “on the nose” and make the inclusion functor ( )_{∗}: A → Π_{2}A a 2-functor. Here we may simplify calculations considerably by choosing a bicategory from the class of those equivalent to Π_{2}A which makes the relationship with Span(A) more transparent.

The bicategory we use, which we shall by abuse of notation also refer to as Π_{2}A, is defined as follows:

Its objects are those of A.

An arrow A → B is a nonempty path of spans in A,

A = A_{0} ← S_{1} → A_{1} ← S_{2} → A_{2} ⋯ A_{n−1} ← S_{n} → A_{n} = B  (5)

We say that this is a path of length n.

The 2-cells are represented by equivalence classes of certain commutative diagrams called fences which look like

[figure: A; A_{0}; y_{0}; S_{1}; x_{1}; A_{1}; y_{1}; S_{2}; x_{2}; x_{3}; A_{2}; y_{2}; B; A; B_{0}; T_{1}; B_{1}; T_{2}; B_{2}; T_{3}; B_{3}; B]  (6)

The y_{i} and x_{j} are indexed as follows. A fence from a path of length m to one of length n is a triple (ϕ, ⟨y_{i}⟩, ⟨x_{j}⟩), where

ϕ : {0, …, m} → {0, …, n}

is an order-preserving map such that ϕ(0) = 0 and ϕ(m) = n. For each 0 ≤ i ≤ m, y_{i}: A_{i} → B_{ϕ(i)}, with y_{0} = 1_{A} and y_{m} = 1_{B}. As ϕ preserves the top element, it has a left adjoint ψ and for each 0 ≤ j ≤ n, x_{j}: S_{ψ(j)} → T_{j}. The equivalence relation is generated by identifying two fences if they differ only by

\xymatrix{S_{i} \ar[r] & A_{i} \ar[ddl]_{h_{i}} \ar@{.>}[dd]^{l} & S_{i+1} \ar[l] \ar[ddl]^{x_{j}} &  & S_{i} \ar[ddr]_{x′_{j}} \ar[r] & A_{i} \ar@{.>}[dd]^{l} \ar[ddr]^{h′_{i}} & S_{i+1} \ar[l] \\  &  &  & and \\ B_{j−1} & T_{j} \ar[l] \ar[r] & B_{j} &  & B_{j−1} & T_{j} \ar[l] \ar[r] & B_{j}}

and there exists an l factoring both parallelograms.

Horizontal composition is by concatenation and vertical composition by composing the individual components of fences

(ϕ′, ⟨y′_{j}⟩, ⟨x′_{k}⟩)(ϕ, ⟨y_{i}⟩, ⟨x_{j}⟩) = (ϕ′ϕ, ⟨y′_{ϕ(i)}y_{i}⟩, ⟨x′_{k}x_{ψ(k)}⟩).

In a forthcoming paper we will discuss the properties of this bicategory in more detail. For now we only need that there is a homomorphism of bicategories Υ: Π_{2}A → Span(A), for which we will give a direct construction.

On objects Υ is the identity. Υ takes an arrow, represented by a path as in (5) to the inverse limit, or generalized pullback, of the path:

S_{1} ×_{A_{1}} S_{2} × ⋯ × S_{n−1} ×_{A_{n−1}} S_{n}: \xymatrix{A \ar[r]|{+} & B.}

It can be computed using pullbacks. Given another path

A = B_{0} ← T_{1} → B_{1} ← T_{2} → B_{2} ⋯ B_{m−1} ← T_{m} → B_{m} = B

and a fence (ϕ, ⟨y_{i}⟩, ⟨x_{j}⟩) between them, Υ associates to it the morphism of spans given by the universal property of the limit

(x_{j}p_{ϕ^{∗}(j)}): Π_{A_{i}}S_{i} → Π_{B_{j}}T_{j}

where p_{i}: Π_{A_{i}}S_{i} → S_{i} is the projection.

For example, for the fence (6) we get

\xymatrix{S_{1} ×_{A_{1}} S_{2} \ar[r]^{(x_{1}p_{1},x_{2}p_{2},x_{3}p_{2})} & T_{1} ×_{B_{1}} T_{2} ×_{B_{2}} T_{3}.}

If we have a different fence (ϕ′, ⟨h′_{i}⟩, ⟨x′_{j}⟩), differing only by

\xymatrix{S_{i} \ar[r] & A_{i} \ar[dl]_{h_{i}} \ar@{.>}[d]_{l} & S_{i+1} \ar[l] \ar[dl]^{x_{j}} & S_{i} \ar[dr]_{x′_{j}} \ar[r] & A_{i} \ar@{.>}[d]_{l} \ar[dr]^{h′_{i}} & S_{i+1} \ar[l] \\ B_{j−1} & T_{j} \ar[l] \ar[r] & B_{j} & B_{j−1} & T_{j} \ar[l] \ar[r] & B_{j}}

with the same l factoring both parallelograms, the induced morphism will be the same except possibly in the j^{th} component. But the commutative diagram

\xymatrix{ & ∏_{A_{i}} S_{i} \ar[dl]_{p_{i}} \ar[dr]^{p_{i+1}} \\ S_{i} \ar[dr]_{x′_{j}} \ar[r] & A_{i} \ar[d]^{l} & S_{i+1} \ar[l] \ar[dl]^{x_{j}} \\  & T_{j}}

shows that in fact they are equal in the j^{th} component as well, so that Υ is well-defined on 2-cells of Π_{2}A. It is not hard to check that Υ: Π_{2}A → Span(A) is a homomorphism of bicategories. Span(A) is contained in Π_{2}A, but not as a sub-bicategory.

Recall the definition of oplax morphism of bicategories (the vertical dual of Bénabou’s morphism of bicategories [Bé1]). An oplax morphism Φ: A → B of bicategories takes an object A of A to an object Φ(A) of B and for all pairs A, B of objects we have a functor

Φ_{A,B}: A(A, B) → B(ΦA, ΦB).

For each object A we are given a morphism

φ_{A}: Φ(1_{A}) → 1_{ΦA}

and for each pair of morphisms \xymatrix{A \ar[r]^{f} & B \ar[r]^{g} & C} a morphism

φ_{g,f}: Φ(gf) → Φ(g)Φ(f).

The φ_{A} and φ_{g,f} satisfy the following naturality and coherence conditions:

• φ_{A} is natural in A.

• φ_{g,f} is natural in g and f.

• The diagram

\xymatrix{Φ(hgf) \ar[r]^{φ_{hg,f}} \ar[d]_{φ_{h,gf}} & Φ(hg)Φ(f) \ar[d]^{φ_{h,g}Φ(f)} \\ Φ(h)Φ(gf) \ar[r]_{Φ(h)φ_{g,f}} & Φ(h)Φ(g)Φ(f)}

commutes.

• The diagram

\xymatrix{Φ(f1_{A}) \ar[dr]_{≅} \ar[r]^{φ_{f,1_{A}}} & Φ(f)Φ(1_{A}) \ar[d]^{Φ(f)φ_{A}} \\  & Φ(f)1_{Φ(A)}}

commutes.

• The diagram

\xymatrix{Φ(1_{B}f) \ar[dr]_{≅} \ar[r]^{φ_{1_{B} ,f}} & Φ(1_{B})Φ(f) \ar[d]^{φ_{B}Φ(f)} \\  & 1_{Φ(B)}Φ(f)}

commutes.

We say that Φ is normal if all the φ_{A} are isomorphisms. Note that from now on all our oplax morphisms will be assumed to be normal.

The inclusion Ψ: Span(A) → Π_{2}A (which forms a splitting for Υ) is an oplax morphism of bicategories. Again, on the objects it is the identity. It takes a span A ← S → B to itself considered as a path of length one. A morphism of spans s: S → S′ is sent to the equivalence class of fences determined by

[figure: A; S; s; B; A; S′; B]

(which consists only of that one fence).

2.1. Proposition. Ψ is a locally fully faithful normal oplax morphism Span(A) → Π_{2}A.

Proof. That the morphism Ψ is locally fully faithful and normal is obvious. The morphisms Ψ(T ⊗ S) → Ψ(T)Ψ(S) making Ψ oplax are

[figure: A; S ×_{B} T; p_{1}; p_{2}; C; A; S; B; T; C.]

The associativity and unit conditions are easily checked. This is routine except for the non-emptiness of identity paths; we illustrate how this is handled for one of the unit laws. We must show that

\xymatrix{Ψ(I_{B} ⊗ S) \ar[d] \ar[r]^{Ψ(λ_{S})} & Ψ(S) \\ Ψ(I_{B})Ψ(S) \ar[r]_{=} & I_{B}Ψ(S) \ar[u]_{λ′_{Ψ(S)}}}

commutes.

When we define Span(A) we first make an arbitrary choice of pullbacks for all pairs of morphisms but we may as well make life easier by choosing pullbacks of identities to be identities. Then the top map of our diagram is the identity. Going around the long way gives

which is the identity on S.

[figure: A; S; 1; B; A; S; 1; B; 1; B; B; A; S; B]

2.2. Proposition. Ψ is a local left adjoint for Υ, i.e. the functors

\xymatrix{Π_{2}(A)(A, B) \ar[r]^{Υ_{A,B}} & Span(A)(A, B) \ar[l]^{Ψ_{A,B}}}

obtained by applying Υ and Ψ are adjoints

Ψ_{A,B} ⊣ Υ_{A,B}.

Proof. Consider an object A ← S → B of Span(A, B) and A ← T_{1} → B_{1} ← T_{2} → B_{2} ⋯ T_{n} → B an object of Π_{2}(A)(A, B). In this case, a morphism Ψ_{A,B}(S) → ⟨B_{j}, T_{j}⟩ is a diagram of the form

[figure: A; S; ···; B; A; T_{1}; B_{1}; T_{2}; B_{2}; ···; T_{n}; B]

as there is only one choice for the indexing function and no possibility of applying the equivalence relation. This is clearly the same as a morphism of spans

[figure: A; S; B; A; ∏_{B_{j}} T_{j}; B,]

i.e., a morphism S → Υ_{A,B}⟨B_{j}, T_{j}⟩.

The composite ΨΥ gives an oplax comonad on Π_{2}A which is idempotent and the identity on objects. Lax monads on bicategories were considered by Carboni and Rosebrugh [CR] as an extension of Kock’s work on tensor products in categories of algebras over a monoidal category [Ko]. They show that given a lax monad on a bicategory which is the identity on objects, a new bicategory can be formed with the same objects, whose arrows are algebras and composition given by a tensor product which classifies “bilinear” cells. This tensor product is defined as a joint coequalizer of 2-cells which is assumed to exist and be preserved by the monad. Our situation is dual with the 2-cells reversed. Local equalizers don’t exist in Π_{2}A but as our comonad is idempotent the arrows to be equalized are already equal (this point was already made in [RSW] in their Proposition 43 and the remark before it), so those equalizers do exist and are preserved by the comonad. Thus we obtain Span(A) as coalgebras for the oplax comonad ΨΥ on Π_{2}A. We summarize this in the following.

2.3. Proposition. Span(A) is equivalent to the Eilenberg-Moore category (Π_{2}A)_{ΨΥ} for the idempotent oplax comonad ΨΥ on Π_{2}A.

The existence of Ψ hints at another possible universal property of Span(A), namely with respect to normal oplax morphisms. But these don’t preserve adjoints in general, so the value of such a morphism on a span would not be determined by its values on arrows coming from A. A closer look at Ψ shows that it preserves some compositions, in particular those of the form f_{∗} ⊗ S. By this we mean that the canonical morphism Ψ(f ⊗ S) → Ψ(f_{∗})Ψ(S) is an isomorphism. We show something a bit stronger in Proposition 2.9 below. This leads to the following definition.

2.4. Definition. We say that a (normal) oplax morphism of bicategories Φ : A → B is jointed if for any pair of morphisms f : A → B and g : B → C for which g has a right adjoint, the structure cell ϕ_{g,f}: Φ(gf) → Φ(g)Φ(f) is an isomorphism.

Note that we do not require Φ to preserve composites gf where f has a left adjoint; we will show below that this follows automatically.

Note also that jointedness can be defined identically for lax morphisms. If the structural cells ψ_{A}: Φ(1_{A}) → 1_{ΦA} and (when g has a right adjoint) ψ_{g,f}: Ψ(g)Ψ(f) → Ψ(gf) are isomorphisms, then their inverses are isomorphisms exactly as required for a jointed oplax morphism; the difference rests entirely in the direction of the “ordinary” structural cells.

The usefulness of this condition has already been noted by several authors. The authors of [CKW] study morphisms of bicategories that are weaker than lax or oplax. Their “flabby” morphisms have laxity for composition on the left, and oplaxity for composition on the right, by maps. They observe that, when there is full oplaxity, they get what we call jointedness. However, they only consider the locally-ordered case. In [CKVW], they develop a very nice general theory (not just locally-ordered) in which they consider all combinations of laxity and oplaxity. They do a detailed study of the functorial properties of the Span construction but do not consider its universal property. In [DMS], Day, Mc-Crudden, and Street use jointedness; Clementino, Hofmann, and Tholen have also noted the usefulness of the property (see [CHT]).

2.5. Example. Let R be a commutative ring and consider the contravariant functor Hom(−, R) : R-Mod → R-Mod. There is a canonical morphism for any R-modules A and B,

φ_{A,B} : Hom(A, R) ⊗ Hom(B, R) → Hom(A ⊗ B, R)

f ⊗ g ⟼ ( \xymatrix{A ⊗ B \ar[r]^{f⊗g} & R ⊗ R \ar[r]^{μ} & R} ).

If we make R − Mod into a one-object bicategory M we get an oplax morphism

( )^{∗}: M → M^{co}

It is normal as R^{∗} ≅ R. Moreover, it is jointed: A has a right adjoint if and only if it is finitely generated and projective, and it is well known that in that case, φ_{A,B} is an isomorphism for all B.

2.6. Example. Closer to our discussion is the following. Let A and B be categories with pullbacks and F : A → B an arbitrary functor. We get an oplax morphism

Span(F): Span(A) ⟶ Span(B)
\xymatrix{ & S \ar@{-->}[dl]_{p} \ar@{-->}[dr]^{g} &  & ⟼ &  & F S \ar@{-->}[dl]_{F p} \ar@{-->}[dr]^{F g} \\ A &  & A′ &  & F A &  & F A′.}

The structure morphisms expressing oplaxity are given by the universal property of pullback

[figure: F (S ×_{A′} S′); φ; F S ×_{F A′} F S′; p.b.; F S; F S′; F A; F A′; F A′′.]

Clearly, if F preserves pullbacks then all the φ are isomorphisms and Span(F) is a homo-

morphism. But \xymatrix{A′ & S′ \ar[l]_{p′} \ar[r]^{q′} & A} has a right adjoint if and only if p′ is an isomorphism and any F will preserve the pullback

\xymatrix{ & S ×_{A′} S′ \ar@{-->}[dl] \ar@{-->}[dr] \\ S \ar[dr]_{q} &  & S′ \ar[dl]^{p′} \\  & A′}

when p′ is an isomorphism. So Span(F) is a jointed oplax morphism.

2.7. Proposition. Let Φ: A → B be oplax (and normal) and suppose that f ⊣ u, ε: fu → 1_{B}, η: 1_{A} → uf is an adjunction. If there is a 2-cell \overline{ε}: Φ(f)Φ(u) → 1_{Φ(B)} such that

\xymatrix{Φ(fu) \ar[d]_{φ_{f,u}} \ar[r]^{Φ(ε)} & Φ(1_{B}) \ar[d]^{φ_{B}} \\ Φ(f)Φ(u) \ar[r]_{\overline{ε}} & 1_{Φ(B)}}  (7)

commutes, then Φ(f) ⊣ Φ(u) with counit \overline{ε}.

Proof. Let \overline{η} be the unique arrow such that

\xymatrix{Φ(1_{A}) \ar[r]^{Φ(η)} \ar[d]_{φ_{A}}^{≅} & Φ(uf) \ar[d]^{φ_{u,f}} \\ 1_{Φ(A)} \ar[r]_{\overline{η}} & Φ(u)Φ(f);}  (8)

then

[figure: Φ(f); ≅; Φ(f); Φ(f1_{A}); φ_{f,1_{A}}; Φ(fη); Nat; Φ(fuf); φ_{f,uf}; φ_{fu,f}; Φ(εf); Φ(1_{B}f); Nat; φ_{1_{B} ,f}; ≅; Φ(f)Φ(1_{A}); Φ(f)Φ(η); (8); Φ(f)φ_{A}; Φ(f)Φ(uf); coh; Φ(f)φ_{u,f}; Φ(fu)Φ(f); φ_{f,u}Φ(f); Φ(ε)Φ(f); (7); Φ(1_{B})Φ(f); φ_{B}Φ(f); Φ(f); ≅; Φ(f)1_{ΦA}; Φ(f)\overline{η}; Φ(f)Φ(u)Φ(f); \overline{ε}Φ(f); 1_{ΦB}Φ(f); ≅; Φ(f)]  (9)

shows one of the triangle equalities. The other triangle equality is obtained in a similar fashion.

We say that the morphism Φ preserves the adjunction f ⊣ u when the condition of this proposition is satisfied, and Φ preserves adjoints if it preserves all adjunctions.

2.8. Proposition. Jointed oplax morphisms of bicategories preserve adjoints.

Proof. Let the oplax morphism Φ: A → B be jointed, and let f: A → X, u: X → A, ε: fu → 1_{X}, η: 1_{A} → uf be the data for an adjunction. We may take

\xymatrix{\overline{ε} = Φ(f)Φ(u) \ar[r]^{φ_{f,u}^{−1}} & Φ(fu) \ar[r]^{Φ(ε)} & Φ(1_{X}) \ar[r]^{φ_{X}} & 1_{Φ(X)}.}

2.9. Proposition. If Φ preserves adjoints and is normal, then it is jointed.

Proof. Suppose f has a right adjoint u with adjunctions ε and η as usual. Let g be any morphism composable with f. We will show that the composite

\xymatrix{Φ(f)Φ(g) \ar[r]^{Φ(f)Φ(ηg)} & Φ(f)Φ(ufg) \ar[r]^{Φ(f)φ_{u,fg}} & Φ(f)Φ(u)Φ(fg) \ar[r]^{\overline{ε}Φ(fg)} & Φ(fg)}

is inverse to φ_{f,g}. Indeed

[figure: Φ(f)Φ(g); Φ(f)Φ(ηg); Nat; Φ(f)Φ(ufg); Φ(f)φ_{u,fg}; Assoc; Φ(f)Φ(u)Φ(fg); \overline{ε}Φ(fg); (7); Φ(fg); Φ(fg); φ_{f,g}; Φ(fηg); _{id_{Φ(fg)}}; Δ =; Φ(fufg); Φ(εfg); δ_{fu,fg}; φ_{f,ufg}; Φ(fu)Φ(fg); Nat; Φ(ε)Φ(fg); φ_{f,u}Φ(fg); Φ(1_{B})Φ(fg); φ_{B}Φ(fg); Φ(1_{B}fg); φ_{1_{B} ,fg}]

commutes for the indicated reasons and the composite of the φ’s on the right is the identity (unit law for oplax morphisms). We also have

[figure: Φ(f)Φ(g); Φ(f)φ_{1,g}; Φ(f)Φ(ηg); Φ(f)Φ(ufg); Φ(f)φ_{uf,g}; Φ(f)φ_{u,fg}; Assoc; Nat; Φ(f)Φ(u)Φ(fg); \overline{ε}Φ(fg); Φ(f)Φ(u)φ_{f,g}; Nat; Φ(fg); φ_{f,g}; Φ(f)Φ(1_{A})Φ(g); Φ(f)Φ(η)Φ(g); Φ(f)φ_{A}Φ(g); Φ(f)Φ(uf)Φ(g); (8); Φ(f)φ_{u,f} Φ(g); Φ(f)Φ(u)Φ(f)Φ(g); \overline{ε}Φ(f)Φ(g); Φ(f)Φ(g); Φ(f)Φ(g); Φ(f)\overline{η}Φ(g); _{id_{Φ(f)Φ(g)}}; (9)]

and the composite of φ’s on the left is the identity by the unit law for oplax morphisms. This shows the Φ preserves composites when the second arrow (diagrammatically) has a right adjoint. Thus Φ is jointed.

We have shown that, for normal oplax morphisms, jointedness is equivalent to preservation of adjoints, which is a self-dual property (reversing arrows). This gives the following corollary.

2.10. Corollary. A normal oplax morphism Φ is jointed if and only if for every f and g where f has a left adjoint, φ_{g,f}: Φ(gf) → Φ(g)Φ(f) is an isomorphism.

The following example shows that the condition that Φ be normal is necessary in Proposition 2.9.

2.11. Example. Let G be a comonad which is adjoint to itself, e.g.,

[figure: Ab; G] G: A ↦ A ⊕ A.

This comonad gives rise to an oplax morphism 1 → Cat which is not normal and preserves adjoints. However, it doesn’t preserve composition with adjoints, since 1 ∘ 1 = 1, but G ∘ G ≅ G̸.

2.12. Proposition. Ψ: Span(A) → Π_{2}A is jointed.

Proof. Let \xymatrix{A \ar[r]|{+}^{S} & B \ar[r]|{+}^{T} & C} with T a left adjoint, so that the h in the diagram below is an isomorphism. Then φ_{S,T} is represented by the bottom fence in the following diagram, and φ_{S,T}^{−1} the top one.

[figure: A; S; f; g; 1; B; kh^{−1}; T; h; k; C; A; S; f; kh^{−1}g; 1; h^{−1}g; C; A; S; f; g; B; T; h; k; C]

The composite is

[figure: A; S; f; 1; h^{−1}g; g; B; kh^{−1}; T; h; k; C; A; S; f; g; B; T; h; k; C]

and h^{−1} factors the parallelogram, showing that this fence is equivalent to the identity. The other composite gives the identity immediately.

The following lemma will be useful in the proof of the main theorem of this section.

2.13. Lemma. Let G, H: X → B be jointed oplax morphisms and t: G → H an oplax transformation. If f: X → Y is left adjoint to u in X, then the cell

\xymatrix{GX \ar[d]_{Gf} \ar[r]_{⇑tf}^{tX} & HX \ar[d]^{Hf} \\ GY \ar[r]_{tY} & HY}

is an isomorphism whose inverse is the mate of

\xymatrix{GY \ar[d]_{Gu} \ar[r]_{⇑tu}^{tY} & HY \ar[d]^{Hu} \\ GX \ar[r]_{tX} & HX}

Proof. The proof of this lemma is exactly the same as the proof of Lemma 1.9. Note that in that proof we only use φ^{−1} and ψ^{−1} for composites of arrows where one of the arrows has an adjoint, as in the definition of jointedness.

2.14. Definition. For bicategories A and B, we will denote the category of jointed oplax morphisms from A → B with oplax transformations by JOL (A, B).

For a category A, we let Sin(A, B) be the category of sinister morphisms from A to B with strong transformations.

2.15. Theorem. Let A be a category with pullbacks with canonical inclusion

( )_{∗}: A → Span(A),

and let B be any bicategory. Then:

1. Composing with ( )_{∗} gives an equivalence of categories between JOL (Span(A), B) and Sin(A, B).

2. An oplax transformation t: G → H: Span(A) → B is strong if and only if t( )_{∗} is sinister.

3. G is a homomorphism if and only if G( )_{∗} satisfies the Beck condition.

Proof. For jointed oplax G : Span(A) → B, G( )_{∗} : A → B is a homomorphism as G preserves left composition by left adjoints. G also preserves adjoints and f_{∗} is a left adjoint for each f in A, so G( )_{∗} is sinister.

For an oplax transformation t: G → H, t( )_{∗} is certainly an oplax transformation, but as f_{∗} is a left adjoint, t( )_{∗} is in fact a strong transformation in view of the previous lemma.

Note that t and t( )_{∗} have the same values at both the arrow and 2-cell levels, so composing with ( )_{∗} does indeed give a functor

JOL(Span(A), B) → Sin(A, B).

We shall show that it is full and faithful. Let G, H : Span(A) → B be jointed oplax morphisms and t: G( )_{∗} → H( )_{∗} a strong transformation. We must show that there is a unique oplax transformation u: G → H such that t = u( )_{∗}. As the objects of A and Span(A) are the same, there is no problem there. Let \xymatrix{A & S \ar[l]_{p} \ar[r]^{q} & B} be a morphism in Span(A). If there is such a u, then by the previous lemma, the mate of u(p^{∗}) is the inverse of u(p_{∗}), or put another way, u(p^{∗}) is the mate (u(p_{∗})^{−1})^{∗} of the inverse of u(p_{∗}). Thus u(S) must be given by

[figure: GA; GS; GA; G(p^{∗}); ⇑(t(p_{∗})^{−1})^{∗}; tA; HA; H(p^{∗}); HA; HS; ⇑φ; GS; tS; G(q_{∗}); ⇑t(q_{∗}); HS; H(q_{∗}); ⇑φ^{−1}; GB; GB; tB; HB; HB.]

This shows the uniqueness of u. Showing that u, thus defined, is a lax transformation is a tedious calculation that we won’t reproduce here.

We see immediately from the formula for u(S) that u is strong if and only if t is sinister.

Next we show that for every sinister F: A → B there exists a jointed oplax G: Span(A) → B such that G( )_{∗} ≅ F. Of course G is the same as F on objects. As jointed oplax morphisms preserve left composition by left adjoints G(q_{∗} ⊗ p^{∗}) must be G(q_{∗})G(p^{∗}) and as they preserve adjoints as well this must be F (q)F (p)^{∗} where F (p)^{∗} is a chosen right adjoint for F (p). For a morphism of spans

[figure: A; S; p; x; q; B; A; S′; r; s; B]

G(x): G(S) → G(S′) is given by the composite

[figure: F (q)·F (p)^{∗}; φ·F (p)^{∗}; F (s)·F (x)·F (p)^{∗}; F (s)·η_{r}·F (x)·F (p)^{∗}; F (s)·F (r)^{∗}·F (r)·F (x)·F (p)^{∗}; F (s)·F (r)^{∗}·φ^{−1}·F (p)^{∗}; F (s)·F (r)^{∗}·F (p)·F (p)^{∗}; F (s)·F (r)^{∗}ε_{p}; F (s)·F (r)^{∗}.] Functoriality is easily verified.

To see that G is oplax consider a composite of spans,

\xymatrix{ &  & S ×_{B} T \ar[dl]_{p_{1}} \ar@{-->}[dr]^{p_{2}} \\  & S \ar[dl]_{p} \ar[dr]^{q} &  & T \ar[dl]_{t} \ar[dr]^{u} \\ A &  & B &  & C.}

We have

\xymatrix{F (up_{2})·F (pp_{1})^{∗} \ar[r]^{can}_{≅} & F (u)·F (p_{2})·F (p_{1})^{∗}·F (p)^{∗} \ar[r]^{Beck} & F (u)·F (t)^{∗}·F (q)·F (p)^{∗}.}

That G is normal is easily seen. T has a right adjoint if and only if t is an isomorphism. Then by Proposition 1.7, the Beck morphism is an isomorphism; so G is jointed.

It is now clear from the above formula that G is a homomorphism if and only if F satisfies the Beck condition.

2.16. Remark. As the above universal property of Span(A) does not involve pullbacks or the Beck condition, we could use it to define Span for an arbitrary A or even a bicategory A; this will be done in a forthcoming paper.

Acknowledgements. The authors thank Aurelio Carboni, Robert Rosebrugh, Dietmar Schumacher, Richard Wood (and an anonymous referee possibly disjoint from this set) for stimulating conversations and helpful suggestions at various times during the writing of this paper.

References

[Bé1] Bénabou, J., Introduction to bicategories, in Reports of the Midwest Category Seminar, Lecture Notes in Mathematics, Vol. 47, pp. 1–77, Springer-Verlag, New York/Berlin, 1967.

[Bé2] Bénabou, J., Les Distributeurs, Univ. Cath. de Louvain, Inst. de Mathématique Pure et Appliquée, rapport 33, 1973.

[BW] Betti, R., Walters, R. F. C., On completeness of locally-internal categories, J. Pure Appl. Algebra 47 (1987), pp. 105–117.

[BCSW] Betti, R., Carboni, A., Street, R., Walters, R., Variation through enrichment, J. Pure Appl. Algebra 29 (1983), pp. 109–127.

[Br] Brinkmann, H. B., Relations for groups and for exact categories, in Category Theory, Homotopy Theory and their Applications, Lecture Notes in Mathematics, Vol. 92, P. Hilton Ed., pp. 1–9, Springer Verlag, New York/Berlin, 1969.

[CHT] Clementino, M. M., Hofmann, D., Tholen, W., Exponentiability in categories of lax algebras, Theory Appl. Categ. 11 (2003), p. 337–352.

[CKS] Carboni, A., Kasangian, S., Street, R., Bicategories of spans and relations, J. Pure Appl. Algebra 33 (1984), pp. 259–267.

[CKW] Carboni, A., Kelly, G. M., Wood, R. J., A 2-categorical approach to change of base and geometric morphisms I, Cahiers Topologie Géom. Différentielle Catég., Vol. XXXII-1 (1991), pp. 47–95.

[CKVW] Carboni, A., Kelly, G. M., Verity, D., Wood, R. J., A 2-categorical approach to change of base and geometric morphisms II, Theory Appl. Categ. 4 (1998), pp. 82–136.

[CR] Carboni, A., Rosebrugh, R., Lax monads – indexed monoidal monads, J. Pure Appl. Alg. 76 (1991), pp. 13–32.

[DMS] Day, B. J., McCrudden, P., Street, R., Dualizations and antipodes, Appl. Categ. Struct. 11 (2003) pp. 229–260.

[DPP] Dawson, R. J. M., Paré, R., Pronk, D. A., Adjoining adjoints, Adv. in Math. 178 (2003), pp. 99–140.

[GP1] Grandis, M., Paré, R., Limits in double categories, Cahiers Topologie Géom. Différentielle Catég., Vol. XL-3 (1999), pp. 162–220.

[He1] Hermida, C., Representable multicategories, Advances in Mathematics 151 (2000), pp. 164–225.

[He2] Hermida, C., A categorical outlook on relational modalities and simulations, preprint.

[Hi] Hilton, P., Correspondences and exact squares, in Proceedings of the Conference on Categorical Algebra, La Jolla 1965, pp. 254–271, Springer Verlag, New York/Berlin, 1966.

[JRW] Johnson, M., Rosebrugh, R., Wood, R. J., Entity-relationship-attribute designs and sketches, Theory Appl. Categ. 10 (2002), pp. 94–112.

[Ka] Kan, D. M., Adjoint functors, Trans. Amer. Math. Soc. 87 (1958) pp. 294–329.

[KSW] Katis, P., Sabadini, N., Walters, R. F. C., Bicategories of processes, J. Pure Appl. Algebra 115 (1997), pp. 141–178.

[Ke] Kelly, G. M., On clubs and doctrines, in Category Seminar (Proc. Sem., Sydney, 1972/1973), Springer Lecture Notes, Vol. 420, pp. 181–256, Springer Verlag, New York/Berlin, 1974.

[KS] Kelly, G. M., Street, R., Review of the elements of 2-categories, in Category Seminar (Proc. Sem., Sydney, 1972/1973), Springer Lecture Notes, Vol. 420, pp. 75–103, Springer Verlag, New York/Berlin, 1974.

[Ko] Kock, A., Strong functors and monoidal monads, Arch. Math. 23 (1972), pp. 113–120.

[Lam] Lambek, J., Goursat’s theorem and the Zassenhaus lemma, Can. J. Math 10 (1958), pp. 45–56.

[Law] Lawvere, F. W., Metric spaces, generalized logic and closed categories, Rendiconti del Seminario Matematico e Fisico di Milano, XLIII (1973), 135–166. Republished in: Reprints in Theory and Applications of Categories, 1 (2002), pp. 1–37.

[M1] Mac Lane, S., An algebra of additive relations, Proc. Nat. Acad. Sci., USA 47 (1961), pp. 1043–1051.

[M2] Mac Lane, S., Categories for the Working Mathematician, 2nd ed’n, Springer Verlag, New York/Berlin, 1997.

[MP] Mac Lane, S., Paré, R., Coherence for bicategories and indexed categories, J. Pure and Appl. Alg. 37 (1985), pp. 59–80.

[P] Puppe, D., Korrespondenzen in abelsche Kategorien, Math. Annal. 148 (1962), pp. 1–30.

[RSW] Rosebrugh, R., Sabadini, N., Walters, R. F. C., Minimal realization in bicategories of automata, Mathematical Structures in Computer Science 8 (1998), pp. 93–116.

[SS] Schanuel, S., Street, R., The free adjunction, Cahiers Topologie Géom. Differentielle Catégoriques 27 (1986), pp. 81–83.

Dept. of Mathematics, Dalhousie University, Halifax, NS

Email: Robert.Dawson@smu.ca, pare@mathstat.dal.ca, pronk@mathstat.dal.ca

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

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/13/4/13-04.{dvi,ps}

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.

Editorial board.

Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com 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@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 Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz 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