Overspill in models of arithmetic

Question

Assume that $M$ is a non-standard model of complete arithmetic, i.e. of the theory $Th(\mathbb{N})$. Suppose that $R$ and $S$ are proper cuts of $M$. (With a cut, I mean a subset of the universe of $M$ which is closed under successor and which is downward closed.) Let $\varphi(x,y)$ be a formula in the language of arithmetic, possibly with parameters from $M$. My question is whether the following variant of the overspill principle holds:

If for all $s \in S$ and all $r \in R$, it holds that $M\vDash \varphi(s,r)$, then there is an element $s_0 > S$ and an element $r_0 > R$ with $M \vDash \varphi(s_0,r_0)$.

It will also be helpful for me to learn about some "interesting" special cases where the above statement may hold (e.g. restrictions on the cuts $R$ and $S$, restrictions on the formula $\varphi$, ...).

Answer 1

No, this "double overspill" can fail; here's an example. Fix a non-standard element $q\in M$. Let $S$ be the cut consisting of just the standard numbers, and let $R$ consist of those elements $r\in M$ that are infinitely far below $q$ (i.e., $r+n<q$ for all standard $n$). Then $R$ is also a cut, and all elements $s\in S$ and $r\in R$ satisfy $s+r<q$. But if $s_0>S$ (i.e., $s_0$ is infinite) and $r_0>R$ (i.e., for some standard $n_0$, $r_0+n_0\geq q$), then $s_0+r_0>n_0+r_0\geq q$.

Answer 2

You asked about positive instances, so here is a natural one.

Theorem. If $M\models\text{PA}$ is nonstandard, and $S< R$ are cuts in $M$ with $R\prec M$, then the double overspill principle holds.

Proof. Assume $S<R\prec M$, and suppose $\varphi(s,r)$ holds in $M$ for all $s\in S$ and $r\in R$. Since by elementarity $R$ sees that $\forall r\varphi(s,r)$ holds for each particular $s\in S$, and since $S$ cannot be definable in $R$, as it satisfies $\text{PA}$, it must be that there is some $s_0\in R-S$ with $\varphi(s_0,r)$ for all $r\in R$. But now, $M$ sees all those facts, and since $M$ cannot define the cut determined by $R$, it must be that $\varphi(s_0,r_0)$ for some $r_0> R$. So we've achieved the double overspill principle. QED

We don't really need $\varphi(s,r)$ for all $s\in S$ and $r\in R$, but rather only for unboundedly many such $s$ and $r$, and the principle is perhaps more interesting and useful in that form.

Indeed, we achieved a stronger principle: if $S<R\prec M$ and $\varphi(s,r)$ for unboundedly many $s\in S, r\in R$, then there is $s_0\in R-S$ and $r_0>R$ with $\varphi(s_0,r_0)$.