Exercice 12, § 2

Soit I un ensemble non vide. Montrer que les éléments du magma libre M(I) peuvent être identifiés aux suites $(a_i)_{1 \leq i \leq n}$ ($n$ entier $\geq 1$ arbitraire) où les $a_i$ sont, soit des éléments de $I$, soit un signe spécial $P$ (qui représente les « parenthèses ouvertes »), ces suites vérifiant les conditions suivantes : (i) La longueur $n$ de la suite est égale à deux fois le nombre des signes $P$ qui y figurent, plus 1. (ii) Pour tout $k \leq n - 1$, le nombre des signes $P$ qui figurent dans la suite partielle $(a_i)_{1 \leq i \leq k}$ est $\geq k/2$. (Utiliser E, I, p. 42–45, pour associer à chaque suite $(a_i)$ un élément de $M(I)$; par exemple, à la suite PPPxyzPxy correspond le mot (((xy)z)(xy))).