Theory and Applications of Categories, Vol. 19, No. 2, 2007, pp. 19–40.

COMPONENTS, COMPLEMENTS AND THE REFLECTION FORMULA

CLAUDIO PISANI

Abstract. We illustrate the formula (↓p)x = Γ_{!}(x/p), which gives the reflection ↓p of a category p : P → X over X in discrete fibrations. One of its proofs is based on a “complement operator” which takes a discrete fibration A to the functor ¬A, right adjoint to Γ_{!}(A × −) : Cat/X → Set and valued in discrete opfibrations.

Some consequences and applications are presented.

1. Introduction

The “classical” formulas (see [Lawvere, 1973] and [Paré, 1973])

(↓p)x = Γ_{!}(x/p) ;  (↑p)x = Γ_{!}(p/x)  (1)

or better

↓p = Γ_{!}(−/p) ;  ↑p = Γ_{!}(p/−)  (2)

which display the presheaves corresponding to the reflections of a category p : P → X over a base category X in discrete fibrations and in discrete opfibrations as components of “comma” categories, do not appear at a first sight particularly pregnant or self-explicatory. However, noting that x/p is the product x/X ×p in Cat/X (and similarly p/x = X/x×p) and that x/X and X/x (corresponding to the representable presheaves) are the reflections ↑x and ↓x of the object x : 1 → X, we get

(↓p)x = Γ_{!}(↑x × p) ;  (↑p)x = Γ_{!}(↓x × p)  (3)

These are exactly the set-valued version of the formulas

x ∈ ↓p ⟺ Γ_{!}(↑x ∩ p) ;  x ∈ ↑p ⟺ Γ_{!}(↓x ∩ p)  (4)

which clearly give the reflections of a subset p of a poset in lower and upper subsets. (Here Γ_{!} is the two-valued correspective of the components functor, and gives false on the empty set and true elsewhere). Remarkably, also the most natural proof of (4), based on the classical complement operator which takes lower sets into upper sets (and conversely) and on the consequent law

Received by the editors 2006-10-26 and, in revised form, 2007-05-10.

Transmitted by F. W. Lawvere. Published on 2007-05-12.

2000 Mathematics Subject Classification: 18A99.

Key words and phrases: categories over a base, discrete fibrations, reflection, components, tensor, complement, strong dinaturality, limits and colimits, atoms, idempotents, graphs and evolutive sets.

\begin{matrix}c \\ ◯ \end{matrix} Claudio Pisani, 2007. Permission to copy for private use granted.

Γ_{!}(↓p ∩ q) ⟺ Γ_{!}(p ∩↑q)  (5)

generalizes almost straightforwardly to the set-valued context. (See [Pisani, 2007] for a detailed discussion of the poset case, which provides useful insight and motivations.)

Recall that the fundamental adjunctions

Γ_{!} ⊣ Γ^{∗} ⊣ Γ_{∗} : Cat → Set  (6)

between the components, discrete and points functors, can be generalized to

Γ_{!} ⊣ Γ^{∗} ⊣ Γ_{∗} : Cat/X → Set  (7)

where for p : P → X, Γ_{!}p is given by the components of the total (or domain) category P, while for S ∈ Set, Γ^{∗}S is the first projection of the product of X and the discrete category on S. In the present context, the (partially defined) “complement operator” is parametrized by sets:

¬ : Set × (Cat/X)^{op} → Cat/X

It takes a discrete fibration A into the “exponential” functor ¬A := (Γ^{∗}−)^{A} : Set → Cat/X which is valued in discrete opfibrations (and vice versa) and allows to prove the law

Γ_{!}(↓p × q) ⟺ Γ_{!}(p ×↑q)  (8)

from which the reflection formula is easily drawn. (A related definition of “negation” is proposed in [Lawvere, 1996]).

After presenting some basic facts about categories over a base in Section 2, we develop this and other proofs of the reflection formula in Section 3. In Section 4 we treat colimits in X as given by the (partially defined) reflection of Cat/X in principal (or representable) discrete fibrations. Thus ↓(−) is an intermediate step of this reflection, and we can easily derive important properties of (co)limits following [Paré, 1973]. In Section 5 we consider those categories t : T → X over X such that

hom(t, A) ≅ ten(t, A) := Γ_{!}(t × A)  (9)

for any discrete fibration or discrete opfibration A. Again motivated by the two-valued case, we call them “atoms”. Any idempotent arrow in X is an atom, and the reflections of atoms are, as presheaves on X, the retracts of representable functors; so they generate the Cauchy completion of X, displaying it as the Karoubi envelope of X. Finally, in Section 6 we show how the reflection formula can be used to obtain in a very direct way the reflection of graphs in (idempotent, bijective or n-periodic) evolutive sets.

Some of these topics have been presented at the International Conference on Category Theory (CT06) held at White Point in June 2006, and under a slightly different perspective, also in the preprint [Pisani, 2005]. The preprint [Pisani, 2007], to which we will often refer, contains more details and has a more didactical style.

Acknowledgements. The author is grateful to the referee for his helpful remarks.

2. Categories over a base

We review some facts about categories over a base that will be used in the sequel. Though most of them are standard, others seem not to be widely known.

2.1. Discrete fibrations and strong dinaturality. Let X be a fixed category and y : X → Set^{X^{op}} be the Yoneda embedding. Let us denote by i the functor

i := y/− : Set^{X^{op}} → Cat/X  (10)

which takes a presheaf A : X^{op} → Set into the category of elements y/A with its projection over X. The categories over X isomorphic to some iA are the discrete fibrations. The functor i is full and faithful:

Set^{X^{op}}(A, B) ≅ Cat/X(iA, iB)  (11)

Note that the right hand side is discrete even when the 2-structure of Cat/X is acknowledged. We denote by

↓(−) : Cat/X → Set^{X^{op}}  (12)

a left adjoint of i; thus i ↓(−) gives the reflection of Cat/X in the full subcategory of discrete fibrations. Similarly, we define i : Set^{X} → Cat/X and ↑(−) ⊣ i.

