Isomorphism between generated structures

Question

Let $\underline{A}$ and $\underline{B}$ be $\tau$-structures. Let $G_A=\{a_1,\ldots,a_n\}\subseteq A$ and $G_B=\{b_1,\ldots,b_n\}\subseteq B$. Suppose $(a_1,\ldots,a_n)$ and $(b_1,\ldots,b_n)$ satisfy the same quantifier free formulas, then $\underline{A}[G_A]$ is isomorphic to $\underline{B}[G_B]$.

Here $\underline{A}[G_A]$ denotes the smallest substructure of $\underline{A}$ generated by $G_A$.

My attempt: Since a homomorphism is completely determined by the generated set, so denote the required map by $\Phi:a_i\mapsto b_i$.

The map is clearly surjective and injectivity is true because $\underline{A}$ and $\underline{B}$ satisfy the same formulas. In order to show that $\Phi$ is a homomorphism, I am able to show that relations (and their inverses) are preserved because they are atomic formulas. However, how do I show that functions are preserved too?

Answer 1

We first need to specify how extend the assignment $a_i \mapsto b_i$ to a map $F: \underline{A}[G_A] \to \underline{B}[G_B]$. We define $F$ recursively as follows:

1. $F(a_i) = b_i$ for $i=1,\ldots,n$.
2. If $x_1, \ldots, x_l \in \underline{A}[G_A]$, each of $F(x_1), \ldots, F(x_l)$ was defined, and $f$ is an $l$-ary function symbol from $\tau$, then we define $F(f^A(x_1, \ldots, x_l)) = f^B(F(x_1), \ldots, F(x_l))$.

One shows that $F$ is well defined, that the domain of $F$ is indeed $\underline{A}[G_A]$, and that $F$ is a homomorphism (for $F$ to be defined, we need the assumption that $G_A$ and $G_B$ satisfy the same quantifier free formulas).