Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: What is the relation between F-Algebras and Free Algebras?

Davi Sales Barreira (Jun 09 2023 at 14:20):

Hello, Friends.

So, I've been studying Category Theory for Programming, and I'm trying to understand how the concept of an F-Algebra relates (if it does) to the idea of a Free Algebra. For example, suppose that my functor $F$ is $1 + (\cdot \times \cdot)$. If my understanding is correct, I can use this functor to define a category of $F-$ algebras, where an object would be a tuple containing a set $a$ and an algebra (eval function) that takes $F a \to a$. If the algebra function I choose satisfies the associative property and the identity property for my given set $a$, then I have a monoid. Now, does the free monoid has any special property with regards to this $F$-algebra? Do these concepts relate in some sense?

Ralph Sarkis (Jun 09 2023 at 20:54):

An $F$-algebra is simply a set with a constant a binary operation on it (we could call them pointed magmas). I believe the free $F$-algebra generated by a set $X$ is the set $T(X)$ of finite rooted binary trees with leaves labelled in $X$. The algebra map is $[\mathsf{nil}, \mathsf{join}]$ with $\mathsf{nil}: 1 \to T(X)$ picking the empty tree and $\mathsf{join}: T(X) \times T(X) \to T(X)$ joining two trees by adding a root whose left. The emedding $\eta_X: X \to T(X)$ identifies $x$ with the tree with only a root labelled $x$.

If you have an $F$-algebra $[n,j]: 1+A\times A \to A$ and a function $f: X \to A$, the unique homomorphism $f^*: T(X) \to A$ satisfying $f^*\circ \eta_X = f$ is defined inductively. It sends $\mathsf{nil}$ to $n \in A$, it sends $x \in T(X)$ to $f(x) \in A$ and $\mathsf{join}(t_1,t_2)$ to $j(f^*(t_1),f^*(t_2))$.

Ralph Sarkis (Jun 09 2023 at 20:54):

The free monoid on a set $X$ is the set $X^*$ of finite words over $X$.

Ralph Sarkis (Jun 09 2023 at 20:56):

The category of monoids is a subcategory of the category of $F$-algebras (i.e. pointed magmas), so while the free monoid is free as a monoid, it is not free as a pointed magma because it satisfies some equations (unitality and associativity) that it does not need to satisfy as a pointed magma.

Ralph Sarkis (Jun 09 2023 at 20:58):

I cannot really answer your two questions because they are really open-ended, but I would venture a (not very confident) guess that there is no strong interesting relation between the free monoids and the free pointed magmas.

John Baez (Jun 09 2023 at 21:31):

If someone is really interested in describing monoids as algebras of something, they should use the concept of [[algebra over a monad]], not [[algebra for an endofunctor]].

Davi Sales Barreira (Jun 11 2023 at 15:51):

Thanks, @John Baez . I'm still trying to wrap my head around the concepts of F-Algebras, Monad Algebras and so on...

Davi Sales Barreira (Jun 11 2023 at 15:56):

Thanks, also, @Ralph Sarkis . I think I get your point.

Davi Sales Barreira (Jun 11 2023 at 15:56):

After digging a bit, I think I understood the distinction.

Davi Sales Barreira (Jun 11 2023 at 15:57):

What threw me off was the notino of initial F-Algebras, which serve as a way to represent recursive data types. This notion seemed related to how I would construct an equation in, for example, a Ring.

John Baez (Jun 11 2023 at 17:16):

I think basically an [[algebra over a functor]] is a good idea for describing data types not involving equations, like lists or trees or binary trees, while an [[algebra for a monad]] is good for describing data types that do involve equations, like groups or rings.