People keep describing algebras as though evaluation takes expressions back to the set of generators and I don't get it

128 Views Asked by At

Let $F$ be the free monoid functor, and $G$ its right adjoint. Then $G \circ F$ is a monad on $\mathbf{Set}$; and its unit $\eta$ is a natural transformation taking every set $X$ to the set $(G \circ F) X$ ("set of words on the alphabet $X$") in such a way that every element $x$ in $X$ is mapped to its "singleton word" $[x]$. "Insertion of generators."

When it comes to building an algebra to go back the other way, however, I'm lost. An algebra for this monad should be a morphism from the set $(G \circ F) X$ back to $X$. Supposedly these morphisms $(G \circ F) X \to X$ are going to represent the various possible monoid operations on $(G \circ F) X$. But how does that work? Monoid operations do not, in general, map back to the set of the monoid's generators!

To use a concrete example: If $X = \{a, b, c\}$, then the unit of the monoid free-forgetful monad will map $X$ to $T X = \{[], [a], [b], [c], [a, a], [a, b], ... \}$ in precisely the following way: $\{a \to [a], b \to [b], c \to [c]\}$. How on earth would an arbitrary monoid algebra map $T X$ back to $X$ ?

Every time I see these sort of "free-forgetful $\mathbf{Set}$ $T$-algebras" explained online, for example in computer science, people seem to say things like, "Oh, for a set $X$ you use the free structure in $T$ to build up a formal expression, with the formal operations, of elements of $X$. Then for a given $\theta$ for that $T X$, you substitute specific "real" operations in for the formal ones and evaluate." But why should such an evaluation get you back to an element of $X$? In particular, if your "real" operations that you evaluate after subbing in for the formal ones are the formal operations themselves, I can't see how you generally get back an element of the generator set or anything obviously corresponding to it.

I haven't even managed to understand the always-reliable Eugenia Cheng on this matter. Here she writes out "$(a, b, c, d)$" as an example element of $T A$, the set of "words"; presumably, $a$, $b$, $c$, and $d$ are supposed to be elements of $A$, the generators of the free monoid whose elements $T A$ is the set of. But then she says that her algebra $\theta$ is supposed to take this "word" $(a, b, c, d)$ to $abcd \in A$ ("the result of multiplying all these things in a row").

In the subsequent video she supposedly clarifies that, indeed, the juxtaposition notation was intended to represent the particular monoid multiplication provided by the algebra $\theta$. But again, this is no clarification for me, because I can't see any reason why the result of that multiplication should be an element of $A$. She does call $A$ the "underlying set" in this video; and I have a feeling that this cuts to the core of what I'm not understanding, because I'm not getting how that would work.

2

There are 2 best solutions below

13
On BEST ANSWER

Your confusion is that that $T$-algebra structure described by a map $TX \to X$ is not an algebra on $TX$, rather one on $X$!

In your case, it's monoid structures over $X$ that we're interested in, note those on $(G\circ F)X$ (I'll use $T=G\circ F$)

Then, the formal expression $x_1x_2 \in TX$ for instance, has no meaning in $X$. But once we endow $X$ with a monoid structure, that is a multiplication $\times$, then we can say that $x_1x_2 \mapsto x_1\times x_2$ (and similarly for more complex formal expressions). This yields a map $TX\to X$ that corresponds to the given monoid structure.

Conversely, given a sufficiently nice map $h:TX\to X$, we can think of it as being induced by a monoid structure on $X$; indeed it then suffices to define $x_1 \times x_2$ as $h(x_1x_2)$ (where $x_1x_2 \in TX$ is the formal expression). The niceness assumption on $X$ (given by the $T$-algebra axioms) allow one to prove that this does indeed yield a monoid structure.

Moreover these two processes (from a monoid structure get a nice map $TX\to X$, and from a nice map $TX\to X$ get a monoid structure) are inverse to one another.

0
On

A change of perspective that might help clarify things it to look at the corresponding comonad on the category of algebras.

Suppose you have a monoid $M$. The counit is a monoid homomorphism $(F \circ G)M \to M$.

  • $GM$ has the interpretation of being the underlying set of elements of $M$.
  • $(F \circ G)M$ has the interpretation of being the monoid of formal operations applied to the elements of $M$

and the counit $(F \circ G)M \to M$ is simply the "evaluation" homomorphism that replaces the formal operations with their actual values.

Now, let's apply $G$ again, so that we can look at this whole arrangement in terms of the underlying sets. The evaluation map is sent to $(G \circ F \circ G)M \to GM$.

If we define $X = GM$, then evaluation is a map $TX \to X$ which, in fact, satisfies the definition of a $T$-algebra.

The interpretation is now

  • $X$ is the underlying set of a monoid
  • $TX$ is the set of all formal operations on the elements of that monoid
  • $TX \to X$ evaluates the formal operations