I need some help understanding part of my Model Theory notes:

"Given that $T$ is $\omega$-categorical and $\mathfrak{A} \vDash T$, for $S \subseteq A$, let $\langle S\rangle$ denote the smallest substructure of $\mathfrak{A}$ containing $S$. Suppose $S = \{ a_1, \ldots ,a_n\}$ and let $J_n$ be the collection of terms of $\mathcal{L}$ with variables amongst $v_1,\ldots,v_n$, one can easily show that $\langle S\rangle = \{ \tau^\mathfrak{A} [a_1, \ldots, a_n] : \tau \in J_n \}$."

I know that $\tau$ is a term and variables are terms, so $\tau^\mathfrak{A}[a_1,\ldots,a_n] = v_i^\mathfrak{A}[a_1,\ldots,a_n] = a_i$ shows that $S$ is contained within $\langle S\rangle$ as defined above. However, I do not know how to intuit $\langle S\rangle$ as above just from the information given. Also, I do not know how to show that $\langle S\rangle$ is of that form and is indeed a substructure.

Thanks in advance!

  • $\begingroup$ I changed $<S>$ to $\langle S\rangle$ and did some other MathJax corrections. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jan 4 '15 at 20:00
  • $\begingroup$ And I've also changed "w" to $\omega$. $\endgroup$ – Asaf Karagila Jan 4 '15 at 20:00
  • $\begingroup$ thank you both for the edits! $\endgroup$ – jh4 Jan 4 '15 at 20:01
  • $\begingroup$ Hint: it suffices to prove that every $\{ \tau^\mathfrak{A} [a_1, \ldots, a_n] : \tau \in J_n \}$ is a structure and every structure that contains $S$ contains also $\{ \tau^\mathfrak{A} [a_1, \ldots, a_n] : \tau \in J_n \}$. Also, note that it is not necessary to assume that $T$ is $\omega$-categorical. (Assuming $\omega$ categoricity you can prove that $\langle S\rangle$ is finite) $\endgroup$ – Primo Petri Jan 5 '15 at 19:55
  • 1
    $\begingroup$ $\omega$-categoricity is irrelevant here (so far). It is required for $\langle S\rangle$ to be finite, as @AsafKaragila noted: this is because $\omega$-categoricity forces the fact that for each $n$, there are only finitely many inequivalent terms with $n$ free variables. $\endgroup$ – tomasz Jan 6 '15 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.