2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you. "meaning that the children of each vertex are given a fixed order;" How do you formalize this? I have suggested one approach in my question. $\endgroup$
    – HeinrichD
    Dec 14 '16 at 22:41
  • $\begingroup$ @Heinrich: For binary trees your formalization is as good as any, if you really need that level of formalism; generally one simply talks about left and right children. You could also formalize them as sets of finite sequences of zeroes and ones satisfying the conditions that give you a full binary tree: the empty sequence is the root, the left child of $\sigma$ is $\sigma^\frown 0$, and the right child of $\sigma$ is $\sigma^\frown 1$. $\endgroup$ Dec 14 '16 at 22:47
  • $\begingroup$ Could you add these conditions? Also, what is the simplest formalization of binary trees? (Yes, unfortunately for my purposes it has to be completely formal.) $\endgroup$
    – HeinrichD
    Dec 15 '16 at 11:21
  • $\begingroup$ @Heinrich: To make sure that the set $T$ of sequences forms a tree, you need to require that it be closed under taking initial segments. If you think in set-theoretic terms, so that $n=\{0,1,\ldots,n-1\}$, and a binary sequence of length $n$ is a function from $n$ to $2=\{0,1\}$, then you need to require that $\sigma\upharpoonright m\in T$ whenever $\sigma\in T$ and $m<|\sigma|=\operatorname{dom}\sigma$. To ensure that $T$ is full, you must require that for each $\sigma\in T$, either there is no $\tau\in T$ such that $\sigma\subsetneqq\tau$, or $\sigma^\frown 0,\sigma^\frown 1\in T$, where ... $\endgroup$ Dec 15 '16 at 16:57
  • $\begingroup$ ... $\sigma^\frown i=\sigma\cup\{\langle|\sigma|,i\rangle\}$. $\endgroup$ Dec 15 '16 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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