Category of elements

In category theory, a branch of mathematics, the category of elements of a presheaf is a category associated to that presheaf whose objects are the elements of sets in the presheaf. It and its generalization are also known as the Grothendieck construction (named after Alexander Grothendieck) especially in the theory of descent, in the theory of stacks, and in fibred category theory.^[1]

The Grothendieck construction is an instance of straightening (or rather unstraightening).

Significance

In categorical logic, the construction is used to model the relationship between a type theory and a logic over that type theory, and allows for the translation of concepts from indexed category theory into fibred category theory, such as Lawvere's concept of hyperdoctrine.

The category of elements of a simplicial set is fundamental in simplicial homotopy theory, a branch of algebraic topology. More generally, the category of elements plays a key role in the proof that every weighted colimit^{[clarification needed]} can be expressed as an ordinary colimit, which is in turn necessary for the basic results in theory of pointwise left Kan extensions, and the characterization of the presheaf category as the free cocompletion of a category.^{[citation needed]} See also Density theorem (category theory) for an example usage.

Motivation

If ${\displaystyle \left\{A_{i}\right\}_{i\in I}}$ is a family of sets indexed by another set, one can form the disjoint union or coproduct

${\displaystyle \coprod _{i\in I}A_{i}}$,

which is the set of all ordered pairs ${\displaystyle (i,a)}$ such that ${\displaystyle a\in A_{i}}$. The disjoint union set is naturally equipped with a "projection" map

${\displaystyle \pi$ :\coprod _{i\in I}A_{i}\to I,\,\pi (i,a)=i.}

From the projection ${\displaystyle \pi }$ it is possible to reconstruct the original family of sets ${\displaystyle \left\{A_{i}\right\}_{i\in I}}$ up to a canonical bijection, as for each ${\displaystyle i\in I,A_{i}\cong \pi ^{-1}(\{i\})}$ via the bijection ${\displaystyle a\mapsto (i,a)}$. In this context, for ${\displaystyle i\in I}$, the preimage ${\displaystyle \pi ^{-1}(\{i\})}$ of the singleton set ${\displaystyle \{i\}}$ is called the "fiber" of ${\displaystyle \pi }$ over ${\displaystyle i}$, and any set ${\displaystyle B}$ equipped with a choice of function ${\displaystyle f:B\to I}$ is said to be "fibered" over ${\displaystyle I}$. In this way, the disjoint union construction provides a way of viewing any family of sets indexed by ${\displaystyle I}$ as a set "fibered" over ${\displaystyle I}$, and conversely, for any set ${\displaystyle f:B\to I}$ fibered over ${\displaystyle I}$, we can view it as the disjoint union of the fibers of ${\displaystyle f}$. Jacobs has referred to these two perspectives as "display indexing" and "pointwise indexing".^[2]

The Grothendieck construction generalizes this to categories. For each category ${\displaystyle {\mathcal {C}}}$, family of categories ${\displaystyle \{F(c)\}_{c\in {\mathcal {C}}}}$ indexed by the objects of ${\displaystyle {\mathcal {C}}}$ in a functorial way, the Grothendieck construction returns a new category ${\displaystyle {\mathcal {E}}}$ fibered over ${\displaystyle {\mathcal {C}}}$ by a functor ${\displaystyle \pi }$ whose fibers are the categories ${\displaystyle \{F(c)\}_{c\in {\mathcal {C}}}}$.

Construction

Let ${\displaystyle C}$ be a category and let ${\displaystyle F:C^{\rm {op}}\to \mathbf {Sets} }$ be a set-valued functor. The category el(F) of elements of F (also denoted ∫_C F) is the category whose:

• Objects are pairs ${\displaystyle (A,a)}$ where ${\displaystyle A\in \mathop {\rm {Ob}} (C)}$ and ${\displaystyle a\in FA}$.
• Morphisms ${\displaystyle (A,a)\to (B,b)}$ are arrows ${\displaystyle f:A\to B}$ of ${\displaystyle C}$ such that ${\displaystyle (Ff)b=a}$.

