Suppose $\mathcal{M_n} = (M_n ,I_n )$ is an $L$-model, $\mathcal{M_n}$$\preceq$$\mathcal{M_{n+1}}$ for each $n∈\mathbb N$. Let$M = \bigcup_{n \in \mathbb N} M_n $

1.Define an interpretation $I$ on $M$ properly so that each $\mathcal{M_n}$ is a substructure of $\mathcal{M} = (M,I)$.

2.Show $\mathcal{M_n}$$\preceq$$\mathcal{M}$ for each $n$ and the above $\mathcal{M}$.

3.Show if $\mathcal{N}$ is such that $\mathcal{M_n}$$\prec$$\mathcal{N}$ for all $n$, then $\mathcal{M}$$\preceq$$\mathcal{N}$.


First part

I have finished the first part.

1.For constant symbol $c$, $I(c)=I_0(c)$

2.If $F$ is an $n$-ary function symbol, $a_1,...,a_{n+1}∈M_i$, then $I(F)(a_1, \ldots, a_n) =a_{n+1}$ iff$ I(F)(a_1, \ldots, a_n)=$$a_{n+1}$.

3.If $R$ is a $n$-ary relation symbol, $a_1,...,a_n∈M_i$, then$(a_1, \ldots, a_n)∈I(R)$ iff$ (a_1, \ldots, a_n)∈$$I(R_i)$.

The second part

I think we need $Tarski's$ $Criterion$ in this part. Suppose $A$ is definable in $\mathcal{M}$ with parameters from $M_n$, then we need to show $A∩M_n≠∅$. But the difficult is how to find a element which belongs to both $A$ and $M_n$?

the third part

Intuitively, it is obvious. But how to prove? Still use $Tarski's Criterion$?


I hope you can give some help in $Question 2,3$


Remember that $M$ is the union.

Hence if you have a witness in $M$, then there must be a witness in some $M_{k}$ for some $k$. Now using the fact that $M_{n}\leq M_{k}$

I'm not sure about your question 3, unless you mean "then $M\leq N$". In which case once again you just need to check the definition: certainly $M$ is a substructure of $N$, and if $N$ have a solution then $M_{n}$ have a solution, hence $M$.

  • $\begingroup$ There is a typo in question 3. I have amended it. Even though the witness belongs to $M_k$, why must it belong to $M_n$? $\endgroup$ – Marvin Dec 29 '16 at 8:30
  • 1
    $\begingroup$ This answer is quite incomplete. For example: Given a formula $\exists x\, \varphi(x,\overline{a})$ satisfied in $M$, there is (as you say) some $M_k$ such that the tuple $\overline{a}$ and a witness $b$ is in $M_k$. So $M\models\varphi(b,\overline{a})$, but how do you know that $M_k\models\varphi(b,\overline{a})$? [Note that in the Tarski-Vaught test, $\varphi$ may have quantifiers...] $\endgroup$ – Alex Kruckman Dec 31 '16 at 22:47
  • 1
    $\begingroup$ Instead, try doing induction on the number of quantifiers. $\endgroup$ – Alex Kruckman Dec 31 '16 at 23:11
  • $\begingroup$ @AlexKruckman Thanks. I already understand it. $\endgroup$ – Marvin Jan 1 '17 at 13:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.