Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

BOURBAKI, inside his book on ALGEBRA defines and provides explicit constructions concerning the concepts of free magma, free monoid (and implicitele free semi-group) and free group, and as well free commutative monoid (and implicitely 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 doescanyone know about an explicit construction for the free commutative magma over the set X ? Gérard LANG

share|improve this question
2  
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
1  
YES, I do know and had Laurent Schwartz as professor. –  Gérard Lang Sep 24 '10 at 14:47
1  
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

2 Answers 2

up vote 9 down vote accepted

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:

Example tree

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

commutativity relation.

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.

share|improve this answer
    
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
1  
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
1  
Thanks Darij, I have corrected it. –  Martin Brandenburg Sep 24 '10 at 18:33
    
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

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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.