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.
Thanks in advance!
Best Answer
(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