How can the Gödel sentence be Pi_1

Question

The Gödel sentence must be provable or unprovable by itself - you have to resolve all definitions until it only uses the elementary symbols of Peano arithmetic. What is the correct way to resolve definitions of primitive recursive functions so that the Gödel sentence stays Π₁?

According to http://www.staff.science.uu.nl/~ooste110/syllabi/peanomoeder.pdf page 10, the formula that corresponds to a primitive recursive function with f(0)=c and f(x+1)=g(f(x),x) is something like this:

∃am( rm(a,m*(0+1)+1)=c ∧ ∀i<x( g(f(i),i)=rm(a,m*(i+1+1)+1) ) ∧ rm(a,m*(x+1)+1)=u )

Informally: There exists a,m such that the remainder of a divided by m*(i+1)+1 is f(i) for all i <= x (the sequence of values of the function up to f(x) is coded into a,m).

The value of f(x) is in free variable u. Resolving the remainder function rm(a,b) needs additional existential quantifiers.

The formula above is a Σ₁ formula. Adding a generalization (like in the Gödel sentence) makes it Π₂. But the Gödel sentence is said to be Π₁.

So is the formula above the wrong way to resolve definitions in the Gödel sentence or are the unbounded existential quantifiers no problem for some other reason? The paper linked above seems to suggest the latter on page 15/16.

Answer 1

The standard Gödel construction makes the Gödel sentence have the form $\forall x\neg Gdl(x)$ where $Gdl$ is a $\Sigma_1$ wff expressing a certain primitive recursive property. Note the negation sign! It is crucial. The negation of a $\Sigma_1$ wff is $\Pi$, and the universal quantification of such a wff is still $\Pi_1$. So the Gödel sentence is indeed $\Pi_1$.

Adding a generalization (like in the Gödel sentence) makes it $\Pi_2$.

Look carefully and you'll see that there is a crucial negation sign! The Gödel sentence says that every number is such that it isn't the number of the proof of such-and-such. [E.g. Check out the details in my Gödel book.]

Answer 2

There are two ways to say that the value of a primitive recursive function $f$ on input $n$ is $k$:

• One can say that there exists a sequence $a_0, \ldots, a_n$ satisfying these three conditions:

  1. $a_0 = f(0)$,

  2. for all $i < n$, $a_{i+1}$ is computed from $a_i$ using the primitive recursive definition of $f$, and

  3. $a_n = k$.

• Alternatively, $f(n)= k$ if and only if, for every sequence $a_0, \ldots, a_n$ satisfying (1) and (2) above, $a_n = k$. This is because, for every primitive recursive function $f$ and every $n$, there is exactly one sequence satisfying (1) and (2).

The first bullet will give you a $\Sigma^0_1$ definition, the second bullet will give you a $\Pi^0_1$ definition. More generally, every computable function (not just every primitive recursive function) is definable both by a $\Sigma^0_1$ formula and by a $\Pi^0_1$ formula, using much the same method.