Skip to main content
added 135 characters in body
Source Link
Ruizhi Yang
  • 779
  • 3
  • 12

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{$\Sigma_e$ is consistent}\vdash\forall x\phi(x)$$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?

*Please*$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.

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{$\Sigma_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?

*Please forgive my abusing of notation.

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.

Source Link
Ruizhi Yang
  • 779
  • 3
  • 12

Is every true $\Pi^0_1$ statement entailed from a consistency statement of $PA$?

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{$\Sigma_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?

*Please forgive my abusing of notation.