2.2. Remark. For any object x : 1 → X, there are bijections

Cat/X(x, iA) ≅ Ax ≅ Set^{X^{op}}(X(−, x), A)

natural in A ∈ Set^{X^{op}}. So we get ↓x ≅ X(−, x). Since furthermore iX(−, x) ≅ X/x, the reflection i↓x of an object in discrete fibrations is the slice category X/x. Similarly, given an arrow λ : 2 → X of the base category, with domain x and codomain y, ↓λ ≅ X(−, y); and the inclusions of the domain and the codomain become X(−, λ) and the identity respectively.

The construction of the category of elements admits the following generalization. Let Din_{X}^{∗} the category that has the functors X^{op} × X → Set as objects and the strong dinatural transformations (also known as “Barr dinatural”, see [Paré & Roman, 1998] and [Ghani, Uustalu & Vene, 2004]) as arrows. Given a functor H ∈ Din_{X}^{∗}, we define a category iH over X as follows:

• the objects over x ∈ X are the elements of H(x, x);

• given λ : x → y in X, there is at most one arrow from a ∈ H(x, x) to b ∈ H(y, y) over λ, and this is the case iff H(x, λ)a = H(λ, y)b ∈ H(x, y).

Then one easily verifies (see [Pisani, 2007]) that this constructions is the object map of a full and faithful functor

i : Din_{X}^{∗} → Cat/X  (13)

that extends both i : Set^{X^{op}} → Cat/X and i : Set^{X} → Cat/X (which come up when H is dummy in one variable). We are particularly interested in the following case: given A : X^{op} → Set and D : X → Set, let H(x, y) = Ax × Dy, that is H is the composite

\xymatrix{X^{op} × X \ar[r]^{A×D} & Set × Set \ar[r]^{×} & Set}

Then iH over X is the product iA × iD in Cat/X. Furthermore, in this case

Din_{X}(H, K) ≅ Din_{X}^{∗}(H, K) ≅ Cat/X(iH, iK)  (14)

that is, the dinatural transformations with domain H are also strongly dinatural, for any K.

2.3. Change of base and components. Let f : X → Y be a functor. As in any category with pullbacks, it gives rise to a pair of adjoint functors

f_{!} ⊣ f^{∗} : Cat/Y → Cat/X  (15)

where f_{!} is given by composition with f, while f^{∗} is obtained by pulling back in Cat. The pair f_{!} ⊣ f^{∗} satisfies the Frobenius law, that is the morphism

f_{!}π_{1} ∧ (ε ∘ f_{!}π_{2}) : f_{!}(p × f^{∗}q) → f_{!}p × q  (16)

is an isomorphism for any p ∈ Cat/X and q ∈ Cat/Y, ε being the counit of the adjunction. In particular, we get the fibers over objects or arrows of X of a category over X:

\xymatrix{P x \ar[r] \ar[d]_{x^{∗}p} & P \ar[d]^{p} & P λ \ar[r] \ar[d]_{λ^{∗}p} & P \ar[d]^{p} \\ 1 \ar[r]^{x} & X & 2 \ar[r]^{λ} & X}  (17)

The pullback of a discrete fibration is a discrete fibration; more precisely, the left hand diagram below commutes (up to isomorphisms), and so also the right hand square of left adjoints commutes:

\xymatrix{Set^{X^{op}} \ar[d]_{i} & Set^{Y^{op}} \ar[l]_{^{Set^{f}}} \ar[d]^{i} & Set^{X^{op}} \ar[r]^{∃_{f}} & Set^{Y^{op}} \\ Cat/X & Cat/Y \ar[l]_{f^{∗}} & Cat/X \ar[u]^{↓(−)} \ar[r]^{f_{!}} & Cat/Y \ar[u]_{↓(−)}}  (18)

(In particular, the fiber (iA)x of the discrete fibration iA is the discrete category on the set Ax.) We then obtain that in the diagram below

\xymatrix{Set^{X^{op}} \ar[d]_{i} \\ Cat/X \ar[r]^{↓(−)∘f_{!}} & _{Set_{Y^{op}}} \ar[ul]_{_{Set_{f}}}}  (19)

↓(−) ∘ f_{!} ⊣ i ∘ Set^{f}, and since i is full and faithful also ↓(−) ∘ f_{!} ∘ i ⊣ Set^{f}, that is the left Kan extension of A : X^{op} → Set along f^{op} can be computed by:

∃_{f}A ≅ ↓(f_{!}(iA))  (20)

In the special case Y = 1, the diagrams (18) above become

\xymatrix{Set^{X^{op}} \ar[d]_{i} & Set \ar[dl]_{Γ^{∗}} \ar[l]_{Δ} \ar[d]^{i} & Set^{X^{op}} \ar[r]^{Colim} & Set \\ Cat/X & Cat \ar[l]_{X×−} & Cat/X \ar[ur]^{Γ_{!}} \ar[u]^{↓(−)} \ar[r]^{tot} & Cat \ar[u]_{π_{0}}}  (21)

In particular, we have the functors

Γ_{!} ⊣ Γ^{∗} : Set → Cat/X  (22)

Given p : P → X in Cat/X, Γ_{!}p is the set of components of the total category P while for a set S, Γ^{∗}S is the projection X × S → X of the product of X and the discrete category on S. Furthermore, the discrete functor Γ^{∗} has a right adjoint Γ_{∗}, giving the set of points of p, that is its sections.

The formula (20) now becomes

ColimA ≅ π_{0}(tot(iA)) ≅ Γ_{!}(iA)  (23)

which expresses the colimit of a presheaf by the components of its category of elements. (Similarly, LimA = Γ_{∗}(iA).) This can be generalized as follows. Let us denote by

Coend^{∗} : Din_{X}^{∗} → Set

a left adjoint to the functor Δ : Set → Din_{X}^{∗}, defined in the usual way. Then

