Let $A$ be a semigroup and $X\subseteq A$. Define $X_0=X$ and $X_{n+1}=X_n\cup \{ab\, |\, a\in X,\, b\in X_n\}$. Then $\cup_{n=0}^{\infty}X_n=Sg^A(X)$

Question

Let $A$ be a semigroup and $X\subseteq A$. Define $X_0=X$ and $X_{n+1}=X_n\cup \{ab\, |\, a\in X,\, b\in X_n\}$.
Then $\bigcup\limits_{n=0}^{\infty}X_n=Sg^A(X)$, which is the subsemigroup of $A$ generated by $X$.

This is my proof:
( $\subseteq$ ) It suffices to check, by induction on $n$, that $X_n\subseteq Sg^A(X)$ for all $n$.
$X_0=X\subseteq Sg^A(X)$ since $Sg^A(X)$ is the smallest subsemigroup of $A$ containing $X$.
Assume that $X_n\subseteq Sg^A(X)$. If $x\in X_{n+1}\backslash X_n$, then $x=ab$ for some $a\in X$ and $b\in X_n$.
So $a,\, b\in Sg^A(X)$ and $x=ab\in Sg^A(X)$ as well. Hence $X_{n+1}\subseteq Sg^A(X)$.

( $\supseteq$ ) It suffices to check that $\bigcup\limits_{n=0}^{\infty}X_n$ is a subsemigroup of $A$ containing $X$.
My question is how to finish the remaining part. If $a,\, b\in \bigcup\limits_{n=0}^{\infty}X_n$, how to prove $ab\in \bigcup\limits_{n=0}^{\infty}X_n$?

Answer 1

Hint:

$x\in X_n$ iff we can write $x=\prod_{i=0}^ma_i$ for $a_i\in X$ and some $m\leq n$.

This can be proved by means of induction on $n$.