Free commutative magma over a set

Question

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 ?

Answer 1

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.

Answer 2

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.