If $B$ is an algebra, $X \subseteq B$ and $A$ the smallest subset that extends $X$, then $A= \bigcup_{n < \omega} A_n$

Question

I need to prove the next thing:

Let $\textbf{B} = \langle B, (b_i)_{i \in I}, (g_j)_{j\in J} \rangle$. Let $X \subseteq B$ and let $A$ be the smallest subset of $B$ which extends $X$ and is closed in $\textbf{B}$. Then $A= \bigcup_{n < \omega} A_n$ where $A_0 = X \cup \{ b_i : i \in I\}$ and $A_{n+1}= A_n \cup \bigcup_{j \in J}g_j[A^{n_j}_n]$.

So, I know I need to prove both inclusions.

For the first one, $ \bigcup_{n < \omega} A_n \subseteq A$. I need to do it by induction, $A_n \subseteq A$. Let $A_0 = X \cup \{ b_i : i \in I\}$, but I don't know how to justify that it is. I mean, it "clearly" is a subset, because of the way it is constructed, but I don't know how to formally explain that, I would really appreciate the help. Now, As inductive hypothesis, assume $A_n \subseteq A$. As $A_\{n+1\}= A_n \cup \bigcup_{j \in J}g_j[A^{n_j}_n]$. Again, I have the notion: I know that $A_n$ is a subset by hypothesis, and I know that the other elements are also part of the subset because of the form it has, but again, I am stuck when I try to write it in a formal way, and I feel like I might be missing details.

For the other part of the inclusion, I have that $A \subseteq \bigcup_{n < \omega} A_n$. As $\bigcup_{n< \omega} A_n$ is a closed subset of $B$, and it contains $X$, it implies that $A \subseteq \bigcup_{n< \omega} A_n$, but in this case I know I'm missing on the details, but I have issues figuring them out. I would really appreciate your help in working this proof out. I'm working on improving my writing abilities so I really appreciate input on how to express things the best way possible. Thank you very much.

Answer 1

First recall the definition of closed: A subset $A \subseteq B$ is closed in $\def\B{\mathbf B}\B$ if

(1) $b_i \in A$ for $i \in I$.

That is $A$ contains all constants of the algebra $\B$.

(2) $g_j[A^{n_j}] \subseteq A$ for all $j \in J$, here $n_j$ is the arity of the operation $g_j$, that is $g_j \colon B^{n_j} \to B$.

That is $A$ is closed under all operations $g_j$.

To show that $A_0 \subseteq A$, note that as $A$ is closed, we have $\{b_i \colon i \in I\} \subseteq A$ by (1) above, as $X \subseteq A$ by definition of $A$ we have $A_0 \subseteq A$.

Now suppose $A_n \subseteq A$. By (2) above, for each $j \in J$ we have $g_j[A_n^{n_j}] \subseteq g_j[A^{n_j}] \subseteq A$, as $A_n \subseteq A$, we have $A_{n+1} = A_n \cup \bigcup_j g_j[A_n^{n_j}] \subseteq A$.

For the other inclusion, your idea is right: If we can show $\bigcup_n A_n$ is closed in $\B$, we are done (as $\bigcup_n A_n$ contains $X$ and $A$ is the smallest closed subset which contains $X$). For (1), note that for each $i \in I$, we have $b_i \in A_0 \subseteq \bigcup_n A_n$. For (2), let $j \in J$ and $a_1, \ldots, a_{n_j} \in \bigcup_n A_n$. Then there are natural numbers $k_l$ such that $a_l \in A_{k_l}$ for each $l$. Let $ k = \max_l k_l$. As $(A_n)$ is increasing, we have $a_l \in A_k$ for each $l$. But now $$ g_j(a_1, \ldots, a_{n_j}) \in g_j[A_k^{n_j}] \subseteq A_{k+1} \subseteq \bigcup_n A_n $$ hence $\bigcup_n A_n$ is closed.