Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$, ...).

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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$.

share|improve this answer

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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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