godel numbering
in his Incompleteness Theorem [cite:;refer to @godel_incompleteness_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 
.
[cite:;taken from @computability_soare_2016 godel numbering of finite objects]
-tuples of integers , definewhere is the th prime number. given we can effectively recover the prime power . this coding is injective but not surjective on .[cite:;taken from @computability_soare_2016 godel numbering of finite objects]
we define the godel number of the sequence 
to be the number
thus, the godel number of the sequence to be the number
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.)
[cite:;taken from @computability_davis_1994 theorem 8.2]
[cite:;taken from @computability_davis_1994 chapter 3.8 pairing functions and godel numbers], thenthis 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.)[cite:;taken from @computability_davis_1994 theorem 8.2]