From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3519 Path: news.gmane.org!not-for-mail From: Tom Leinster Newsgroups: gmane.science.mathematics.categories Subject: A canonical algebra Date: Wed, 13 Dec 2006 13:19:49 +0000 Message-ID: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241019355 9099 80.91.229.2 (29 Apr 2009 15:35:55 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:35:55 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Wed Dec 13 11:13:48 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Wed, 13 Dec 2006 11:13:48 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GuVbv-00053a-Qf for categories-list@mta.ca; Wed, 13 Dec 2006 11:01:31 -0400 Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 20 Original-Lines: 58 Xref: news.gmane.org gmane.science.mathematics.categories:3519 Archived-At: Dear all, Here is a canonical, but perhaps not trivial, way of constructing an algebra for any finitary algebraic theory. Does anyone know anything about it? E.g. is there existing work on it, or an alternative description? Take a finitary monad (T, eta, mu) on Set. We construct an algebra A for the monad in three steps: (i) Let C be the terminal coalgebra for the endofunctor T (which exists since T is finitary). (ii) Regard C as an algebra for the endofunctor T (via Lambek's Lemma: the structure map of C is invertible). (iii) Turn C into an algebra A for the monad (T, eta, mu) by applying the left adjoint to the inclusion (T, eta, mu)-Alg ----> T-Alg. Here are two examples. 1. Fix a monoid M and let (T, eta, mu) be the theory of left M-sets. Then C is the set of infinite sequences (m_1, m_2, ...) of elements of M, and A = C/~ where ~ is generated by (m_1, m_2, ...) ~ (m_1 ... m_n, m_{n+1}, m_{n+2}, ...) for any natural number n and m_i in M. 2. Let (T, eta, mu) be the theory of monoids. Then C is the set of infinite planar trees in which each vertex may have any natural number of branches ascending from it (or descending, according to convention). Next, A = C/~ where ~ is generated by s o (t_1, ..., t_n) ~ s' o (t_1, ..., t_n) for any finite n-leafed trees s, s' and t_1, ..., t_n in C. Here "o" means "grafting": the left-hand side is the union of s and the (t_i)s, with the root of t_i glued to the i-th leaf of s. Hence A is the set of equivalence classes of infinite trees, where two trees are equivalent if one can be obtained from the other by altering just a finite portion at its base. This equivalence relation (or actually, the analogous one for commutative monoids) is what made me start thinking about all this. Thanks, Tom -- Tom Leinster