A free magma is magma structure that is as general as possible—a magma generated from an initial set with no constraints or relations.
The free magma generated from a set is constructed as follows.
- The set is the set .
- For , the set is defined as
- The set is the union of the sets .
It can be seen from induction on the sets that for any , the integer such that is unique. This is called the length of ; it is sometimes denoted .
Let and be elements of . The element is called the composition of and ; it is denoted multiplicatively.
The set under the law of composition is called the free magma generated by .
The rest of this article details properties useful by extension to free groups and free monoids.
Proposition 1. Let be a set, let be a magma, and let be a function. Then may be extended uniquely to in such a way that the extended mapping is a magma homomorphism.
Proof. We prove by induction on that for all integers , there is a unique extension of to such that, for all in satisfying , . For , this is vacuously true. Now, supposing that this statement holds for integers less than or equal to , we note that every element of is uniquely defined as the composition of two elements of such that ; in particular, ; thus we can and must define as ; for elements of length less than , must be defined as for , by inductive hypothesis.
Now, for any , we define to be . This is then a homomorphism from into , since , for all , and it is the only possible one.
Let and be sets, a function; this is also a function . The unique homomorphic extension of to is denoted .
Proposition 2. If is injective (or surjective), then so is .
The proof is analogous to the proof of the first proposition.
Relations on a free magma; Universal property
Let be an index set, and a set of ordered pairs of elements of a free magma . The quotient magma under the equivalence relation compatible with generated by the pairs is called the magma generated by and the relators . Let denote this equivalence relation, and let be the canonical homomorphism from to . Then generates .
Proposition 3. Every magma is isomorphic to a magma generated by a magma generated by a set under a set of relators.
Proof. Let be a magma, and a generating subset of . Let be the unique homomorphic extension of the identity mapping on to , and let be a generating set of the equivalence relation defined as . Then is isomorphic to the magma generated by with the relators .