View source for Free magma

A '''free magma''' is [[magma]] structure that is as general as possible&mdash;a magma generated from an initial set with no constraints or relations.

== Construction ==

The free magma generated from a [[set]] <math>X</math> is constructed as follows.

*The set <math>M_1(X)</math> is the set <math>X \times \{0\}</math>.
*For <math>n>1</math>, the set <math>M_n(X)</math> is defined as
<cmath> M_n = \bigcup_{i=1}^{n-1} M_i \times M_{n-i} \times \{i\} . </cmath>
*The set <math>M(X)</math> is the union of the sets <math>M_n(X)</math>.

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

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

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

The rest of this article details properties useful by extension to [[free group]]s and [[free monoid]]s.

== Constructive properties ==

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

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

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

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

'''Proposition 2.'''  If <math>f : X \to Y</math> is [[injective]] (or [[surjective]]), then so is <math>M(f)</math>.

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

== Relations on a free magma; Universal property ==

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

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

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

== See also ==

* [[Free group]]
* [[Free monoid]]

[[Category:Abstract algebra]]
[[Category:Mathematics]]