Demystifying Codensity Monads via Duality

We start with what is probably the best known instance of a codensity monad: the characterization of the ultrafilter monad on $\mathrm{𝐒𝐞𝐭}$ as the codensity monad of the inclusion ${\mathrm{𝐒𝐞𝐭}}_{𝖿}\hookrightarrow \mathrm{𝐒𝐞𝐭}$ of finite sets into sets. This classical result goes back to Kennison and Gildenhuys [27]; see also Leinster [29] for a streamlined exposition.

Let $\mathrm{𝐁𝐀}$ denote the category of Boolean algebras. An ultrafilter on a Boolean algebra $B$ is a subset $U\subseteq B$ such that (1) $U$ is upwards closed, (2) $U$ is closed under meet, and (3) for every $b\in B$, either $b\in U$ or $\neg b\in U$. Equivalently, an ultrafilter is given by a morphism $\chi \in \mathrm{𝐁𝐀}(B,2)$, where $2=\{0,1\}$ is the two-element Boolean algebra, by identifying $\chi$ with the preimage ${\chi }^{-1}(1)\subseteq B$. An ultrafilter on a set $X$ is an ultrafilter on the Boolean algebra $\mathrm{𝐒𝐞𝐭}(X,2)\cong 𝒫X$ of predicates (equivalently subsets) of $X$. The ultrafilter monad $𝒰$ on $\mathrm{𝐒𝐞𝐭}$ sends a set $X$ to the set of $𝒰X=\mathrm{𝐁𝐀}(\mathrm{𝐒𝐞𝐭}(X,2),2)$ of its ultrafilters; more precisely, $𝒰$ is the monad induced by the adjunction in (4.1) below. The category $\mathrm{𝐄𝐌}(𝒰)$ of algebras for $𝒰$ is isomorphic to the category of compact Hausdorff spaces and continuous maps [31, 1.5.24–33]; hence the ultrafilter monad provides a bridge between algebra, Boolean logic, and topology.
The ultrafilter monad $𝒰$ is captured by codensity setting (4.1) shown below on the left:

Here $I$ and $J$ are the inclusions of the full subcategories of finite sets and finite Boolean algebras, respectively, and the equivalence functor on the left is the restriction of Birkhoff duality [6] between distributive lattices and finite posets to finite sets (discrete posets). The functor $J$ is dense by Example 2.1.3; note that since the free Boolean algebra $2^{2^X}$ on a finite set $X$ is finite, we have ${\mathrm{𝐁𝐀}}_{\mathrm{𝖿𝗉}}={\mathrm{𝐁𝐀}}_{𝖿}$. From Theorem 3.2 we obtain:

A similar result was given by Sipoş [38] for the ultrafilter monad $\overline{𝒰}$ on the category $\mathrm{𝐓𝐨𝐩}$ of topological spaces and continuous maps assigning to a space $X$ the space $\overline{𝒰}X=\mathrm{𝐁𝐀}(\mathrm{𝐓𝐨𝐩}(X,2),2)$ of ultrafilters of clopens; that is, $\overline{𝒰}$ is the monad given by the adjunction in (4.2). Here $2$ is the two-element discrete space, $\mathrm{𝐓𝐨𝐩}(X,2)\cong \mathrm{Cl}X$ is the Boolean algebra of clopen subsets of a space $X$, and $\mathrm{𝐁𝐀}(B,2)$ is the space of ultrafilters of a Boolean algebra $B$, viewed as subspace of the space $2^{|B|}$ equipped with the product topology. Algebras for $\overline{𝒰}$ correspond to Stone spaces (compact Hausdorff spaces with a basis of clopens) [38].

To capture the topological ultrafilter monad in our setting, we just use $\mathrm{𝐓𝐨𝐩}$ in lieu of $\mathrm{𝐒𝐞𝐭}$ in (4.1), which leads to the codensity setting (4.2). Here $I$ identifies a finite set with a discrete topological space. From Theorem 3.2 we obtain:

A natural generalization of ultrafilter monads are filter monads. They are captured in our setting as well by working with semilattices in lieu of Boolean algebras.

