# 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 ?

• Dear Gérard: your title makes it sound like spam giving away a certain computer algebra system... en.wikipedia.org/wiki/Magma_computer_algebra_system Was it intentional? – Thierry Zell Sep 24 '10 at 14:26
• Certainly no intention ! Certainly BORBAKI should read BOURBAKI ! – Gérard Lang Sep 24 '10 at 14:31
• "BORBAKI, inside his book on ALGEBRA defines..." You do know that Bourbaki is not a person, right? en.wikipedia.org/wiki/Nicolas_Bourbaki – Alex B. Sep 24 '10 at 14:32
• YES, I do know and had Laurent Schwartz as professor. – Gérard Lang Sep 24 '10 at 14:47
• I certainly didn't mean to insult you. It wasn't clear from the way your worded the question. – Alex B. Sep 24 '10 at 15:04

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 – Gérard Lang Sep 24 '10 at 15:40
• Wait, how can your tree have a vertex with 3 children? I thought a magma had only a binary operation. – darij grinberg Sep 24 '10 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? – darij grinberg Jul 14 '13 at 11:53
• Right. One should prefer, say, $(a,(a,a))$. – Martin Brandenburg Jul 15 '13 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. – Benoit Jubin Aug 15 '17 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 – Gérard Lang Sep 24 '10 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. – Martin Brandenburg Sep 24 '10 at 15:44