\xymatrix{Din_{X}^{∗} \ar[d]_{i} \\ Cat/X & Set \ar[l]_{Γ^{∗}} \ar[ul]_{Δ}}  (24)

commutes, and as above we get

Coend^{∗}H ≅ Γ_{!}(iH)  (25)

While in general Coend^{∗}H and the usual CoendH are different (see [Pisani, 2007]), by the remark at the end of section 2.1, they coincide for H(x, y) = Ax × Dy:

A ⊗ D ≅ Γ_{!}(iH) ≅ Γ_{!}(iA × iD)  (26)

Thus we are led to consider Γ_{!}(iA × iD) as a generalized tensor product, and we pose

ten := Γ_{!}(− × −) : Cat/X × Cat/X → Set  (27)

calling it the “tensor functor”.

2.4. Exponentials and complements. The category Cat is not locally cartesian closed, that is exponentials in Cat/X may not exist. When they do, the objects of p^{q} over x are the functors P x → Qx, while the arrows of p^{q} over λ are the functors P λ → Qλ over 2 (see diagram 17).

Discrete fibrations and opfibrations are exponentiable. The following particular case will be needed in the sequel (see [Pisani, 2007]):

2.5. Proposition. If iA is a discrete fibration and iD a discrete opfibration over X, then the exponential (iD)^{iA} in Cat/X is a discrete opfibration (and dually (iA)^{iD} is a discrete fibration).

Explicitly, as a covariant presheaf (iD)^{iA} is the composite

\xymatrix{X \ar[r]^{Δ} & X × X \ar[r]^{A×D} & Set^{op} × Set \ar[r]^{hom} & Set}  (28)

that is, (iD)^{iA}x = Dx^{Ax} and

(iD)^{iA}f = Df^{Af} : Dx^{Ax} → Dy^{Ay}
h ↦ Df ∘ h ∘ Af

2.6. Definition. Given p : P → X in Cat/X, a right adjoint to ten(p, −) = Γ_{!}(p × −) : Cat/X → Set is called “the complement of p” and is denoted by ¬p:

ten(p, −) ⊣ ¬p : Set → Cat/X  (29)

It is easy to see that p has a complement iff the exponential (Γ^{∗}S)^{p} exists for any set S. In this case we have

¬p ≅ (Γ^{∗}−)^{p}  (30)

In particular, since Γ^{∗}S is both a discrete fibration and a discrete opfibration for any set S, Proposition 2.5 gives the following correspective of the fact that classical complementation on the subsets of a poset takes lower sets into upper sets (and conversely):

2.7. Corollary. Any discrete fibration iA has a complement valued in discrete opfibrations (and conversely). Explicitly, as a covariant presheaf (¬ iA)S = (Γ^{∗}S)^{iA} = Set(A−, S) , that is:

(¬ iA)Sx = S^{Ax}
(¬ iA)Sf = S^{Af} : S^{Ax} → S^{Ay}
h ↦ h ∘ Af

2.8. Remark. The adjunction ten(iA, −) ⊣ ¬ iA : Set → Cat/X restricts to

A ⊗ − ⊣ Set(A−, ) : Set → Set^{X}

a particular case of the closed structure of the bicategory of distributors.

We now prove an “adjunction-like” property of the tensor functor on Cat/X which will allow us to derive directly the reflection formula.

2.9. Proposition. Let X be a category, iA a discrete fibration and iD a discrete opfibration on X. Then for any p : P → X in Cat/X there are natural bijections

ten(p, iA) ≅ ten(i↑p, iA)  ;  ten(p, iD) ≅ ten(i↓p, iD)

Proof. We prove the first one, the other being symmetrical. For any set S

ten(p, iA) → S
p → (¬ iA)S
i↑p → (¬ iA)S
ten(i↑p, iA) → S

where we have used Proposition 2.7. The result follows by Yoneda.

The following proposition can be interpreted as the fact that complementation in Cat/X is classical, when restricted to discrete fibrations and discrete opfibrations; in particular, it is possible to “recover” a discrete fibration (or presheaf) from its complement (see [Pisani, 2007]):

2.10. Proposition. If iA and iB are both discrete fibrations (or both discrete opfibrations), then there is a natural bijection

hom(iA, iB) ≅ hom(¬ iB, ¬ iA)

3. The reflection formula

The values of the “slice functors”

X/− : X → Cat/X  ;  −/X : X → Cat/X  (31)

used in the following propositions are understood with their canonical projection X/x → X and x/X → X.

3.1. Proposition. The left adjoint ↓(−) ⊣ i is given on a p : P → X by

↓p ≅ ten(−/X, p)

or equivalently ↓p ≅ Γ_{!}(−/p).

3.2. Proposition. The right adjoint i ⊣ (−)^{∘} is given on a p : P → X by

p^{∘} ≅ hom(X/−, p)

We begin with a proof of Proposition 3.1, by means of the complement operator, which has a striking similarity with that (straightforward) of Proposition 3.2.

In [Pisani, 2007] it is checked directly that the above formulas actually give the desired adjoints. For the left adjoint, this check is here superseded by reviewing other proofs of Proposition 3.2, that rest on standard completeness properties; namely on Kan extensions of set functors and on colimits of presheaves respectively.

3.3. The reflection formula via complementation. We begin by noticing that for any discrete fibration iA

Ax ≅ ten(x, iA) ≅ hom(x, iA)  (32)

Indeed, in general for any p : P → X, ten(x, p) = Γ_{!}(P x) and hom(x, p) = Γ_{∗}(P x) are the components and the objects of the fiber category over x; since iA has discrete fibers the result follows.

3.4. Proposition. Given a category p : P → X over X, the presheaf ↓p : X^{op} → Set acts on objects as follows

(↓p)x = ten(x/X, p)

Proof.

(↓p)x
ten(x, i↓p)
ten(i↑x, i↓p)
ten(i↑x, p)

