ncatlab.org

codensity monad in nLab

Contents

Context

Category Theory

universal construction

applications of (higher) category theory

Idea

Recall (eg. from here) that every right adjoint functor F⊣G:ℬ→𝒜F\dashv G \,\colon\, \mathcal{B}\to\mathcal{A} induces a monad on 𝒜\mathcal{A} whose underlying endofunctor is G∘FG\circ F.

The notion of the codensity monad 𝕋 G\mathbb{T}^G is a generalization of this construction to functors G:ℬ→𝒜G \colon \mathcal{B}\to\mathcal{A} that need not be right adjoints but do at least admit a right Kan extension Ran GGRan_G G along themselves, such that both constructions agree when GG is in fact a right adjoint.

The name ‘codensity monad’ stems from the fact that 𝕋 G\mathbb{T}^G reduces to the identity monad iff G:ℬ→𝒜G \colon \mathcal{B}\to\mathcal{A} is a codense functor. Thus, in general, the codensity monad “measures the failure of GG to be codense”.

The same idea applies to 2-categories or bicategories more general than Cat: codensity monads can be defined whenever suitable right Kan extensions exist.

Definition

(codensity monad)
Let G:ℬ→𝒜G \colon \mathcal{B}\to\mathcal{A} be a functor whose pointwise right Kan extension Ran GG≡(T G,α)Ran_G G \,\equiv\, (T^G,\;\alpha) along itself exists, with α:T G∘G⇒G\alpha \,\colon\, T^G \circ G \Rightarrow G denoting the corresponding universal 2-morphism on the underlying functor T G:𝒜→𝒜T^G \colon \mathcal{A}\to\mathcal{A}.

The codensity monad of GG is the monad

𝕋 G≔⟨T G:𝒜→𝒜,η G:id 𝒜⇒T G,μ G:T G∘T G⇒T G⟩, \mathbb{T}^G \coloneqq \big\langle \; T^G \,\colon\, \mathcal{A} \to\mathcal{A} ,\;\;\; \eta^G \colon id_\mathcal{A}\Rightarrow T^G ,\;\;\; \mu^G \colon T^G\circ T^G \Rightarrow T^G \; \big\rangle \,,

where

the carrier functor 𝕋 G\mathbb{T}^G is given by the end

𝕋 G(A)=∫ B∈ℬ𝒜(A,GB)⋔GB \mathbb{T}^G(A) = \int_{B \in \mathcal{B}} \mathcal{A}(A, GB) \pitchfork GB

where ⋔\pitchfork is power, i.e. repeated product.
the monad unit η G:id 𝒜⇒T G\eta^G \colon id_\mathcal{A}\Rightarrow T^G is the natural transformation given by the universal property of (T G,α)(T^G,\;\alpha) with respect to the pair (id 𝒜,1 G)(id_\mathcal{A},\;1_G)\;,
the monad multiplication μ G:T G∘T G⇒T G\mu^G \colon T^G\circ T^G\Rightarrow T^G results from the universal property of (T G,α)(T^G,\;\alpha) with respect to the pair (T G∘T G,α∘(1 T G*α))(T^G\circ T^G,\;\alpha\circ (1_{T^G}\ast\alpha)).

Concerning existence, Ran GGRan_G G exists for G:ℬ→𝒜G \colon \mathcal{B}\to\mathcal{A}, e.g. when ℬ\mathcal{B} is small and 𝒜\mathcal{A} is complete.

In this circumstance, when ℬ\mathcal{B} is small and 𝒜\mathcal{A} is complete, then the codensity monad is equivalently the one that arises from the adjunction

𝒜⊥⟵⟶hom(−,G)[ℬ,Set] op, \mathcal{A} \underoverset {\underset{}{\longleftarrow}} {\overset{hom(-,G)}{\longrightarrow}} {\bot} [\mathcal{B},Set]^{op} \,,

where

