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)