Sets of sentences-Structures-Definable subsets in a structure There is this question I am working on, but since I am not very familiar with this area I am really struggling to do it.
That is :
Let $V = \{ +, \cdot , 0, 1 \}$ and let $\mathcal{N} = (\mathbb{N} , +, \cdot , 0, 1 )$, where $\mathbb{N}$ is the set of non-negative integers and the symbols are interpreted as usual on $\mathbb{N}$. Let $T = Th(\mathcal{N})$ be the set of all $V-$sentences which are true in $\mathcal{N}$.
Now consider the definition of ${\phi}(\mathcal{M})$ and definable subset in a structure (The set ${\phi}(\mathcal{M})$ is called a $V$-definable subset of $\mathcal{M}$).
1)Suppose that ${\phi}(x)$ is a $V$-formula and ${\phi}(\mathcal{N})$ is finite. Show that for every $\mathcal{N} \preccurlyeq \mathcal{M}$, ${\phi}(\mathcal{M}) = {\phi}(\mathcal{N})$.
2)Show that if $\mathcal{M} \equiv \mathcal{N}$ then $\mathcal{M} \succsim \mathcal{N}$. (Hint: for every $n\in \mathbb{N}$, there is a V-term $t_{n}$, without variables, such that $(t_n)^{\mathcal{N}} = n$. Consider the function $n \mapsto (t_n)^{\mathcal{M}})$.
In 1) I tried to show that ${\phi}(\mathcal{N}) \subseteq {\phi}(\mathcal{N})$ and $|{\phi}(\mathcal{N})| = |{\phi}(\mathcal{M})|$ but I couldn't do it.
Any help would be very much appreciated it.
Thank you in advance!
 A: For (1), can you think of a sentence expressing "there are $n$ elements satisfying $\varphi$"? Now, with that in mind, what does elementarity tell you about $\varphi(\mathcal{M})$ and $\varphi(\mathcal{N})$ if one of the two is finite? Now, why does $\varphi(m)^\mathcal{N}\implies\varphi(m)^\mathcal{M}$? (Think about what elementarity means ...)
For (2), the function $n\mapsto t_n^\mathcal{M}$ is clearly an embedding of $\mathcal{N}$ into $\mathcal{M}$, so you just need to show that it's elementary - that is, for each $n$, we have $\mathcal{N}\models\varphi(n)$ iff $\mathcal{M}\models\varphi(t_n^\mathcal{M})$ for each formula $\varphi$. The elementary equivalence of $\mathcal{M}$ and $\mathcal{N}$ means that sentences true in one are true in the other; so, for a given $n$, can you see how to transform the formula-with-a-parameter $\varphi(n)$ into a genuine sentence with the same meaning? HINT: think about $t_n$ ...

Incidentally, these both have generalizations beyond $\mathcal{N}$:


*

*For arbitrary $\mathcal{A}\preccurlyeq\mathcal{B}$ and formula $\varphi$,if $\varphi(\mathcal{A})$ is finite then $\varphi(\mathcal{A})=\varphi(\mathcal{B})$.

*If every element of $\mathcal{A}$ is definable and $\mathcal{B}\equiv\mathcal{A}$, then there is a unique elementary embedding of $\mathcal{A}$ into $\mathcal{B}$.
Once you've finished the proofs of (1) and (2), see if you can generalize them to prove these stronger statements.