the left adjoint hom(-,G):𝒜→[ℬ,Set] ophom(\text{-},G) \,\colon\, \mathcal{A} \to [\mathcal{B},Set]^{op} takes any object aa to the hom-functor Hom 𝒜(a,G(-)):ℬ→SetHom_{\mathcal{A}}\big(a, \,G(\text{-})\big) \colon \mathcal{B}\to Set,
the right adjoint [ℬ,Set] op→𝒜[\mathcal{B},Set]^{op}\to \mathcal{A} is the unique limit-preserving functor from the free completion of ℬ\mathcal{B} to 𝒜\mathcal{A} which agrees on ℬ\mathcal{B} with GG.

(See also nerve and realization; the description of the adjunction above is a formal dual of a nerve-realization adjunction, and gives the right Kan extension Ran GGRan_G G as a pointwise Kan extension. In the pointwise setting, GG is codense if and only if the left adjoint is full and faithful.)

Even if Ran GGRan_G G (assuming it exists) is not a pointwise Kan extension, Def. indeed defines a monad. The proof may be given generally for any 2-category in which the right Kan extension Ran GGRan_G G exists for a 1-cell G:ℬ→𝒜G: \mathcal{B} \to \mathcal{A}.

Theorem

Ran GGRan_G G, with the unit η G\eta^G and multiplication μ G\mu^G, is a monad.

Proof

The universal property of the Kan extension states that for any H:𝒜→ℬH: \mathcal{A} \to \mathcal{B}, there is a natural bijection

hom(H,T G)≅hom(HG,G);\hom(H, T^G) \cong \hom(H G, G);

let ε:T GG→G\varepsilon: T^G G \to G be the 2-cell corresponding to 1 T G∈hom(T G,T G)1_{T^G} \in \hom(T^G, T^G). Note that the bijection takes a 2-cell α:H→T G\alpha: H \to T^G to the composite

The 2-cell η G:1→T G\eta^G\colon 1 \to T^G is defined so that (ε)(η GG)=1 G(\varepsilon) (\eta^G G) = 1_G, and the 2-cell μ G:T GT G→T G\mu^G \colon T^G T^G \to T^G is defined so that (ε)(μ GG)=(ε)(T Gε)(\varepsilon) (\mu^G G) = (\varepsilon)(T^G \varepsilon).

To check the monad unit law that says the triangle

commutes, it suffices by universality to check that applying GG on the right, followed by ε\varepsilon, results in a commutative diagram. This follows from commutativity of the diagram

(where the square commutes by 2-categorical interchange), together with commutativity of

To check the other monad unit law is even simpler, because it follows directly from the commutativity of

where commutativity of the triangle comes from how we introduced η G\eta^G in this proof.

Monad associativity follows by showing that the maximal paths in

evaluate to the same 2-cell. By 2-categorical interchange, we may replace the composite “down, then right” to obtain the diagram

and then use how we introduced μ G\mu^G in this proof to further replace “right, then down” by

and finally finish the proof by observing that ε\varepsilon coequalizes μ GG\mu^G G, T GεT^G \varepsilon.

Examples

Properties

Proposition

Let G:B→AG : B \to A be a functor admitting a codensity monad T GT^G on AA. The Kleisli category for T GT^G has homs Kl(T G)(a,a′)≅[B,Set](B(a′,G−),B(a,G−))Kl(T^G)(a, a') \cong [B, Set](B(a', G-), B(a, G-)).

See Bourn and Cordier 1980, for instance.

References

One of the first references is

Anders Kock, Continuous Yoneda Representations of a Small Category, Preprint Aarhus University (1966). (pdf)

For the special case of double dualisation, see:

Anders Kock. On double dualization monads, Mathematica Scandinavica 27.2 (1970): 151-165. (JSTOR)

Overview:

Fred Linton, Codensity triples, Section 8 in: An outline of functorial semantics, in Seminar on Triples and Categorical Homology Theory, Lecture Notes in Mathematics 80, Springer (1969) 7-52 [doi:10.1007/BFb0083080]
Tom Leinster, Codensity and the Ultrafilter Monad , TAC 12 no.13 (2013) pp.332-370. [tac:28-13]