PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (34)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
pairing function (Definition)

A pairing function is a function $ P \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$ which establishes a one-to-one correspondence between $ \mathbb{Z}_+^2$ and $ \mathbb{Z}_+$. Such functions are useful in the theory of recursive functions because they allow one to express recursive functions of $ m$ variables in terms of recursive functions of $ n$ variables with $ m \ne n$.

Two examples of pairing functions are the following;

$\displaystyle P_1 (x,y) = (x+y)(x+y+1)/2 + y$
$\displaystyle P_2 (x,y) = 2^x (2y + 1) - 1$

It is not hard to see that these functions are recursive. For instance, one could use the recursion relations and initial conditions

$\displaystyle P_1 (x+1,y) = P_1(x,y) + x + y + 1$
$\displaystyle P_1 (0,y) = T(y) + y$
$\displaystyle T(y+1) = T(y) + y + 1$
$\displaystyle T(0) = 0$
where $ T(n)$ is the $ n$-th triangular number to show that $ P_1$ is recursive. Likewise, one could use the recursions
$\displaystyle P_2 (x+1,y) = P_2 (x,y) + P_2 (x,y)$
$\displaystyle P_2 (0,y) = y + y$
to show that $ P_2$ is recursive.

An easy way to see that $ P_1$ effects a one-to-one correspondence between $ \mathbb{Z}_+^2$ and $ \mathbb{Z}_+$ is as follows: Define the “successor” of a pair $ (x,y) \in \mathbb{Z}_+^2$ to be the pair $ (x-1,y+1)$ when $ x=0$; otherwise, when $ x=0$, the successor is $ (y+1,0)$. It is easy to see that every pair has a successor and that every pair except $ (0,0)$ 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 $ P_1$ it follows that, if $ (x',y')$ is the successor of $ (x,y)$, then $ P_1 (x',y') = P(x,y) + 1$ and that $ P_1(0,0) = 0$. This means that $ P_1$ is the isomorphism described two sentences ago.

That $ P_2$ effects a one-to-one correspondence between positive integers and pairs of positive integers follows readily from uniqueness of factorization of integers. On the one hand, for any number $ z$, one can find numbers $ x$ and $ y$ such that $ z = P_2 (x,y)$ by factoring $ z+1$ and letting $ x$ be the power of $ 2$ which apears in the factorization. On the other hand, this is the only solution of $ z = P_2 (x,y)$ because prime factorization is unique.

Since a pairing function $ P$ sets up a 1-1 correspondence between $ \mathbb{Z}_+$ and $ \mathbb{Z}_+^n$, there exist uniquely defined unpairing functions $ R$ and $ L$ such that

$\displaystyle P(L(x),R(x)) = x$
It is not hard to show that, if $ P$ is recursive, $ R$ and $ L$ will also be recursive.

Once one has a pairing function $ P^{(2)}$, one can use it to set up 1-1 corespondences between $ \mathbb{Z}_+$ and $ \mathbb{Z}_+^n$ for any $ n$. For instance, one could define

$\displaystyle P^{(3)} (x,y,z) = P^{(2)} (x, P^{(2)}(y,z))$
$\displaystyle P^{(4)} (x,y,z,w) = P^{(2)} (x, P^{(3)}(y,z,w)) P^{(2)} (x,(y, P^{(2)}(z,w)))$
In general,
$\displaystyle P^{(n+1)} (x_1, \ldots, x_{n+1}) = P^({2}) (x_1, P^{(n)} (x_2, \ldots, x_n)$
(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 1-1 correspondence between recursive functions of $ n$ variables and recursive functions of a single variable. If we have a function $ F \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$, we can associate to it the function $ G \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ by the formula

$\displaystyle F(x_1, \ldots, x_n) = G( P^{(n)} (x_1, \ldots, x_n))$



"pairing function" is owned by rspuzio.
(view preamble)

View style:

See Also: example of bijection
Log in to rate this entry.
(view current ratings)

Cross-references: formula, associate, consequence, representation, translates, 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, one-to-one correspondence, function
There are 2 references to this entry.

This is version 12 of pairing function, born on 2004-09-04, modified 2006-12-24.
Object id is 6140, canonical name is ParingFunction.
Accessed 2344 times total.

Classification:
AMS MSC: 03D20 (Mathematical logic and foundations :: Computability and recursion theory :: Recursive functions and relations, subrecursive hierarchies)
Pending Errata and Addenda
None.
[ View all 4 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)