# Exam question: Show that each infinite L-structure has a countable, elementary substructure

I've had the following question in a midterm exam about first order logic, and didn't manage to solve it:

Let $$\mathcal{L}$$ be a language and $$\mathcal{A}, \mathcal{B}$$ structures over $$\mathcal{L}$$. We say "$$\mathcal{A}$$ is an elementary substructure of $$\mathcal{B}$$" (short $$\mathcal{A}\preccurlyeq \mathcal{B}$$), if $$\mathcal{A}$$ is a substructure of $$\mathcal{B}$$ and if for all formulas $$\phi$$ over $$\mathcal{L}$$ the following holds true:

$$\quad \quad\quad\mathcal{A} \models \phi \Leftrightarrow \mathcal{B}\models \phi$$

Now prove: Let $$\mathcal{L}$$ be countable. Every infinite $$\mathcal{L}$$ structure has a countable, elementary substructure. Note: Construct a countable Set $$B_0 \subseteq B$$, that for each formula $$\phi(x,y)$$ over $$\mathcal{L}$$ and for each tuple $$a\in B_0$$ contains a $$b$$ with $$\mathcal{B} \models \phi(a,b)$$, if such a $$b$$ exists.

I honestly wasn't able to solve this with the time given, and it seems to be way to long a proof for an exam. I nevertheless want to understand this, since we didn't get any solutions afterwards.

(for every formula/funciton $$P$$, I denote $$n_P$$ as the number of variable it takes, and if $$G$$ is a function, $$G[\cdot]$$ is the image)

Let $${\cal A}$$ be infinite model of some countable theory.

Let $$B_0\subseteq A$$ be countable, let $$F$$ be the set of function symbols, now for each $$φ$$ formula define $$f_φ$$ such that:

If $$\bar x\in A^{n_φ-1}$$ such that $$∃y(φ(y,\bar x))$$ we have $$φ(f_φ(\bar x), \bar x)$$, otherwise $$f_φ(\bar x)$$ is some arbitrary element of $$A$$(we need AC to prove such $$f$$ exists.)

Then let $$B_{k+1}=B_k\cup\bigcup_\limits{f\in F}f[B_k^{n_f}]∪\bigcup_\limits{φ\text{ formula}}f_φ[B_k^{n_φ}]$$ and $$B=\bigcup B_k$$(this is the closure of all of the function symbols and the functions we defined), because the theory is countable, and there are only countable formulas, $$B$$ is countable.

Now use Tarski–Vaught test to show that $$B$$ with the same interpretation as $$\cal A$$ is elementary substructure

• Thank you so much for your answer. The only problem I have with understanding it is that we never covered the Tarski-Vaught test, so I am unsure if this is the way I was supposed to solve it in the exam. – nshct Apr 27 at 16:23
• @nshct did you cover "canonical model of a theory"? – ℋolo Apr 27 at 16:25
• @nshct in what method did you prove the completeness theorem? – ℋolo Apr 27 at 16:30
• Okay, "a theory has a model iff it is not contradictory", so given a theory T with not contradictions you created a model using Henkin's functions right? If you take a look on this model, you can show that the model you get is the size of the language, if M is an infinite model of a countable theory T, create T' to be the set of all formulas true in M, add to the language countably many constant symbols, create a new theory T'' to be T'+for every 2 constant symbols a,b the axiom "a≠b", now Henkin model you create for this will be the countable model you wanted – ℋolo Apr 27 at 16:47
• Oh I think I get it know! Thank you! – nshct Apr 27 at 16:55