Free magma

Example

Let $X$ be a set. The free magma $M(X)$ on $X$ is defined inductively. Every $x \in X$ is an element of $M(X)$, and if $u, v \in M(X)$, then the formal product $(u v)$ is an element of $M(X)$. Two elements are equal only when they are built in the same way. The binary operation is $u \cdot v = (u v)$. So $M(X)$ is a magma. Its elements are the fully parenthesised nonempty words in $X$, or equivalently the binary trees with leaves labelled by $X$.

It is an absolutely free algebra of the signature with one binary operation. Check: $M(X)$ is generated by $X$ by construction. Given a magma $N$ and a map $f \colon X \to N$, define $h(x) = f(x)$ and $h((u v)) = h(u) \cdot h(v)$ by recursion on the construction. This is well defined because each element has exactly one construction, and it is the only homomorphism that extends $f$. So $M(X)$ is the free algebra on $X$ of the variety of all magmas.

For $X = \set{x}$, the elements with three leaves are $((x x) x)$ and $(x (x x))$, and they are different. The number of elements with $n$ leaves is the Catalan number $C_{n-1}$, the number of ways to bracket a product of $n$ factors. In Mathlib the free magma is FreeMagma.