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$

Page

Toolbox

Search

Free magma

Contents

Construction

Constructive properties

Relations on a free magma; Universal property

See also