# Isomorphism between generated structures

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?

• $f(c_1,\dots,c_n)=d$ is an atomic formula. Nov 15, 2021 at 13:57
• @PrimoPetri Write, but why is $f^B(\Phi(a_1))=f^B(b_1)$ equal to $\Phi(f^A(a_1))$? Nov 15, 2021 at 14:20
• @modeltheory Why is "a homomorphism is completely determined by the generat[ing] set"? How do we extend the map $a_n \mapsto b_n$ to a homomorphism of the generated structures? Answer that, and you'll see why $f^B(\Phi(a_1)) = \Phi(f^A(b_1))$ holds.
– j3M
Nov 16, 2021 at 10:23
• @j3M I know that from here. Nov 16, 2021 at 12:21

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).
• I fixed some typos, I hope you don't mind. Also, to nitpick: I think the hypothesis that $G_A$ and $G_B$ satisfy the same quantifier-free formulas is used only to show that $F$ is well-defined and that $F$ preserves the relation symbols in the language. The fact that $F$ preserves the function symbols in the language is just by definition of $F$, and the fact that the domain of $F$ is $\underline{A}[G_A]$ follows from the characterization of the elements of $\underline{A}[G_A]$ as evaluations of terms at elements of $G_A$. Nov 17, 2021 at 16:00
• @AlexKruckman Thanks for fixing! My bad.. And for the other comment, of course, it's just that to talk about the domain of $F$, and about $F$ preserving function symbols we need $F$ to be defined. But I guess my choice of language wasn't optimal.