where we used twice the adjunction-like properties of Proposition 2.9. The result now follows from the fact that i↑x ≅ iX(x, −) ≅ x/X (see Remark 2.2).

It is worth stressing the strong similarity between the above derivation of the reflection formula and the following derivation of the coreflection formula:

3.5. Proposition. Given a category p : P → X over X, the presheaf p^{∘} : X^{op} → Set acts on objects as follows

(p^{∘})x = hom(X/x, p)

Proof.

(p^{∘})x
hom(x, ip^{∘})
hom(i↓x, ip^{∘})
hom(i↓x, p)

where only the adjunction laws have been used.

To complete the proofs of propositions 3.1 and 3.2, note that the action of the arrows λ in X on the fibers follows from the form of the reflection ↓λ (see Remark 2.2).

3.6. The reflection formula via Kan extension. We begin by noting that the usual coend formula for the left Kan extension of a presheaf A : X^{op} → Set along a functor f : X → Y

(∃_{f}A)y ≅ A ⊗ Y (y, f−)  (33)

may be rewritten as

∃_{f}A ≅ ten(iA, −/f)  (34)

Indeed, by (26), A ⊗ Y (y, f−) ≅ ten(iA, i(Y (y, f−))) and i(Y (y, f−)) ≅ y/f. By the second of diagrams (18)

∃_{f} ↓p ≅ ↓(f_{!}p)  (35)

for any p : P → X. In particular

↓p ≅ ↓(p_{!}1_{P}) ≅ ∃_{p} ↓1_{P} ≅ ∃_{p}Δ1  (36)

where 1_{P} is the terminal discrete fibration id_{P} : P → P over P. So by the (34) above we conclude

↓p ≅ ∃_{p}Δ1 ≅ ten(iΔ1, −/p) ≅ Γ_{!}(1_{P} × −/p) ≅ Γ_{!}(−/p)  (37)

as desired. (Conversely, the reflection formula can be used to derive the coend formula (33) or (34), as shown in [Pisani, 2007].)

3.7. The reflection formula via colimits of presheaves. We begin by observing that for any p : P → X there is a bijection

Cone(p, x) ≅ Cone(1, X(p−, x)) = Cone(1, Set^{p} ↓x)  (38)

natural in x, and that by Yoneda

A ≅ Set^{y} ↓A  (39)

for any presheaf A : X^{op} → Set (on the right hand side, A is considered as an object of Set^{X^{op}}). Then we have the following chain of bijections, natural in A:

Cat/X(p, iA)
Cat/X(p_{!}1_{P} , iA)
Cat/P (1_{P} , p^{∗}(iA))
Cat/P (iΔ1, i(Set^{p}A))
Set^{P^{op}}(Δ1, Set^{p}A)
Set^{P^{op}}(Δ1, Set^{p}(Set^{y} ↓A))
Set^{P^{op}}(Δ1, Set^{y∘p} ↓A)
Cone(1, Set^{y∘p} ↓A)
Cone(y ∘ p, A)
Set^{X^{op}}(Colim(y ∘ p), A)

Thus,

↓p ≅ Colim(y ∘ p)  (40)

and since colimits in Set^{X^{op}} are computed pointwise, we get

(↓p)x ≅ (Colim(y ∘ p))x ≅ Colim((y ∘ p)x) ≅ ColimX(x, p−) ≅ Γ_{!}(x/p)  (41)

as desired.

4. Colimits as reflections

For any fixed p : P → X, we have the following bijections, natural in x:

Cat/X(p, X/x)
Cat/X(p_{!}1_{P} , X/x)
Cat/P (1_{P} , p^{∗}(X/x))
Cat/P (1_{P} , p/x)
Cat/P (iΔ1, iX(p−, x))
Set^{P^{op}}(Δ1, X(p−, x))
Cone(1, X(p−, x))
Cone(p, x)

(where (38) is used again). That is,

Cat/X(p, X/−) ≅ Cone(p, −)  (42)

4.1. Remark. Of course, this can be seen directly: a morphism p → X/x over X takes an object a ∈ P (over pa) to an object λ_{a} : pa → x (over pa) of X/x; and an arrow u : a → b in P (over pu) to a commutative triangle

[figure: pa; λ_{a}; pu; x; pb; λ_{b}]

(Composition is preserved automatically.)

So p : P → X has a colimit iff there is a universal arrow from p to X/−. If this is the case, the universal arrow is a limiting cone p → X/Colim p. Letting p vary, we in fact have two different modules “cone”

Cone : X^{P} → X  ;  Cone : Cat/X → X

both representable on the right, and so also two different operative definitions of the colimit functor: either as the partially defined left adjoint

Colim : X^{P} → X

to the functor Δ : X → X^{P} , or as the partially defined left adjoint

Colim : Cat/X → X

to the functor X/− : X → Cat/X. Dually, we have two limit functors

Lim : X^{P} → X  ;  Lim : (Cat/X)^{op} → X

respectively right adjoint to Δ : X → X^{P} and to −/X : X → (Cat/X)^{op}.

4.2. Remark. The two colimit functors (which agree on each single p : P → X as an object of two different categories) can be merged in a single

Colim : Cat/X^{∗} → X

(see [Mac Lane, 1971], [Paré, 1973] and [Kan, 1958]) where Cat/X^{∗} is the Grothendieck category associated to the 2-representable functor Cat(−, X) : Cat → Cat (which includes both Cat/X and all the X^{P} as subcategories). Indeed, we have the further module “cone” (which includes the other ones)

Cone(p, x) := Cat/X^{∗}(p, δx)

where δ : X → Cat/X^{∗} is the full and faithful functor which sends an object x ∈ X to the corresponding category over X.

The isomorphisms

Cone(p, −) ≅ Cat/X(p, X/−) ≅ Cat/X(i↓p, X/−) ≅ Cone(i↓p, −)

show that the colimits of a functor are determined by its reflection: Colim p exists iff Colim(i↓p) exists, and if this is the case they are isomorphic. Thus, if p and q in Cat/X have isomorphic reflections then

