Hall basis

Definition

Let $A$ be a set, and let $M(A)$ be the free magma on $A$. Its elements are the binary trees with leaves labelled by $A$. A tree that is not a single leaf is a pair $t = (t', t'')$ of a left and a right subtree. A Hall set on $A$ is a subset $H \subseteq M(A)$ with a total order $<$ such that:

1. $A \subseteq H$.
2. If $t = (t', t'') \in H \setminus A$, then $t'' \in H$ and $t < t''$.
3. A tree $t = (t', t'') \in M(A) \setminus A$ lies in $H$ if and only if $t', t'' \in H$, $t' < t''$, and either $t' \in A$ or $t' = (u, v)$ with $v \ge t''$.

Let $k$ be a field and let $L(A)$ be the free Lie algebra over $k$ on $A$. For $t \in M(A)$ let $P_t \in L(A)$ be given by $P_a = a$ for $a \in A$ and $P_{(t', t'')} = [P_{t'}, P_{t''}]$. The Hall basis attached to $H$ is the family $(P_h)_{h \in H}$. A standard theorem states that for every Hall set $H$ this family is a basis of $L(A)$ as a vector space.