An equivalent definition is that the category of elements of ${\displaystyle F}$ is the comma category ∗↓F, where ∗ is a singleton (a set with one element).

The category of elements of F is naturally equipped with a projection functor Π: ∫_C F→C that sends an object (A, a) to A, and an arrow (A,a)→(B,b) to its underlying arrow in C.

For small C, this construction can be extended into a functor ∫_C from Ĉ to Cat, the category of small categories. Using the Yoneda lemma one can show that ∫_C P≅y↓P, where y:C→Ĉ is the Yoneda embedding.^{[citation needed]} This isomorphism is natural in P and thus the functor ∫_C is naturally isomorphic to y↓–:Ĉ→Cat.

For some applications, it is important to generalize the construction to even a contravariant pseudofunctor ${\displaystyle F}$ (the covariant case is similar). Namely, given ${\displaystyle F}$, define the category ${\displaystyle C_{F}}$, where

• an object is a pair ${\displaystyle (x,a)}$ consisting of an object ${\displaystyle x}$ in ${\displaystyle C}$ and an object ${\displaystyle a}$ in ${\displaystyle F(x)}$,
• a morphism ${\displaystyle {\overline {f}}:(x,a)\to (y,b)}$ consists of ${\displaystyle f:x\to y}$ in ${\displaystyle C}$ and ${\displaystyle \varphi$ :(Ff)b\to a} in ${\displaystyle F(x)}$,
• the composition of ${\displaystyle {\overline {f}}}$ above and ${\displaystyle {\overline {g}}=(g,\psi ):(y,b)\to (z,c)}$ consists of ${\displaystyle g\circ f}$ and ${\displaystyle \varphi \circ (Ff)\psi }$; i.e.,

${\displaystyle F(g\circ f)c\simeq (Ff\circ Fg)c{\overset {(Ff)\psi }{\to }}(Ff)b{\overset {\varphi }{\to }}a.}$^[3]

Perhaps it is psychologically helpful to think of ${\displaystyle Ff}$ as the pullback along ${\displaystyle f}$ (i.e., ${\displaystyle Ff=f^{*}}$) and then ${\displaystyle (Ff)b}$ is the pullback of ${\displaystyle b}$ along ${\displaystyle f}$.

Note here the associativity of the composition is a consequence of the fact that the isomorphisms ${\displaystyle F(g\circ f)\simeq Ff\circ Fg}$ are coherent.

Examples

Group

If ${\displaystyle G}$ is a group, then it can be viewed as a category, ${\displaystyle {\mathcal {C}}_{G},}$ with one object and all morphisms invertible. Let ${\displaystyle F:{\mathcal {C}}_{G}\to \mathbf {Cat} }$ be a functor whose value at the sole object of ${\displaystyle {\mathcal {C}}_{G}}$ is the category ${\displaystyle {\mathcal {C}}_{H},}$ a category representing the group ${\displaystyle H}$ in the same way. The requirement that ${\displaystyle F}$ be a functor is then equivalent to specifying a group homomorphism ${\displaystyle \varphi :G\to \operatorname {Aut} (H),}$ where ${\displaystyle \operatorname {Aut} (H)}$ denotes the group of automorphisms of ${\displaystyle H.}$ Finally, the Grothendieck construction, ${\displaystyle F\rtimes {\mathcal {C}}_{G},}$ results in a category with one object, which can again be viewed as a group, and in this case, the resulting group is (isomorphic to) the semidirect product ${\displaystyle H\rtimes _{\varphi }G.}$

Representable functor

