What's the appropriate definition of "tree" here?

Question

The free monoid on $X$ can be described as the underlying set of the skeleton of the groupoid whose objects are finite totally ordered sets graded in $X$, and whose morphisms are isomorphisms of totally-ordered sets that preserve the grading. Ergo, the aforementioned groupoid can be viewed as "groupoidifying" the free monoid on $X$. But since it's always a thin groupoid, we're not getting any new by doing this.

We can do something similar for commutative monoids; the free commutative monoid on $X$ is the underlying set of the skeleton of the groupoid whose objects are finite sets graded in $X$. If $X$ has one or more elements, this won't be a thin groupoid, so this time, we're actually getting something new by doing this.

I'd like to do this for free magmas and/or free commutative magmas (where "commutative" means $xy=yx$.) The idea is to:

• replace finite sets with finite full binary trees, defined appropriately.

• replace finite totally ordered sets with totally-ordered finite full binary trees.

Question. What are the appropriate definitions here?

I'd want something a bit like this: a finite full binary tree consists of a finite set $X$ (of leaves) together with some further structure on $X$, subject to some axioms, that can somehow be viewed as making $X$ into a full binary tree.

Maybe we should be viewing the vertexes of $X$ as being subsets of $X$, or something like that.

Answer 1

I doubt there's anything interesting to say about free magmas--I can't think of any reasonable definition for which the resulting groupoid would not be thin (which means you might as well just take the free magma itself as a discrete category). That said, I don't see any reason to expect to be able to get a non-thin groupoid in that case: what sort of elements of the free magma would you expect to have automorphisms?

For free commutative magmas, here's a definition you might give. A binary tree is a poset $P$ with a greatest element such for any $p\in P$ the set $\{q\in P:q\geq p\}$ is totally ordered and there are either exactly $2$ or exactly $0$ maximal elements in the set $\{q\in P:q<p\}$. (If $P$ is allowed to be infinite, you probably want to also say that every element of $\{q\in P:q<p\}$ is less than a maximal element.) Given a binary tree $P$, the leaves of $P$ are the minimal elements of $P$; we write $L(P)$ for the set of leaves of $P$. An $X$-graded binary tree is then a binary tree $P$ together with a map $L(P)\to X$. The isomorphism classes of finite $X$-graded binary trees should then be in natural bijection with elements of the free commutative magma on $X$.

Note that an isomorphism of finite binary trees is determined by where it sends the leaves, so you can think of the leaves of $P$ as the true "underlying set" of $P$ if you like. The poset $P$ can canonically be embedded in the power set of $L(P)$ by sending each element to the set of leaves below it, so you can think of the tree as a set $L$ together with a certain subposet $P$ of the power set of $L$. I don't immediately see a nice way to directly axiomatize such subposets though. In any case, if you only really care about the groupoid you get, none of this matters, since it would give an equivalent groupoid.

(To generalize to free magmas, you could define an "ordered binary tree" to be a binary tree together with a total ordering of the set of maximal elements of $\{q\in P:q<p\}$ for each $p\in P$. But finite ordered binary trees have no nontrivial automorphisms, so this gives you a thin groupoid.)