What is the significance of the primes in Gödel's incompleteness theorem?

Question

I'm probably way out over my skis here but I'm trying to understand (what I assume is already an extremely dumbed down) explanation of Gödel's incompleteness theorem that I saw in this Veritasium video.

He describes the way in which Gödel encodes expressions as a Gödel number. The example given in the video, $0 = 0$ is encoded like so: $2^6\times 3^5\times 5^6$ because the Gödel number for $0$ is $6$ and for $=$ it's $5$.

My question is why can't the Gödel number for $0 = 0$ just be $656$? Why does he introduce raising each prime by the symbol's Gödel number?

Answer 1

Let me start by pointing out that there are many ways of coding strings into numbers. You're reading this on a computer, and ASCII codes are a very good example of how a string can be coded into a number.

The thing is that you need to be able to decode your string in a unique way. In the case of ASCII we break it into 8bit chunks, which is very easy if you think of the number in binary, and each chunk codes a symbol.

Now, if you only have 10 symbols in your language, then you can very easily think of concatenation as your encoding, that would work out fine. And in principle one can in fact do that if one chooses the "correct formal framework" so that it has only 10 symbols (or even less!).

But if you have more than that, you will run into a problem. In the course I used to teach with Itay Kaplan that was focused in part on the incompleteness theorem we used the coding that reduces the formal language to 13 symbols, and then looks at a string as a single number in base 13.

On the other hand, using prime decomposition is independent of a basis, which conceptually is clearer (and yet more complicated) since it doesn't require you to keep track of what base you're writing your number in.

Answer 2

First of all, I believe the Gödel number for $0=0$ would be $2^6 * 3^6 * 5^6$. Secondly, what we want is that each statement has a unique integer representing it right? Now your method assumes that there are at most 10 different symbols, which makes it not very useful for generalizing (just look at all the symbols there are in the video, its more than 10 already). The reason primes are used, is so that you can work backward from any integer and decode from it exactly what the symbols in the original statement would be, since any integer has a unique prime factorization.