Free magmas and binary trees

Question

The free magma on a set $S$ can be constructed by defining $S_0 = S$, $S_{n+1} := \coprod_{p+q=n} S_p \times S_q$ and then endowing $\coprod_{n \geq 0} S_n$ with the evident magma structure (Bourbaki, Algebra, Chapter 1, §7.1). I would like to know if there is a more "global" and "non-recursive" description of the free magma, in particular of its underlying set.

Now it seems to be common sense in algebra that the free magma consists of rooted binary trees which are finite, proper (i.e. every node has $0$ or $2$ children) and whose leaves are labeled with elements from $S$. For example, if $S=\{a,b,c\}$, then the term $a((bc)a)$ corresponds to the tree

  /\
 /  \
a   /\
   /  \
  /\   a
 /  \
b    c

Now, most of the time people speak of graphs and trees they actually mean isomorphism classes of them, because it really does not matter how the nodes are called. But now consider $a(aa)$ and $(aa)a$ with corresponding trees

  /\                  /\
 /  \                /  \
a   /\              /\   a
   /  \            /  \
  a    a          a    a

These labeled trees are isomorphic, right? But they represent different elements in the free magma. It seems to me that we need a different notion of tree here, and I wonder if this is already known under a certain name.

A (rooted, proper) binary "left/right" tree is a pointed set $(T,x)$ equipped with two partial functions $l,r : T \to T$ with $\mathrm{dom}(l)=\mathrm{dom}(r)$, $\mathrm{im}(l) \cap \mathrm{im}(r)=\emptyset$, $x \notin \mathrm{im}(l) \cup \mathrm{im}(r)$, and such that every element of $T$ can be reached from $x$ by applying $l$ or $r$ finitely many times. A labeling of the leaves is a map $T \setminus \mathrm{dom}(l) \to S$. We have an obvious notion of isomorphism between such structures. Then we take isomorphism classes.

It does not seem to agree with the concept of an oriented tree. I also welcome any other ideas how to give a global description or encoding of elements of the free magma.

Answer 1

The elements are rooted, full (or proper) binary trees whose leaves are labelled with elements of $S$. Binary trees are by default ordered (or plane) trees, meaning that the children of each vertex are given a fixed order; in the case of binary trees we simply say that each internal vertex has a left child and a right child. Thus, your last two trees are not isomorphic as binary trees: the left child of the root of the first tree is a leaf, while the left child of the root of the second tree is not a leaf.