Is there an explicit construction of a free coalgebra? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T20:32:44Z http://mathoverflow.net/feeds/question/31109 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31109/is-there-an-explicit-construction-of-a-free-coalgebra Is there an explicit construction of a free coalgebra? Bruce Westbury 2010-07-08T20:09:15Z 2012-01-22T17:54:26Z <p>I am interested in the differences between algebras and coalgebras. Naively, it does not seem as though there is much difference: after all, all you have done is to reverse the arrows in the definitions. There are some simple differences: </p> <p>The dual of a coalgebra is naturally an algebra but the dual of an algebra need not be naturally a coalgebra. </p> <p>There is the Artin-Wedderburn classification of semisimple algebras. I am not aware of a classification even of simple, semisimple coalgebras. </p> <p>More surprising is: a finitely generated comodule is finite dimensional.</p> <p>This question is about a more striking difference. The free algebra on a vector space $V$ is $T(V)$, the tensor algebra on $V$. I have been told that there is no explicit construction of the free coalgebra on a vector space. However these discussions took place following the consumption of alchohol. What is known about free colagebras?</p> http://mathoverflow.net/questions/31109/is-there-an-explicit-construction-of-a-free-coalgebra/31112#31112 Answer by supercooldave for Is there an explicit construction of a free coalgebra? supercooldave 2010-07-08T20:25:45Z 2010-07-08T20:33:57Z <p>One place to really see the difference is by considering <a href="http://dx.doi.org/10.1016/S0304-3975%2800%2900056-6" rel="nofollow">Universal Coalgebra</a> (also known as <a href="http://en.wikipedia.org/wiki/F-coalgebra" rel="nofollow">F-coalgebras</a>) (in contrast to <a href="http://en.wikipedia.org/wiki/Universal_algebra" rel="nofollow">Universal Algebra</a>). The structures considered by Universal Coalgebra are typically infinite, whereas those considered by Universal Algebra are finite. This is taken from a computer science angle. Universal Algebra is about data types and Universal Coalgebra is about systems. Initial algebras are correspond to least fixed points, whereas final coalgebras correspond to greatest fixed points.</p> <p>A <em>free coalgebra</em> (in this setting) corresponds to the final coalgebra of some functor (although one would call it a cofree coalgebra). A general introduction to the kinds of coalgebras I'm talking about is <em><a href="http://www.tac.mta.ca/tac/volumes/14/8/14-08.ps" rel="nofollow">Introduction to Coalgebra</a></em> by Jiri Adamek. This <a href="http://arxiv.org/abs/math/0403227v1" rel="nofollow">paper</a> provides a way of constructing the final coalgebras for a certain class of functors.</p> http://mathoverflow.net/questions/31109/is-there-an-explicit-construction-of-a-free-coalgebra/31126#31126 Answer by Theo Johnson-Freyd for Is there an explicit construction of a free coalgebra? Theo Johnson-Freyd 2010-07-08T22:07:53Z 2012-01-22T17:54:26Z <p>There cannot be a "free coalgebra" functor, at least in what I think is the standard usage. Namely, suppose that "orange" is a type of algebraic object, for which there is a natural "forgetful" functor from "orange" objects to "blue" objects. Then the "free orange" functor from Blue to Orange is the <em>left</em> adjoint, if it exists, to the forgetful map from Orange to Blue.</p> <p>Suppose that the forgetful map from coalgebras to vector spaces had a left adjoint; then it would itself be a right adjoint, and so would preserve products. Now the product in the category of coalgebras is something huge &mdash; think about the coproduct in the category of algebras, which is some sort of <a href="http://en.wikipedia.org/wiki/Free_product" rel="nofollow">free product</a> &mdash; and it's clear that the forgetful map does not preserve products.</p> <p>On the other hand, the coproduct in the category of coalgebras is given by the direct sum of underlying vector spaces, and so the forgetful map does preserve coproducts. This suggests that it may itself be a left adjoint; i.e. it may have a <em>right</em> adjoint from vector spaces to coalgebras, which should be called the "cofree coalgebra" on a vector space.</p> <p>Let me assume axiom of choice, so that I can present the construction in terms of a basis. Then I believe that the cofree coalgebra on the vector space with basis $L$ (for "letters") is the graded vector space whose basis consists of all words in $L$, with the comultiplication given by $\Delta(w) = \sum_{a,b| ab = w} a \otimes b$, where $a,b,w$ are words in $L$. I.e. the cofree coalgebra has the same underlying vector space as the free algebra, with the dual multiplication. It's clear that for finite-dimensional vector spaces, the cofree coalgebra on a vector space is (canonically isomorphic to) the graded dual of the free algebra on the dual vector space. Anyway, this is clearly a coalgebra, and the map to the vector space is zero on all words that are not singletons and identity on the singletons. I haven't checked the universal property, though.</p> <p><strong>Edit:</strong> The description above of the cofree coalgebra is incorrect. I learned the correct version from Alex Chirvasitu. The description is as follows. Let $V$ be a vector space, and write $\mathcal T(V)$ for the tensor algebra of $V$, i.e. for the free associative algebra generated by $V$. Then the cofree coassociative algebra cogenerated by $V$ is constructed as follows. First, construct $\mathcal T(V^\ast)$, and second construct its <em>finite dual</em> $\mathcal T(V^\ast)^\circ$, which is the direct limit of duals to finite-dimensional quotients of $\mathcal T(V^\ast)$. There is a natural inclusion $\mathcal T(V^\ast)^\circ \hookrightarrow \mathcal T(V^\ast)^\ast$, and a natural map $\mathcal T(V^\ast)^\ast \to V^{\ast\ast}$ dual to the inclusion $V^\ast \to \mathcal T(V^\ast)$. Finally, construct $\operatorname{Cofree}(V)$ <strong>as the union of all subcoalgebras of $\mathcal T(V^\ast)^\circ$ that map to $V \subseteq V^{\ast\ast}$ under the map $\mathcal T(V^\ast)^\circ \hookrightarrow \mathcal T(V^\ast)^\ast \to V^{\ast\ast}$. Details are in section 6.4 (and specifically 6.4.2) of the book <em>Hopf Algebras</em> by Moss E. Sweedler.</strong></p> <p>In any case, $\operatorname{Cofree}(V)$ is something like the coalgebra of "finitely supported distributions on $V$" (or, anyway, that's is how to think of it in the cocomutative version). For example, when $V = \mathbb k$ is one-dimensional, and $\mathbb k = \bar{\mathbb k}$ is algebraically closed, then $\operatorname{Cofree}(V) = \bigoplus_{\kappa \in \mathbb k} \mathcal T(\mathbb k)$. I should emphasize that now when I write $\mathcal T(\mathbb k)$, in characteristic non-zero I do not mean to give it the Hopf algebra structure. Rather, $\mathcal T(\mathbb k)$ has a basis $\lbrace x^{(n)}\rbrace$, and the comultiplication is $x^{(n)} \mapsto \sum x^{(k)} \otimes x^{(n-k)}$. Identifying $x^{(n)} = x^n/n!$, this is the comultiplication on the "divided power" algebra. It's reasonable to think of the $\kappa$th summand as consisting of (divided power) polynomials times $\exp(\kappa x)$, but maybe better to think of it as the algebra of descendants of $\delta(x - \kappa)$ &mdash; but this is just some Fourier duality.</p> <p>In the non-algebraically-closed case, there are also summands corresponding to other closed points in the affine line. <strong>end edit</strong></p> <hr> <p>I should mention that in my mind the largest difference between algebras and coalgebras (by which I mean, and I assume you mean also, "associative unital algebras in Vect" and "coassociative counital coalgebras in Vect", respectively) is one of finiteness. You hinted at the difference in your answer: if $A$ is a (coassociative counital) coalgebra (in Vect), then it is a colimit (sum) of its finite-dimensional subcoalgebras, and moreover if $X$ is any $A$-comodule, then $X$ is a colimit of its finite-dimensional sub-A-comodules. This is absolutely not true for algebras. It's just not the case that every algebra is a limit of its finite-dimensional quotient algebras. A good example is any field of infinite-dimension.</p> <p>It follows from the finiteness of the corepresentation theory that a coalgebra can be reconstructed from its category of <em>finite-dimensional</em> corepresentations. Let $A$ be a coalgebra, <code>$\text{f.d.comod}_A$</code> its category of finite-dimensional right comodules, and <code>$F : \text{f.d.comod}_A \to \text{f.d.Vect}$</code> the obvious forgetful map. Then there is a coalgebra <code>$\operatorname{End}^\vee(F)$</code>, defined as some natural coequalizer in the same way that the algebra of natural transformations <code>$F\to F$</code> is defines as some equalizer, and there is a canonical coalgebra isomorphism <code>$A \cong \operatorname{End}^\vee(F)$</code>. (Proof: see André Joyal and Ross Street, An introduction to Tannaka duality and quantum groups, Category theory (Como, 1990), Lecture Notes in Math., vol. 1488, Springer, Berlin, 1991, pp. 413–492. MR1173027 (93f:18015).)</p> <p>For an algebra, on the other hand, knowing its finite-dimensional representation theory is not nearly enough to determine the algebra. Again, the example is of an infinite-dimensional field (e.g. the field of rational functions). On the other hand, it is true that knowing the <em>full</em> representation theory of an algebra determines the algebra. Namely, if $A$ is an (associcative, unital) algebra (in Vect), <code>$\text{mod}_A$</code> its category of all right modules, and <code>$F: \text{mod}_A \to \text{Vect}$</code> the forgetful map, then there is a canonical isomorphism <code>$A \cong \operatorname{End}(F)$</code>. (Proof: $F$ has a left adjoint, $V \mapsto V\otimes A$. But $V \mapsto V\otimes \operatorname{End}(F)$ is also left-adjoint to $F$. The algebra structure comes from the adjunction: the <code>$\text{mod}_A$</code> map $A\otimes A \to A$ corresponds to the vector space map $\operatorname{id}: A\to A$.) ((Note that you don't actually need the <em>full</em> representation theory, which probably doesn't exist foundationally, but you do need modules at least as large as $A$.))</p> <p>All this all means is that if you believe that almost everything is finite-dimensional, you should reject algebras as "wrong" and coalgebras as "right", whereas if you like infinite-dimensional objects, algebras are the way to go.</p> http://mathoverflow.net/questions/31109/is-there-an-explicit-construction-of-a-free-coalgebra/31127#31127 Answer by darij grinberg for Is there an explicit construction of a free coalgebra? darij grinberg 2010-07-08T22:26:17Z 2010-07-08T22:26:17Z <p>This may be the third time here that I am linking to <a href="http://arxiv.org/abs/0804.3888" rel="nofollow">Michiel Hazewinkel's "Witt vectors, part 1"</a>. This time it's Section 12, mainly 12.11. The graded cofree coalgebra over a vector space is the tensor coalgebra (i. e. the tensor algebra, but you forget the tensor multiplication and instead take the deconcatenation coproduct). "Graded" means that all morphisms in the universal property are supposed to be graded. If you leave out the "graded", however, things get difficult. I have but briefly skimmed the contents of <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V0K-48V83V7-1&amp;_user=10&amp;_coverDate=09%252F01%252F2003&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=a1678af0192840112562c56a066be7ad" rel="nofollow">this paper</a>, but it seems to contain a description.</p> http://mathoverflow.net/questions/31109/is-there-an-explicit-construction-of-a-free-coalgebra/80263#80263 Answer by robot for Is there an explicit construction of a free coalgebra? robot 2011-11-07T02:28:45Z 2011-11-07T02:28:45Z <p>I do not know the answer for your question, but let me rephrase the warning that takes places right after Definition 4.17 (p.21) of certain unrelated <a href="http://arxiv.org/abs/0705.3719" rel="nofollow">lecture notes</a>:</p> <blockquote> <p>Contrary to general belief, the coalgebra $T(V)$ with the projection $T(V) → V$ is not cofree in the category of coassociative coalgebras! Cofree coalgebras (in the sense of the obvious dual of definition of free algebras) are surprisingly complicated objects [10, 43, 20]. The coalgebra $T (V )$ is, however, cofree in the subcategory of coaugmented nilpotent coalgebras [38, Section II.3.7].</p> </blockquote> <p>[10] T.F. Fox. The construction of cofree coalgebras. J. Pure Appl. Algebra, 84(2):191–198, 1993.</p> <p>[20] M. Hazewinkel. Cofree coalgebras and multivariable recursiveness. J. Pure Appl. Algebra, 183(1-3):61–103, 2003.</p> <p>[43] J.R. Smith. Cofree coalgebras over operads. Topology Appl., 133(2):105–138, September 2003.</p> <p>[38] M. Markl, S. Shnider, and J. D. Stasheﬀ. Operads in Algebra, Topology and Physics, volume 96 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, Rhode Island, 2002.</p>