Skip to main content
\\, -> \, (TeX)
Source Link
Goldstern
  • 14k
  • 1
  • 47
  • 71

The answer is no, and in particular, $X$ is $\Pi^0_1$-hard. Let $\sigma(x)=\exists v\\,\theta(x,v)$$\sigma(x)=\exists v\,\theta(x,v)$ be a complete $\Sigma^0_1$-formula, where $\theta\in\Delta^0_0$, and find a formula $\pi(x)$ such that PA proves

$$\pi(x)\leftrightarrow\forall w\\,(\mathrm{Proof_{PA}}(w,\ulcorner\pi(\dot x)\urcorner)\to\exists v\le w\\,\theta(x,v))$$$$\pi(x)\leftrightarrow\forall w\,(\mathrm{Proof_{PA}}(w,\ulcorner\pi(\dot x)\urcorner)\to\exists v\le w\,\theta(x,v))$$

by self-reference. Let $n\in\omega$. Since $\neg\pi(\bar n)$ is equivalent to a $\Sigma^0_1$ sentence, PA proves $\neg\pi(\bar n)\to\mathrm{Pr_{PA}}(\ulcorner\neg\pi(\bar n)\urcorner)$. By definition, $\neg\pi(\bar n)\to\mathrm{Pr_{PA}}(\ulcorner\pi(\bar n)\urcorner)$, hence PA proves $\mathrm{Con_{PA}}\to\pi(\bar n)$. I claim that

$$\tag{$*$}\mathbb N\models\sigma(n)\Leftrightarrow\mathrm{PA}\vdash\pi(\bar n),$$

which means that $n\mapsto\ulcorner\pi(\bar n)\urcorner$ is a reduction of the $\Pi^0_1$-complete set $\{n:\mathbb N\models\neg\sigma(n)\}$ to $X$.

To show $(*)$, assume first that $M\models\mathrm{PA}+\neg\pi(\bar n)$. Then there is no standard PA-proof of $\pi(\bar n)$, hence the witness $w\in M$ to the leading existential quantifier of $\neg\pi(\bar n)$ must be nonstandard. Then $\neg\theta(n,v)$ holds for all $v\le w$, and in particular, for all standard $v$, hence $\mathbb N\models\neg\sigma(\bar n)$.

On the other hand, assume that PA proves $\pi(\bar n)$, and let $k$ be the code of its proof. Since PA is sound, $\mathbb N\models\pi(\bar n)$, hence there exists $v\le k$ witnessing $\theta(\bar n,v)$, i.e., $\mathbb N\models\sigma(\bar n)$.

The answer is no, and in particular, $X$ is $\Pi^0_1$-hard. Let $\sigma(x)=\exists v\\,\theta(x,v)$ be a complete $\Sigma^0_1$-formula, where $\theta\in\Delta^0_0$, and find a formula $\pi(x)$ such that PA proves

$$\pi(x)\leftrightarrow\forall w\\,(\mathrm{Proof_{PA}}(w,\ulcorner\pi(\dot x)\urcorner)\to\exists v\le w\\,\theta(x,v))$$

by self-reference. Let $n\in\omega$. Since $\neg\pi(\bar n)$ is equivalent to a $\Sigma^0_1$ sentence, PA proves $\neg\pi(\bar n)\to\mathrm{Pr_{PA}}(\ulcorner\neg\pi(\bar n)\urcorner)$. By definition, $\neg\pi(\bar n)\to\mathrm{Pr_{PA}}(\ulcorner\pi(\bar n)\urcorner)$, hence PA proves $\mathrm{Con_{PA}}\to\pi(\bar n)$. I claim that

$$\tag{$*$}\mathbb N\models\sigma(n)\Leftrightarrow\mathrm{PA}\vdash\pi(\bar n),$$

which means that $n\mapsto\ulcorner\pi(\bar n)\urcorner$ is a reduction of the $\Pi^0_1$-complete set $\{n:\mathbb N\models\neg\sigma(n)\}$ to $X$.

To show $(*)$, assume first that $M\models\mathrm{PA}+\neg\pi(\bar n)$. Then there is no standard PA-proof of $\pi(\bar n)$, hence the witness $w\in M$ to the leading existential quantifier of $\neg\pi(\bar n)$ must be nonstandard. Then $\neg\theta(n,v)$ holds for all $v\le w$, and in particular, for all standard $v$, hence $\mathbb N\models\neg\sigma(\bar n)$.

