On coalgebras over algebras (Q639641): Difference between revisions

\textit{M. Barr} [``Terminal coalgebras in well-founded set theory'', Theor. Comput. Sci. 114, No.\,2, 299--315 (1993; Zbl 0779.18004)] showed that for a bicontinuous endofunctor \(H\) on \(\mathbf{Set}\), the final coalgebra can be realized as the completion of its initial algebra (this works when the endofunctor \(H\) is such that \(H(\varnothing)\neq \varnothing\)). In Section 2 the authors show that Barr's theorem extends from coalgebras on \(\mathbf{Set}\) to coalgebras on \(\mathbf{Alg}(\mathbb{M})\), the Eilenberg-Moore category of algebras for a monad \(\mathbb{M}\) on \(\mathbf{Set}\), dropping the assumption \(H(\varnothing)\neq \varnothing\). Specifically, for an endofunctor \(H\) on \(\mathbf{Set}\) and a monad \(\mathbb{M} = (M,m,u)\) on \(\mathbf{Set}\), they first define an algebra (Eilenberg-Moore) lifting of \(H\) as an endofunctor \(\widetilde{H}\) on \(\mathbf{Alg}(\mathbb{M})\) such that \(H\circ U^{\mathbb{M}} = U^{\mathbb{M}}\circ \widetilde{H}\), where \(U^{\mathbb{M}}\) is the forgetful functor from \(\mathbf{Alg}(\mathbb{M})\) to \(\mathbf{Set}\). Then it is shown (Theorem 2.2) that, for a category \(\mathbf{C}\), an endofunctor \(H\) on \(\mathbf{C}\), and a monad \(\mathbb{M}\) on \(\mathbf{C}\), there is a bijection between a suitable set of natural transformations from \(M\circ H\) to \(H\circ M\) and the set of all algebra lifts of \(H\). Therefore, the monad \(\mathbb{M}\) also lifts to a monad \(\widetilde{\mathbb{M}}\) on \(\mathbf{Coalg}(H)\), the categories \(\mathbf{Coalg}(\widetilde{H})\) and \(\mathbf{Alg}(\widetilde{\mathbb{M}})\) are isomorphic, and \(F^{\mathbb{M}}\dashv U^{\mathbb{M}}\) lifts to the adjunction \(\widetilde{F}\dashv \widetilde{U}\) associated with \(\widetilde{\mathbb{M}}\), so that \(U_{H}\circ \widetilde{U} = U^{\mathbb{M}}\circ U_{\widetilde{H}}\) and \(U_{\widetilde{H}}\circ \widetilde{F} = F^{\mathbb{M}}\circ U_{H}\). Using this, the authors show that, given an \(\omega^{\mathrm{op}}\)-continuous endo\-functor \(H\) on \(\mathbf{Set}\) and a monad \(\mathbb{M}\) on \(\mathbf{Set}\), if (1) \(M(\varnothing) = 1\), (2) \(H\) admits a lifting \(\widetilde{H}\) to \(\mathbf{Alg}(\mathbb{M})\), and (3) the lifted functor \(\widetilde{H}\) is \(\omega\)-cocontinuous, then the carrier of the final \(H\)-coalgebra is the Cauchy completion of the image of the initial \(\widetilde{H}\)-algebra under a suitable ultrametric, and this completion is compatible with the algebra structure (in the sense that both objects involved become topological algebras). In Section 3 it is discussed under which conditions the initial \(\widetilde{H}\)-algebra is free as an \(\mathbb{M}\)-algebra and can be realized by a ``similar'' construction (in the sense of extending a functor from \(\mathbf{Set}\) to \(\mathbf{Alg}(\mathbb{M})\)). More precisely, after defining, for an endofunctor \(H\) on \(\mathbf{Set}\) and a monad \(\mathbb{M}\) on \(\mathbf{Set}\), the Kleisli lifting of \(H\) as an endofunctor \(\widehat{H}\) on \(\mathbf{Kl}(\mathbb{M})\), the Kleisli category for \(\mathbb{M}\), such that \(F_{\mathbb{M}}\circ H = \widehat{H}\circ F_{\mathbb{M}}\), where \(F_{\mathbb{M}}\) is the canonical functor from \(\mathbf{Set}\) to \(\mathbf{Kl}(\mathbb{M})\), and taking the left Kan extension \(\overline{H}\colon \mathbf{Alg}(\mathbb{M})\rightarrow \text\textbf{Alg}(\mathbb{M})\) of \(\Phi\circ\widehat{H}\) along \(\Phi\), where \(\Phi\colon \mathbf{Kl}(\mathbb{M})\rightarrow\text\textbf{Alg}(\mathbb{M})\) is the comparison functor, they show that \(\overline{H}\circ F^{\mathbb{M}} \cong F^{\mathbb{M}}\circ H\). Following this the authors consider two endofunctors \(T\), \(H\) on \(\mathbf{Set}\) such that both an algebra lifting \(\widetilde{H}\) of \(H\) and a Kleisli lifting \(\widehat{T}\) of \(T\) exist and \(\widetilde{H}\cong \overline{T}\). Then it holds that \(M\circ T\cong H\circ M\). This seems to motivate the authors to call, for a monad \(\mathbb{M}\) on \(\mathbf{Set}\), a pair of endofunctors \((T,H)\) on \(\mathbf{Set}\) an \(\mathbb{M}\)-commuting pair if \(M\circ T\cong H\circ M\). Finally, assuming that \((T,H)\) form an \(\mathbb{M}\)-commuting pair such that the natural bijection \(M(T(X))\cong H(M(X))\) is an algebra morphism, they prove that if \(H\) is \(\omega^{\mathrm{op}}\)-continuous and \(M(\varnothing) = 1\) as \(\mathbb{M}\)-algebras, then the final \(H\)-coalgebra is the completion of the free \(\mathbb{M}\)-algebra built on the initial \(T\)-algebra under a suitable metric. Reviewer's remarks: Definition 2.1 of the present article which deals with the concept of algebra lifting is a particular case of Definition 2.19 of the article by the reviewer and \textit{J. Soliveres Tur} [``Kleisli and Eilenberg-Moore constructions as parts of biadjoint situations'', Extr. Math. 25, No. 1, 1--61 (2010; Zbl 1223.18002)], which deals with the notion of Eilenberg-Moore morphisms from \((\mathbf{C},\mathbb{T})\) to \((\mathbf{C}',\mathbb{T}')\). Moreover, the equivalence between the first and the second statement in Theorem 2.2 of the present article is also a particular case of Proposition 2.21 of the aforementioned article [loc. cit.]. Identical observations are applicable for the concept of Kleisli lifting and for the corresponding equivalence. Finally, Balan and Kurz assert that there is a large class of \(\mathbf{Set}\)-monads \(\mathbb{M}\) such that \(\mathbf{Alg}(\mathbb{M})\) has a zero object. This is true, but it is also true that there are many interesting monads \(\mathbb{M}\) on \(\mathbf{Set}\) (and monads on \(\mathbf{Set}^{S}\), with \(S\) a set of sorts for which \(\text{card}(S)\geq 2\)) such that \(\mathbf{Alg}(\mathbb{M})\) does not have a zero object.