[FOM] Question on Incompleteness Theorems

[Mitchell Spector]

On May 30, 2004, at 5:20 PM, Dmytro Taranovsky wrote:
> Is there an arithmetical formula phi with one free variable such that
> for every Pi-0-1 formula psi with one free variable it is consistent
> with Peano Arithmetic that
> Forall n (phi(n) <--> psi(n)).
> Can phi be a Pi-0-1 formula?
>
> My motivation for this question is (in part) finding the strongest
> possible forms of the incompleteness results.
>
> Dmytro Taranovsky


I believe this (the strong version with phi being Pi-0-1)
can be proven by an application of the recursion theorem,
along the following lines:

Let W(x) for x = 0, 1, 2, ... be a standard enumeration
of the recursively enumerable sets.

We claim that there exists e such that for all n,
Con(PA + W(e) = W(n)).

If not, then for each e, there exists an n such that
PA proves "W(e) does not equal W(n)". In fact, such
an n can be found from e effectively.  Let f be a
recursive function such that, for every e, if n
denotes the numeral f(e), PA proves the statement
"W(e) does not equal W(n)".

By the recursion theorem, there exists e such that
W(e) = W(f(e)).  Letting n be the numeral denoting
f(e), we have that PA proves "W(e) does not equal W(n)".
But this is a contradiction, since the standard model
of arithmetic satisfies "W(e) = W(n)".

Now, to answer your question, let phi(x) be the Pi-0-1
formula "x does not belong to W(e)".  The correspondence
between Sigma-0-1 formulas and r.e. sets yields the desired
result.

Mitchell Spector