Colim p ≅ Colim q  (43)

either existing if the other one does. More than that, the same remains true after composing with any functor f : X → Y:

4.3. Proposition. Two categories p : P → X and q : Q → X over X have isomorphic reflections i↓p ≅ i↓q if and only if for any f : X → Y

Colim(f ∘ p) ≅ Colim(f ∘ q)

either side existing if the other one does.

Proof. One direction is a direct consequence of equation (40). The other follows from the isomorphisms

Cone(f ∘ p, −) ≅ Cat/Y (f_{!}p, Y/−) ≅ Cat/X(p, f^{∗}(Y/−)) ≅ Cat/X(i↓p, f/−) ≅ Cat/Y (f_{!}(i ↓p), Y/−) ≅ Cone(f ∘ (i↓p), −)

Alternatively, one could use (35) and (43).

Following [Paré, 1973], by applying Proposition 4.3 to the special cases q = id_{X} and q = x : 1 → X we obtain:

4.4. Corollary.

1. The functor p : P → X is final iff i↓p ≅ id_{X} (that is, ↓p ≅ Δ1 ).

2. The object x ∈ X is the absolute colimit of p : P → X iff i ↓p ≅ X/x (that is, ↓p ≅ X(−, x) ).

So a functor has an absolute colimit iff the “intermediate step” i↓(−) of the reflection of a category over X in principal discrete fibrations, is in fact already the final step.

4.5. Remark. Since Colim ⊣ X/− ≅ i ∘ y and i is full and faithful

\xymatrix{Set^{X^{op}} \ar[d]_{i} \\ Cat/X \ar[r]^{Colim} & X \ar[ul]_{y}}  (44)

also Colim ∘ i ⊣ y, so that the left adjoint to the Yoneda embedding has the well-known form: it takes a presheaf A to the colimit ColimiA of its category of elements over X.

By composing the adjunctions f_{!} ⊣ f^{∗} and Colim ⊣ Y/−

\xymatrix{Cat/X \ar[r]^{f_{!}}_{⊥} \ar[rr]^{Colim(f∘−)} & Cat/Y \ar[l]^{f^{∗}} \ar[r]^{Colim}_{⊥} & Y \ar[l]^{Y/−} \ar[ll]^{f/−}}  (45)

we get

Colim(f ∘ −) ⊣ f/− : Y → Cat/X  (46)

And since f/− ≅ i ∘ Set^{f} ∘ y

\xymatrix{Set^{X^{op}} \ar[d]_{i} \\ Cat/X \ar[r]^{Colim(f∘−)} & Y \ar[ul]_{Set^{f} ∘y}}  (47)

as above we get

Colim(f ∘ i−) ⊣ Set^{f} ∘ y  (48)

where the left adjoint takes a presheaf A to the weighted colimit A ∗ f ≅ Colim(f ∘ iA), displaying it as a colimit.

In the particular case Y = Set, the adjunction (46) is the (dual of) ten(A, −) ⊣ ¬A of section 2.4, while the adjunction (48) becomes the (dual of) A ⊗ − ⊣ Set(A−, ).

5. Atoms and their reflections

We say that a category t : T → X over X is a “left atom” if there are bijections

ten(t, iA) ≅ hom(t, iA)

natural in A ∈ Set^{X^{op}}. Dually, t is a “right atom” if

ten(t, iD) ≅ hom(t, iD)

natural in D ∈ Set^{X}. We say that t is an atom if it is both a left and a right atom. We shall see that the distinction between left and right atoms is illusory. Observe that any object x : 1 → X of the base category X is an atom (see (32)).

5.1. Proposition. For any functor f : X → Y there are bijections

ten_{X}(p, f^{∗}q) ≅ ten_{Y} (f_{!}p, q)

natural in p ∈ Cat/X and q ∈ Cat/Y.

Proof. Using the Frobenius law (16), we have:

ten_{X}(p, f^{∗}q) = Γ_{!}(p × f^{∗}q) ≅ Γ_{!}(f_{!}(p × f^{∗}q)) ≅ Γ_{!}(f_{!}p × q) = ten_{Y} (f_{!}p, q)  (49)

5.2. Corollary. Let f : X → Y any functor. Then for any atom t : T → X in Cat/X, f_{!}t : T → Y is an atom in Cat/Y.

Proof. We have the following chain of natural bijections:

ten_{Y} (f_{!}x, D) ≅ ten_{X}(x, f^{∗}D) ≅ hom_{X}(x, f^{∗}D) ≅ hom_{Y} (f_{!}x, D)

We now show that idempotent arrows of the base category are atoms. This is essentially the fact that in the graph corresponding to an idempotent endomapping, the fixed points (or loops) correspond to the components. Let e be the monoid which represents the idempotent arrows of categories, that is the one whose unique non-identity arrow is idempotent.

5.3. Proposition. Any idempotent e : e → X in X is an atom. For any discrete fibration or discrete opfibration D on X, ten(e, iD) ≅ hom(e, iD) is the set fixDe of the elements of Dx fixed by De : Dx → Dx.

Proof. For any discrete fibration or discrete opfibration iD,

ten(e, iD) ≅ Γ_{!}(e × iD) ≅ Γ_{!}(e^{∗}(iD)) ≅ Γ_{!} i(Set^{e}D) ≅ Colim(Set^{e}D)
hom(e, iD) ≅ hom(1_{e}, e^{∗}(iD)) ≅ Γ_{∗}(e^{∗}(iD)) ≅ Γ_{∗} i(Set^{e}D) ≅ Lim(Set^{e}D)

But for any functor e : e → C, the limit and the colimit of e, when they exist, are canonically isomorphic (see [Borceux, 1994]). If C = Set these are given by the fixed points of the idempotent mapping.

Note that in this context it is important to distinguish between idempotent arrows as defined above, and arrows e : 2 → X which happen to be idempotent endomorphisms; an arrow λ : 2 → X is an atom iff it is an isomorphism.

