Proposition 13

Let X be a finite set with at least two elements. Let H denote a Hall set relative to X. Then there exist a strictly increasing bijection $p \mapsto w_p$ of $\mathbf{N}$ onto H and a sequence $(P_p)_{p \in \mathbf{N}}$ of subsets of H with the following properties: (a) $P_0 = X$. (b) For every integer $p \geq 0$, $w_p \in P_p$. (c) For every integer $n \geq 1$, there exists an integer $p(n)$ such that every element of $P_p$ is of length $> n$ for all $p \geq p(n)$. (d) For every integer $p \geq 0$, the set $P_{p+1}$ consists of the elements of the form $w_p^i w$, where $i \geq 0$, $w \in P_p$ and $w \neq w_p$.

As X is finite, each of the sets $M^n(X)$ is finite. Let $H_n = H \cap M^n(X)$ for all $n \geq 1$. The Corollary to Proposition 12 shows that the finite set $H_n$ is non-empty. Let $u_n$ be the cardinal of $H_n$; let $v_0 = 0$ and $v_n = u_1 + \cdots + u_n$ for $n \geq 1$. As $H_n$ is a totally ordered finite set, there exists a strictly increasing bijection $p \mapsto w_p$ of the interval $[v_{n-1}, v_n - 1]$ of $\mathbf{N}$ onto $H_n$. It is immediate that $p \mapsto w_p$ is a strictly increasing bijection of $\mathbf{N}$ onto H.

Let $P_0 = X$ and for every integer $p \geq 1$ let $P_p$ be the set of elements $w$ of H such that $w \geq w_p$, and, either $w \in X$, or $\alpha(w) < w_p$ (note that if $w$ is of length $\geq 2$ the relation $w \in H$ implies $\alpha(w) \in H$ by condition (C) of Definition 2). Then $w_p \in P_p$; this is clear if $w_p \in X$ and follows from the inequality $l(\alpha(w_p)) < l(w_p)$ and condition (A) of Definition 2 when $w_p \notin X$.

Hence conditions (a) and (b) are satisfied.

Let $n$ be an integer $\geq 1$ and let $p \geq v_n$. For all $w \in P_p, l(w) \geq l(w_p) > n$ by the very definition of the mapping $p \mapsto w_p$. This establishes (c).

We now show that every element of the form $u = w_p^i w$ with $i \geq 0, w \in P_p$ and $w \neq w_p$ belongs to $P_{p+1}$. If $i \neq 0$, then $l(u) > l(w_p)$, whence $u > w_p$ and $u \geq w_{p+1}$; then $u \notin X$ and $\alpha(u) = w_p < w_{p+1}$, whence $u \in P_{p+1}$. If $i = 0$, then $u \in P_p$ and $u \neq w_p$; then $u > w_p$, whence $u \geq w_{p+1}$; if $u$ does not belong to $X$, then $\alpha(w) < w_p$, whence $\alpha(w) < w_{p+1}$; then again $u \in P_{p+1}$.

Conversely, let $u \in P_{p+1}$. We distinguish two cases:

(α) There exists no element $v$ of $M(X)$ such that $u = w_p v$. By definition of $P_{p+1}$, $u > w_p$. Further, if $u \notin X$, then $\alpha(u) \neq w_p$ by the given hypothesis and $\alpha(u) < w_{p+1}$ since $u \in P_{p+1}$; hence $\alpha(u) < w_p$. Hence $u \in P_p$ and $u \neq w_p$.

(β) There exists $v$ in $M(X)$ such that $u = w_p v$. By Definition 2, of necessity, either $w_p \in X, v \in X$ and $w_p < v$, or $v \notin X$ and $\alpha(v) \leq w_p < v$. In either case, $v \in P_{p+1}$.

Then there exist an integer $i \geq 0$ and an element $w$ of $M(X)$ such that $u = w_p^i w$, and either $w \in X$ or $w \notin X$ and $\alpha(w) \neq w_p$. If $i = 0$, we have case (α) above, whence $w \in P_p$ and $w \neq w_p$. If $i > 0$, the proof of (β) above establishes, by induction on $i$, the relations $w \in P_{p+1}$ and $w \neq w_p$. Suppose $w \notin X$; from $w \in P_{p+1}$ it follows that $\alpha(w) \leq w_p$ and as $\alpha(w) \neq w_p$, we conclude that $w \in P_p$. This completes the proof of (d).