Proposition 11

There exists a Hall set relative to $X$.

We shall construct by induction on the integer $n$ sets $H_n \subset M^n(X)$ and a total ordering on these sets: (a) We write $H_1 = X$ and give it a total ordering. (b) The set $H_2$ consists of the products $xy$ with $x, y$ in $X$ and $x < y$. We give it a total ordering. (c) Let $n \geqslant 3$ be such that the totally ordered sets $H_1, \ldots, H_{n-1}$ are already defined. The set $H'_{n-1} = H_1 \cup \cdots \cup H_{n-1}$ has a total ordering which induces the given relations on $H_1, \ldots, H_{n-1}$ and is such that $w < w'$ if $l(w) < l(w')$. We define $H_n$ to be the set of products $a(bc) \in M^n(X)$ with $a, b, c$ in $H'_{n-1}$ satisfying the relations $bc \in H'_{n-1}$, $b \leqslant a < bc$, $b < c$ and give $H_n$ a total ordering.

We write $H = \bigcup_{n \geqslant 1} H_n$; we give $H$ the total ordering defined thus: $w \leqslant w'$ if and only if $l(w) < l(w')$ or $l(w) = l(w') = n$ and $w \leqslant w'$ in the set $H_n$. It is immediate that $H$ is a Hall set relative to $X$.

For every subset S of X, we identify the free magma M(S) with its canonical image in M(X).