Monadicity and Beck's Theorem — Examples

The maps are $f(0)=f(1)=0$, $g(0)=0$, $g(1)=1$, $t=g$, $h(0)=h(1)=\ast$, and $s(\ast )=0$.

Both $hf$ and $hg$ are the unique map to $Z$; $hs(\ast )=\ast$; $gt$ is the identity on $0$ and $1$; and both $ft$ and $sh$ are constant at $0$. Thus all four equations in [L1] hold on both elements.

By [L2], the displayed fork is a coequalizer.

Directly, if $k:Y\to W$ satisfies $kf=kg$, then $k(0)=k(y)$ for both $y=0,1$, so $k$ is constant and factors uniquely through $h:Y\to \{\ast \}$. This independently checks the universal property.

The multiplication table is $1\cdot 1=1$, $1\cdot e=e\cdot 1=e$, and $e\cdot e=e$, so $M$ is a monoid and $a:M^{\ast }\to M$ evaluates every finite word to its product.

On a word of words $[w_1,\dots ,w_n]$, the map $T(a)$ gives $[a(w_1),\dots ,a(w_n)]$, while ${\mu }_M$ gives the concatenated word $w_1\cdots w_n$, as in [L1] and [L2].

Evaluating either result multiplies the same letters in the same order, so $aT(a)=a{\mu }_M$ for every finite word of words, including the empty one and words containing empty inner words.

The theorem [L1] now gives the coequalizer universal property. On underlying sets the sections are the one-letter-word maps ${\eta }_{M^{\ast }}$ and ${\eta }_M$, and the monad unit and naturality equations verify the split presentation.

By [L2], the structure map is the underlying counit $U{\epsilon }_G$ of the free-group adjunction. Under [L4] the counit corresponds to the identity of $UG$, so ${\epsilon }_G$ is the unique group homomorphism $F(UG)\to G$ carrying each basis element $g$ to $g$; a homomorphism out of a free group is determined by its values on the basis, so it evaluates a reduced word in $UG$ to its product in $G$.

By [L5] the algebra-homomorphism equation says that a function commutes with evaluation of every word. Evaluating the words $[x,y]$, the empty word and $[x^{-1}]$ makes such a function preserve product, identity and inverse, and conversely a group homomorphism preserves the value of every word; so the comparison morphisms are exactly group homomorphisms, in agreement with [L1] and with $K(h)=U(h)$ in [L2].

Evaluating a one-letter word returns its letter, and evaluating after substitution of words agrees with evaluating the flattened word by associativity of group multiplication. These are the algebra unit and multiplication laws.

In the group [L3], one has $\bar{1}+\bar{1}=\bar{0}$ and $\bar{0}+\bar{1}=\bar{1}$, so the displayed three-letter word evaluates to $\bar{1}$.

A map $X\to Y⨿\{\mathrm{\perp }\}$ is a partial function from $X$ to $Y$, with $\mathrm{\perp }$ marking undefined values, so [L1] identifies the Kleisli category with sets and partial functions.

A maybe-monad algebra chooses a point $y_0$ as the value of $\mathrm{\perp }$ and fixes every $y\in Y$ by the unit law; the multiplication law adds no further data. Algebra homomorphisms are precisely basepoint-preserving maps, so the Eilenberg–Moore category is the category of pointed sets.

By [L6] the Kleisli adjunction induces the maybe monad on the nose, so [L5] applies to it and its comparison is the canonical one of [L7]. That comparison sends a Kleisli object $X$ to the free algebra $(T(X),{\mu }_X)$, which step 1.2 identifies with the free pointed set $X⨿\{\mathrm{\perp }\}$ based at $\mathrm{\perp }$, and sends a Kleisli arrow to its underlying function. A quasi-inverse sends a pointed set $(Y,y_0)$ to $Y\setminus \{y_0\}$; adjoining and deleting the basepoint give the natural isomorphisms required by [L2], including the empty Kleisli object and the one-point algebra.

Thus the comparison is an equivalence, and by [L6] the Kleisli right adjoint induces the maybe monad, so it is monadic by [L4].

By [L7] the strict image of the comparison is the full subcategory of free algebras. Under the fixed tagged-coproduct encoding, the pointed singleton $(\{0\},0)$ is isomorphic to but not literally equal to the free pointed set on the empty set, whose point is the distinguished tag $\mathrm{\perp }$, so it is not in that image. The comparison is therefore not surjective on objects and is not an isomorphism by [L3], so strict monadicity fails by [L4].

