nLab codensity monad

Contents

Contents

Idea

Recall (eg. from here) that every right adjoint functor FG:𝒜F\dashv G \,\colon\, \mathcal{B}\to\mathcal{A} induces a monad on 𝒜\mathcal{A} whose underlying endofunctor is GFG\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

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 GGG\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

𝕋 GT G:𝒜𝒜,η G:id 𝒜T G,μ G:T GT GT 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 GT GT 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 GT 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 GGG\varepsilon: T^G G \to G be the 2-cell corresponding to 1 T Ghom(T G,T G)1_{T^G} \in \hom(T^G, T^G). Note that the bijection takes a 2-cell α:HT G\alpha: H \to T^G to the composite

The 2-cell η G:1T 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 GT 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

Example

Every monad that is induced by an adjunction LRL \dashv R is the codensity monad of RR. In particular, every enriched monad is a codensity monad (via its Kleisli category).

Example

Let dd be an object in a closed category CC. Then the CC-enriched codensity monad of the constant functor d:1Cd : 1 \to C is the double dualization monad associated to dd, given by d d ()d^{d^{(-)}}.

More conceptually, the codensity monad construction may be seen as a generalisation of the double dualisation construction analogous to the generalisation from algebras for a monad to modules over a monad (the latter is the perspective that is most natural 2-categorically).

Example

The Giry monad (as well as a finitely additive version) arise as codensity monads of forgetful functors from subcategories of the category of convex sets to the category of measurable spaces (Avery 14).

Example

The codensity monad of the inclusion FinSet \hookrightarrowSet is the ultrafilter monad. Its algebras are compact Hausdorff spaces.

Example

The codensity monad of the inclusion FinGrpFinGrp \hookrightarrow Grp, is the profinite completion monad, whose algebras may be identified with profinite groups – that is, topological groups whose underlying topological space is profinite (Avery 17, Proposition 2.7.10).

Example

The codensity monad of the inclusion FinSetTopFinSet \to Top computes the Stone spectrum of the Boolean algebra of clopen subsets of a topological space. Its algebras are precisely the Stone spaces. (Sipoș, Theorem 2).

Example

The codensity monad of the inclusion NTopN \to Top, where NN denotes the full subcategory of Top consisting of arbitrary small products of the Sierpiński space, is the localic spectrum? of the frame of opens of a topological space. Its algebras are precisely the sober spaces. (Sipoș, Theorem 6)

Example

The codensity monad of the inclusion of countable sets in all sets, CtblSetCtbl \hookrightarrow Set, assigns to each set XX the set of ultrafilters on XX closed under countable intersections. This still holds for the inclusion of the full subcategory of CtblCtbl on the single set \mathbb{N}.

Example

More generally, the codensity monad of the inclusion of sets of cardinality less than that of fixed YY, Set <YSetSet_{\lt Y} \hookrightarrow Set, assigns to each set XX the set of YY-complete ultrafilters on XX.

Example

For the codensity monad induced by the inclusion of homotopy types with finite homotopy groups into all homotopy types see there.

Example

The codensity monad induced by the Yoneda embedding is isomorphic to the monad induced by the Isbell adjunction.

Example

In the bicategory Rel, the right Kan extension of a relation T:ACT: A \to C along a relation R:ABR: A \to B is the relation T/R:BCT/R: B \to C such that (b,c)T/R(b,c)\in T/R iff a:AR(a,b)T(a,c)\forall_{a: A}\; R(a, b) \Rightarrow T(a, c). In particular, R/RR/R reduces to the identity relation id Bid_B iff whenever (b,b)(b,b') is such that a:AR(a,b)R(a,b)\forall_{a:A}\; R(a,b)\Rightarrow R(a,b') then b=bb=b'\,, in other words, iff R 1bR 1bR^{-1}b\subseteq R^{-1}b' implies b=bb=b'. The codensity monad R/R:BBR/R: B \to B, being a monad in RelRel, is a preorder. This construction frequently recurs; see for instance specialization order for a topology.

Properties

….

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:

See alos:

Codensity monads arising from subcategory inclusions are studied in

  • Ivan Di Liberti, Codensity: Isbell duality, pro-objects, compactness and accessibility, arXiv:1910.01014 (2019). (abstract)

The role in shape theory is discussed in

  • Armin Frei, On categorical shape theory , Cah. Top. Géom. Diff. XVII no.3 (1976) pp.261-294. (numdam)

  • D. Bourn, J.-M. Cordier, Distributeurs et théorie de la forme, Cah. Top. Géom. Diff. Cat. 21 no.2 (1980) pp.161-189. (pdf)

  • J.-M. Cordier, T. Porter, Shape Theory: Categorical Methods of Approximation , (1989), Mathematics and its Applications, Ellis Horwood. Reprinted Dover (2008).

The dual concept of a “model-induced cotriple”:

On possible uses in functional programming:

  • Ralf Hinze, Kan extensions for program optimisation - Or: Art and Dan explain an old trick, in: Jeremy Gibbons, Pablo Nogueira (eds.), 11th International Conference on Mathematics of Program Construction (MPC ‘12), LNCS 7342 Springer (2012) 324–362. (doi: 10.1007/978-3-642-31113-0_16, pdf draft)

For a description of the Giry monad and other probability monads as codensity monads, see

Other references include

  • Tom Avery, Structure and Semantics, (arXiv:1708.01050)

  • C. Casacuberta, A. Frei, Localizations as idempotent approximations to completions , JPAA 142 (1999) no. 1 pp.25–33. (draft)

  • Yves Diers, Complétion monadique , Cah. Top. Géom. Diff. Cat. XVII no.4 (1976) pp.362-379. (numdam)

  • S. Katsumata, T. Sato, T. Uustalu, Codensity lifting of monads and its dual , arXiv:1810.07972 (2012). (abstract)

  • J. Lambek, B. A. Rattray, Localization and Codensity Triples , Comm. Algebra 1 (1974) pp.145-164.

  • Jiří Adámek, Lurdes Sousa?, D-Ultrafilters and their Monads, (arXiv:1909.04950)

  • Andrei Sipoş?, Codensity and Stone spaces, Mathematica Slovaca, 68 no. 1, p. 57–70, (2018). doi:10.1515/ms-2017-0080, (arXiv:1409.1370)

Last revised on October 2, 2024 at 09:59:38. See the history of this page for a list of all contributions to it.