3
$\begingroup$

It is clear that many different Gödel numberings can work in Gödel's proof. Yet for the proof one just needs a few properties of how the numberings of related sentences are related, and I'm wondering if those few properties are enough to force the numberings to be "essentially the same." This would be an analogue of Rogers's Equivalence Theorem for admissible numberings of the partial computable functions.

Is there some small set of natural axioms (I realize both "small" and "natural" here are informal) such that any numbering of statements of first-order arithmetic and lists thereof that satisfies those axioms is isomorphic (in some precise sense) to the "usual" Gödel numbering (or, let's say, to Gödel's version)?

Here both the axioms and the notion of isomorphism can be defined in the answer. For axioms, just to give an idea of the kind of thing I have in mind, I was hoping for something along the lines of "There are [easily computable? primitive recursive?] functions that do the following....project the numbering of a list to the numbering of its i-th element, take the numbering of a formala of the form $\exists x \varphi(x)$ to the numbering of $\varphi(x)$" etc.

Related but different questions:

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ We can whip up a theory $T$ describing numbers-sentences-formulas-etc. (think of it as a "theory of syntax") such that every "reasonable" Godel numbering scheme is essentially describing an interpretation $\Phi$ of $T$ into $\mathsf{PA}$ such that for every $\mathcal{M}\models\mathsf{PA}$ the interpreted structure $\Phi^\mathcal{M}$ uniquely embeds into any other model of $T$ definable in $\mathcal{M}$ (basically, $\Phi^\mathcal{M}$ is what $\mathcal{M}$ thinks is the minimal model of $T$). (Cont'd) $\endgroup$
    – Noah Schweber
    Commented Feb 6 at 3:31
  • 2
    $\begingroup$ In particular, if $\Phi,\Psi$ are the interpretations corresponding to two "reasonable" Godel numberings, there is a formula $\theta$ such that in every $\mathcal{M}\models\mathsf{PA}$ we have $\theta^\mathcal{M}:\Phi^\mathcal{M}\cong\Psi^\mathcal{M}$. Is this the sort of situation you're looking for? If so, I can expand this into an answer. $\endgroup$
    – Noah Schweber
    Commented Feb 6 at 3:32
  • $\begingroup$ @NoahSchweber: I admit I didn't quite follow all of that, but it sounds plausibly like what I was hoping for, so I would certainly appreciate reading more details about it! $\endgroup$
    – Joshua Grochow
    Commented Feb 6 at 5:13

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .