Linked to the 1Lab for the proof that (forgetful functor from F-algebras has left adjoint) implies algebraically-free monad.
]]>added link to algebraically compact category
]]>@Todd_Trimble, thanks for clarifying. I was slow in filling in the details, and did not realize (forgot) that $(\vert f \vert)$ denotes the unique homomorphism to the algebra $(X, f)$ among some researchers ^{1} ^{2}. I have seen the notation before, so the misunderstanding is my own fault.
Bird and Moore, The algebra of programming, in Deductive Program Design. google book preview ↩
Thanks for that information, varkor.
]]>Added some text in response to the preceding comments.
]]>(I don’t recall seeing that notational convention before; is it well known?)
$\mu$ is often used in computer science to denote least fixed points (with $\nu$ being used for greatest fixed points), for example in the modal μ-calculus, and by extension initial (and final co)algebras, for instance in Algebras, Coalgebras, Monads and Comonads.
]]>I think you’re right that the author slightly misspoke, or elided over something you’re pointing out, but to me what he was trying to say is clear enough.
So $\Sigma^\ast \Sigma^\ast X$ is the initial algebra for the endofunctor $Y \mapsto \Sigma Y + \Sigma^\ast X$. Meanwhile there is an algebra structure on $\Sigma^\ast X$ for that endofunctor, i.e., a map $\Sigma \Sigma^\ast X + \Sigma^\ast X \to \Sigma^\ast X$, and that’s given by $[\alpha, Id]$. Thus by initiality, we have a map $\Sigma^\ast \Sigma^\ast X \to \Sigma^\ast X$ that is induced by the algebra structure $[\alpha, Id]$. That’s what he meant to say, no?
Another thing to point out is that he’s overloading the notation $\mu$. The first time $\mu$ appears, I guess he wants $\mu Y.\Sigma(Y) + X$ to denote the initial algebra of the endofunctor $\lambda Y. \Sigma Y + X$. (I don’t recall seeing that notational convention before; is it well known?) On the other hand, $\mu$ denotes the monad multiplication.
One could try writing him about these issues, but let me think about a graceful way of handling it at the nLab.
]]>In the referenced Maciej Piróg’s blog post, there is a construction of $\mu$ just before the Eilenberg-Moore Algebra section. The construction seems problematic to me. In particular, $\Sigma^*\Sigma^* X\cong \Sigma\Sigma^*\Sigma^* X + \Sigma^*X$, and $[\alpha, 1]\colon \Sigma\Sigma^*X+\Sigma^*X\to \Sigma^* X$ does not seem to type-check there. If I understand the matter correctly, the multiplication $\mu$ should be given by initiality, probably not expressible by $\alpha\colon \Sigma\Sigma^* X\to \Sigma^*X$ without further assumption.
If the above is correct, maybe it is better to have a note next to the reference to remind the reader.
– Anonymous Coward
]]>Added a mention of pointed algebras for pointed endofunctors. Perhaps those should have their own page, but at the moment I don’t have much to say about them other than “they’re analogous to the unpointed case”.
]]>@Mike:
Ah, now I get what you’re saying - thanks for taking the time to elaborate!
]]>Re #43: Thanks Alexis!
]]>It would certainly be nice to include redirects in search results, I’ve wished for that before. However, I do note that https://www.google.com/search?q=site:ncatlab.org+F-algebra gets you to algebra for an endofunctor as the top hit, and this is the search that’s done by the green “Search the nLab” box on the HomePage. Possibly we should consider putting the google search box at the top of every page instead of or in addition to the built-in instiki one.
You’re right that there is no qualitative difference between $n$-category and $F$-algebra; both are names that contain a variable. In practice, however, when we write $n$-category there is practically no potential for confusion: the only other name of the form “?-category”, with ? a variable, that I can think of is $V$-category for an enriched category, and the chances of someone using lowercase $n$ to denote a monoidal category are slim to none. Even given that, I would have preferred to name the page n-category as something not including a variable, were it not for the fact that there is really no other option available.
With algebras, in contrast, there are oodles of different kinds of algebras: in addition to algebras for endofunctors we have algebras for monads, algebras for pointed endofunctors, algebras for rings and fields, algebras for algebraic theories, and probably others; all of which are commonly denoted by “?-algebra”, and in many cases the ? might quite reasonably be denoted by the letter $F$ (particularly, for instance, a pointed endofunctor or a field). Moreover, algebra for an endofunctor is a quite reasonable and unambiguous alternative page name.
]]>@Richard: Done - thanks. :-)
]]>Hi Alexis, I missed your suggestion about searching first time around. At first glance, it sounds good to me. Please add it to the Technical TODO list (nlabmeta).
]]>Okay, sorry for my misunderstanding.
Here’s the context of why I’ve been looking at this: in reading discussions about Haskell, I’ve encountered people talking using ’F-algebra’ as a category-theoretic concept. My first thought was to come to the nLab for an explanation of this concept. i did a search, and was surprised to find no specific entry for ’F-algebra’ in the search results; and as I alluded to in an earlier comment, not knowing what an F-algebra is, I didn’t know which of the entries listed in the search results I should look at for further information. I ended up doing a search on Wikipedia, and found the F-algebra entry. Now having a general sense about F-algebras, I ended up at the nLab ’algebra for an endofunctor’ page, and thought it would be helpful for other people in my situation to be directed to that page.
If people who want to know about F-algebras should only be directed to the ’algebra for an endofunctor’ page, then I certainly think the suggestion I made in #39, about search result listings, should be implemented at some point. Having said that, I’m not sure I understand why having a page for ’F-algebra’ is substantially different from having a page for (say) (n,r)-category - in both cases, it seems to me we’re talking about a ’type’ that needs to be ’instantiated’. Is this incorrect?
]]>My point is that there is no definition of “an F-algebra” until you know the type of F, so it doesn’t make sense as a thing to search for.
]]>Hmm. Given Mike’s comment, I’m wondering if it might be better to create a new page for ’F-algebra’. (Particularly given that a search for ’F-algebra’ doesn’t show that ’F-algebra’ is a redirect to ’algebra for an endofunctor’, so that if one is looking for a definition of an F-algebra, the search results don’t make it obvious which entr(y|ies) contains such a definition. Perhaps if a search is for a term that has a redirect, that redirect should be noted in the search results?)
]]>Well, the problem with “F-algebra” is that nowhere is it decreed that an object called $F$ must be an endofunctor. But I suppose F is used more often for endofunctors than for other things that have algebras, like monads and rings and theories.
]]>That sounds reasonable to me. We also have the page initial algebra of an endofunctor.
As for the ’co-’ case, terminal coalgebra for an endofunctor comments on coinductive types.
I guess redirects are needed for the range of prepositions used: of, for and over
]]>I’ve added a redirect from F-algebra, since I was surprised to not find such an entry already extant, and didn’t immediately think to look at the entry algebra for an endofunctor.
I’ve also added a comment about noting initial algebras for endofunctors’ relationship to inductive types.
If all this is okay, I’d like to make analogous updates re. F-coalgebra and coalgebra over an endofunctor.
]]>On the other hand, one does occasionally find monads that are “cooked up” as you describe in #33 but whose initial algebras are highly non-vacuous. For instance, the category of elementary toposes is monadic over categories, or over graphs, but its initial algebra — the free topos — is highly nontrivial (it knows all about higher-order logic!).
]]>Well, since the initial algebra of a 1-monad is also a free algebra of that monad (free on the initial object of the base category), I think #22 encompasses all examples. (-:
]]>We could still find interesting examples of initial algebras of non-free $1$-monads. Unfortunately, the examples of monads that I mostly know are those cooked up to give familiar objects as their algebras, and the initial algebras there tend to be fairly vacuous. So I only know one good example (really a parametrised infinitude of examples): #22.
]]>Okay, I think this discussion has gone on long enough. (-:
]]>