Free magma

A free magma is magma structure that is as general as possible—a magma generated from an initial set with no constraints or relations.

Construction

The free magma generated from a set $X$ is constructed as follows.

  • The set $M_1(X)$ is the set $X \times \{0\}$.
  • For $n>1$, the set $M_n(X)$ is defined as

\[M_n = \bigcup_{i=1}^{n-1} M_i \times M_{n-i} \times \{i\} .\]

  • The set $M(X)$ is the union of the sets $M_n(X)$.

It can be seen from induction on the sets $M_n(X)$ that for any $w\in M(X)$, the integer $n$ such that $x \in M_n(X)$ is unique. This is called the length of $x$; it is sometimes denoted $l(x)$.

Let $x$ and $y$ be elements of $M(X)$. The element $(x,y,l(x))$ is called the composition of $x$ and $y$; it is denoted multiplicatively.

The set $M(X)$ under the law of composition $(x,y) \mapsto xy$ is called the free magma generated by $X$.

The rest of this article details properties useful by extension to free groups and free monoids.

Constructive properties

Proposition 1. Let $X$ be a set, let $S$ be a magma, and let $f : X \to S$ be a function. Then $f$ may be extended uniquely to $M(X)$ in such a way that the extended mapping is a magma homomorphism.

Proof. We prove by induction on $n$ that for all integers $n$, there is a unique extension $f_n$ of $f$ to $\bigcup_{i=1}^n M_n(X)$ such that, for all $x,y$ in $M$ satisfying $l(x) + l(y) \le n$, $f(xy) = f(x)f(y)$. For $n=1$, this is vacuously true. Now, supposing that this statement holds for integers less than or equal to $n$, we note that every element $w$ of $M_n(X)$ is uniquely defined as the composition of two elements $x,y$ of $M(X)$ such that $l(x) + l(y) \le n$; in particular, $l(x),l(y) <n$; thus we can and must define $f(w)$ as $f(x)f(y)$; for elements $w$ of length less than $n$, $f(w)$ must be defined as for $\bigcup_{i=1}^{n-1} M_i(X)$, by inductive hypothesis.

Now, for any $x\in M(X)$, we define $g(x)$ to be $f_{l(x)}(x)$. This is then a homomorphism from $M(X)$ into $S$, since $f_{l(x)}(x) = f_n(x)$, for all $n\ge l(x)$, and it is the only possible one. $\blacksquare$

Let $X$ and $Y$ be sets, $f : X \to Y$ a function; this is also a function $f : X \to M(Y)$. The unique homomorphic extension of $f$ to $M(X)$ is denoted $M(f)$.

Proposition 2. If $f : X \to Y$ is injective (or surjective), then so is $M(f)$.

The proof is analogous to the proof of the first proposition.

Relations on a free magma; Universal property

Let $I$ be an index set, and $(u_i,v_i)_{i\in I}$ a set of ordered pairs of elements of a free magma $M(X)$. The quotient magma under the equivalence relation compatible with $M(X)$ generated by the pairs $(u_i,v_i)_{i\in I}$ is called the magma generated by $X$ and the relators $(u_i,v_i)$. Let $R$ denote this equivalence relation, and let $h$ be the canonical homomorphism from $M(X)$ to $M(X)/R$. Then $h(X)$ generates $M(X)/R$.

Proposition 3. Every magma is isomorphic to a magma generated by a magma generated by a set under a set of relators.

Proof. Let $S$ be a magma, and $X$ a generating subset of $S$. Let $f$ be the unique homomorphic extension of the identity mapping on $X$ to $M(X)$, and let $(u_{i},v_i)_{i\in I}$ be a generating set of the equivalence relation $R(x,y)$ defined as $f(x) = f(y)$. Then $S$ is isomorphic to the magma generated by $X$ with the relators $(u_{i},v_i)_{i\in I}$. $\blacksquare$

See also