%This is "The Construction of Cofree Coalgebras" by Tom Fox
%It appeared in JPAA 84 (1993)
%It should be run using Latex
\documentstyle[12pt]{article}
% This is a file of macros accumulated since 1987 called ftex.tex
% It is Barr's mtex modified by Fox
\hyphenation{co-ho-mol-ogy } \font\tensfb=cmssbx10 scaled\magstep1\font\sevensfb=cmssbx10\textfont11=\tensfb \scriptfont11=\sevensfb\scriptscriptfont11=\sevensfb\font\tenfrak=eufm10 scaled\magstep1\font\sevenfrak=eufm7 scaled\magstep1\font\fivefrak=eufm5 scaled\magstep1\textfont12=\tenfrak \scriptfont12=\sevenfrak\scriptscriptfont12=\fivefrak\long\def\ig#1{\relax} \makeatletter \def\mld{\null\,$$\vcenter\bgroup\def\\{\cr&}\openup9pt\m@th\ialign\bgroup\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil\crcr}\def\emld{\crcr\egroup\egroup\,$$}
%ARROWS
\newcount \repetitions\def\repto#1 {\mathrel{\repetitions=0\loop\ifnum\repetitions<#1 \advance \repetitions by 1 \relbar\mkern-3.2mu\repeat\rightarrow}}
\def\to{\repto0 }\def\reptwo#1 {\mathrel{\vcenter{\hbox{\oalign {$\repto{#1}$\crcr$\repto{#1}$}}}}}
\def\two{\reptwo0 }\def\Two{\reptwo1 }
\def\tofro{\mathrel{\vcenter{\hbox{\oalign{$\longrightarrow$\crcr$\longleftarrow$}}}}}
\def\tl{\leftarrow}\def\from{\leftarrow}\def\imp{\Rightarrow}
\def\epi{\mathrel{\mathchar"221\mkern -12mu\mathchar"221}}
\def\leftepi{\mathrel{\mathchar"220\mkern -12mu\mathchar"220}}
\def\mon{\mathrel{\m@th\hbox to 14.6pt{\lasyb\char'51\hskip-2.1pt$\arrext$\hss$\mathord\rightarrow$}}}
% width of \epi
\def\leftmono{\mathrel{\m@th\hbox to14.6pt{$\mathord\leftarrow$\hss$\arrext$\hskip-2.1pt\lasyb\char'50}}}
% width of \epi
\font\lasyb=lasyb10 scaled \magstephalf % for \mon
\mathchardef\arrext="0200 % amr minus for arrow extension (see \into)
\makeatother \def\mathopn#1{\expandafter\def\csname#1\endcsname{\mathop{\rm#1}\nolimits}}
\def\mathbf#1{\expandafter\def\csname#1\endcsname{{\rm\bf#1}}}
\def\mathrm#1{\expandafter\def\csname#1\endcsname{{\rm#1}}}
%ABREVIATIONS FOR EDITING
\def\bdoc{\begin{document}}\def\edoc{\end{document}}\def\bcenter{\begin{center}}
\def\ecenter{\end{center}}\def\bd{\begin{description}}\def\ed{\end{description}}
\def\beq{\begin{equation}}
%for numbered equations and
\def\eeq{\end{equation}}
\def\beqn{\equation}
\def\eeqn{\endequation}\def\be{\begin{enumerate}}\def\ee{\end{enumerate}}\def\bitem{\begin{itemize}}
\def\eitem{\end{itemize}}\def\bpic{\begin{picture}}
\def\epic{\end{picture}}\def\btab{\begin{tabular}}\def\etab{\end{tabular}}
\def\pa{\vfill\newpage}\def\beqa{\begin{equation}\begin{array}{c}}\def\eeqa{\end{array}\end{equation}\vskip 2ex}\def\bref{\bigskip\begin{center}{\bf References}\end{center}\newcounter{reff}\begin{list}{\bf\arabic{reff}}{\usecounter{reff}}\itemsep-1ex}
%{\leftmargin8mm \itemindent-8mm \itemsep2pt \topsep0pt}}
%{\itemindent{-10pt}}{\labelsep}{10pt}}\def\eref{\end{list}}
\def\abst{\begin{quotation}\footnotesize\begin{center}{\bf Abstract}\end{center}\noindent} \def\eabst{\end{quotation} \normalsize\par\noindent} \def\hh{\hspace{1em}}
\def\vvn{\vskip1ex\noindent}\def\vv{\vskip1ex}\def\kk{\kern-1.02em}\def\nn{\hspace{-1em}} \def\thm{\refstepcounter{subsection}\vvn{\bf\thesubsection\hh Theorem:}\hh\begingroup\em}
\def\thp{\refstepcounter{subsection}\vvn{\bf\thesubsection\hh Proposition:}\hh\begingroup\em}
\def\thc{\refstepcounter{subsection}\vvn{\bf\thesubsection\hh Corollary:}\hh\begingroup\em}
\def\thl{\refstepcounter{subsection}\vvn{\bf\thesubsection\hh Lemma:}\hh\begingroup\em} \def\subd{\refstepcounter{subsection}\vvn{\bf\thesubsection\hh Definition:}\hh}
\def\sube{\refstepcounter{subsection}\vvn{\bf\thesubsection\hhExample:}\hh}
\def\subr{\refstepcounter{subsection}\vvn{\bf\thesubsection\hhRemarks:}\hh} \def\eth{\endgroup \par\addvspace{\medskipamount}}
\def\proof{\par\addvspace{\medskipamount}\noindent Proof.\enskip}
\def\endproof{~\hfill\Box\par\addvspace{\medskipamount}}
\def\emph{\begingroup\em}
\def\pf{\proof}\def\epf{\endproof}
\def\subs#1{\subsection{#1}}
%MATH OPERATIONS
\def\Box{\vbox{\hrule\hbox{\vrule\kern.5ex \vbox{\kern1ex}\kern.5ex\vrule}\hrule}}
\def\dir{\oplus}\def\iso{\cong}\def\join{\vee}\def\meet{\wedge}\def\op{{}^{\rm op}}
\def\o{\circ}
\def\relstack#1#2#3{\mathrel{\mathop{#1}\limits^{\textstyle#2}\limits_{\textstyle#3}}}
%tensors
\def\ten{\otimes}
\def\TEN{\bigotimes}\def\Ten{\mathop{\:\hbox{$\times$}\kern-.3em\raise.2pt\hbox{\makebox(45,45){\circle{62}}}}}
\def\Bx{\:\Box\:}\def\BX{\:\:\Box\:\:}\def\Cup{\bigcup}
\def\eps{\varepsilon}\def\x{\times}\def\.{\cdot} \def\emph#1{{\em #1}\futurelet\next\itcorr}
\def\itcorr{\ifx\next.\else\if\next,\else\/\fi\fi}\def\obeylines{\catcode`\^^M=\active}{\obeylines \gdef^^M{\leavevmode\par\noindent}}
\def\bfig{\begin{picture}(\xext,\yext)(\xoff,\yoff)}\def\efig{\end{picture}}
%GREEK LETTERS
\def\gkk{\kappa}\def\gka{\alpha}\def\gkb{\beta}\def\gkg{\gamma}\def\gkc{\gamma}
\def\gkd{\delta}\def\gkD{\Delta}\def\Del{\Delta}\def\gke{\varepsilon}\def\gkf{\phi}
\def\gkm{\mu}\def\gkn{\nu}\def\gkp{\pi}\def\gkw{\omega}\def\gkW{\Omega}
\def\gkk{\kappa}\def\gkt{\tau}\def\gkl{\lambda}
\def\gkL{\Lambda}\def\gks{\sigma}\def\gkx{\chi}\def\gkz{\zeta}\def\gkK{\Kappa}
%OTHER MATH CHARACTERS
\mathchardef\Asc="0241\mathchardef\B="0B42
\mathchardef\Bsc="0242\mathchardef\C="0B43\mathchardef\Csc="0243
\mathchardef\D="0B44\mathchardef\Dsc="0244
\mathchardef\E="0B45\mathchardef\Esc="0245
\def\F{{\bf F}}
\mathchardef\Fsc="0246
\def\G{{\bf G}}\mathchardef\Gsc="0247
\mathchardef\H="0B48\mathchardef\Hsc="0248\mathchardef\I="0B49
\mathchardef\Isc="0249\mathchardef\J="0B4A\mathchardef\Jsc="024A\mathchardef\K="0B4B
\mathchardef\Ksc="024B
%\mathchardef\L="0B4C
\mathchardef\Lsc="024C
%\mathchardef\M="0B4D
\mathchardef\Msc="024D
%\mathchardef\N="0B4E
\mathchardef\Nsc="024E
%\mathchardef\O="0B4F
\mathchardef\Osc="024F
%\mathchardef\P="0B50
\mathchardef\Psc="0250
%\def\Q{{\bf Q}}
\mathchardef\Qsc="0251
\def\R={{\bf R}}
\mathchardef\Rsc="0252
%\def\S={{\bf S}}
\mathchardef\Ssc="0253\def\T{{\bf T}}
\mathchardef\Tsc="0254
\def\U{{\bf U}}\mathchardef\Usc="0255
\mathchardef\V="0B56\mathchardef\Vsc="0256\mathchardef\W="0B57
\mathchardef\Wsc="0257\mathchardef\X="0B58\mathchardef\Xsc="0258\mathchardef\Y="0B59
\mathchardef\Ysc="0259\mathchardef\Z="0B5A\mathchardef\Zsc="025A\mathchardef\Afk="0C41
\mathchardef\Bfk="0C42\mathchardef\Cfk="0C43\mathchardef\Dfk="0C44\mathchardef\Efk="0C45
\mathchardef\Ffk="0C46\mathchardef\Gfk="0C47\mathchardef\Hfk="0C48\mathchardef\Ifk="0C49
\mathchardef\Jfk="0C4A\mathchardef\Kfk="0C4B\mathchardef\Lfk="0C4C\mathchardef\Mfk="0C4D
\mathchardef\Nfk="0C4E\mathchardef\Ofk="0C4F\mathchardef\Pfk="0C50\mathchardef\Qfk="0C51
\mathchardef\Rfk="0C52\mathchardef\Sfk="0C53\mathchardef\Tfk="0C54\mathchardef\Ufk="0C55
\mathchardef\Vfk="0C56\mathchardef\Wfk="0C57\mathchardef\Xfk="0C58\mathchardef\Yfk="0C59
\mathchardef\Zfk="0C5A\mathchardef\gt="313E
%relation\mathchardef\lt="313C
%relation\mathchardef\lte="0214
%\leq, with class of ordinary char
\mathbf{Arith}\mathbf{Array}\mathbf{BinOp}\mathbf{BinTree}
\mathbf{Cat}\mathbf{Complex}\mathbf{Dom}\mathbf{Diag}\mathbf{FL}\mathbf{Nat}
\mathbf{PO}\mathbf{Real}\mathbf{Rec}\mathbf{Set}\mathbf{Stack}\mathbf{String}\mathbf{Th}\mathbf{Trig} \mathrm{Bider}\mathrm{Der}\mathrm{Diff}\mathrm{exp}\mathrm{Gal}\mathrm{Hom}
\mathrm{Hoch}\mathrm{Hom}\mathrm{Ob}\mathrm{Sub}\mathopn{colim}\mathrm{comp}
\mathrm{eval}\mathrm{id}\mathrm{mult}\mathrm{proj}\mathrm{rec}\mathrm{source}
\mathrm{sou}\mathrm{Spec}\mathrm{succ}\mathrm{target}\mathrm{tar}\mathrm{unit} \newcounter{lister}\newcounter{romlister}\newcounter{alphlister} \newenvironment{romlist}
%{\begin{list}{{\rm(\roman{romlister})}}{\usecounter{romlister}}}
%{\end{list}}\def\bromlist{\begin{romlist}}\def\eromlist{\end{romlist}}
%\newenvironment{alphlist}%{\begin{list}{{\rm(\alph{alphlister})}}{\usecounter{alphlister}}}
%{\end{list}}\def\balphlist{\begin{alphlist}}\def\ealphlist{\end{alphlist}}
%\newenvironment{labeledlist}[1]{\begin{list}{{\rm#1\arabic{lister}. }}{\usecounter{lister}}}
%begin text{\end{list}}
%\def\blist#1{\begin{labeledlist}{#1}}
\def\elist{\end{labeledlist}}
\newdimen\down\def\nl{\par\advance\down by -14.4pt} \def\[{[\![}\def\]{]\!]}
%This is a list of references collected by T Fox
%They are (more or less) in order by author
%They reflect Fox's interest in category theory, deformation theory,
%homological algebra, coalgebras, quantum groups, and Hopf algebras.
\def\allenferrar{H. Allen and J. Ferrar, {\em Weighted incidence coalgebras}. \jalg{51} (1978) 1--11.}
\def\artin{M. Artin, {\em Deformations of singularities}. Tata Institute of Fundamental Research, Lecture Notes {\bf 54} (1976).}
% MICHAEL BARR
\def\barrctc{M. Barr, {\em Cohomology in tensored categories}.In \lajolla, 344--354.} \def\barrshukla{M. Barr, {\em Shukla cohomology and triples}.\jalg{5} (1967) 222--231.} \def\barrharrison{M. Barr, {\em Harrison homology, Hochschild homology and triples}. \jalg{8} (1968) 314--323.} \def\barrcomposite{M. Barr, {\em Composite cotriples and derived functors}In {\bf Seminar on Triples and Categorical Homology Theory}, \lnm{80} (1969) 336--356.} \def\barrexact{M. Barr, {\em Exact Categories}. In {\bf Exact Categories and Categories of Sheaves}, \lnm{236} (1971) 2--121.} \def\barrcoalg{M. Barr, {\em Coalgebras over a commutative ring}. \jalg{32} (1974) 600--610.} \def\barrpoints{M. Barr, {\em Toposes without points}. \jpaa{5} (1974) 265--280.} \def\barrrepresentations{M. Barr, {\em Representations of categories}. \jpaa{41} (1986) 113--137.} \def\barrll{M. Barr, {\em Accessible categories and models of linear logic}. Preprint 1990.} \def\barrcofree{M. Barr, {\em Terminal coalgebras in well-founded set theory}. \tcs{} (to appear)} \def\barrtermcoalg{M. Barr, {\em Terminal coalgebras in well-founded set theory}. \tcs{} (to appear)} \def\barrx{M. Barr, unpublished manuscript.} \def\barrbeckacyclicmodels{M. Barr and J. Beck, {\em Acyclic models and triples}. In \lajolla, 336--343.} \def\barrbeckacyclic{M. Barr and J. Beck, {\em Acyclic models andtriples}. In \lajolla, 336--343.} \def\barrbecksp80{M. Barr and J. Beck, {\em Homology and standard constructions}. In {\bf Seminar on Triples and Categorical Homology Theory}, \lnm{80} (1969) 245--335.} \def\beckthesis{J. Beck, {\em Triples, algebras and cohomology}. Dissertation, Columbia University, New York (1967).} \def\becklaws{J. Beck, {\em Distributive laws}. In {\bf Seminar on Triples and Categorical Homology Theory}, \lnm{80} (1969) 119--140.}
%%%%%%%%%%%%%%%%%%%%
\def\bensonbialgebras{David B. Benson, {\em Bialgebras: some foundations for distributed and concurrent computation}. Fundamenta Informaticae{\bf 12} (1989) 427--486.} \def\bensonimpartiality{David B. Benson, {\em On Impartiality}.WSU Tech. Rpt., 1992.} \def\bergmaneverybody{G. Bergman, {\em Everybody knows what a Hopf algebra is}. Contemporary Math. {\bf 43} (1985) 25--48.} \def\block{R. Block, {\em Commutative Hopf algebras, Lie coalgebras, and divided powers}. \jalg{96} (1985) 275--317.} \def\blockleroux{R. Block and P. Leroux, {\em Generalized dual coalgebras of algebras, with applications to cofree coalgebras}. \jpaa{36} (1985) 15--25.} \def\browncohomology{K. Brown, {\bf Cohomology of Groups}. \springer, 1982.} \def\coffeefiltered{J. Coffee, {\em Filtered and associated graded rings}. \amsbull{78} (1972) 584--587.} \def\coffeerigid{J. Coffee, {\em On the rigidity of graded algebras}. \amsproc{76} (1979) 219--222.} \def\diazharris{S. Diaz and J. Harris, {\em Ideals associated todeformations of singular plane curves}. \amstrans{309} (1988) 433--468.} \def\doi{Y. Doi, {\em Homological coalgebra}. J. Math. Soc. Japan {\bf 33} (1981) 31--50.} \def\donaldflanigan{J. Donald and F. Flanigan, {\em Deformations of algebra modules}. \jalg{31} (1974) 245--256.}
% DRINFELD
\def\drinfeldhaqybe{V. Drinfel'd, {\em Hopf algebras and the quantumYang-Baxter equation}. Soviet Math. Dokl. {\bf 32} (1985) 254--258.} \def\drinfeldqgicm{V. Drinfel'd, {\em Quantum groups}. Proc. I.C.M., 1986.} \def\drinfeldqgjsm{V. Drinfel'd, {\em Quantum groups}. J. Soviet Math. {\bf 41} (1988) 898--915.} \def\drinfeldacha{V. Drinfel'd, {\em On almost cocommutative Hopfalgebras}. Leningrad Math. J. {\bf 1} (1990) 321--342.} \def\drinfeldqha{V. Drinfel'd, {\em Quasi-Hopf algebras}. LeningradMath. J. {\bf 1} (1990) 1419--1457.} \def\drinfeldqqa{V. Drinfel'd, {\em On quasitriangular quasi-Hopf algebrasand a group closely connected with $\Gal(\overline{\bf Q}/\bf Q)$}. Leningrad Math. J. {\bf 2} (1991) 829--860.}
%%%%%%%%%%%%%%
\def\eilenbergkelly{S. Eilenberg and G. M. Kelly, {\em Closed categories}. In \lajolla , 421--562.} \def\EK{\eilenbergkelly} \def\eilenbergsteenrod{S. Eilenberg and N. Steenrod, {\bf Foundations of Algebraic Topology}. Princeton University Press, New Jersey, 1952.} \def\ES{\eilenbergsteenrod} \def\eilenbergmoorretriples{S. Eilenberg and J. Moore, {\em Adjoint functors and triples}. Ill. J. Math {\bf 9} (1965) 381--398.} \def\EMt{\eilenbergmoorretriples} \def\eilenbergmoorrefibrations{S. Eilenberg and J. Moore, {\em Homology and fibrations I: coalgebras, cotensor product and its derived functors}. Comm. Math. Helv. {\bf 40} (1966) 199--236} \def\EMf{\eilenbergmoorrefibrations}
%FOX
\def\foxmasters{T. Fox, {\em Combinatory logic and cartesian closedcategories}. M.Sc. thesis, McGill University, l970.} \def\foxcombinatory{T. Fox, {\em Cartesian products in combinatory logic.}Preprint 1975.} \def\foxcartesian{T. Fox, {\em Coalgebras and cartesian categories}. \commalg{4} (1976) 665--667.} \def\foxpurity{T. Fox. {\em Purity in locally-presentable monoidal categories}. \jpaa{8}, (1976) 261--265.} \def\foxenrichments{T. Fox, {\em The coalgebra enrichment of algebraic categories}. \commalg{9} (1981) 223--234.} \def\foxalgdefos{T. Fox, {\em Algebraic deformations and triple cohomology}. \amsproc{78} (1982) 584--587.} \def\foxjumpdefos{T. Fox, {\em Jump deformations and triple cohomology}.\jalg{105} (1987) 437--442.} \def\foxmilan{T. Fox, {\em On the enriched cohomology of algebras}. Ren.Sem. Mat. Fis. Milano {\bf 62} (1987) 249--260.} \def\foxtensor{T. Fox, {\em The tensor product of Hopf algebras}. Rend.Mat. Trieste {\bf 24} (1992) 65--71.} \def\foxoperations{T. Fox, {\em Operations on triple cohomology}.\jpaa{51} (1988) 119--128.} \def\foxbicohomology{T. Fox, {\em Algebraic deformations and bicohomology}. \canbull{32} (1989) 182--189.} \def\foxintro{T. Fox, {\em An introduction to algebraic deformationtheory}. \jpaa{84} (1993) 17--41.} \def\foxlescp{T. Fox, {\em Long exact sequences and circle products}. Preprint, 1991.} \def\foxlesdo{T. Fox, {\em Long exact sequences and circle products}. Preprint, 1991.} \def\foxcofree{T. Fox, {\em The construction of cofree coalgebras}. \jpaa{84} (1993) 191--198.}
% MURRAY GERSTENHABER
\def\gersten{M. Gerstenhaber, {\em The cohomology structure of anassociative ring}. \annals{78} (1963) 267--288.} \def\gersteni{M. Gerstenhaber, {\em On the deformation of rings andalgebras}. \annals{79} (1964) 59--103.} \def\gerstenii{M. Gerstenhaber, {\em On the deformation of rings andalgebras II}. \annals{84} (1966) 1--19.} \def\gersteniii{M. Gerstenhaber, {\em On the deformation of rings andalgebras III}. \annals{88} (1968) 1--34.} \def\gersteniv{M. Gerstenhaber, {\em On the deformation of rings andalgebras IV}. \annals{99} (1974) 257--276.} \def\gerstenschackmorphism{M. Gerstenhaber and S. Schack, {\em On thecohomology of an algebra morphism}. \jalg{95} (1985) 245--262.} \def\gerstenschackrelative{M. Gerstenhaber and S. Schack, {\em RelativeHochschild cohomology, rigid algebras, and the Bockstein}. \jpaa{43}(1986) 53--74.}
\def\gerstenschackbig{M. Gerstenhaber and S. Schack, {\em Algebraiccohomology and deformation theory}. In {\bf Deformation Theory of Algebrasand Structures and Applications}, Kluwer Academic Publishers, 1988,11--264.} \def\gerstenschackbialgebra{M. Gerstenhaber and S. Schack, {\em Bialgebracohomology, deformations, and quantum groups}. Proc. Natl. Acad. Sci. USA{\bf 87} (1990) 478--481.}
%%%%%%%%%%%%%%%%%%%%%%%%
\def\girardll{J-Y Girard, {\em Linear logic}. \tcs{50} (1987) 1--101.} \def\graves{W. Graves, {\em Cohomology of incidence coalgebras}. DiscreteMath. {\bf 10} (1974) 75--92.} \def\griffing{G. Griffing, {\em The cofree nonassociative coalgebra}. \commalg{16} (1988) 2387--2414.}
\def\grossmanlarson{R. Grossman and R. Larson, {\em Solving nonlinearequations from higher order derivations in linear stages}.Adv. in Math. {\bf 82} (1990) 180--202.} \def\grunenfelderpare{L. Grunenfelder and R. Par\'e, {\em Familiesparametrized by coalgebras}. \jalg{107} (1987) 316--375.} \def\hartshorne{R. Hartshorne, {\bf Algebraic Geometry}. \springer ,1977.}
\def\heller{A. Heller, {\em Principal bundles and group extensions withapplications to Hopf algebras}. \jpaa{3} (1973) 219--250.} \def\hochschild{G. Hochschild, {\em On the cohomology groups of anassociative algebra}. \annals{46} (1945) 58--67.} \def\jonah{D. Jonah, {\em Cohomology of coalgebras}. \amsmem{82} (1968).}
\def\jonirota{S. Joni and G.-C. Rota, {\em Coalgebras and bialgebras incombinatorics}. Studies in Applied Math. {\bf 61} (1979) 93--139.} \def\joyalstreet{A. Joyal and R. Street, {\em An introduction to Tannakaduality and quantum groups}. To appear in proceedings of conference atComo 1990, \springer .}
\def\kodairaspencer{K. Kodaira and D. Spencer, {\em On deformations ofcomplex analytic structures I \& II}. \annals{67} (1958) 328--466.} \def\kleiner{M. Kleiner, {\em Integrations and cohomology in theEilenberg-Moore category of a monad}. Preprint, 1986.} \def\lambeklambda{J. Lambek, {\em From lambda-calculus to cartesian closedcategories}. In {\bf To H.B. Curry, essays in combinatory logic, lambda calculus and formalism} (Seldin and Hindley eds.), Academic Press, 1980, 375--402.} \def\maclane{S. Mac\/Lane, {\bf Homology}. \springer , 1963.} \def\maclaneca{S. Mac\/Lane. {\em Categorical algebra}.\amsbull{71} (1965) 40--106.}
%SHAHN MAJID
\def\majidpa{S. Majid, {\em Physics for algebraists: non-commutative andnon-cocommutative Hopf algebras by a bicrossproduct construction}.\jalg{130} (1990) 17--64.} \def\majidqhaybe{S. Majid, {\em Quasitriangular Hopf algebras andYang-Baxter equations}. Inter. J. Modern Physics {\bf 5} (1990) 1--91.} \def\majidqbla{S. Majid, {\em Quantum and braided linear algebra}. preprint, DAMTP 1992.} \def\majidbghaot{D. Gurevich and S. Majid, {\em Braided groups of Hopfalgebras obtained by twisting}. preprint, DAMPT 1991.} \def\majidqggtqs{T. Brzezi\' nski and S. Majid, {\em Quantum group gage theory on quantum spaces}. preprint, DAMTP 1992.} \def\majidbmssaqlg{S. Majid, {\em Braided matrix structure of the Sklyanin algebra and of the quantum Lorentz group}. preprint, DAMTP 1992.} \def\majidtktqha{S. Majid, {\em Tannaka-Krein theorem for quasi-Hopfalgebras and other results}. Cont. Math., Proc. Deformation theoryof alebras and quantization (to appear).} \def\majidbg{S. Majid, {\em Braided groups}. preprint, DAMPT 1991.} \def\majidqrwtr{S. Majid, {\em Quantum random walks and time-reversal}.preprint, DAMPT 1992.} \def\majidmebdcpha{S. Majid, {\em More examples of bicrossproduct anddouble cross product Hopf algebras}. Israel J. Math. {\bf 72} (1990)133--148.} \def\majidaqg{S. Majid, {\em Anyonic quantum groups}. preprint,DAMPT 1991.}
%%%%%%%%%%%%%%%%%%
\def\marklcotangent{M. Markl, {\em Cotangent cohomology of acategory and deformations}. Preprint 1992.} \def\michaelis{W. Michaelis, {\em Lie coalgebras}. Advances in Math. {\bf 38} (1980) 1--54.} \def\newmanfree{K. Newman, {\em The structure of free irreduciblecocommutative Hopf algebras}. \jalg{29} (1974) 1--26. } \def\newmancorrespondence{K. Newman, {\em A correspondence betweenbi-ideals and sub-Hopf algebras in cocommutative Hopf algebras}. \jalg{36} (1975) 1--15.}
\def\newmanradfordcofree{K. Newman and D. Radford, {\em The cofreeirreducible Hopf algebra on an algebra}. \amerj{101} (1979) 1025--1045.} \def\nijenlie{A. Nijenhuis and R. Richardson, {\em Cohomology anddeformations in graded Lie algebras}. \amsbull{72} (1966) 1--29.} \def\nijencomm{A. Nijenhuis and R. Richardson, {\em Commutative algebracohomology and deformations of Lie and associative algebras}. \jalg{9} (1968) 42--105.} \def\piper{W. S. Piper, {\em Algebraic deformation theory}. J. Diff. Geometry {\bf 1} (1967) 133--168.}
\def\raeburntaylor{I. Raeburn and J. Taylor, {\em Hochschild cohomologyand perturbations of Banach algebras}, J. Func. Analysis {\bf 25} (1977)241--280.} \def\ravenelwilson{D.Ravenel and W. Wilson, {\em The Hopf ring for complexcobordism}. \jpaa{9} (1977) 241--280.} \def\RW{\ravenelwilson} \def\schoeller{C. Schoeller, {\em Etude de la categorie des algebres deHopf commutative connexes sur un corps}. Manuscripta Math. {\bf 3} (1970)133--155.} \def\seelyll{R. Seely, {\em Linear logic, *-autonomous categories andcofree coalgebras.} In {\bf Conference on Categories in Computer Science and Logic}, AMS Contem. Math. {\bf 92} (1989) 371--382.} \def\shnider{S. Shnider, {\em Bialgebra deformation cohomology}. MFN {\bf 41} 1--32.}
%STASHEFF
\def\sstasheffi{M. Schlessinger and J. Stasheff, {\em The Lie Algebrastructure of tangent cohomology and deformation theory}. \jpaa{38} (1985) 313--322.} \def\sstasheffii{M. Schlessinger and J. Stasheff, {\em Deformation theoryand rational homotopy type}. Preprint, 1991.} \def\stasheffdiff{J. Stasheff, {\em Differential graded Lie algebras,quasi-Hopf algebras and higher homotopy algebras}. Preprint, 1991.} \def\stasheffbracket{J. Stasheff, {\em The intrinsic bracket on thedeformation complex of an associative algebra}. \jpaa{} (to appear).} \def\stasheffmarkl{M. Markl and J. Stasheff. {\em Deformation theory via deviations}. preprint 1992.}
%%%%%%%%%%%%%%%%%%%%%
\def\steenrodproducts{N. Steenrod, {\em Products of cocyclyes andextensions of mappings}. \annals{48} (1947) 290--320.} \def\sweedler{M. Sweedler, {\bf Hopf Algebras}. Benjamin, New York,1969.} \def\takeuchifree{M. Takeuchi, {\em Free Hopf algebras generated bycoalgebras}. J. Math. Soc. Japan {\bf 23} (1971) 561--582.} \def\takeuchicorrespondence{M. Takeuchi, {\em A correspondence betweenHopf-ideals and sub-Hopf algebras}. Manuscripta Math. {\bf 7} (1972)251--270.}
%TAFT ET AL:
\def\petertaft{B. Peterson and E. Taft, {\em The Hopf algebra of linearlyrecursive sequences}. Aequationes Math. {\bf 20} (1980) 1--17.}
\def\taftwitt{E. Taft, {\em Witt and Virasoro algebras as Lie bialgebras}.Preprint, 1991.} \def\larsontaft{R. Larson and E. Taft, {\em The algebraic structure oflinearly recursive sequences under Hadamard product}. Israel J. Math. {\bf 72} (1990) 118--132.} \def\greenleft{J. Green, W. Nichols, and E. Taft, {\em Left Hopfalgebras}. \jalg{65} 399-411.}
% VAN OSDOL
\def\vanosdolcoalgebras{D. VanOsdol, {\em Coalgebras, sheaves, andcohomology}. \amsproc{33} (1972) 257--263.} \def\vanosdolbicohomology{D. VanOsdol, {\em Bicohomology theory}. \amstrans{183} (1973) 449-476.} \def\vanosdolles{D. VanOsdol, {\em Long exact sequences in the firstvariable for algebraic cohomology theories}. \jpaa{23} (1982) 271--309.}
%%%%%%%%%%%%%%%%
\def\wilson{W. S. Wilson, {\em Brown-Peterson homology}. AMS RegionalConf. Series in Math. {\bf 48} (1982).} \def\wraithpreprint{G. Wraith, {\em Derived categories of algebras andcoalgebras}. preprint, 1972.} \def\wraithabelian{G. Wraith, {\em Abelian Hopf algebras}. \jalg{6} (1967) 135--156.} \def\yettertqft{D. Yetter, {\em Topological quantum field theoriesassociated to finite groups and crossed G-sets}. preprint.} \def\yettercccr{D. Yetter, {\em Coalgebras, comodules, coends andreconstruction}. preprint.} \def\yetterft{D. Yetter, {\em Framed tangles and a theorem of Deligne onbraided deformations of Tannakian categories.}}
% JOURNAL ABBREVIATIONS
\def\amstrans#1{Trans. Amer. Math. Soc. {\bf #1}} \def\amsproc#1{Proc. Amer. Math. Soc. {\bf #1}} \def\amsbull#1{Bull. Amer. Math. Soc. {\bf #1}} \def\amsmem#1{Mem. Amer. Math. Soc. {\bf #1}} \def\amerj#1{Amer. J. Math. {\bf #1}} \def\annals#1{Ann. of Math. {\bf #1}} \def\cahiers#1{Cah\-iers de Topo\-lo\-gie et G\'e\-o\-m\'e\-trieDif\-f\'e\-ren\-ti\-elle\ifnum#1>25 { Cat\-\'e\-go\-rique}\fi, {\bf #1}} \def\canbull#1{Canad. Bull. Math. {\bf #1}} \def\commalg#1{Comm. Algebra {\bf #1}} \def\jalg#1{J. Algebra {\bf #1}} \def\jpaa#1{J. Pure Applied Algebra {\bf #1}} \def\lnm#1{Lecture Notes in Math. {\bf #1}, \springer} \def\tcs#1{Theoretical Comp. Sci. {\bf #1}}
%SPECIAL
\def\springer{Sprin\-ger-Verlag, Berlin, Heidelberg, New York} \def\lajolla{{\bf Proceedings of the Conference on Categorical Algebra (La Jolla)}, \springer \/(1966)} \def\MSZ{$MS_1\ $}\def\MSX{$MS_0F\ $}\def\MSY{$MS_0\ $}
\def\del{\Delta}
\def\SA{\Ssc\Asc}
\def\SB{\Ssc\Bsc}
\def\SD{\Ssc\Dsc}
\def\RA{\Rsc\Asc}
\begin{document}
\title{\bf The Construction of Cofree Coalgebras}
\author{Thomas F. Fox\thanks{To appear in \jpaa{}. This work was partially supported by grants from the FCAR of Qu\'ebec and the NSERC of Canada.}\\McGill University\\Montr\'eal, Canada}\maketitle
\abst
Elementary constructions of the cofree coalgebra generated by a module are given, with applications to the cohomology of coalgebras and bialgebras.\eabst
Everyone knows that the cofree coalgebra exists ``on general principles''[1]. As far as constructions go, most attention has been given to vector spaces [4,5,9,10,15], and these depend on the idea of duals of free algebras on duals (although the pointed-irreducible and complete cases arestraightforward [13,12]). We here offer two simple constructions of the cofree coalgebra generated by a module over a commutative ring, with applications to the cohomology of bialgebras.
\section{Cofree coalgebras}
Let $R$ be a commutative ring. An $R$-coalgebra is a module $M$ equipped with a comultiplication
$\Del_M: M\to M\ten_RM$. For now we will not assume $\Del$ is coassociative, nor will we require a counit. One should think of $\Del$ as giving each element $m$ of $M$ an ``$R$-decomposition'' into a sum of pairs ofelements of $M$ .The {\em cofree coalgebra generated by $M$} is a coalgebra $MS$ together with a linear map $\pi:MS\to M$ such that for each coalgebra $C$ and linear map $f:C\to M$ there is a unique coalgebra map$f':C\to MS$ such that $f'\pi = f$. If $\pi :MS\to M$ is the cofree $R$-coalgebra over $M$, then $MS$ mustrepresent all possible decompositions of $M$, i.e.\ for each element $m$ of $M$and each $\del_M$ such that $m\del _M = \sum m_{(1)}\ten m_{(2)}$, there must be elements $[m]$ and $[m_{(i)}]$ of $MS$ such that $[m]\pi = m$, $[m_{(i)}]\pi = m_{(i)}$, and $[m]\del _{MS} = \sum [m_{(1)}]\ten [m_{(2)}]$ in $MS\ten MS$.
To see this, let $C$ be the free $R$-module generated by symbols$\{x,x_{(i)}\}$ and choose a diagonal $\del:C\to C\ten C$ such that$x\del = \sum x_{(1)}\ten x_{(2)}$. Now define a linear map $f:C\to M$ by$xf = m$ and $x_{(i)}f = m_{(i)}$. Since $f'$ is a coalgebra map,we must have $xf'\del = \sum x_{(1)}f'\ten x_{(2)}f'$, and of course$x_{(i)}f'\pi = m_{(i)}$. Now just set $xf' = [m]$. The point is that$\{m_{(i)}\}$ can be chosen at random. The trouble comes when each$x_{(i)}$ must be given a decomposition, and that depends on the choice of $\del:C\to C\ten C$, which also may be chosen at random. Hence, the cofree coalgebra has an element $[m]$ for each possible decomposition of $m$ and each possible decomposition of the decomposition, etc. Our task is to sort all this out.
Our first construction is a linearization of that outlined in [2], which is a multidimensional version of the recursive functions used in [14] to define the cofree coalgebra over a one dimensional space. In section 3 below we give another construction which looks more like the dual of a tensor algebra.
An \emph{$M$-tree} is a tree with an element of $M$ at each node such that at each node there is a finite non-zero number of ordered pairs of branches, and each pair of branches has a coefficient chosen from $R$. The set of all $M$-trees is denoted \MSY and an element of \MSY is denoted $[m]$. We can say an $M$-tree is a tree whose root is an element $m$ of $M$, and whose branches at $m$ are elements of $R\x MS_0\x MS_0$ (if it were not for the circularity, we could make this a definition). With this in mind, we can write$$ [m] = (m, \{(r^i,[m^i_1],[m^i_2]) \}) $$
\pagebreak
Now \MSY has a natural $R$-module structure inherited from $M$ and defined by the following equations:
$$r(m, \{(r^i,[m^i_1],[m^i_2]) \}) = (rm,\{(rr^i,[m^i_1],[m^i_2]) \})$$
$$(m, \{(r^i,[m^i_1],[m^i_2]) \}) + (n,\{(r^j,[n^j_1],[n^j_2]) \}) =\hspace*{1.5in}$$
$$\hspace*{1.5in} (m+n,\{(r^i,[m^i_1],[m^i_2]) \}\Cup\{(r^j,[n^j_1],[n^j_2]) \})$$
\subd {\em Let $MS$ be the quotient of \MSY by the equivalence relation generated by:}
\bd
\item{}If $\sum r^i[m^i_1]\ten [m^i_2] = \sum r^j[m^j_1]\ten [m^j_2]$ in $MS_0\ten MS_0$, then\\ $ (m, \{(r^i,[m^i_1],[m^i_2]) \}) \equiv (m, \{(r^j,[m^j_1],[m^j_2]) \})$\ed
\vskip1ex
To understand the phrase ``generated by'', let $MS_0(n)$ be the set of$M$-trees truncated at height $n$ (so that $MS_0(0) = M$), and let$MS(n)$ be its quotient using $\equiv$ as above. This is applied from the top down. The nodes at level $n$ are elements of
$M\ten M$.If $(m,\{(1,m_1,m_2),(1,n_1,n_2)\})$ is at level $n-1$, and $m_1 = n_1$ in $M$, then $$(m,\{(1,m_1,m_2),(1,n_1,n_2)\})\equiv (m,\{(1,m_1,m_2 + n_2)\})$$
if and only if the nodes above $m_1$ and $n_1$ are equal. There is then a chain of epimorphisms$ \cdots MS(n+1)\to MS(n)\to\cdots M$and $MS$ is the direct limit. Note that this equivalence relation does not mean that we can think of the branches at $m$ as elements of $M\ten M$. The definition above does ensure that the elements of $MS$ (also denoted $[m]$) may be written in the form $[m] = (m, \sum [m^i_1]\ten [m^i_2]) $, or using Sweedler's notation [15]
$$[m] = (m, \sum _{[m]} [m_{(1)}]\ten [m_{(2)}])$$
The map $\pi :MS\to M$ sends $[m]$ to $m\ $, while the map $\del :MS\to MS\ten MS$ is defined by$$[m]\del = \sum _{[m]} [m_{(1)}]\ten [m_{(2)}]$$ This recursive definition of $\del$ can be understood by displaying $MS$as the limit of the $MS(n)$. There are maps $\del:MS(n+1)\to MS(n)\ten MS(n)$ defined as above. The map $\del:MS\to MS\ten MS$ is the unique map filling in the diagram
$$\matrix{MS\ten MS & \to & \cdots & MS(n)\ten MS(n) & \to & MS(n-1)\ten MS(n-1) & \to & \cdots \cr & & &
\uparrow & & \uparrow & \cr MS & \to & \cdots & MS(n+1) & \to & MS(n) & \to & \cdots}$$
\thm $\pi :MS\to M$ is the cofree coalgebra over $M\ $.\eth
\pf Let $C$ be a coalgebra with $\del _C :C\to C\ten C$, and let $f:C\to M$ be a linear map. Define $f':C\to MS$ by
$$cf' = (cf, \sum_c c_{(1)}f'\ten c_{(2)}f')$$
where $c\del _C = \sum c_{(1)}\ten c_{(2)}$. It is clear that $f'$ is the unique coalgebra map
$C\to MS$ such that $f'\pi = f$\ ,since the root of $cf'$ is determined by $cf'\pi = cf$\ , and its branches are determined by the condition that $f'$ be a coalgebra map.\epf
Of course $MS$ is the most general type of cofree coalgebra -- there is no coassociativity nor counit. If we want the cofree coassociative or cocommutative or Lie coalgebra, we just take the largest subcoalgebra of $MS$ satisfying the appropriate identity. This is simply dual to the algebraic situation, where special types of free algebras are quotients of the (nonassociative, nonunitary) tensor algebra. If we want a counit, we must look at $(M\times R)S$, define the counit by $[(m,r)]\mapsto r$, and then take the largest subcoalgebra satisfying the counitary property.
There is an alternate description of $MS$ available. Let \MSX denote the free $R$-module generated by \MSY , and let \MSZ be thequotient $MS_1/\equiv$ where ``$\equiv$'' is the equivalence relation on$MS_1$ defined by the following:
\bd\item[1] If $\sum r^i[m^i_1]\ten [m^i_2] = \sum r^j[m^j_1]\ten [m^j_2] $ in $MS_0F\ten MS_0F$, then\\ $(m, \{(r^i,[m^i_1],[m^i_2]) \}) \equiv (m, \{(r^j,[m^j_1],[m^j_2]) \})$\ed
Finally, let $MS$ be the quotient of $MS_1F$ by the equivalence relation defined by the two conditions.
\bd\item[2] $ r(m, \sum [m^i_1]\ten [m^i_2] )\equiv (rm, \sum r[m^i_1]\ten [m^i_2] )$ for all $r$ in $R$.\item[3] $(m, \sum [m^i_1]\ten [m^i_2] ) + (n, \sum [n^j_1]\ten [n^j_2])\\ \equiv (m+n, \sum [m^i_1]\ten [m^i_2] + \sum [n^j_1]\ten [n^j_2])$\ed
It should be clear that this yields the same $MS$ as defined above.The meaning of this second definition will become clear when we consider coalgebras as bialgebras in sets in section 3 below.
\section{Applications}
Until recently the cofree coalgebra was little more than an formal construction ``dual'' to the free algebra, but current work on the deformation theory and cohomology of bialgebras has made a more concrete construction desirable. We will briefly describe how cofree coalgebras arise in this context.
The cofree construction gives rise to a functor $S:\Msc \to \Msc$, where$\Msc$ denotes the category of $R$-modules. If $f:M\to N$ in $\Msc$, then $fS$ is defined by $[m]f = (mf, \sum_{[m]} [m_{(1)}]f\ten [m_{(2)}]f)$. In factwe have a cotriple (``comonad'') $(S,\gke,\gkd)$ on $\Msc $ where $\gke :S\to1$ and $\gkd :S\to S^2$ are natural transformations satisfying well know conditions. Of course $\gke $ is defined by $\pi\ $, and $\gkd\ $ is defined by $$[m]\gkd = ([m], \sum [m_{(1)}]\gkd \ten [m_{(2)}]\gkd\ )$$ The reader should draw $[m]$ as a tree to see what this means.Now the category $\Csc $ of $R$-coalgebras may be described as the category of modules $C$ equipped with a comultiplication $\del:C\to CS$ picking out a decomposition for each element of $C$ and satisfying the usual identities:$\del \gke = 1$ and $\Del\delta = \Del\.\Del S$. The former ensures that $\del$ maps each element of $C$ to a tree whose root is that element, while the latter ensures that the choices are compatible, i.e.\ if $c\del = (c, \sum [c_{(1)}]\ten [c_{(2)}])$ then $c_{(1)}\del = (c_{(1)}, [c_{(1)}]\del )$. Of course, using the cocommutative variant of $S$ gives cocommutative coalgebras, using the Lie version of $S$ gives Lie coalgebras, etc.
The cohomology of coalgebras is defined using a simplicial complex generated by repeated applications of $S$, that is if $C$ and $D$ are coalgebras the groups $H^n(C,D)$ are defined by a complex $(C,D^*)$ whose boundary maps dependon the comultiplications on $C$ and $D$ [16,17].
Now suppose that we are also given a triple $(T, \mu ,\eta)$ on $\Msc$ which defines the category of $T$-algebras. For example, $T$ could be the tensoralgebra triple or the free Lie algebra triple, yielding the category of associative or Lie algebras respectively. To ensure harmony between $S$ and $T$, we insist that there be a ``distributive law'' [3], i.e.\ a natural transformation $\gkl :ST\to TS$ satisfying certain conditions with which we need not concern ourselves. A $T$-$S$-bialgebra is a module $B$ equipped withtwo structure maps $\beta :BT\to B$ and $\del:B\to BS$, making it a $T$-algebra and an $S$-coalgebra. Further, the structure maps $\beta$ and $\del$ must satisfy $\del T\.\gkl\.\beta S = \beta\.\del$, which says $\beta$ is acoalgebra map and $\del$ is an algebra map. Note that $\gkl\.\beta S:BST\to BS$ makes $BS$ a$T$-algebra, and $\del T\.\gkl:BT\to BTS$ makes $BT$ an $S$-coalgebra. If $A$ is also a bialgebra, the bialgebra cohomology groups are defined via a double complex $(AT^*,BS^*)$ whose boundaries depend on the structure maps of $A$ and $B$, as well as $\gkl$, [6,7,17]. The boundaries of the double complex are just the usual boundaries for algebra and coalgebra cohomology. To define the cohomology groups for a particular category of bialgebras, one need only define the cotriple $S$, the triple $T$, and the distributive law $\gkl$.
We close this section by giving a description of the distributive law which is used in the most common situation, where $T$ is the associative tensor algebra construction, and $S$ is as above. For each$R$-module $M$ we need $\gkl :MST\to MTS$. Now $MST$ is spanned byelements of the form $[m^1]\ten [m^2]\ten \ldots \ten [m^i]$. Let $[m]\gkl = [m]$ and $$([m]\ten [n])\gkl =\\ (m\ten n, \sum_{[m]} \sum_{[n]} ([m_{(1)}]\ten[n_{(1)}])\gkl\ten ([m_{(2)}]\ten [n_{(2)}])\gkl )$$ In fact this is just the formula for making $MS\ten MS$ a coalgebra, and extending this in the obvious way to the higher tensor powers of $MS$ defines $\gkl$.
\section{A more classical construction}
In this section we will give an alternate construction of the cofree {\em coassociative} coalgebra generated by a module. We will indicate at the end of the section how to generalize this to the non-coassociative or counitary cofree coalgebra. Since coalgebras are formally dual to algebras, one might think that the cofree coalgebra could be given by a construction dual to the associative tensor algebra. The first attempt at such a construction would be to look at theproduct of the tensor powers of $M$, which we will denote $MF$$$MF = M\times M\ten M\times M\ten M\ten M \ldots$$ The fact that the cofree coalgebra should be, in some sense, a completion of the free algebra also makes this an inviting approach [2]. However, $MF$ is not a coalgebra in any natural way, the problem being that the tensor does not preserve products.
Look at the product of tensor powers of $M$ indexed byall possible cuts. Denote this by $MF_2$$$MF_2 = (M)\ten (M)\x (M\ten M)\ten (M)\x (M)\ten (M\ten M)\x $$$$ (M)\ten (M\ten M\ten M)\x (M\ten M)\ten (M\ten M)\x\ldots$$ There is a canonical injection $MF\ten MF\to MF_2$, and there is a natural``diagonal'' $\Del :MF\to MF_2$ generated by $$(m_1\ten m_2\ten\ldots\ten m_k)\Del = \sum_{i=1}^{i=k-1} (m_1\ten\ldots\ten m_i)\ten(m_{i+1}\ten\ldots\ten m_k)$$Unfortunately $\Del$ does not map into $MF\ten MF$. It will turn out that the cofree coalgebra is a particular submodule $MS$ of $MF$ that does map into $MS\ten MS$ using $\Del$ as defined above.
Let $m_n$ be an element of $M^{\ten n}$ given by $$m_n = \sum_I m^i_1\ten m^i_2\ten\ldots\ten m^i_n$$Let $(m_n)M^{\ten n}$ be the subspace of $M^{\ten n+1}$ defined asfollows:
\bd\item{ }$n_{n+1} \in M^{\ten n+1}$ is in $(m_n)M^{\ten n}$ if for each $i\in I$ and each $1\leq j\leq n$ there is an element $n_j^i\in M\ten M$ such that
$$n_{n+1} = \sum_I m^i_1\ten \ldots m_{j-1}^i\ten n_j^i\ten m^i_{j+1}\ten \ldots \ten m_n^i$$
\ed
Note that $m^i_j = m^{i'}_{j'}$ does not imply $n^i_j = n^{i'}_{j'}$. Let $MS$ be the subspace of $MF$ of elements $(m_1,m_2,\ldots)$ satisfying $m_{n+1}\in (m_n)M^{\ten n}$. The reader can easily verify that $MS$ is indeed a subspace of $MF$, and that $\Del$ maps $MS$ into $MS\ten MS$.Furthermore, the map $\pi:MS\to M$ given by $(m_1,m_2,\ldots)\mapsto m_1$ is thecofree coassociative coalgebra generated by $M$. Indeed, if $f:C\to M$ is a linear map from a coassociative coalgebra $C$,define $f':C\to MS$ by $$cf' = \Pi_{k=0}^{\infty} c\Del^kf^k = (cf,c\Del (f\ten f) , c\Del(1\ten\Del)(f\ten f\ten f),\ldots)$$
The necessary isomorphism from our first construction of $MS$ using treesto $MS$ as given here is easy to see.
To find the $n^{th}$ term in$MF$ just tensor the elements along any path of length $n$ starting at theroot. Since we are in the coassociative case the choice of path will not matter.The cofree non-coassociative coalgebra may be constructed in a similar way, but one must use the analogue of the non-associative tensor algebra -- the productof tensor powers of $M$ indexed by all possible associations into pairs of copies of $M$. Once again, if we want a counitary cofree coalgebra we should look at $(M\x R)S$ and pick out the elements satisfying the counitary property.
\section{Coalgebras as bialgebras over sets}
In many ways coalgebras are not malleable. Our unfamiliarity with their structure stems from the fact that they are not defined over the category$\Ssc$ of sets; they are neither tripleable nor cotripleable, theunderlying functor preserving neither limits nor colimits. They are, however, cotripleable over $\Msc$, which is tripleable over $\Ssc$. In fact $\Csc$ can be viewed as a category of bialgebras over $\Ssc$. An \emph{ $R$-analysis} is a set $X$ with a function $\Del$ from $X$ to $XT\ten_R XT$ where $XT$ is the free $R$-module generated by $X$, that is for $x\in X$ we have $x\Del = \sum r^ix^i_1\ten x^i_2$. Of course this is the same as giving $XT$ an $R$-coalgebra structure.In fact $R$-analyses are quite common.
For example, let $(P,\leq)$ be a locally finite partially ordered set, and let $X$ be the set of intervals$[x,y]$ of $P$. Then define $[x,y]\Del = \sum_{ x\leq z\leq y}[x,z]\ten[z,y]$. This makes $X$ acoassociative $R$-analysis --- but for coefficients this is the ``incidence coalgebra'' of $(P,\leq)$, [11]. Similarly, let $X$ be the set of non-zero integers, and let $x\Del = \{y\ten z: yz = x\}$. Then $X$ is a coassociative, cocommutative $R$-analysis, though it is not an $R$-coalgebra for any ring$R$. We can also consider a ``multiposet'' $\Psc$, that is a category with finite hom sets and maps running in one direction only. Once again let $X$ be the set of intervals of $\Psc$. This has a natural structure as a $Z$-analysis if we let $[x,y]\Del = \sum_{z\in \Psc} |[x,z]|\.|[z,y]|\: [x,z]\ten[z,y]$
$R$-analyses form a category$\RA$ in an obvious way, and there is an underlying functor $\RA\to \Ssc$. This has a right adjoint given by $X\mapsto XS_1$ as defined at the end of section 1, and $\RA$ is the category of $S_1$-coalgebras in $\Ssc$. Let $T$ be the free $R$-module triple on $\Ssc$. Defining $\gkl:XS_1T\to XTS_1$ by $$(r(x,\sum x^i_1\ten x^i_2) +s(y,\sum y^j_1\ten y^j_2 ))\gkl = (rx + sy,\sum rx^i_1\ten x^i_2 + sy^j_1\ten y^j_2)$$ gives a distributive law $\gkl:S_1T\to TS_1$. Hence we may consider the category of $S_1$-$T$-bialgebras in $\Ssc$.
It should be clear that an $S_1$-$T$-bialgebra is just an $R$-module $X$ with a ``diagonal'' map $\Del:X\to XT\ten XT$. This is almost an $R$-coalgebra in the usualsense, but not quite. On the other hand, the module structure of $X$is given by a map $\xi:XT\to X$. Consider the quotient map$\xi\ten\xi:XT\ten XT\to X\ten X$. Then $\Del\.\xi\ten\xi:X\to X\ten X$ makes $X$ an $R$-coalgebra in a canonical way.These observations should illuminate our second description of $MS$ in section 1 above. In constructing $MS$ we applied $S_1$ to the underlying set of $M$, applied $T$ to get an $S_1$-$T$-bialgebra. The module structure on this is defined by $\gkl\.\xi S_1$. {\em Mod}\/ing out by conditions 2 and 3 performed these two operations at once. This is just the lifting of the cotriple$S_1U:\Msc\to\Msc$ to the category of algebras [3]. The whole point of distributive laws is that constructions done in several steps may many times be broken up into separate constructions connected by a distributive law. The reader may want to consider the first definition of $MS$ in this light.
Note that we could consider the cohomology theory on $\Csc$ given by the double complex $(XT^*,YS_1^*)$. In order to make this into a complex of abelian groups, we would ask that $X$ be a cogroup object over $Y$, and that $Y$ be a group object over $X$, as in [17]. This would give an ``absolute'' cohomology theory for $R$-coalgebras, corresponding to Shukla cohomology forassociative algebras. For incidence coalgebras, this is the same as cohomology defined in [8].
Constructions similar to that of $S_1$ serve to give right adjoints to forgetful functors from other ``coalgebraic'' categories over $\Ssc$. Let $\Gsc$ be the category of cosemigroups, i.e.\ sets $X$ equipped with a decomposition map $\del :X\to X\times X$ (not necessarily {\em the} diagonal). $\Gsc$ is a category in a natural way, and the underlying functor $U:\Gsc\to\Ssc$ has a right adjoint $S'$ -- the cofree cosemigroup functor constructed as follows: For any set $X$, we let $XS'$ be the set of all binary trees with an element of $X$ at each node. Once again we can write theelements of $XS'$ as $[x]$ where $ [x] = (x,([x_1],[x_2])) $ Of course $\del:XS'\to XS'\times XS'$ is given by $[x]\del = ([x_1],[x_2])$, and$\pi:XS'\to X$ is given by $[x]\pi = x$. The interested reader should see [2] for many more examples of this type.
\pagebreak
\bref
\item \barrcoalg\item \barrtermcoalg\item \becklaws
\item \block\item \blockleroux \item \foxbicohomology
\item \gerstenschackbialgebra
\item \graves\item \griffing\item \grunenfelderpare
\item \jonirota\item \michaelis\item \newmanradfordcofree\item \petertaft\item \sweedler\item \vanosdolcoalgebras\item \vanosdolbicohomology
\end{list}
\noindent
Department of Mathematics and Statistics\\McGill University
\\805 Sherbrooke St. W.\\Montr\'eal, Qu\'ebec\\CANADA H3A 2K6
\\fox@math.mcgill.ca\hfill
\end{document}