Gödel numbering for sequences Using the Chinese remainder theorem

Question

I looked into some YouTube videos and got a simple idea about Gödel numbering and Chinese remainder theorem separately... But can't see how to use them as one. Wikipedia giving a way or may be it's an explanation... any way I didn't get what's it's saying.

If anybody can give a brief explanation about Gödel numbering and Chinese remainder theorem and how to use them together, it would be really helpful.

Cheers!!!

Answer 1

I think you're confusing two different methods for representing a finite sequence of natural numbers, which are often explained together because both originated in Gödel's 1931 paper that proved the Incompleteness Theorem:

Gödel numbering represents a sequence $(a_1,a_2,a_n,\ldots,a_n)$ by the single number $$ 2^{a_1}\cdot 3^{a_2}\cdot 5^{a_3}\cdot 7^{a_4} \cdots p_n^{a_n} $$ Gödel's β trick represents the sequence using two numbers $k$ and $m$, such that $$ a_n = k \bmod (m\cdot n+1) $$ The Chinese Remainder Theorem is used to prove that every finite sequence can be represented in this way, if we can find a sufficiently long arithmetic sequence of sufficiently large coprime integers. (Which we can, for example by choosing $m$ as the factorial of the maximum of the largest element and the number of elements of the sequence).

The reason to have two methods of achieving apparently the same result is that they have different advantages that are neccessary for different purposes.

• Gödel numbers represent a sequence by a single number, which is technically convenient.
• Gödel numbers are unique, that is, every sequence has just one Gödel number. So you can check whether two sequences are the same simply by comparing their Gödel numbers.
• Gödel numbers are somewhat involved to construct and take apart, but not more involved than what can be done with primitive recursive functions.
• On the other hand, a sequence encoded by the β trick is extremely easy to decode, with much simpler tools than primitive recursion. It is therefore useful when we're trying to show what can be done using those simpler tools.

It is not particularly simple to encode a given sequence with the β trick, but as it turns out, we do not actually need to do that -- the trick is almost exclusively used in a context where what we want to show is that the claim "there exists a sequence such that etc etc etc" can be expressed in a particular formal system -- and so all we need is to quantify simultaneously over all $k$ and $m$.