5.4. Proposition. For any t : T → X, t is a right atom iff

↓t ⊗ − ≅ Nat(↑t, −) : Set^{X} → Set

Dually, t is a left atom iff

− ⊗↑t ≅ Nat(↓t, −) : Set^{X^{op}} → Set

In particular, for any idempotent atom e : e → X,

↓e ⊗ D ≅ Nat(↑e, D) ≅ fixDe  ;  A ⊗ ↑e ≅ Nat(↓e, A) ≅ fixAe

Proof. Recalling Proposition 2.9, one has the following bijections, natural in D ∈ Set^{X}:

Nat(↑t, D) ≅ hom(i ↑t, iD) ≅ hom(t, iD)
↓t ⊗ D ≅ ten(i ↓t, iD) ≅ ten(t, iD)

5.5. Corollary. For any idempotent e : x_{0} → x_{0} in X,

↓e ≅ fixX(−, e)

that is ↓e the subfunctor of ↓x_{0} = X(−, x_{0}) given by the arrows fixed by composition with e:

λ : x → x_{0} ∈ (↓e)x ⟺ e ∘ λ = λ

For any idempotents e : x → x and e′ : y → y in X, Nat(↓e, ↓e′) is the set of arrows λ : x → y such that λ ∘ e = λ = e′ ∘ λ.

Proof. For the first part, we have

(↓e)x ≅ ↓e ⊗↑x ≅ Nat(↑e, ↑x) ≅ fix((↑x)e) ≅ fixX(x, e)

The second part follows from the first, since Nat(↓e, ↓e′) ≅ fix(↓e′)e.

By Yoneda, any idempotent in Set^{X^{op}} on a representable X(−, x_{0}) has the form

X(−, e) : X(−, x_{0}) → X(−, x_{0})

for a unique idempotent e : x_{0} → x_{0} in X.

5.6. Corollary. Let A : X^{op} → Set be a presheaf on X. Then A is a retract in Set^{X^{op}} of the representable functor X(−, x_{0}), associated to the idempotent X(−, e) : X(−, x_{0}) → X(−, x_{0}), if and only if A ≅ ↓e.

Proof. The retract A is the limit of X(−, e) : e → Set^{X^{op}}, and thus is given pointwise by Ax ≅ fixX(x, e). The result then follows by Corollary 5.5.

34  CLAUDIO PISANI

5.7. Proposition. Let A : X^{op} → Set and D : X → Set be such that

− ⊗ D ≅ Nat(A, −) : Set^{X^{op}} → Set

Then A is a retract in Set^{X^{op}} of a representable functor. Proof. Let u ∈ A ⊗ D ≅ Γ_{!}(iA × iD) be a universal element of − ⊗ D. Then u is the component of a pair ⟨a, d⟩ over, say, x_{0} ∈ X:

u = [⟨a, d⟩], a ∈ Ax_{0}, d ∈ Dx_{0}

Let ι : A → X(−, x_{0}) be the unique morphism in Set^{X^{op}} such that (ι ⊗ D)u = [⟨id_{x_{0}}, d⟩]:

[⟨id_{x_{0}}, d⟩] = (ι ⊗ D)u ≅ Γ_{!}(ι × iD)[⟨a, d⟩] = [⟨ιa, d⟩]

and let ρ : X(−, x_{0}) → A be the unique morphism in Set^{X^{op}} such that ρ id_{x_{0}} = a. Then

(ρ ∘ ι) ⊗ D ≅ Γ_{!}((ρ ∘ ι) × iD) : [⟨a, d⟩] ↦ [⟨a, d⟩]

so that ρ ∘ ι = id_{A}, as required. 5.8. Proposition. Let A : X^{op} → Set and D : X → Set. The following are equivalent:

1. A ⊗ − ≅ Nat(D, −) : Set^{X} → Set.

2. − ⊗ D ≅ Nat(A, −) : Set^{X^{op}} → Set.

3. A ≅ ↓e and D ≅ ↑e, for an idempotent atom e.

4. A ≅ ↓t and D ≅ ↑t, for an atom t. Proof. Trivially 3 implies 4, and 4 implies 1 and 2 by Proposition 5.4. From Proposition 5.7 and Corollary 5.6 it follows that 2 implies that A ≅ ↓e. Furthermore,

D ≅ ↓− ⊗ D ≅ Nat(A, ↓−) ≅ Nat(↓e, ↓−) ≅ ↓− ⊗ ↑e ≅ ↑e

where Proposition 5.4 have been used again. Thus 2 implies 3. Since 1 and 2 are dual and 3 is autodual, also 1 implies 3. 5.9. Remark. In [Kelly & Schmitt, 2005] it is shown, in an enriched context, the equivalence between 1 and 2 and the fact that A and D are adjoint modules.

By Proposition 5.4 and the equivalence between 1 and 2 in Proposition 5.8, it follows 5.10. Corollary. Any right atom is also a left atom, and vice versa.

By Proposition 5.8, for any atom t : T → X there exists an idempotent e : x → x in X such that ↑t ≅ ↑e and ↓t ≅ ↓e. This idempotent is not unique, since for example if e splits as x →^{r} y →^{i} x, then ↓e ≅ ↓y.

5.11. Corollary. For an atom T →^{t} X the following are equivalent:

1. t has a limit.

2. t has a colimit.

3. t has an absolute limit.

4. t has an absolute colimit.

Proof. Indeed, all the above are equivalent for any e : e → X (see [Borceux, 1994]), and so by propositions 4.3 and 4.4 they are equivalent also for t.

5.12. Remark. If the conditions of the above proposition are satisfied, that is if ↓t ≅ ↓x for an object x ∈ X, we could say that t “converges” to its (co)limit x. In particular, any split idempotent in X converges to its retracts, and a category is Cauchy complete iff any atom converges. Furthermore, any functor f : X → Y is “continuous”: if t converges to x, then f_{!}t converges to fx (see Corollary 5.2 and Proposition 4.3).