Given a category C and a fixed object * in it, take ${\displaystyle F=\operatorname {Hom} (-,*)}$, the contravariant functor represented by *. Then the category ${\displaystyle C_{F}}$ associated to it by the Grothendieck construction is exactly the comma category ${\displaystyle C\downarrow *}$.^[4] Indeed, if ${\displaystyle (x,a)}$ is an object in ${\displaystyle C_{F}}$, then ${\displaystyle a:x\to *}$. If ${\displaystyle (f,\varphi ):(x,a)\to (y,b)}$ is a morphism in ${\displaystyle C_{F}}$, then ${\displaystyle \varphi :b\circ f\to a}$. But ${\displaystyle \varphi }$ is supposed to be a morphism in ${\displaystyle F(x)}$, which is a hom-set; in particular, a set. Thus, ${\displaystyle \varphi }$ is the identity and thus ${\displaystyle b\circ f=a}$; i.e., ${\displaystyle f}$ is a map over *.

Twisted arrows

Main article: Twisted diagonal (category theory)

Given a category C, take ${\displaystyle F}$ to be the hom-functor

${\displaystyle \operatorname {Hom} :C^{op}\times C\to {\textbf {Set}},}$

where ${\displaystyle \times }$ denotes a product of categories. Then the category of elements for ${\displaystyle F}$ is known as the category of twisted arrows in C.^[5] The opposite of it is known as the twisted diagonal of C.

Homotopy colimit

Let ${\displaystyle X:I\to {\textbf {Set}}}$ be a functor (thought of as a diagram) and ${\displaystyle EX}$ the category of elements for ${\displaystyle X}$. The nerve of ${\displaystyle EX}$ is a simplicial set that is isomorphic to the homotopy colimit of ${\displaystyle X}$ by Thomason's homotopy colimit theorem:

${\displaystyle \operatorname {hocolim} X\simeq N(EX).}$

Sometimes, this is taken as a definition of a homotopy colimit.^[6]

More generally, if ${\displaystyle X:I\to {\textbf {sSet}}}$ is a simplicial diagram, then taking the above colimit for each ${\displaystyle X_{n}}$, one also gets the homotopy colimit of X as well.

As a cartesian fibration

Let ${\displaystyle \pi :C_{F}\to C}$ be the forgetful functor and the category associated to a contravariant pseudofunctor ${\displaystyle F}$ on ${\displaystyle C}$ by the Grothendieck construction. A key property is that ${\displaystyle \pi }$ is a cartesian fibration (or that ${\displaystyle C_{F}}$ is a category fibered over ${\displaystyle C}$), meaning each morphism ${\displaystyle f:x\to y}$ in ${\displaystyle C}$ with target ${\displaystyle y=\pi ((y,b))}$ lifts to a cartesian morphism ${\displaystyle {\overline {f}}}$ with target ${\displaystyle {\overline {y}}=(y,b)}$.^[3] Indeed, we simply let ${\displaystyle {\overline {x}}=(x,a),\,a=(Ff)(b)}$ and ${\displaystyle {\overline {f}}=(f,\operatorname {id} _{a}).}$ The required lifting property then holds trivially.

Next, if ${\displaystyle \mu :F\to G}$ is a natural transformation (between contravariant pseudofunctors), then ${\displaystyle \mu }$ induces a functor

${\displaystyle \mu :C_{F}\to C_{G}}$

