7
$\begingroup$

For a certain project I am currently working on, I need to be able to find PA cuts in nonstandard models of PA, in desirable intervals. For example, I wonder if the following is true, where $\newcommand\PA{\text{PA}}\PA_k$ refers to the theory with only $\Sigma_k$ induction.

Question. If $M$ is a model of $\PA$ in which $\PA_{k-1}$ is consistent, but $\PA_k$ is not (so $k$ is nonstandard), then is there a $\PA$ cut in $M$ above $k$ in which $\PA_k$ is consistent?

That is, I want to cut $M$ below the first proof of a contradiction in $\PA_k$, but above $k$, and have $\PA+\text{Con}(\PA_k)$.

Alternatively, is there some other $\Sigma_1$ property of $k$, other than $\neg\text{Con}(\PA_k)$, such that I can always find a $\PA$ cut in $M$ between $k$ and the witness of that property? Kameryn Williams suggested that the Paris-Harrington result may provide this, since it is designed to ensure $\PA$ cuts below the corresponding PH-Ramsey number. But I would need, however, that one can always end-extend the model so as to make the $\Sigma_1$ property true. Does the PH construction have both these features?

With the consistency statements, for example, for any nonstandard $k$ in any model $M$ of $\PA$, there is always an end-extension of $M$ to a model of $\PA$ with $\neg\text{Con}(\PA_k)$.

$\endgroup$
19
  • $\begingroup$ If it helps, feel free to assume that$M$ is countable. $\endgroup$ Dec 3, 2017 at 14:51
  • $\begingroup$ What do you mean by "$\Sigma_k$ fragment of PA"? Taken literally, this would mean that all the PA_k theories are equiconsistent with PA (provably in a weak base theory), hence no k as in the question exists. $\endgroup$ Dec 3, 2017 at 16:21
  • 1
    $\begingroup$ Doesn't this paper of Solovey give a negative answer to your question? In remarks after the theorem 1.1, it gave a sufficient lower bound for $n$ respect to the $k$. This implies that there exists a model of $PA$ that $PA_k$ has a short proof of inconsistency, but $PA_{k-1}$ is consistent. $\endgroup$ Dec 3, 2017 at 21:02
  • 2
    $\begingroup$ @ErfanKhaniki Yes, I think you are right. Could you be so kind as to write up and post an answer to explain this? It would be even better if you could summarize Solovay's construction. $\endgroup$ Dec 3, 2017 at 21:44
  • 2
    $\begingroup$ @Joel In standard terminology, $\Gamma$-fragment of a theory $T$ denotes the set of $\Gamma$-sentences provable in $T$. Under this definition, any proof of contradiction in PA immediately gives a contradiction in $\mathrm{PA}_0$, by the definition of $\mathrm{PA}_0$. Thus, it is impossible that $\mathrm{PA}_k$ is inconsistent, but $\mathrm{PA}_{k-1}$ is consistent. Since this appears not to be what you want, you should avoid the standard term, and call it differently, and in any case, explain it in the question itself, not just in the comments. $\endgroup$ Dec 4, 2017 at 9:46

1 Answer 1

5
$\begingroup$

Q1

Theorem1. Let $M$ be a countable nonstandard model of $PA$, let $r,c,a\in M\setminus\mathbb{N}$, $M\models r,c\leq a$, and suppose $M\models Con_{{\bf I}\Sigma_r}$. Then there exists a model $K$ of $PA$ such that $a\in K$ and

  1. $M|_a=K|_a$,
  2. $M|_{2^a}\subseteq K$,
  3. $K\models\exists d<2^{a^c}Pr_{{\bf I}\Sigma_r}(d,\ulcorner\bot\urcorner)$,
  4. $K\models Con_{{\bf I}\Sigma_{r-1}}$.

Proof. See this paper.


The proof of theorem 1 uses finite Godel's theorem and some other provability results:

Theorem2. Let $T\supseteq {\bf I}\Delta_0+\mathsf{EXP}$ be a consistent theory with provability predicate $Pr_T(x,y)$ such that $Pr_T(x,y)\in\mathsf{P}$, then there exists a $\epsilon >0$ such that the length of the shortest $T$-proof of $Con_T(\bar{n})$ defined by $\forall x(|x|\leq \bar{n}\to \neg Pr_T(x,\ulcorner \bot \urcorner))$ is at least $n^\epsilon$.

Proof. See this paper.


Let $M$ be a countable nonstandard model of $PA+Con_{{\bf I}\Sigma_{r}}$ for some nonstandard $r\in M$, then by theorem 1, there exists a countable nonstandard model $K\models PA$ such that:

  1. $M|_{2^{r+1}}\subseteq K$,

  2. $K\models\exists d<2^{(r+1)^r}Pr_{{\bf I}\Sigma_r}(d,\ulcorner\bot\urcorner)$,

  3. $K\models Con_{{\bf I}\Sigma_{r-1}}$.

This implies that for any $PA$-cut $K'$ in $K$ above $r$, $K|_{2^{(r+1)^r}}\subseteq K'$, hence $K'\models \exists d<2^{(r+1)^r}Pr_{{\bf I}\Sigma_r}(d,\ulcorner\bot\urcorner)$, therfore the answer of the question is no.


Q2

Let $Y(x,y)$ be the $PA$ indicator defined in theorem 3.23 of metamathematics of first-order arithmetic. Suppose $(Y(x,y)=z) \equiv \exists w \psi(x,y,z,w)$ for some $\psi\in\Delta_0$. Define $\phi(x)$ by $\exists y \left(\psi(x,(y)_0,(y)_1,(y)_2)\land x< (y)_0\land x< (y)_1\right)$. Let $M$ be a nonstandard model of $PA$. Suppose for some nonstandard element $k\in M$, $M\models \phi(k)$. This implies that there exists a least element $c\in M$ such that $M\models \psi(k,(c)_0,(c)_1,(c)_2)\land k< (c)_0\land k< (c)_1$. This implies:

  1. $Y(k,(c)_0)=(c)_1$,
  2. $(c)_1$ is nonstandard,
  3. $k < (c)_0$,

therefore by definition of indicator there exists a cut $I$ in $M$ such that:

  1. $I\models PA$,
  2. $k\in I$,
  3. $(c)_0\not \in I$, and hence $c\not\in I$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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