4
$\begingroup$

Let $\underline{B}$ be a $\tau$-structure and $G\subseteq B$. Suppose $\underline{A}=\langle G\rangle_B$ denote the smallest substructure of $\underline{B}$ generated by $G$.

Show that for each $a\in A$, there exist a $\tau$-term $t(x_1,\ldots,x_n)$ and $g_1,\ldots,g_n\in G$ such that $t^{\underline{B}}(g_1,\ldots,g_n)=a$.

My attempt: Let $$C=\{a\in A\mid \exists \tau\text{-term }t(x_1,\ldots,x_n) \text{ and } g_1,\ldots,g_n\in G :t^{\underline{B}}(g_1,\ldots,g_n)=a \}.$$ My idea is to show that $\underline{C}$ is a substructure of $B$ and $G\subseteq C$. Then I can directly obtain $\underline{A}\subseteq\underline{C}$.

To show that $G\subseteq C$, let $g\in G$ and for a variable $x_1$, let $t=x_1$, then $t^{\underline{B}}(g)=g$ and hence $g\in C$.

Is this correct? Moreover, how do I show that $\underline{C}$ is a substructure?

$\endgroup$
9
  • 1
    $\begingroup$ It's correct. What does it mean to be a substructure? Check that $C$ is closed under the basic operations. It's quite straightforward. $\endgroup$
    – Berci
    Commented Nov 13, 2021 at 23:48
  • $\begingroup$ @Berci I'm not able to show that $C$ is closed under relations. $\endgroup$ Commented Nov 14, 2021 at 0:47
  • $\begingroup$ Every subset is closed under relations. Or, what do you mean? $\endgroup$
    – Berci
    Commented Nov 14, 2021 at 0:51
  • $\begingroup$ @Berci $\underline{A}$ is called a substructure of $\underline{B}$ (with same signature $\tau$) if $A\subseteq B$, for each $R\in\tau$, we have $\overline{a}\in R^{\underline{A}}$ iff $\overline{a}\in R^{\underline{B}}$, and for each $f\in\tau$, we have $f^{\underline{A}}(\overline{A})=f^{\underline{B}}(\overline{A})$. $\endgroup$ Commented Nov 14, 2021 at 16:46
  • $\begingroup$ Yes, correct. The relations are preserved in any subset! (Because their interpretation is simply kept the same in the substructure.) So you only need to worry about closedness under basic operations and your solution is complete. $\endgroup$
    – Berci
    Commented Nov 14, 2021 at 16:53

1 Answer 1

1
$\begingroup$

Your attempt is fine. $\def\B{\underline B} \def\C{\underline C}$

For any $n$-ary basic operation symbol $f$ and elements $a_i={t_i}^{\B}(\vec{b_i}) \ \in C$ with all $b_{i,j}\in G$, just consider the composed term $\tau:=f\big(t_1(\vec{x_1}),\,\dots,\,t_n(\vec{x_n})\big)$, so that $$f^\B(a_1,\dots,a_n)\ =\ f^\B\Big({t_1}^\B(\vec{b_1}),\,\dots,\,{t_n}^\B(\vec{b_n})\Big)\ =\ \tau^\B(\vec{b_1},\dots,\vec{b_n})\ \in C$$ so $C$ is closed under the interpretation $f^\B$ of $f$ within $\B$.

This is necessary for enabling us to define the interpretation $f^\C$ so that it is the restriction of $f^\B$, because operation symbols must be interpreted as functions defined on every $n$-tuples.

On the other hand, for an $n$-ary relation symbol $R$, we can (and actually must) simply define $R^\C(a_1,\dots,a_n)$ to have the same truth value as $R^\B(a_1,\dots,a_n)$ for any elements $a_1,\dots,a_n\in C$.
This way the structure $\C$ defined on set $C$ (with the help of structure $\B$) is indeed a substructure.


Note that if the signature doesn't contain operation symbols, then every subset of any structure is a substructure (of course if we interpret each relation symbols as the restriction of those in the original structure).

$\endgroup$
1
  • 1
    $\begingroup$ Thank you! I see it now and I understand now that the reason to include relations in the definition of the substructure is to make it explicit that we consider restriction of relation. $\endgroup$ Commented Nov 14, 2021 at 18:49

You must log in to answer this question.

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