that sends cartesian morphisms to cartesian morphisms. Indeed, for objects, we let ${\displaystyle \mu ((x,a))=(x,\mu (a))}$ through ${\displaystyle \mu :F(x)\to G(x)}$. As for a morphism ${\displaystyle {\overline {f}}=(f,(Ff)b\,{\overset {\varphi }{\to }}\,a):{\overline {x}}\to {\overline {y}}}$, we let ${\displaystyle \mu ({\overline {f}})=(f,\mu (\varphi ))}$ where ${\displaystyle \mu (\varphi ):\mu (Ff)b=(Gf)\mu (b)\to \mu (a)}$. Now, if ${\displaystyle f':x'\to {\overline {y}}}$ is an arbitrary cartesian morphism, then since ${\displaystyle x',{\overline {x}}}$ are isomorphic, we see that ${\displaystyle \varphi _{f'}}$ is invertible and thus ${\displaystyle \mu (\varphi _{f'})}$ is invertible. It follows that ${\displaystyle \mu (f')}$ has the required lifting property to be a cartesian morphism, completing the proof of the claim.

Formulation in ∞-categories

Using the language of ∞-categories, the Grothendieck construction can be stated in the following succint way. Namely, it says there is an equivalence of ∞-categories:

${\displaystyle {\textrm {Fct}}(C^{op},{\textrm {Cat}})\to {\textrm {Cart}}(C)}$

between the functor category and the (2, 1)-category of cartesian fibrations (or fibered categories) over ${\displaystyle C}$.^[7] Moreover, the equivalence is given by sending the pseudofunctor ${\displaystyle F:C^{op}\to {\textrm {Cat}}}$ to the category ${\displaystyle C_{F}}$ of pairs for ${\displaystyle F}$ (see above) and the opposite direction by taking fibers; i.e., ${\displaystyle \pi }$ is mapped to the pseudofunctor ${\displaystyle X\mapsto \pi ^{-1}(X)}$.

In more details, given a cartesian fibration ${\displaystyle \pi }$, define the contravariant pseudofunctor ${\displaystyle F}$ as follows.^[8] For an object ${\displaystyle x}$, ${\displaystyle F(x)=\pi ^{-1}(x)}$. Next, since ${\displaystyle \pi }$ is a cartesian fibration, for each morphism ${\displaystyle f:x\to y}$ and each object ${\displaystyle {\overline {y}}}$ in ${\displaystyle \pi ^{-1}(y)}$, there is an object ${\displaystyle {\overline {x}}}$ in ${\displaystyle \pi ^{-1}(x)}$ as well as a cartesian morphism ${\displaystyle {\overline {f}}:{\overline {x}}\to {\overline {y}}}$ in ${\displaystyle \pi ^{-1}(f)}$. By the axiom of choice, for each ${\displaystyle {\overline {y}}}$, we thus choose ${\displaystyle (Ff){\overline {y}}}$ in ${\displaystyle \pi ^{-1}(x)}$ as well as a cartesian morphism ${\displaystyle {\overline {f}}_{\overline {y}}:(Ff){\overline {y}}\to {\overline {y}}}$. To simplify the notation, we shall let ${\displaystyle f^{*}=Ff}$. We now make

${\displaystyle f^{*}:\pi ^{-1}(y)\to \pi ^{-1}(x)}$

a functor; i.e., it also sends morphisms. If ${\displaystyle \alpha$ :{\overline {y}}_{1}\to {\overline {y}}_{2}} is a morphism in ${\displaystyle \pi ^{-1}(y)}$, since ${\displaystyle {\overline {f}}:f^{*}{\overline {y}}_{2}\to {\overline {y}}_{2}}$ is cartesian, there is a unique morphism ${\displaystyle f^{*}{\overline {y}}_{1}\to f^{*}{\overline {y}}_{2}}$, which we denote by ${\displaystyle f^{*}\alpha }$, such that ${\displaystyle \alpha \circ {\overline {f}}_{{\overline {y}}_{1}}={\overline {f}}_{{\overline {y}}_{2}}\circ f^{*}\alpha }$. By the uniqueness of choices, we have ${\displaystyle f^{*}(\alpha \circ \beta )=f^{*}\alpha \circ f^{*}\beta }$. Thus, ${\displaystyle Ff=f^{*}}$ is a functor. Hence, ${\displaystyle F:C^{op}\to {\textbf {Cat}}}$ is defined. Finally, we show ${\displaystyle F}$ is a contravariant pseudofunctor. Roughly, this is because, even though we made a choice using the axiom of choice, different choices differ by unique isomorphisms. Consequently, the isomorphisms ${\displaystyle F(g\circ f)\simeq (Fg)(Ff)}$ will be coherent.