Recall that the Cauchy completion of a category can be obtained as the full subcategory of Set^{X^{op}} generated by the retracts of representable functors (see for example [Borceux, 1994]). But we have seen that the latter have the form ↓t or ↓e, and so we get the first part of the following proposition. The second part is in Corollary 5.5.

5.13. Proposition. The reflections of atoms (or of idempotent atoms) in discrete fibrations generate the Cauchy completion of X. Furthermore, given two idempotent arrows e : x → x and e′ : y → y in X, hom(↓e, ↓e′) is the set of arrows f : x → y such that f ∘ e = f = e′ ∘ f. So the Cauchy completion is the same thing as the “Karoubi envelope” of X (see [La Palme, Reyes & Zolfaghari, 2004], [Lambek & Scott, 1986] and [Lawvere, 1989]).

6. Graphs and evolutive sets

As a particular case of the reflection formula, consider X = N, the monoid of natural numbers, as the base category. Then we have the adjunction

↑(−) ⊣ i : Set^{N} → Cat/N  (50)

with the usual formula: for any p : P → N,

(↑p)⋆ ≅ ten(N /⋆, p)  (51)

where ⋆ is the only object of N, so that N /⋆ is (opposite of) the poset of natural numbers, with its projection on N. The action is given by the right shift:

k : [n, a] ↦ [n + k, a] (a ∈ P)

Among the categories over N there are the unique factorization lifting (UFL) functors (see [Bunge & Niefield, 2000]), which include discrete fibrations and discrete opfibration, and which can be identified with (irreflexive) graphs as follows. For any G ∈ Gph we have the UFL functor F! : FG → FL ≅ N, where L is the terminal graph (the loop), and F : Gph → Cat is the free category functor; slightly improperly, we denote by F also the resulting functor F : Gph → Cat/N. Conversely, for any UFL functor p : P → N we get a graph G by the pullback below (in Gph):

\xymatrix{G \ar[r] \ar[d]_{η^{∗}|p|} & |P | \ar[d]^{|p|} \\ L \ar[r]^{η} & |N |}  (52)

that is, the arrows of G are those of |P | which are over 1 ∈ N. It is easy to see that we so obtain an equivalence between Gph and the full subcategory of Cat/N of UFL functors. Furthermore, since UFL functors are closed under pullbacks, the functor F : Gph → Cat/N preserves products: F(G × H) ≅ FG × FH. And since a graph and the free category on it have the same components, F : Gph → Cat/N also preserves components: Γ_{!}G ≅ Γ_{!}FG. Thus in the particular case that p : P → N is an UFL functor FG → N, the reflection formula (51) takes the following form:

(↑FG)⋆ ≅ ten(N /⋆, FG) ≅ ten(FA, FG) ≅ Γ_{!}(FA × FG)
≅ Γ_{!}(F(A × G)) ≅ Γ_{!}(A × G)  (53)

where A ∈ Gph is the infinite anti-chain:

[figure: •; •; •; •; •]

Thus the formula (53) gives a left adjoint to Set^{N} → Gph, or equivalently the reflection (−)^{−} of graphs in those with a bijective domain mapping: given G ∈ Gph, the nodes of G^{−} are the components of A × G, while the only arrow out of the node [n, x] ∈ Γ_{!}(A × G), is

[n, x] → [n + 1, x]

that is, the evolution of G^{−} is given by the shift of the anti-chain A.

6.1. Remark. “Dually”, the coreflection G^{∘} is given by the set of its chains Gph(A^{op}, G), with the evolution given by the shift of the generic chain A^{op}:

[figure: •; •; •; •; •]

6.2. Remark. Similarly, one gets the reflection formula for graphs over a base graph G in graph (op)fibrations over G (see [Boldi & Vigna, 2002]); or equivalently, the left adjoint to the inclusion Set^{FG} → Gph/G (see [Pisani, 2007] and [Pisani, 2005]).

6.3. Examples.

1. Let G be the graph \xymatrix{• \ar[r] & •} which is not an evolutive set because there are no arrows out of the second node. Applying the reflection formula, we multiply G by the anti-chain A, getting the graph

[figure: •; •; •; •; •; •; •; •; •; •]

with an infinite number of components, which are the nodes of the reflection of G. Furthermore, the action on it is given by translation, which sends any component in the one on its right. So G^{−} is the chain [figure: •; •; •; •; •] , wherein the missing codomains in G have been added. On the other hand, there are no chains in G, so that the coreflection G^{∘} is void: the nodes with no codomains have been deleted.

2. Let G be the graph [figure: •; •; •] which is not an evolutive set because there are two arrows out of one node. Applying the reflection formula, we multiply G by the anti-chain A, getting the two-components graph

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

So the reflection of G has two nodes. Furthermore, the action on it is given again by right translation, so that the second component is a fixed point and we get

G^{−} = [figure: •; •]

wherein the multiple codomains in G have been identified. On the other hand, there are four chains in G so that G^{∘} has four nodes:

G^{∘} = [figure: •; •; •; •]

that is, the nodes with multiple codomains have been split.

3. If G = \xymatrix{• \ar[rr] & • \ar[l] \ar[r] & •}, A × G is the graph

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

so that G^{−} = [figure: •; •] again. One should compare this example with the technique used in [La Palme, Reyes & Zolfaghari, 2004] to compute the same reflection.

4. An example where both the phenomena of adding and identifying codomains, are present is given by the graph \xymatrix{• & • \ar[l] \ar[r] & •} , whose reflection is again the chain.

5. If G_{1} = [figure: •; •], G_{2} = [figure: •; •] and G_{3} = [figure: •] , then G_{1}^{−}, G_{2}^{−} and G_{3}^{−} are all the loop (identification prevails in G_{1}^{−}). As for coreflections, G_{1}^{∘} is the loop, G_{2}^{∘} is the sum of the loop and the anti-chain with a loop added at its end, and G_{3}^{∘} is the set of sequences in a two-element set, under the action s ↦ s(1 + ).

