Suppose $\mathcal{M} \preccurlyeq \mathcal{N}$, where $M$ is the universe of $\mathcal{M}$, and $N$ is the universe of $\mathcal{N}$. Let $\phi(x,y)$ be an $L$-formula, where $x$ is n-ary and $y$ is m-ary. Suppose $\forall k \in N^m$, $\phi(x,k)$ defines a finite set in $N^n$.
Show that there exists $n\in \omega$ such that for all $k\in M^m$, $\phi(x,k)$ defines a set of size at most $n$ in $M^n$.
Attempt:
Since $\forall k \in N^m$, $\phi(x,k)$ defines a finite set in $N^n$. I thought about taking the maximum of the size of each $k$. But I'm not sure how to find some $n\in \omega$ such that for all $k\in M^m$ $\phi(x,k)$ defines a set of size almost $n$ in $M^n$.
I thought about using Tarski-Vaught test. But I couldn't get anywhere.
Conversely, suppose there exists $n\in \omega$ such that for all $k\in M^m$, $\phi(x,k)$ defines a set of size at most $n$ in $M^n$. Show if $\mathcal{M} \preccurlyeq \mathcal{N}$, then $\forall k \in N^m$, $\phi(x,k)$ defines a finite set in $N^n$.
Attempt:
Suppose $\mathcal{M}\preccurlyeq \mathcal{N}$. Then we know $\mathcal{N} \models \phi(j(a))$ iff $\mathcal{N} \models \phi(a)$, where $j$ is the containment map, $a \in M^n$. Hence, by definition of an elementary substructure. We get our desired result.
Could someone help me with the first part? And please let me know if my second part makes sense.
Thank you so much!
This is false as written: take for example $\mathcal{M}=\mathcal{N}=(\mathbb{N}; <)$, and let $\varphi(x,y)\equiv x<y$. Clearly for each $k\in N$ there are only finitely many $a\in N$ such that $\mathcal{N}\models\varphi(a,k)$; however, it's also clear that there's no bound on the size of the sets picked out by $\varphi$ in $M$.
Here are a couple versions of the claim which are true:
Suppose $\mathcal{M}\preccurlyeq\mathcal{N}$, $\varphi(-,a)^\mathcal{N}$ is finite for each $a\in N$, and $\mathcal{N}$ is $\omega$-saturated. Then the conclusion holds.
Suppose $\mathcal{M}$ is such that every elementary extension $\mathcal{M}\preccurlyeq\mathcal{N}$ has $\varphi(-,a)^\mathcal{N}$ finite for each $a\in N$. Then the conclusion holds.
These two facts are really the same fact phrased two different ways, and the key to proving it/them is