---
tag: ZZF8XPBG3Z
kind: example
name: Free magma
msc: [08B20, 20N02]
instance_of: [TTTEV3NWWM, 9689SFPVE9]
uses: [9689SFPVE9, TTTEV3NWWM, GTS4DRRMZR, 0M418FE7BB]
sources:
  - url: https://en.wikipedia.org/wiki/Magma_(algebra)
    locator: 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|0M418FE7BB]] is $u \cdot v = (u v)$.
So $M(X)$ is a [[magma|9689SFPVE9]].
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|TTTEV3NWWM]] 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|GTS4DRRMZR]] 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`.

## Explanations

### L1 human

The free magma is what one gets by multiplying letters without any rule at all, not even associativity.
Every way of putting brackets around a product gives a different element.
For one letter $x$ and three factors there are two elements, $(xx)x$ and $x(xx)$; for four factors there are five.
Imposing associativity on it gives the free semigroup of nonempty words.