# Elementary substructure question

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!

• Do you mean "at most $n$" rather than "almost $n$"? Nov 30 '20 at 21:17
• Yes! Thanks you. That was a typo. Nov 30 '20 at 21:23

This is false as written: take for example $$\mathcal{M}=\mathcal{N}=(\mathbb{N}; <)$$, and let $$\varphi(x,y)\equiv x. 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

compactness.

• Do I consider the theory $Th(\mathcal{M})$ in this case? For example for the backwards direction: We know that $Th(\mathcal{M}) \models \mathcal{M}$. Then by compactness theorem, there exists a subset $\tau \subset Th(\mathcal{M})$ such that $\tau \models Th(\mathcal{M})$. Since $\mathcal{N}$ is an elementary extension of $\mathcal{M}$, $\tau \models Th(\mathcal{N})$. But how do you get $\omega$-saturation from here? Dec 1 '20 at 0:25
• @cciirrcclllee I don't understand your question. Which bulletpoint are you trying to prove? (The second one genuinely uses the compactness theorem, the first uses the idea behind the notion of compactness.) Dec 1 '20 at 0:26
• I'm trying to prove that both bullets are equivalent, from assuming the second one. Dec 1 '20 at 0:27
• Also, you mean "$\mathcal{M}\models Th(\mathcal{M})$. And compactness doesn't say that every theory is entailed by some finite subtheory; that's not the case. Dec 1 '20 at 0:27
• @cciirrcclllee You need to apply the compactness theorem to build the desired $\mathcal{N}$; you want to use compactness, + the assumption on $\mathcal{M}$, to show that there is an $\mathcal{N}$ with some element whose corresponding $\varphi$-set is infinite. Think about how you build a nonstandard model of $\mathsf{PA}$ (say) by compactness ... Dec 1 '20 at 2:32