provability of a formula in a given theory

18 Views Asked by At

Suppose $T$ is an arithmetically sound theory. If there exists a polynomial function $p$ such that $T$ proves for every $n$

$\neg\varphi(\overline{p(n)})\rightarrow\varphi(\overline{n})$

is it true that for every $n$, $T$ proves $\varphi(\overline{n})$

1

There are 1 best solutions below

0
On

No, and this has nothing to do with logic: take $\varphi(x)$ to be "$x$ is even" and $p(x)=x+1$. The statement $$\forall x(\neg\varphi(p(x))\rightarrow\varphi(x))\wedge \neg\varphi(\overline{1})$$ is - to nuke a mosquito - provable in the arithmetically sound theory PA.