I want to prove the following.

For every $\Pi^0_1$ statement $\forall x\phi(x)$, where $\phi(x)$ is a $\Delta^0_1$ formula, there is $e\in\mathbb{N}$ such that $\forall x\phi(x)$ implies $W_e=PA$* and $PA+\text{$W_e$ is consistent}\vdash\forall x\phi(x)$.

The argument is inspire by an argument of Turing in his PhD dissertation (lately rephrased in Feferman 1962) to show that the transfinite progressions of adding consistency statements is sensitive on which branch we choose at the limit stage of Kleene's $\mathcal{O}$, and it is as follow.

Fix a computable function $\sigma$ such that the range of $\sigma$ is $PA$. By recursion theorem, we can construct a partial computable function $\varphi_e$ such that

$\varphi_e(n)=\begin{cases}\sigma(n),&\text{if $\forall x<n\phi(n)$},\\ \sigma(n)\wedge\text{$W_e$ is consistent*},&\text{o.w.}\end{cases}$

Since $\forall x\phi(x)$ holds, $W_e=PA$. So the statement "$W_e$ is consistent" is really "$PA$ is consistent". In the next paragraph, we prove in $PA+$"$W_e$ is consistent".

Assume $\forall x\phi(x)$ fails, than $W_e=PA+$"$W_e$ is consistent". By Goedel's second incompleteness theroem, $W_e$ is not consistent. A contradiction.

This finishes the argument.

My question is (1) is this argument valid, or if something is missed or misunderstood? (2) is there other reference on this and related issues?

*$W_e$ is the range of $\Phi_e$ by fixing an enumeration of Turing machines $\{\Phi_e\}_{e\in\mathbb{N}}$. $PA$ stands for Peano Arithmetic. Please forgive my abusing of notation.

  • $\begingroup$ I don’t understand the notation. What is $W_e$, $\Sigma_e$, and $PA^*$? $\endgroup$ – Emil Jeřábek Jan 15 at 8:00
  • $\begingroup$ $W_e$ is the range of $\Phi_e$ by fixing an enumeration of Turing machines $\{\Phi_e\}_e$. $\Sigma_e$ is a typo (fixed), which should be $W_e$. $PA$ stands for Peano Arithmetic. I am sorry for the ambiguities. $\endgroup$ – Ruizhi Yang Jan 15 at 10:29
  • $\begingroup$ I think the "PA$^*$" in your opener should just be PA. $\endgroup$ – Noah Schweber Jan 15 at 21:46

The statement you want to prove is true, and your argument works - but there's a simpler one: drop all reference to the recursion theorem and Godelian incompleteness, and just change the second clause in your definition of $\varphi_e(n)$ to "$\sigma(n)\wedge\exists x(x\not=x)$." That is, introduce an inconsistency directly rather than playing with deeper facts about the theory and computability.

As you say, the only way $W_e$ can be consistent is if that second case doesn't occur, and if $\forall x\phi(x)$ is indeed true then that second case never occurs and $W_e$ "is" PA.

Given the directness of this construction, I suspect that there is no explicit reference.

| cite | improve this answer | |

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.