マグマ

右辺を $U$ とおく。$x,y\in U$ なら、ある $p,q\ge1$ で $x\in X_p$、$y\in X_q$ であり、定義から $xy\in X_pX_q\subseteq X_{p+q}\subseteq U$ である。よって $U$ は閉じていて、$X=X_1\subseteq U$ だから $\langle X\rangle\subseteq U$ である。
逆に、$X$ を含む閉じた部分集合 $A$ を任意にとり、すべての $n\ge1$ で $X_n\subseteq A$ となることを $n$ についての累積的な数学的帰納法で示す。$X_1=X\subseteq A$ である。$n\ge2$ とし、$n$ 未満のすべての $m$ で $X_m\subseteq A$ と仮定する。$p+q=n$、$p,q\ge1$ なら $p,q< n$ なので $X_p,X_q\subseteq A$ であり、$A$ が閉じていることから $X_pX_q\subseteq A$ となる。よって $X_n\subseteq A$ である。したがって $U\subseteq A$ であり、$A$ として $\langle X\rangle$ をとれば $U\subseteq\langle X\rangle$ を得る。$\square$

1. prop-mg-generated の記号で、$M$ における $X_n$ と、$N$ における $Y:=f(X)$ から作った $Y_n$ を比べる。$f(X_n)=Y_n$ を $n$ についての累積的な帰納法で示す。$n=1$ では定義そのものである。$n\ge2$ のとき、準同型性から $f(X_pX_q)=\{f(x)f(y)\mid x\in X_p,\ y\in X_q\}=f(X_p)f(X_q)$ であり、帰納法の仮定によりこれは $Y_pY_q$ に等しい。$p+q=n$ にわたって合併をとれば $f(X_n)=Y_n$ を得る。prop-mg-generated により $f(\langle X\rangle)=\bigcup_nf(X_n)=\bigcup_nY_n=\langle Y\rangle$ である。
2. $E:=\{x\in M\mid f(x)=g(x)\}$ とおく。$x,y\in E$ なら $f(xy)=f(x)f(y)=g(x)g(y)=g(xy)$ なので $xy\in E$ であり、$E$ は閉じている。仮定から $X\subseteq E$ なので、$\langle X\rangle\subseteq E$ である。$\square$

存在を示す。写像 $\overline u_n\colon M_n(X)\to N$ を $n$ についての累積的な帰納法で定める。$\overline u_1:=u$ とする。$n\ge2$ で $\overline u_1,\dots,\overline u_{n-1}$ が定まっているとき、$M_n(X)$ の元は、ある $1\le p\le n-1$ と $w'\in M_p(X)$、$w''\in M_{n-p}(X)$ によって $w'w''$ とただ一通りに書けるので、
$$ \overline u_n(w'w''):=\overline u_p(w')\,\overline u_{n-p}(w'') $$
と定めれば写像が定まる。各 $M_n(X)$ の上で $\overline u_n$ に一致する写像を $\overline u\colon M(X)\to N$ とする。$w'\in M_p(X)$、$w''\in M_q(X)$ なら $w'w''\in M_{p+q}(X)$ であり、定義から $\overline u(w'w'')=\overline u(w')\overline u(w'')$ となる。よって $\overline u$ は準同型であり、$M_1(X)=X$ の上で $u$ に一致する。
一意性を示す。準同型 $v\colon M(X)\to N$ が $v\circ\iota=u$ を満たすとする。長さについての累積的な帰納法で $v(w)=\overline u(w)$ を示す。長さ $1$ では $v(x)=u(x)=\overline u(x)$ である。長さ $n\ge2$ の元は $w=w'w''$（$w',w''$ の長さは $n$ 未満）と書けるので、
$$ v(w)=v(w')v(w'')=\overline u(w')\overline u(w'')=\overline u(w) $$
である。$\square$

$a_n:=\#M_n(X)$ とおく。$M_n(X)$ は $M_p(X)\times M_{n-p}(X)$（$1\le p\le n-1$）の非交和なので、$a_1=k$、$n\ge2$ で $a_n=\sum_{p=1}^{n-1}a_pa_{n-p}$ である。$a_n=C_{n-1}k^n$ を累積的な帰納法で示す。$n=1$ では $C_0=1$ より成り立つ。$m\ge1$ とし、$n\le m$ で成り立つと仮定すると
$$ a_{m+1}=\sum_{p=1}^{m}C_{p-1}k^p\,C_{m-p}k^{m+1-p}=k^{m+1}\sum_{i=0}^{m-1}C_iC_{m-1-i}=C_mk^{m+1} $$
となる。最後の等号は Catalan数 の命題「最初の復帰による漸化式」$C_m=\sum_{i=0}^{m-1}C_iC_{m-1-i}$ による。括弧の付け方の個数は、$x_1,\dots,x_n$ をすべて異なる文字とした $X$ の、各文字をちょうど一回ずつ順に使う長さ $n$ の元の個数であり、同じ漸化式 $b_1=1$、$b_n=\sum_{p=1}^{n-1}b_pb_{n-p}$ を満たすので $C_{n-1}$ に等しい。$\square$

1. $(xx)x$ は $M_2(X)\times M_1(X)$ の成分、$x(xx)$ は $M_1(X)\times M_2(X)$ の成分に属するので異なる。2. $x\ne y$ なら組 $(x,y)\ne(y,x)$ なので $xy\ne yx$ である。3. 単位元 $e$ があれば $l(ex)=l(e)+l(x)>l(x)$ なので $ex\ne x$ となり矛盾する。$l(ww)=2l(w)\ne l(w)$ なので冪等元もない。4. 長さ $2$ 以上の元を $w'w''$ と書く表し方は一通りなので、$ww'=ww''$ なら組 $(w,w')$ と $(w,w'')$ が一致し、$w'=w''$ である。右側も同様である。$\square$

1. $\sim_f$ は等号を写像で引き戻したものなので同値関係である。$x\sim_fx'$、$y\sim_fy'$ なら $f(xy)=f(x)f(y)=f(x')f(y')=f(x'y')$ なので $xy\sim_fx'y'$ である。$f(x)f(y)=f(xy)\in f(M)$ だから $f(M)$ は閉じている。
2. $[x]=[x']$ は $f(x)=f(x')$ と同値なので、$\overline f$ は代表元によらず定まり、しかも単射である。$f(M)$ の元は $f(x)$ の形なので全射である。さらに
   $$ \overline f([x][y])=\overline f([xy])=f(xy)=f(x)f(y)=\overline f([x])\,\overline f([y]) $$
   なので準同型であり、全単射な準同型として同型である。
3. 各 $x\in M$ で $j(\overline f(\pi(x)))=f(x)$ である。$\square$

thm-mg-free-universal により $\overline u$ が存在する。$M(X)$ は $X$ で生成される（長さ $2$ 以上の元はより短い元の積なので、長さについての帰納法で各元が $\langle X\rangle$ に属する）ので、prop-mg-hom-generated の 1 により $\overline u(M(X))=\langle\overline u(X)\rangle=\langle X\rangle=M$ である。thm-mg-isomorphism を $\overline u$ に当てはめればよい。$\square$