On the other hand, assume that PA proves $\pi(\bar n)$, and let $k$ be the code of its proof. Since PA is sound, $\mathbb N\models\pi(\bar n)$, hence there exists $v\le k$ witnessing $\theta(\bar n,v)$, i.e., $\mathbb N\models\sigma(\bar n)$.

The answer is no, and in particular, $X$ is $\Pi^0_1$-hard. Let $\sigma(x)=\exists v\,\theta(x,v)$ be a complete $\Sigma^0_1$-formula, where $\theta\in\Delta^0_0$, and find a formula $\pi(x)$ such that PA proves

$$\pi(x)\leftrightarrow\forall w\,(\mathrm{Proof_{PA}}(w,\ulcorner\pi(\dot x)\urcorner)\to\exists v\le w\,\theta(x,v))$$

by self-reference. Let $n\in\omega$. Since $\neg\pi(\bar n)$ is equivalent to a $\Sigma^0_1$ sentence, PA proves $\neg\pi(\bar n)\to\mathrm{Pr_{PA}}(\ulcorner\neg\pi(\bar n)\urcorner)$. By definition, $\neg\pi(\bar n)\to\mathrm{Pr_{PA}}(\ulcorner\pi(\bar n)\urcorner)$, hence PA proves $\mathrm{Con_{PA}}\to\pi(\bar n)$. I claim that

$$\tag{$*$}\mathbb N\models\sigma(n)\Leftrightarrow\mathrm{PA}\vdash\pi(\bar n),$$

which means that $n\mapsto\ulcorner\pi(\bar n)\urcorner$ is a reduction of the $\Pi^0_1$-complete set $\{n:\mathbb N\models\neg\sigma(n)\}$ to $X$.

To show $(*)$, assume first that $M\models\mathrm{PA}+\neg\pi(\bar n)$. Then there is no standard PA-proof of $\pi(\bar n)$, hence the witness $w\in M$ to the leading existential quantifier of $\neg\pi(\bar n)$ must be nonstandard. Then $\neg\theta(n,v)$ holds for all $v\le w$, and in particular, for all standard $v$, hence $\mathbb N\models\neg\sigma(\bar n)$.

On the other hand, assume that PA proves $\pi(\bar n)$, and let $k$ be the code of its proof. Since PA is sound, $\mathbb N\models\pi(\bar n)$, hence there exists $v\le k$ witnessing $\theta(\bar n,v)$, i.e., $\mathbb N\models\sigma(\bar n)$.

Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

The answer is no, and in particular, $X$ is $\Pi^0_1$-hard. Let $\sigma(x)=\exists v\\,\theta(x,v)$ be a complete $\Sigma^0_1$-formula, where $\theta\in\Delta^0_0$, and find a formula $\pi(x)$ such that PA proves

$$\pi(x)\leftrightarrow\forall w\\,(\mathrm{Proof_{PA}}(w,\ulcorner\pi(\dot x)\urcorner)\to\exists v\le w\\,\theta(x,v))$$

by self-reference. Let $n\in\omega$. Since $\neg\pi(\bar n)$ is equivalent to a $\Sigma^0_1$ sentence, PA proves $\neg\pi(\bar n)\to\mathrm{Pr_{PA}}(\ulcorner\neg\pi(\bar n)\urcorner)$. By definition, $\neg\pi(\bar n)\to\mathrm{Pr_{PA}}(\ulcorner\pi(\bar n)\urcorner)$, hence PA proves $\mathrm{Con_{PA}}\to\pi(\bar n)$. I claim that

$$\tag{$*$}\mathbb N\models\sigma(n)\Leftrightarrow\mathrm{PA}\vdash\pi(\bar n),$$

which means that $n\mapsto\ulcorner\pi(\bar n)\urcorner$ is a reduction of the $\Pi^0_1$-complete set $\{n:\mathbb N\models\neg\sigma(n)\}$ to $X$.

To show $(*)$, assume first that $M\models\mathrm{PA}+\neg\pi(\bar n)$. Then there is no standard PA-proof of $\pi(\bar n)$, hence the witness $w\in M$ to the leading existential quantifier of $\neg\pi(\bar n)$ must be nonstandard. Then $\neg\theta(n,v)$ holds for all $v\le w$, and in particular, for all standard $v$, hence $\mathbb N\models\neg\sigma(\bar n)$.

On the other hand, assume that PA proves $\pi(\bar n)$, and let $k$ be the code of its proof. Since PA is sound, $\mathbb N\models\pi(\bar n)$, hence there exists $v\le k$ witnessing $\theta(\bar n,v)$, i.e., $\mathbb N\models\sigma(\bar n)$.