# Free commutative magma over a set

BOURBAKI, inside his book on ALGEBRA defines and provides explicit constructions concerning the concepts of free magma, free monoid (and implicitly free semi-group) and free group, and as well free commutative monoid (and implicitly free commutative semi-group) and free commutative group over a set X; It seems clear that the concept of free commutative magma also makes sense, but does anyone know about an explicit construction for the free commutative magma over a set X ?

• I think that a free commutative magma over a set $X$ is the magma of all (non-labeled) rooted binary trees whose leaves are decorated with elements of $X$, up to isomorphism. Commented Sep 24, 2010 at 14:45

## 2 Answers

The free magma on $X$ consists of finite sequences of length $1$ or $2$, which consist of finite sequences of length $1$ or $2$, etc., of elements of $X$; the magma operation is just concatenation, i.e. $mn = (m,n)$. For example, $(a,((b,c),d))$ is such a sequence, where $a,b,c,d$ are in $X$. Elements may be visualized as finite binary trees, whose leaves are labelled in $X$. The examples gives:

To give a formal construction, define by recursion the sets $X_n$ of elements of height $n$ by $X_0 = X$ and $X_{n+1} = X_n + X_n^2$ (disjoint union). Then the disjoint union of $X_n$ is the free magma on $X$.

Now the free commutative magma is obtained by taking the quotient with respect to the smallest congruence relation satisfying $(a,b) \sim (b,a)$. This can be visualized with trees: Every branch can be rotated freely. So for example, now we don't distinguish between the trees

.

Note, however, that this does not justify that we may replace every bracket $(...)$ with $\{...\}$. Namely, $(a,a)$, which has two leaves, has to be distinguished from $(a)$, which has only one.

Remark: These constructions are "abstract nonsense", the same procedure works for free algebraic structures of any type (free monoids, free groups, free Lie algebras, etc.). Usually a bit of work has to be done to find normal forms for the elements of free algebraic structures. For free magmas, every element is already in normal form. For the free commutative magma on $X$, choose a total order on $X$, and call an element in normal form if the occuring elements of $X$ (ignoring the brackets) are ordered from left to the right. In the picture above, when we order $a<b<c<d$, then the tree on the left is the normal form of the tree on the right.

• Thank you very much. This answer is somewhat helping to have an intuitive interpretation of the free commutative magma over X Commented Sep 24, 2010 at 15:40
• Wait, how can your tree have a vertex with 3 children? I thought a magma had only a binary operation. Commented Sep 24, 2010 at 18:00
• I am not sure about your claim about the normal form for the free commutative magma, by the way. Don't $(a,(a,a))$ and $((a,a),a)$ both fall under your definition of a normal form? Commented Jul 14, 2013 at 11:53
• Right. One should prefer, say, $(a,(a,a))$. Commented Jul 15, 2013 at 19:43
• Not every element of the magma need have a normal form as you define it, for instance (ab)(ab). One could define a normal form by considering the lexicographic order (ignoring parentheses) and then an ordering of the parenthesizations, as your previous comment suggests. Commented Aug 15, 2017 at 17:10

As a set-theorist, I'd view the free commutative magma $M$ on $X$ as the family of hereditarily 1-or-2-element sets over $X$, together with $X$ itself. Here the members of $X$ are to be regarded as atoms (= urelements), not as sets.

In more detail, $M$ consists of the members of $X$ together with all those sets $a$ for which there is a transitive set $t$ ("transitive" means that, if a set $s$ is a member of $t$ then so are all members of $s$) such that $a\in t$ and such that every member of $t$ is either a member of $X$ or a set of cardinality 1 or 2.

• Thank you. This answer does not allow for a easy intuitive interpretation of the considered set Commented Sep 24, 2010 at 15:39
• I think that set theorists, or anyone who has worked with transitive sets for a while, have an intuition for Andreas Blass' construction. Commented Sep 24, 2010 at 15:44