
pairing function

(Definition)


A pairing function is a function
which establishes a onetoone correspondence between
and
. Such functions are useful in the theory of recursive functions because they allow one to express recursive functions of variables in terms of recursive functions of variables with .
Two examples of pairing functions are the following;
It is not hard to see that these functions are recursive. For instance, one could use the recursion relations and initial conditions
where is the th triangular number to show that is recursive. Likewise, one could use the recursions
to show that is recursive.
An easy way to see that effects a onetoone correspondence between
and
is as follows: Define the “successor” of a pair
to be the pair when ; otherwise, when , the successor is . It is easy to see that every pair has a successor and that every pair except is the successor of exactly one other pair. With this definition of successor, the set of pairs of positive integers satisfies the Peano axioms and, hence, is isomorphic to the integers. From the definition of it follows that, if is the successor of , then
and that
. This means that is the isomorphism described two sentences ago.
That effects a onetoone correspondence between positive integers and pairs of positive integers follows readily from uniqueness of factorization of integers. On the one hand, for any number , one can find numbers and such that
by factoring and letting be the power of which apears in the factorization. On the other hand, this is the only solution of
because prime factorization is unique.
Since a pairing function sets up a 11 correspondence between
and
, there exist uniquely defined unpairing functions and such that
It is not hard to show that, if is recursive, and will also be recursive.
Once one has a pairing function , one can use it to set up 11 corespondences between
and
for any . For instance, one could define
In general,
(This manner of encoding a list one pair at a time will be familiar to anyone who has programmed a computer in LISP. In fact, LISP was designed to be serve as a mathematical definition of computability equivalent to Turing machines or recursive functions. A fun exercise is to write a compiler which translates LISP programs into recursive functions using the representation of lists by single integers defined above.)
An important consequence of the fact noted above is that there is a 11 correspondence between recursive functions of variables and recursive functions of a single variable. If we have a function
, we can associate to it the function
by the formula

"pairing function" is owned by rspuzio.


(view preamble)
See Also: example of bijection
Crossreferences: formula, associate, representation, Turing machines, prime factorization, solution, power, sentences, isomorphism, isomorphic, Peano axioms, satisfies, integers, positive, easy to see, successor, triangular number, initial conditions, relations, recursive, terms, variables, recursive functions, theory, onetoone, function
There is 1 reference to this entry.
This is version 12 of pairing function, born on 20040904, modified 20061224.
Object id is 6140, canonical name is ParingFunction.
Accessed 1565 times total.
Classification:
AMS MSC:  03D20 (Mathematical logic and foundations :: Computability and recursion theory :: Recursive functions and relations, subrecursive hierarchies) 



Pending Errata and Addenda







