I am trying to implement the Gödel numbering scheme in Nagel and Newman [1]. It uses first an encoding of the alphabet which we can use to give Gödel numbers to formulas and then an encoding of sequences of such formulas. They claim that given a Gödel number we can retrieve the original formula or sequence of formulas. They note that if the factorization of the Gödel number is the product of successive primes then it can be either a formula or a sequence of formulas. On page 79 they say "In this case the expression to which it corresponds can be exactly determined". I would like to know how this can be done. If I am not mistaken I find exactly the same Gödel number for two different expressions:
Take the formula $\vee \vee$ and the sequence of formulas $\sim : \sim$ (I use a colon to separate the formulas in a sequence since this symbol isn't present in their alphabet, write such sequences on top of each other.).
The encoding of a formula $f$ uses a previously fixed assignment of numbers $n(f_i)$ to the symbols $f_i$ and then takes the product of the $i$th prime to the power of the number $n(i)$ assigned to the $i$th symbol.
$$\phi(f):=\prod_{i =1}^{\text{Length}(f)} p_i^{n(f_i)}.$$
Similarly, for a sequence $s$ of formulas they take the Gödel number $\phi(s_i)$ of each formula and then form the product of the $i$th prime to the power of the Gödel number $\phi(s_i)$ of the $i$th formula:
$$\phi(s):=\prod_{i = 1}^{\text{Length}(f)} p_i^{\phi(s_i)}.$$
Note that $n(\vee)=2$ and $n(\sim)=1$. This is enough to see that
$$\phi(\vee \vee)=2^2 \times 3^2=36$$
and
$$\phi(\sim : \sim)=2^{(2^1)} \times 3^{(2^1)}=36.$$
These are somehow trivial examples and maybe they violate the rules for what constitutes a formula, but can I really be sure that this encoding scheme doesn't have collisions for non-trivial cases? Did I miss something that solves this problem? If not, is there a better encoding scheme? I have had a look and somehow the sequence of formula encoding is usually only mentioned as a side note if at all.
[1] Nagel, Ernest, and James R. Newman. "Gödel’s Proof, ed. Douglas R. Hofstadter, rev. ed." (2001).
Best Answer
In Goedel's original paper, all the single symbols of the formal alphabet were encoded as distinct odd numbers. Since every encoded alphabet sequence begins with a positive power of two, i.e is an even number, for any number which encodes anything at all, if its exponent for two is odd it must encode a formula, whereas if its exponent of two is even the number must encode a sequence of formulae.
Note that Nagel and Newman's encoding causes problems by encoding $\vee$ as 2.