In more detail, let $\mathrm{𝐌𝐒𝐋}$ denote the category of meet-semilattices with a top element (equivalently, algebras for the finite power set monad ${𝒫}_{𝖿}$). A filter on a meet-semilattice $M$ is a non-empty subset $F\subseteq M$ that is both upwards closed and closed under meets. A filter corresponds to morphism $\chi \in \mathrm{𝐌𝐒𝐋}(M,2)$, where $2=\{0,1\}$ is the two-element semilattice with the meet given by minimum, by identifying $\chi$ with the preimage ${\chi }^{-1}(1)\subseteq M$. A filter on a set $X$ is a filter on the semilattice $\mathrm{𝐒𝐞𝐭}(X,2)\cong 𝒫X$. The filter monad $ℱ$ on $\mathrm{𝐒𝐞𝐭}$ sends a set $X$ to the set of $ℱX=\mathrm{𝐌𝐒𝐋}(\mathrm{𝐒𝐞𝐭}(X,2),2)$ of its filters; that is, $ℱ$ is the monad induced by the adjunction in (4.3). Algebras for $ℱ$ correspond to complete lattices where finite meets distribute over directed joins [9]. Two suitable codensity settings for $ℱ$ are given below:

In setting (4.3), $U$ is the forgetful functor, and $J$ is the dense inclusion (Example 2.1.3), where we use that $\mathrm{𝐄𝐌}({𝒫}_{𝖿})\cong \mathrm{𝐌𝐒𝐋}$ (viewing $\mathrm{𝐌𝐒𝐋}$ as the algebraic category of commutative idempotent monoids) and that finitely presentable semilattices coincide with the finite ones. Moreover, we make use of the self-duality ${\mathrm{𝐌𝐒𝐋}}_{𝖿}^{\mathrm{𝗈𝗉}}\simeq {\mathrm{𝐌𝐒𝐋}}_{𝖿}$ of finite meet-semilattices [24, Sec. VI.3.6], which maps a finite meet-semilattice $M$ to the semilattice $\mathrm{𝐌𝐒𝐋}(M,2)$ of its filters, with the semilattice structure defined pointwise. This codensity setting restricts to (4.4); to see this, first recall the functors $U_{{𝒫}_{𝖿}}$ and $I_{{𝒫}_{𝖿}}$ from Section 2 (p. 2, “Monads”) and that $I_{{𝒫}_{𝖿}}$ is dense (Example 2.1.2). (Note that it maps a set $X$ to ${𝒫}_{𝖿}X$ equipped with $\cup$ as the binary operation.) Here ${\mathrm{𝐊𝐥}}_{𝖿}{({𝒫}_{𝖿})}^{\mathrm{𝗈𝗉}}\simeq {\mathrm{𝐊𝐥}}_{𝖿}({𝒫}_{𝖿})$ is the standard identity-on-objects self-duality of the category of finite sets and relations, sending $f:X\to {𝒫}_{𝖿}Y$ to $f^{\mathrm{𝗈𝗉}}:Y\to {𝒫}_{𝖿}X$ given by $f^{\mathrm{𝗈𝗉}}(y)=\{x:y\in f(x)\}$. The outer square clearly commutes since both ${(f^{\mathrm{𝗈𝗉}})}^{\mathrm{\#}}=2^{f^{\mathrm{\#}}}:{𝒫}_{𝖿}Y\to {𝒫}_{𝖿}X$ take the preimage of $S\subseteq Y$ under $f^{\mathrm{\#}}$.

From Theorem 3.2 we obtain two novel codensity presentations of the filter monad:

Similar to the ultrafilter monad, this reasoning carries over from $\mathrm{𝐒𝐞𝐭}$ to suitable topological categories. For example, the filter monad $\overline{ℱ}$ on $\mathrm{𝐓𝐨𝐩}$ is given by $\overline{ℱ}X=\mathrm{𝐌𝐒𝐋}(\mathrm{𝐓𝐨𝐩}(X,𝕊),2)$, that is, $\overline{ℱ}$ is induced by the adjunction in the diagram below. Here $𝕊$ is the Sierpinski space carried by $2=\{0,1\}$ with open sets $\mathrm{\varnothing }$, $\{1\}$, $\{0,1\}$, and the set $\mathrm{𝐌𝐒𝐋}(M,2)$ is topologized as a subspace of the product space ${𝕊}^{|M|}$. As open subsets of a space $X$ correspond to continuous maps from $X$ to $𝕊$, the monad $\overline{ℱ}$ sends $X$ to the space $\overline{ℱ}X$ of filters of open sets. Algebras for $\overline{ℱ}$ carried by $T_0$ spaces correspond to continuous lattices [9]. To capture $\overline{ℱ}$ as a codensity monad, we modify the codensity setting (4.4) to the one shown below. Here we regard the functor $U_{{𝒫}_{𝖿}}:{\mathrm{𝐊𝐥}}_f({𝒫}_{𝖿})\to \mathrm{𝐒𝐞𝐭}$ from (4.3) as a functor to $\mathrm{𝐓𝐨𝐩}$ by identifying $U_{{𝒫}_{𝖿}}X={𝒫}_{𝖿}X$ with the topological space ${𝕊}^X$.

From Theorem 3.2 we obtain a novel codensity presentation of $\overline{ℱ}$:

Another interesting class of codensity monads that naturally emerge in our framework are certain double dualization monads, which are monads given by dual adjunctions as shown in the first diagram below, where $𝐂$ is a symmetric monoidal closed category, $D$ is a fixed object of $𝐂$, and $𝐂(C,D)\in 𝐂$ denotes the internal hom object of $C,D\in 𝐂$.

The other three adjunctions above are concrete instances. Here $\mathrm{𝐕𝐞𝐜𝐭}$ is the category of vector spaces over a field $K$ and linear maps, and $X^{\ast }=\mathrm{𝐕𝐞𝐜𝐭}(X,K)$ is the dual space of a space $X$ with pointwise structure. The induced monads are the neighbourhood monad on $\mathrm{𝐒𝐞𝐭}$ (whose algebras are complete atomic Boolean algebras [31, 1.5.17–23]), the monad on $\mathrm{𝐌𝐒𝐋}$ sending a semilattice to its semilattice of filters of filters, and the monad sending a vector space $X$ to its double dual space $X^{\ast \ast }$ (whose algebras are linearly compact vector spaces [29, Thm. 7.8]).
Suitable codensity settings for these three monads are given as follows:

Here $U:{\mathrm{𝐁𝐀}}_{𝖿}\to \mathrm{𝐒𝐞𝐭}$ denotes the forgetful functor, ${\mathrm{𝐕𝐞𝐜𝐭}}_{\mathrm{𝖿𝖽}}$ is the full subcategory of $\mathrm{𝐕𝐞𝐜𝐭}$ given by finite dimensional vector spaces, and the functors $I$ are inclusion functors, which are dense (Example 2.1.3). In the first two diagrams we use the dualities ${\mathrm{𝐁𝐀}}_{𝖿}^{\mathrm{𝗈𝗉}}\simeq {\mathrm{𝐒𝐞𝐭}}_{𝖿}$ and ${\mathrm{𝐌𝐒𝐋}}_{𝖿}^{\mathrm{𝗈𝗉}}\simeq {\mathrm{𝐌𝐒𝐋}}_{𝖿}$ encountered before, and in the third one we use the familiar self-duality of the category of finite dimensional vector spaces, which amounts to the fact that every such space is naturally isomorphic to its double dual. All three diagrams clearly commute.

From Theorem 3.2 we obtain the following codensity presentations; the first appears to be new, the second is due to Adámek and Sousa [3], and the third due to Leinster [29].

The last item readily generalizes to modules over a commutative semiring $S$, where in lieu of ${\mathrm{𝐕𝐞𝐜𝐭}}_{\mathrm{𝖿𝖽}}$ one takes finitely generated free $S$-modules. Note that all vector spaces are free.

For a slightly more intricate example, we consider the category $\mathrm{𝐀𝐛}$ of abelian groups and as the dualizing object the circle group $S^1=\{x\in ℂ\mid |x|=1\}$, a subgroup of the multiplicative group of non-zero complex numbers. It forms a (compact Hausdorff) topological group w.r.t. the Euclidian topology on $ℂ$. A suitable codensity setting is given by:

While all previous examples are based on simple dualities, we now use a corollary of a more advanced duality result: (discrete) Pontryagin duality [35, 34], the dual equivalence ${\mathrm{𝐀𝐛}}^{\mathrm{𝗈𝗉}}\simeq \mathrm{𝐂𝐇𝐀𝐛}$ between $\mathrm{𝐀𝐛}$ and the category $\mathrm{𝐂𝐇𝐀𝐛}$ of compact Hausdorff abelian groups and continuous group morphisms. The equivalence sends an abelian group $A$ to the topological group $\mathrm{𝐀𝐛}(A,S^1)$ of all group morphisms into $S^1$, topologized as a subspace of ${(S^1)}^{|A|}$. Under this duality, the additive group $\mathbb{Z}\times \mathbb{Z}$ (the free abelian group on two generators) corresponds to the torus $S^1\times S^1$, since

Thus, we see that Pontryagin duality restricts to a dual equivalence between the one-object full subcategories $\{\mathbb{Z}\times \mathbb{Z}\}\hookrightarrow \mathrm{𝐀𝐛}$ and $\{S^1\times S^1\}\hookrightarrow \mathrm{𝐂𝐇𝐀𝐛}$. The functor $U$ is the composition of the inclusion $\{S^1\times S^1\}\hookrightarrow \mathrm{𝐂𝐇𝐀𝐛}$ with the forgetful functor to $\mathrm{𝐀𝐛}$. The inclusion $J:\{\mathbb{Z}\times \mathbb{Z}\}\hookrightarrow \mathrm{𝐀𝐛}$ is dense (Example 2.1.2), and the outside of the diagram commutes, since Pontryagin duality is given by the functor $\mathrm{𝐀𝐛}(-,S^1):{\mathrm{𝐀𝐛}}^{\mathrm{𝗈𝗉}}\to \mathrm{𝐂𝐇𝐀𝐛}$. From Theorem 3.2 we obtain the following new result:

We conclude this section with an example of a more abstract nature: for every small category $𝐂$, the codensity monad of the Yoneda embedding $𝐂\hookrightarrow [{𝐂}^{\mathrm{𝗈𝗉}},\mathrm{𝐒𝐞𝐭}]$ is the monad given by Isbell duality [19]. This result due to Kock [28] originally motivated the introduction of codensity monads. Recall that Isbell duality is the dual adjunction in (4.5) between the categories of contravariant and covariant presheaves on $𝐂$ defined by

The two Yoneda embeddings $y$ and $\tilde{y}$ give rise to the codensity setting shown below:

Indeed, the embedding $\tilde{y}$ is dense (Example 2.2), and the outside of the diagram commutes up to isomorphism by the Yoneda lemma: for all objects $C,D\in 𝐂$, we have

From Theorem 3.2 we obtain:

We start with the Vietoris monad on the category $\mathrm{𝐒𝐭𝐨𝐧𝐞}$ of Stone spaces and continuous maps. The Vietoris space $𝕍X$ of a Stone space $X$ is given by the set of all closed subsets of $X$ equipped with the hit-or-miss topology, which has the following subbasic open sets:

We can represent $𝕍X$ as a double dual space as follows. Let $\mathrm{𝐉𝐒𝐋}$ be the category of join-semilattices with bottom. Morphisms from $J$ to the join-semilattice $2=\{0,1\}$ (with join given by maximum) correspond to ideals: non-empty subsets of $J$ that are downwards closed and closed under join. The set $\mathrm{𝐉𝐒𝐋}(J,2)$ of ideals is topologized as a subspace of the product space $2^{|J|}$, where $2$ carries the discrete topology. We then have the isomorphism $𝕍X\cong \mathrm{𝐉𝐒𝐋}(\mathrm{𝐒𝐭𝐨𝐧𝐞}(X,2),2)$ which identifies a closed set $C\subseteq X$ with the ideal of all clopen sets $U\subseteq X$ with $C\cap U=\mathrm{\varnothing }$ (i.e. $C\in \mathrm{\square }U$). The object mapping $X\mapsto 𝕍X$ thus naturally extends to a monad, for which the appropriate codensity setting is given by (5.1):

Here $U_{{𝒫}_{𝖿}}:{\mathrm{𝐊𝐥}}_f({𝒫}_{𝖿})\to \mathrm{𝐒𝐞𝐭}$ from (4.4) is lifted to $\mathrm{𝐒𝐭𝐨𝐧𝐞}$, identifying $U_{{𝒫}_{𝖿}}X={𝒫}_{𝖿}X$ with the discrete space $2^X$. The functor $I_{{𝒫}_{𝖿}}$ is the dense inclusion (Example 2.1.2), using $\mathrm{𝐄𝐌}({𝒫}_{𝖿})\cong \mathrm{𝐉𝐒𝐋}$. Commutativity of (5.1) is shown like for (4.4). From Theorem 3.2 we obtain:

By varying the ingredients of the above setting a bit, codensity presentations for other Vietoris-type monads emerge easily. Here we consider the lower Vietoris monad, a.k.a. Hoare hyperspace monad [12], on the category $\mathrm{𝐓𝐨𝐩}$ of topological spaces. Given a topological space $X$, the lower Vietoris space is the topological space ${𝕍}_{\downarrow }X$ of all closed subsets of $X$ with the topology generated by the subbasic open sets $\mathrm{◇}U$ (as defined above) for $U\subseteq X$ open. Similar to $𝕍X$, we can represent ${𝕍}_{\downarrow }X$ as a double dual space. Let $\mathrm{𝐂𝐉𝐒𝐋}$ be the category of complete join-semilattices and join-preserving maps (i.e. algebras for the power set monad $𝒫$). Morphisms in $\mathrm{𝐂𝐉𝐒𝐋}$ from $J$ to $2=\{0,1\}$ correspond to complete ideals: subsets of $J$ that are downwards closed and closed under arbitrary joins. The set $\mathrm{𝐂𝐉𝐒𝐋}(J,2)$ of all complete ideals is topologized as a subspace of the product space ${𝕊}^{|J|}$. We then have ${𝕍}_{\downarrow }X\cong \mathrm{𝐂𝐉𝐒𝐋}(\mathrm{𝐓𝐨𝐩}(X,𝕊),2),$ where the isomorphism identifies a closed set $C\subseteq X$ with the complete ideal of all open sets $U\subseteq X$ with $C\cap U=\mathrm{\varnothing }$. Thus, the object mapping $X\mapsto {𝕍}_{\downarrow }X$ extends to a monad, whose codensity setting is given by (5.2). Note that this setup is very similar to the filter monad on $\mathrm{𝐓𝐨𝐩}$ from Section 4.2, except that we now work with complete join-semilattices in lieu of (finitary) meet-semilattices and with the full Kleisli category for the monad $𝒫$ in lieu of its finite restriction. The canonical functor $U_{𝒫}:\mathrm{𝐊𝐥}(𝒫)\to \mathrm{𝐒𝐞𝐭}$ is taken as a functor to $\mathrm{𝐓𝐨𝐩}$ by identifying $U_{{𝒫}_{𝖿}}X={𝒫}_{𝖿}X$ with the topological space ${𝕊}^X$, and $I_{𝒫}$ is the dense inclusion (Example 2.1.1), using that $\mathrm{𝐄𝐌}(𝒫)\cong \mathrm{𝐂𝐉𝐒𝐋}$. The outside commutes analogously to (5.1). From Theorem 3.2 we obtain the following new result:

Just like Stone spaces correspond to algebras for the filter monad on $\mathrm{𝐓𝐨𝐩}$ (Section 4.2), the well-studied subcategory of sober spaces [20, 24] is captured by the sobrification monad, introduced by Sipoş [38]. It emerges in our framework by working with frames in lieu of meet-semilattices. Recall that a frame is a poset $X$ which has all finite meets and all joins and which satisfies the infinite distributive law $x\wedge {\bigvee }_{i\in I}{x}_i={\bigvee }_{i\in I}x\wedge x_i$ for all $x,x_i\in X$, $i\in I$. We denote by $\mathrm{𝐅𝐫𝐦}$ the category of frames and maps preserving finite meets and all joins. It is isomorphic to the category of algebras $\mathrm{𝐄𝐌}(ℒ)$ for the free frame monad $ℒ$ on $\mathrm{𝐒𝐞𝐭}$ sending a set $X$ to the set $ℒX$ of upwards closed subsets of ${𝒫}_{𝖿}X$ [25, C1.1, Lem. 1.1.3].

The sobrification monad on $\mathrm{𝐓𝐨𝐩}$ is given by $𝒮X=\mathrm{𝐅𝐫𝐦}(\mathrm{𝐓𝐨𝐩}(X,𝕊),2)$; more precisely, $𝒮$ is the monad induced by the dual adjunction in (5.3). Sipoş [38] has shown that algebras for $𝒮$ correspond to sober spaces and has given a codensity presentation of this monad, which in our duality-based framework corresponds to the codensity setting given by:

Here $J$ is the inclusion of the full subcategory $\mathrm{𝐒𝐢𝐞𝐫}$ of $\mathrm{𝐓𝐨𝐩}$ consisting of powers ${𝕊}^X$, where $X$ is any set, and $I_{ℒ}$ is the canonical dense inclusion functor from Example 2.1.1. The equivalence functor $E$ and commutation of the diagram are given by the following lemma.

From Theorem 3.2 we obtain:

We start with the expectation monad [44, 23], a probability monad that has recieved a lot of attention in recent years, e.g. in quantum foundations. A finitely additive probability measure on a set $X$ is a finitely additive probability measure on the discrete measurable space $(X,{\mathrm{\Sigma }}_X=𝒫X)$, that is, a map $p:𝒫X\to [0,1]$ with $p(X)=1$ and $p(A+B)=p(A)+p(B)$ for disjoint $A,B\in 𝒫X$. If $X$ is finite, then every finitely additive probability measure on $X$ is discrete: recall that a discrete finite probability measure on $X$ is a map $p:X\to [0,1]$ with ${\sum }_{x\in X}p(x)=1$ and $p(x)=0$ for all but finitely many $x\in X$. We denote the set of finitely additive probability measures on a set $X$ by $ℰX$, and the set of discrete finite probability measures by ${𝒟}_{𝖿}X$. For the codensity presentation of the expectation monad we embed these notions into an algebraic setting given by effect algebras and effect modules [22, 17].

An effect algebra is a partial commutative monoid $(A,\oplus ,0)$ together with an operator ${(-)}^{\perp }:A\to A$ satisfying that $x^{\perp }$ is the unique element in $A$ with $x\oplus x^{\perp }=1$, where $1=0^{\perp }$, and $x\oplus 1$ is defined iff $x=0$. Morphisms of effect algebras preserve all this structure, forming a category $\mathrm{𝐄𝐀}$. The unit interval $[0,1]$ forms an effect algebra with $r\oplus s=r+s$ defined if $r+s\le 1$, and $r^{\perp }=1-r$. Boolean algebras form a full subcategory of effect algebras, with $a\oplus b=a\vee b$ defined whenever $a\wedge b=0$, and $a^{\perp }=\neg a$. The following non-trivial density result, which is not covered by Example 2.1, is due to Staton and Uijlen [39, Cor. 10]:

Effect algebras carry a monoidal structure $\otimes$ such that $A\otimes B$ represents bilinear morphisms [22], analogous to commutative monoids, with tensor unit $2=\{0,1\}$. The unit interval $[0,1]$ with multiplication forms a monoid $[0,1]\otimes [0,1]\to [0,1]$ for this monoidal structure.

An effect module is an effect algebra $E$ that is a $[0,1]$-module for this tensor product, that is, $E$ is equipped with a bilinear map $[0,1]\times E\to E$ of effect algebras. Effect module morphisms are effect algebra morphisms preserving the action, forming a category $\mathrm{𝐄𝐌𝐨𝐝}$. Its forgetful functor to $\mathrm{𝐄𝐀}$ has a left adjoint $A\mapsto [0,1]\otimes A$. This adjunction yields a monad $ℳ$ on $\mathrm{𝐄𝐀}$ given by $ℳA=[0,1]\otimes A$. On finite Boolean algebras we have $ℳ(2^X)\cong {[0,1]}^X$. We extend the density result from ˜6.1 to effect modules, where we denote the full subcategory of $\mathrm{𝐊𝐥}(ℳ)$ on finite Boolean algebras by ${\mathrm{𝐊𝐥}}_{{\mathrm{𝐁𝐀}}_{𝖿}}(ℳ)$:

Finitely additive probability measures on a set $X$ correspond to effect algebra morphisms from $2^X$ to $[0,1]$, that is, $ℰX\cong \mathrm{𝐄𝐀}(2^X,[0,1])$. They also correspond to effect module morphisms from ${[0,1]}^X$ to $[0,1]$, which is the content of the following discrete integral representation theorem [23, Prop. 33]:

The bijection sends $f\in \mathrm{𝐄𝐌𝐨𝐝}({[0,1]}^X,[0,1])$ to the measure $p$ with $p(A)=f({\chi }_A)$, where ${\chi }_A$ is the characteristic map of $A\subseteq X$ given by ${\chi }_A(x)=1$ if $x\in A$, and ${\chi }_A(x)=0$ if $x\notin A$.

We thus define the expectation monad $ℰ$ on $\mathrm{𝐒𝐞𝐭}$ by $ℰX=\mathrm{𝐄𝐌𝐨𝐝}({[0,1]}^X,[0,1])$; more precisely, $ℰ$ is given by the adjunction in the codensity setting below:

The inclusion $I_{ℳ}$ is dense by ˜6.2 and the outer square commutes since $ℳ2=[0,1]\otimes 2^1\cong [0,1]$. The duality of the left extends the duality ${\mathrm{𝐁𝐀}}_{𝖿}^{\mathrm{𝗈𝗉}}\simeq {\mathrm{𝐒𝐞𝐭}}_{𝖿}$. Indeed, for $A,B\in {\mathrm{𝐒𝐞𝐭}}_{𝖿}$ we have the following natural bijection:

From Theorem 3.2 we obtain a novel codensity presentation of $ℰ$:

To capture general probability theory, we move from finitely additive to countably additive probability measures. A probability measure on a measurable space $(X,{\mathrm{\Sigma }}_X)$ is a map $p:{\mathrm{\Sigma }}_X\to [0,1]$ such that $p(X)=1$ and $p({\sum }_i{A}_i)={\sum }_{i}p(A_i)$ for every countable family ${(A_i)}_i$ of pairwise disjoint sets. We denote the set of probability measures on $X$ by $𝒢X$. The assignment $X\mapsto 𝒢X$ forms a monad on the category $\mathrm{𝐌𝐞𝐚𝐬}$ of measurable spaces and measurable maps called the Giry monad [16]. Here, $𝒢X$ is equipped with the $\mathrm{\Sigma }$-subalgebra of the power ${[0,1]}^{{\mathrm{\Sigma }}_X}$ of $[0,1]$ in $\mathrm{𝐌𝐞𝐚𝐬}$, where $[0,1]$ carries the usual Borel $\sigma$-algebra. On a countable discrete space $(X,{\mathrm{\Sigma }}_X=2^X)$, a probability measure corresponds to a map $p:X\to [0,1]$ with ${\sum }_{x}p(x)=1$. We denote the set of all such discrete probability measures by $𝒟X$. If we equip $𝒟X$ with the $\mathrm{\Sigma }$-subalgebra of ${[0,1]}^X$, then $𝒟:{\mathrm{𝐒𝐞𝐭}}_{𝖼}\to \mathrm{𝐌𝐞𝐚𝐬}$ forms a functor, where ${\mathrm{𝐒𝐞𝐭}}_{𝖼}\hookrightarrow \mathrm{𝐒𝐞𝐭}$ denotes the full subcategory of countable sets.

Again, these constructions can be expressed in the language of effect algebras, though we have to use a countably infinitary sum operation. A $\sigma$-effect algebra [4] is an effect algebra $A$ with a partial commutative associative operation that behaves as expected with unit $0$ and addition $\oplus$ of $A$ (here commutativity means that the operation is independent of permutation of the arguments). Morphisms of $\sigma$-effect algebras preserve all this structure, forming a category ${\mathrm{𝐄𝐀}}_{\sigma }$. It contains the category of $\sigma$-algebras and the category of countably complete Boolean algebras as subcategories. The familiar dual equivalence between $\mathrm{𝐒𝐞𝐭}$ and the category $\mathrm{𝐂𝐀𝐁𝐀}$ of complete atomic Boolean algebras [24, Sec. VI.4.6] restricts to countable sets, yielding a dual equivalence between ${\mathrm{𝐒𝐞𝐭}}_{𝖼}$ and the category ${\mathrm{𝐂𝐀𝐁𝐀}}_{𝖼}$ of countably complete Boolean algebras of the form $2^A$ for a countable set $A$.

The codensity presentation of $𝒢$ again rests on a representation theorem [42, Cor. 3.8]:

The isomorphism is analogous to that of Theorem 6.3. This means that the Giry monad is given by the adjunction in the diagram below, which also establishes a codensity setting:

Here $I$ is the inclusion, and we have:

From Theorem 3.2 we obtain the codensity presentation of $𝒢$ due to van Belle [42].

Let us mention that in much the same way, Theorem 3.2 yields codensity presentations of

1. 1.

   the Giry monad by the forgetful functor $U_{𝒟}:{\mathrm{𝐊𝐥}}_{𝖼}(𝒟)\to \mathrm{𝐌𝐞𝐚𝐬}$, analogous to Theorem 6.4;

2. 2.

   the countable expectation monad ${ℰ}_{\sigma }X={\mathrm{𝐄𝐌𝐨𝐝}}_{\sigma }({[0,1]}^X,[0,1])$ on $\mathrm{𝐒𝐞𝐭}$ by the functor $𝒟:{\mathrm{𝐒𝐞𝐭}}_{𝖼}\to \mathrm{𝐒𝐞𝐭}$, analogous to Theorem 6.8.

Here ${\mathrm{𝐄𝐌𝐨𝐝}}_{\sigma }$ is the category of $\sigma$-effect modules [4], the infinitary version of effect modules. Both results rest on the fact that every ${\mathrm{𝐄𝐀}}_{\sigma }$-morphism of type ${[0,1]}^X\to [0,1]$ is an ${\mathrm{𝐄𝐌𝐨𝐝}}_{\sigma }$-morphism, i.e. linear [42, Lem. A.3]. More details are given in the full arXiv version.

Variants of the Giry monad on subcategories of measurable spaces are treated similarly in our framework. Here we consider the Radon monad [13], which captures an important subclass of probability measures. A Radon probability measure on a compact Hausdorff space $X$ is a probability measure $\mu$ on ${\mathrm{𝖡𝗈}}_X$ (the Borel $\sigma$-algebra generated by the open sets of $X$) satisfying the condition $\mu (A)=sup\{\mu (K)\mid K\subseteq A\text{ and }K\text{ compact}\}$ for all $A\in {\mathrm{𝖡𝗈}}_X$. The set of all Radon probability measures on $X$ is denoted by $ℛX$; it forms a compact Hausdorff space when topologized as a subspace of the product space ${[0,1]}^{{\mathrm{𝖡𝗈}}_X}$ in $\mathrm{𝐂𝐇𝐚𝐮𝐬}$.

Similar to Theorem 6.6, Radon measures come with a representation theorem, which yields a particularly simple codensity presentation. It is a variant of the Riesz-Markov representation theorem and proved via the Daniell-Stone representation theorem in [42]:

This representation theorem reduces the Radon monad to the codensity setting shown below:

Here $𝒟X$ is topologized as a subspace of the hypercube ${[0,1]}^X$, and $J$ is the inclusion functor, which is dense by ˜6.1. From Theorem 3.2 we obtain the following codensity presentation of the Radon monad, which is due to van Belle [42]:

As our last example, we depart from classical probability measures and generalize to measures valued in a semiring [36]. Fix a finite semiring $S$, viewed as a discrete topological space. An $S$-valued measure on a Stone space $X$ is a map $p:\mathrm{Cl}X\to S$ satisfying $p(\mathrm{\varnothing })=0$ and $p(A+B)=p(A)+p(B)$ for disjoint clopens $A,B$. Let ${ℳ}_{S}X$ denote the set of such measures.

The set ${ℳ}_{S}X\subseteq S^{\mathrm{Cl}X}$ is a closed subspace [36, Lem. 3.4] and hence a Stone space. The integral representation theorem in this case is particularly simple: Recall that an $S$-module is an abelian group $A$ with an action $S\times A\to A$ satisfying the usual compatibility conditions with respect to the operations of $S$ and $A$. For example, the set $\mathrm{𝐒𝐭𝐨𝐧𝐞}(X,S)$ is an $S$-module under pointwise operations. A morphism of $S$-modules is a morphism of the underlying abelian groups commuting with the action, giving a category ${\mathrm{𝐌𝐨𝐝}}_S$. It is isomorphic to the category of algebras for the free-semimodule monad $𝒮$ on $\mathrm{𝐒𝐞𝐭}$, where $𝒮X=\{f:X\to S\mid f(x)=0\text{ for all but finitely many }x\}$. Given $X\in \mathrm{𝐒𝐭𝐨𝐧𝐞}$ we topologize ${\mathrm{𝐌𝐨𝐝}}_S(\mathrm{𝐒𝐭𝐨𝐧𝐞}(X,S),S)$ as a subspace of $S^{\mathrm{𝐒𝐭𝐨𝐧𝐞}(X,S)}$. Then the following is easy to see:

This implies that a suitable codensity setting for ${ℳ}_S$ is given by the diagram below:

The inclusion $I_{𝒮}$ is dense by Example 2.1.2, using that $\mathrm{𝐄𝐌}(𝒮)\cong {\mathrm{𝐌𝐨𝐝}}_S$, and the outer square commutes similar to (4.4). From Theorem 3.2 we obtain the following result: