Exercise 12, § 2

Let I be a non-empty set. Show that the elements of the free magma $M(I)$ can be identified with the sequences $(a_i)_{1 \leq i \leq n}$ ($n$ an arbitrary integer $\geq 1$) where the $a_i$ are either elements of I or a special symbol P (representing the "open brackets"), where these sequences satisfy the following conditions:

(i) The length $n$ of the sequence is equal to twice the number of symbols P which appear in it, plus 1.

(iii) For all $k \leq n - 1$, the number of symbols P which appear in the subsequence $(a_i)_{1 \leq i \leq k}$ is $\geq k/2$.

(Use Set Theory, I, Appendix to associate with each sequence $(a_i)$ an element of $M(I)$; for example, to the sequence PPPxyzPxy corresponds the word $((xy)z)(xy)$).)