Now, let e the “idempotent arrow” category of Section 5, and f : N → e the functor which takes 1 ∈ N to the non-identity arrow of e. The composite

\xymatrix{Set^{e} \ar[r]^{^{Set^{f}}} & Set^{N} \ar[r]^{i} & Cat/N}

has a left adjoint

l := ∃_{f} ∘↑(−) ≅ ↑(−) ∘ f_{!} : Cat/N → Set^{e}

(see diagrams 18). Then (recalling Proposition 5.1)

(lp)⋆ ≅ ten_{e}(e/⋆, f_{!}p) ≅ ten_{N} (f^{∗}(e/⋆), p)  (54)

where ⋆ is the only object of e, so that e/⋆ is the category [figure: •; •] (only nonidentity arrows drawn) with its projection on e, and f^{∗}(e/⋆) ≅ FE where E is the graph [figure: •; •] . Thus, as above, the nodes of the reflection G^{−} of the graph G in idempotent evolutive sets are the components of the product E × G in Gph. The action is given again by the “shift” in E. (Of course, one has also the corresponding coreflection formula: Gph(E, G) gives the nodes of the coreflection G^{∘}.)

Similarly, to obtain the nodes of the reflections of a graph G in bijective or n-periodic evolutive sets, we have to take the components of the products Z × G and Z_{n} × G respectively, with the graphs Z and Z_{n} below

[figure: Z =; •; •; •; •; •]  (55)
Z_{n} = \xymatrix{• \ar[r] & • \ar@{.>}[dl] \\ • \ar[u]} (n arrows)  (56)

6.4. Examples.

1. It is easy to see that if G is connected (that is, Γ_{!}G = 1) then E × G has n + 1 components, where n is the number of nodes that are not codomains of any arrow. So the reflection in idempotent evolutive sets acts on each component by maintaining such nodes, and collapsing the rest of it to the fixed point.

2. The reflection G^{−} of a graph G in n-periodic evolutive sets is obtained by taking the components of Z_{n} × G. Since, as it is easily checked,

Z_{k} × Z_{n} = gcd(k, n) · Z_{lcm(k,n)}

we deduce that Z_{k}^{−} has gcd(k, n) nodes and so, being connected,

Z_{k}^{−} = Z_{gcd(k,n)}

Since any bijective evolutive set is a sum of cycles, G = ∑_{k=1}^{∞} S_{k} · Z_{k}, its n-periodic reflection is given by

G^{−} = ( ∑_{k=1}^{∞} S_{k} · Z_{k})^{−} = ∑_{k=1}^{∞} S_{k} · Z_{k}^{−} = ∑_{k=1}^{∞} S_{k} · Z_{gcd(k,n)}

6.5. Remark. Considering Gph as a presheaf category (rather than a subcategory of Cat/N), all the above reflections become instances of Kan extensions. But the present approach gives a more direct and intuitive way of computing them.

References

F. Borceux (1994), Handbook of Categorical Algebra 1 (Basic Category Theory), Encyclopedia of Mathematics and its applications, vol. 50, Cambridge University Press.

M. Bunge and S. Niefeld (2000), Exponentiability and Single Universes, J. Pure Appl. Algebra 148, 217-250.

N. Ghani, T. Uustalu and V. Vene (2004), Build, Augment and Destroy. Universally, Proceeding of the Asian Symposium on Programming Languages, LNCS 3302, Springer, Berlin, 327-347.

D.M. Kan (1958), Adjoint Functors, Trans. Am. Math. Soc. 87, 294-329.

G.M. Kelly and V. Schmitt (2005), Notes on Enriched Categories with Colimits of some Class, Theory and Appl. Cat. 17, 399-423.

J. Lambek and P.J. Scott (1986), Introduction to Higher Order Categorical Logic, Cambridge studies in advanced mathematics, vol. 7, Cambridge University Press.

M. La Palme Reyes, G.E. Reyes, H. Zolfaghari (2004), Generic Figures and their Glueings, Polimetrica S.a.s., Monza.

F.W. Lawvere (1970), Equality in Hyperdoctrines and the Comprehension Scheme as an Adjoint Functor, Proceedings of the AMS Symposium on Pure Mathematics, XVII, 1-14.

F.W. Lawvere (1973), Metric Spaces, Generalized Logic and Closed Categories, Rend. Sem. Mat. Fis. Milano 43, 135-166. Republished in Reprints in Theory and Appl. Cat. No. 1 (2002) 1-37.

F.W. Lawvere (1989), Qualitative Distinctions between some Toposes of Generalized Graphs, Proceedings of the AMS Symposium on Categories in Computer Science and Logic, Contemporary Mathematics, vol. 92, 261-299.

F.W. Lawvere (1996), Adjoints in and among Bicategories, Proceedings of the 1994 Conference in Memory of Roberto Magari, Logic & Algebra, Lectures Notes in Pure and Applied Algebra, 180:181-189, Ed. Ursini Aglianò, Marcel Dekker, Inc. Basel, New York.

S. Mac Lane (1971), Categories for the Working Mathematician, Graduate Texts in Mathematics, vol. 5, Springer, Berlin.

R. Paré (1973), Connected Components and Colimits, J. Pure Appl. Algebra 3, 21-42.

R. Paré and L. Román (1998), Dinatural Numbers, J. Pure Appl. Algebra 128(1), 33-92.

C. Pisani (2005), Bipolar Spaces, preprint, math.CT/0512194.

C. Pisani (2007), Components, Complements and Reflection Formulas, preprint, math.- CT/0701457.

P. Boldi, S. Vigna (2002), Fibrations of Graphs, Discrete Math. 243, 21-66.

via Gioberti 86, 10128 Torino, Italy.

Email: pisclau@yahoo.it

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

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/19/2/19-02.{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. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. 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 strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

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@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