in his Incompleteness Theorem (refer to Gödel, Kurt and Meltzer, B. and Schlegel, Richard, 1964), Gödel introduced the method of assigning a code number or Gödel number to every formal (syntactical) object such as a formula, proof, and so on. we now present two ways to effectively code a sequence of -tuples of integers , define where is the th prime number. given we can effectively recover the prime power . this coding is injective but not surjective on .
we define the godel number of the sequence to be the number
thus, the godel number of the sequence is for each fixed , the function is clearly primitive recursive.
godel numbering satisfies the following uniqueness property:
if , then this result is an immediate consequence of the uniqueness of the factorization of integers into primes, sometimes referred to as the unique factorization theorem or the fundamental theorem of arithmetic. (for a proof, see any elementary number theory textbook.)
(taken from Martin Davis, Ron Sigal, Elaine J. Weyuker, 1994 chapter 3.8 pairing functions and godel numbers)