Let $\mathcal{M}$ be a nonstandard model of Peano arithmetic, $\phi(v,\bar{w})$ a formula in the language of arithmetic, and $\bar{a} \in \mathbb{M}$. Show that if $\mathcal{M} \models \phi(n,\bar{a})$ for all $n < \omega$, then there is an infinite $c \in \mathbb{M}$ s.t. $\mathcal{M} \models \phi(c,\bar{a})$.

My Proof

Let $\mathcal{N}$ be the standard model of Peano arithmetic, and $\pmb{PA}$ the theory of Peano arithmetic so that $\mathcal{N} \models \pmb{PA}$; additionally, we know by definition $\mathcal{M} \models \pmb{PA}$. Suppose for the sake of contradiction that there exists a nonstandard model $\mathcal{M}$ so that $\mathcal{M} \models \phi(n,\bar{a})$ but $\mathcal{M} \not\models \phi(c,\bar{a})$. Since $\mathcal{M} \models \pmb{PA}$, $\mathcal{M} \models \phi(0,\bar{a})$ and by the assumption that $\mathcal{M} \models \phi(n,\bar{a})$ for all $n < \omega$, we know $\mathcal{M} \models \forall x (\phi(x,\bar{a}) \Rightarrow \phi(x + 1, \bar{a}))$. Hence by the induction axiom of $\pmb{PA}$:

$$Ind(\phi) := (\phi(0) \wedge \forall x(\phi(x) \Rightarrow (x+1))) \Rightarrow \forall x \phi(x),$$

we know $\mathcal{M} \models \forall x (\phi(x,\bar{v}))$, therefore $\mathcal{M} \models \phi(c,\bar{a})$. But this contradicts our hypothesis and we conclude: $$\mathcal{M} \models \phi(c,\bar{a}).$$

My Problem

My primary concern is whether I can use the induction principle of Peano arithmetic to argue that I can "reach" this $c$ by induction. Since as I understand, this $c$ lies beyond $\omega$.

Additionally, is there another way to prove the proposition without invoking the details of Peano Arithmetic?

  • $\begingroup$ I have a question: why $\mathcal{M}\models \phi(n,\overline{a})$ for all $n<\omega$ implies $\mathcal{M}\models \forall x (\phi(x,\overline{a})\to \phi(x+1,\overline{a}))$? $\endgroup$ – Hanul Jeon Feb 13 '15 at 4:25
  • $\begingroup$ I presume it's because all the n's less than $\omega$ can be reached by induction, ie: $0,1,\ldots$. So for every $x$, you can always count up one and $\phi$ is still satisfied. $\endgroup$ – chibro2 Feb 13 '15 at 4:30
  • $\begingroup$ I can't find a reason that $\phi(x,\overline{a})\to\phi(x+1,\overline{a})$ holds for nonstandard $x$. $\endgroup$ – Hanul Jeon Feb 13 '15 at 4:35
  • $\begingroup$ So I presume the reason is by the induction principle which is an axiom of PA. This is the part where I am iffy about. Since the principle says if it's true for 0 and x, x+1, then it's true for all x. I presume the universal quantifier is over all elements of $\mathbb{M}$, which includes c. $\endgroup$ – chibro2 Feb 13 '15 at 4:47
  • $\begingroup$ Ah, I realize it. If $\phi(x,a)$ does not hold for all nonstandard $x$, then $\lnot\phi(x+1,a)\to \lnot\phi(x,a)$ holds for all nonstandard $x$ so you can guarantee that $\forall x[ \phi(x,a)\to\phi(x+1,a)]$ holds on $\mathcal{M}$. $\endgroup$ – Hanul Jeon Feb 13 '15 at 4:50

The induction principle is OK in $\mathcal M$, but its hypothesis is not necessarily satisfied in your situation. You inferred from (1) $\mathcal M\models\phi(n,\bar a)$ for all $n<\omega$ that (2) $\mathcal M\models\forall x\,(\phi(x,\bar a)\implies\phi(x+1,\bar a))$. Unfortunately, (1) does not imply (2). The error arises because the variable $x$ in (2) ranges over the whole universe of $\mathcal M$, not just over numbers $n<\omega$.

Note also that, if your argument were correct, it would give that $\mathcal M\models\phi(c,\bar a)$ for all elements $c$ of $\mathcal M$. That conclusion is not in general right; the correct conclusion is that some infinite $c$ in $\mathcal M$ satisfies $\mathcal M\models\phi(c,\bar a)$. (One can do a bit better; there is some infinite $d$ in $\mathcal M$ such that $\mathcal M\models\phi(c,\bar a)$ for all $c\leq d$.)

  • $\begingroup$ I think that if we assume (for an argument by contradiction), that $\mathcal{M} \vDash \phi(n,a)$ for all $n \in \mathbb{N}$ but $\mathcal{M} \nvDash \phi(c,a)$ for all $c \in \mathcal{M}\setminus\mathbb{N}$, then the argument of the OP will work. (In the assumption, I have added the quantification for the $n$ and the $c$ which were missing in the original question.) To put it otherwise: If we assume $\mathcal{M}\vDash \phi(n,a)$ only for standard numbers $n$, then (1) would imply (2). Or am I wrong? $\endgroup$ – russoo Feb 13 '15 at 16:10
  • 1
    $\begingroup$ @russoo Yes. From the assumptions that $\phi(x,\bar a)$ holds in $\mathcal M$ for all standard $x$ and that it holds for no nonstandard $x$, then we can infer the assertion (2) in my answer. The OP may or may not have had the second part of the assumption in mind earlier in the argument (as you noticed, the quantification of $c$ is missing), but by the time he wanted (2) he was claiming that it followed from just (1). $\endgroup$ – Andreas Blass Feb 13 '15 at 16:19

This is my current proof. It incorporates suggestions from comments above and elsewhere.

First recall that $\phi(x) \rightarrow \phi(x+1)$ is short hand for $\neg \phi(x) \vee \phi(x+1)$. Now suppose for some infinite $c$, we have $\mathcal{M} \models \neg\psi(c,\bar{a})$, then the statement:

$$\mathcal{M} \models \neg\psi(c,\bar{a}) \vee \mathcal{M} \models (c + 1, \bar{a}),$$

is true since the first statement of the disjunction is true by definition. But by definition:

$$\mathcal{M} \models \neg\psi(c,\bar{a}) \vee \mathcal{M} \models (c + 1, \bar{a}) \Rightarrow \mathcal{M} \models \psi(c,\bar{a}) \rightarrow \psi(c + 1, \bar{a}),$$

hence the implication is true for all infinite $c$. On the other hand, we know $\mathcal{M} \models \psi(n,\bar{a})$ for all $n < \omega$ so $\mathcal{M} \models \psi(n+1,\bar{a})$. Hence we have:

$$\mathcal{M} \models \neg\psi(n,\bar{a}) \vee \mathcal{M} \models (n + 1, \bar{a}) \Rightarrow \mathcal{M} \models \psi(n,\bar{a}) \rightarrow \psi(n + 1, \bar{a}),$$

where the term on the left hand side of of $\Rightarrow$ is true because the term to the right of the disjunction is true by assumption. But we know all terms in $\mathbb{M}$ is either of form $n < \omega$ or some infinite $c$, so we can say:

$$\forall x (\psi(x,\bar{a}) \rightarrow \psi(x+1,\bar{a})) \rightarrow \forall x \psi(x,\bar{a}).$$ Hence $\mathcal{M} \models \psi(c,\bar{a})$ for some infinite $c \in \mathbb{M}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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