Define $f=[\sigma ,1]$ and $g=[1,1]:\mathbb{N}⨿\mathbb{N}\rightrightarrows \mathbb{N}$. The second injection $i_1$ is a common section because $f{i}_1=g{i}_1=1_{\mathbb{N}}$, so the pair is reflexive by [L1].

The unique map $q:\mathbb{N}\to 1$ is the coequalizer: the relation $f(i_0(n))=n+1\sim n=g(i_0(n))$ connects every natural to $0$, and any map coequalizing $f,g$ is therefore constant and factors uniquely through $q$.

Applying $\mathbf{S}\mathbf{e}\mathbf{t}(\mathbb{N},-)$ gives a pair $(\mathbb{N}⨿\mathbb{N}{)}^{\mathbb{N}}\rightrightarrows {\mathbb{N}}^{\mathbb{N}}$. For a function $h:\mathbb{N}\to \mathbb{N}⨿\mathbb{N}$, the two resulting sequences $f\circ h$ and $g\circ h$ differ at each coordinate by either $0$ or $1$.

Every finite zigzag generated by pairs from step 2.2 has a uniform coordinatewise difference bound, namely its number of zigzag edges, by repeated use of the triangle inequality on natural-number differences.

The zero sequence $z(n)=0$ and identity sequence $d(n)=n$ have unbounded coordinatewise difference, so step 3.1 shows that no finite zigzag identifies them.

Both sequences map under $q^{\mathbb{N}}$ to the unique element of $1^{\mathbb{N}}$, yet they remain distinct in the coequalizer of the image pair. Therefore $q^{\mathbb{N}}$ is not the coequalizer required by [L2], and $\mathbf{S}\mathbf{e}\mathbf{t}(\mathbb{N},-)$ does not preserve this reflexive coequalizer.

If an ultrafilter on a nonempty finite set contained no singleton, [L1] would put the complement of every singleton into it; their finite intersection is empty, impossible for a filter. Thus it contains some singleton and is principal.

It cannot contain two distinct singletons because their intersection is empty, so the principal point is unique.

By [L2], ${\eta }_X$ is therefore a bijection and ${\xi }_X={\eta }_X^{-1}$. In the discrete topology [L3], an ultrafilter converges precisely to the point whose singleton it contains, so ${\xi }_X$ is the unique-limit map.

The equation ${\xi }_X{\eta }_X=1_X$ is immediate. Since ${\eta }_X$ is bijective by step 3.1, $\beta ({\eta }_X)$ is bijective with inverse $\beta ({\xi }_X)$. The monad unit law in [L4] says ${\mu }_X\beta ({\eta }_X)=1_{\beta X}$, so uniqueness of the inverse gives ${\mu }_X=\beta ({\xi }_X)$. Composing with ${\xi }_X$ yields ${\xi }_X{\mu }_X={\xi }_X\beta ({\xi }_X)$, and ${\xi }_X$ is an algebra.

If $X=\mathrm{\varnothing }$, no ultrafilter exists, so $\beta X=\mathrm{\varnothing }$ and the unique empty map is an algebra. For $X=\{0,1\}$, steps 1.1 and 2.1 give exactly ${\eta }_X(0),{\eta }_X(1)$ and step 3.1 gives their displayed values.

Applying [L1] and [L3] at $A=\mathbb{N}$ gives the free algebra $(\beta \mathbb{N},{\mu }_{\mathbb{N}})$. Its unit includes every natural, including $0$ and $1$, as the corresponding principal ultrafilter.

Specializing the multiplication formula [L2] to $X=\mathbb{N}$ gives the displayed membership equivalence.

The algebra unit equation ${\mu }_{\mathbb{N}}{\eta }_{\beta \mathbb{N}}=1$ and associativity equation ${\mu }_{\mathbb{N}}\beta ({\mu }_{\mathbb{N}})={\mu }_{\mathbb{N}}{\mu }_{\beta \mathbb{N}}$ are exactly the monad unit and associativity laws in [L3].

Assuming UL/BPI, apply [L4] to extend the cofinite filter on $\mathbb{N}$ to an ultrafilter. It is free: if it were principal at $n$, it would contain both $\{n\}$ and the cofinite set $\mathbb{N}\setminus \{n\}$. Thus $\beta \mathbb{N}$ contains both the principal ultrafilters from step 1.1 and free ultrafilters, but no free ultrafilter is claimed without UL/BPI.