Gödel produces a sentence G that is undecidable in PA.
But the statement itself is not uniquely determined. It is generated using some encoding of the metalanguage, referred to as Godel Numbering. Godel's encoding scheme makes use of the coefficients in the prime factorization of a (very large) number. Symbols of PA are given unique prime number codes as shown here:
Godel Numbering
A simple way to make an additional set of encodings is to shift the prime numbers associated with each symbol by one prime. So the symbols '0' can by assigned a 3 instead of a 1, and 's' can be assigned a 5 instead of a 3, and so on…
Each shifted encoding scheme will correspond to a different Godel sentence. Let $G_0$ denote the sentence associated with Godel's original scheme, and $G_n$ be the Godel Sentence associated with the encoding scheme where the symbol codes are shifted by $n$ primes.
My question is about the relationship between different Godel Sentences. In particular, are the various Godel Sentences all provable from one another? More formally, for all $m$ and $n$ is the following statement true?
$$PA \cup \{G_m\} \vdash G_n$$
To be clear, $PA \cup \{G_m\}$ is meant to be the axioms of $PA$ with $G_m$, and $G_n$ is a second Godel Sentence of $PA$, not $PA \cup \{G_m\}$.
In some sense, I expect all Godel Sentences to entail$(\models)$ each other in that they're all based on the same provability predicate. But it's not obvious to me that each one can be used to prove$(\vdash)$ the others within the system.
If the Godel Sentences can all be used to prove each other could you kindly provide a sketch of the proof of this result?
Update 5/2/2022:
There seems to be disagreement about the answer I accepted here, which uses reasoning based on properties of primitive recursive functions. So I though it might be worthwhile to ask the opposite question.
If my statement above about $PA \cup \{G_m\}$ is false, can someone please provide a proof sketch of this conjecture? For all $m$ and $n$
$$PA \vdash G_m \iff G_n$$
That is to say that even if $PA$ cannot prove either $G_m$ or $G_n$, it can express their interdependence.
Best Answer
First note that your alternative shifting numbering scheme is acceptable. For example, the number of a wff $P_1 \lor P_2$ ($2^{361}×3^{7}×5^{529}$) under your specific new numbering can be converted to $2^{289}×3^{9}×5^{361}$ under the original Gödel numbering, and any such conversion function must be p.r. too. In other words, you can program in advance to convert any given number under your numbering to Gödel number without open searches due to the fundamental theorem of arithmetic and your specific deterministic simple shifting scheme.
Any Gödel sentence (at least one such sentence exists per diagonal lemma) in PA has the following property: $G↔ \lnot Bew(\ulcorner G \urcorner)$ where $\ulcorner G \urcorner$ is the usual Gödel number of a Gödel sentence, $Bew(y)=∃x(y=\ulcorner \phi \urcorner \land x=\ulcorner \psi \urcorner)$, and $\psi$ is a proof of a sentence $\phi$, and the name $Bew$ is short for beweisbar, the German word for "provable" and was originally used by Gödel to denote the provability formula above (see reference). However, it's a well known result that the numerical provability property $Bew(y)$ is not p.r., otherwise any first order sentence $\phi$ whose Gödel number is $y$ can be p.r. decidable contradicting the first incompleteness theorem. Given $G_0$ is the Gödel sentence associated with Gödel's original scheme and suppose $G_1$ is a Gödel sentence associated with your alternative scheme, of course we have $PA \cup \{G_0\} \vdash G_0 \land Bew(\ulcorner G_0 \urcorner)$ trivially. Although we can always find a p.r. function $f$ converts $\ulcorner G_1 \urcorner$ under your shifting scheme to a number under original Gödel scheme, any recursively axiomatized theory containing PA cannot decide the truth value of the provability predicate $Bew(f(\ulcorner G_1 \urcorner))$ even after adjoining $G_0$ to PA since there's no known theorem to always ensure $f(\ulcorner G_1 \urcorner) = \ulcorner G_0 \urcorner$ and the numeral value of $f(\ulcorner G_1 \urcorner)$ can be arbitrary. So similarly under your description in general $PA \cup \{G_m\} \nvdash G_n$ (the augmented theory can not capture $G_n$).