2
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ $f(c_1,\dots,c_n)=d$ is an atomic formula. $\endgroup$ Nov 15, 2021 at 13:57
  • $\begingroup$ @PrimoPetri Write, but why is $f^B(\Phi(a_1))=f^B(b_1)$ equal to $\Phi(f^A(a_1))$? $\endgroup$ Nov 15, 2021 at 14:20
  • $\begingroup$ @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. $\endgroup$
    – j3M
    Nov 16, 2021 at 10:23
  • $\begingroup$ @j3M I know that from here. $\endgroup$ Nov 16, 2021 at 12:21

1 Answer 1

2
$\begingroup$

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).

$\endgroup$
3
  • 2
    $\begingroup$ 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$. $\endgroup$ Nov 17, 2021 at 16:00
  • $\begingroup$ @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. $\endgroup$
    – j3M
    Nov 17, 2021 at 16:12
  • 1
    $\begingroup$ (Nice answer, though, I upvoted!) $\endgroup$ Nov 17, 2021 at 16:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .