Is there an effective way of deciding whether a given Godel numbers for a formula or a sequence of formulas??

Question

If we have a Godel number, how can we tell that this number for a formula or for a sequence of formulas effectively? If we have X is a Godel number of some formula, then we can consider this formula as a sequence of formulas which just containing itself and compute its corresponding Godel number which is 2^X which means that we have two Godel numbers for same formula. Any explanations please??

Answer 1

Your question seems to be: Given some natural number, how do we differentiate a Gödel number for a formula from a Gödel number for a sequence of formulas?

There are essentially two answers to this question depending on the Gödel numbering.

The first is that the Gödel numbering makes them unambiguous. For example, in Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I by Gödel, a formula is represented by a sequence of symbols. Each symbol is numbered with an odd number while sequences of numbers are encoded into the powers of prime numbers in order and thus every sequence of numbers is even. So if the power of $2$ is $0$, then we know we have a symbol, otherwise we know we have a sequence of numbers. A formula would be an even number whose prime powers are all odd. A sequence of formulas would be an even number whose prime powers are all even numbers whose prime powers are all odd. An even number whose prime powers are a mix of even and odd numbers doesn't correspond to a formula or a sequence of formulas (or a sequence of sequences of formulas etc.)

The second approach is if the Gödel numbering gives two different things the same number, or, more likely, you simply have multiple Gödel numberings for different kinds of things. In this case, context would be used to disambiguate just like how your computer will happily open an image file as a text file if you want. It just interprets the same sequence of bits a different way. If we know we are expecting a sequence of formulas, we interpret the number as a sequence of formulas even if it might possibly also be interpretable as a single formula.

Here's an example. Consider a simple propositional language talking about equality of natural numbers. We have a constant symbol $z$ and a unary function symbol $s$, a binary relation symbol $=$, and the logical connectives $\neg$ and $\land$. Define the Gödel numberings $G_f$ and $G_t$ in the following way:$$G_f(\varphi)=\begin{cases}3^{G_t(t_1)}5^{G_t(t_2)},&\varphi=(t_1=t_2)\\ 2^13^{G_f(\psi)},&\varphi=\neg\psi\\ 2^23^{G_f(\psi_1)}5^{G_f(\psi_2)},&\varphi=(\psi_1\land\psi_2)\end{cases}\qquad G_t(t)=\begin{cases}0,& t = z\\1+G_t(t'),& t=s(t')\end{cases}$$

We have $G_f(\varphi)=G_t(s^{G_f(\varphi)}(z))$ where $s^n(z)$ means $z$ if $n=0$ or $s(s^k(z))$ if $n=k+1$. Thus, for every formula there is a term that has the same Gödel numbering. This is not a problem though as long as we know to expect either a term or a formula. For example, given a Gödel numbering of a formula that is a multiple of $4$, we know that the exponents of $3$ and $5$ should be treated as formulas because we are considering the Gödel numbering of $\land$. It doesn't matter that they could also be interpreted as terms. We know we are expecting formulas.