# Function subscript notation

I'm a little confused by the function subscripts Nigel Cutland uses in his 1980 book "Computability: An Introduction to Recursive Function Theory". In 4.16.2:

"Let $\pi(x, y) = 2^x(2y+1)-1$. Show that $\pi$ is a computable bijection from $\mathbb{N}^2$ to $\mathbb{N}$, and that the functions $\pi_1$, $\pi_2$ such that $\pi(\pi_1(z), \pi_2(z)) = z$ for all $z$ are computable."

Do $\pi_1$ and $\pi_2$ refer to $\pi(1,1)$ and $\pi(2,2)?$ I understand proving the bijection (the first part of the prompt) but the exact meaning of those subscripts is not clear to me.

It is a standard notation to take $\pi_1, \pi_2 : \Bbb{N}^2 \to \Bbb{N}$ to be the two projections defined by:

$$\pi_1(i, j) = i\\ \pi_2(i, j) = j.$$

The subscripts are just part of the names of the two functions $\pi_1$ and $\pi_2$ and you are being asked to show how the third function $\pi$ relates to those two functions.

• So if the subscripts refer to the parameters in those positions, what exactly is $\pi_1(z)$? If $\pi$ requires 2 parameters, how can the third function be composed of two previous iterations of the function that have only 1 parameter? – OrdinaryHuman Feb 26 '17 at 23:56
• $\pi_1(z)$ is a natural number. Think of $\pi$ as a function with one parameter that is a pair of natural numbers. – Rob Arthan Feb 27 '17 at 0:09
• Ah...I see. In other words, "Prove that $\pi(x,y)$ is computable when $x = \pi(a,b)$ and $y = \pi(c,d)$? I.e. the recursive version of the function is computable? – OrdinaryHuman Feb 27 '17 at 0:14
• No: you have to work out what the function $\pi_1$ and $\pi_2$ are and then show that they are both computable. – Rob Arthan Feb 27 '17 at 0:28
• Right, obviously, can't compute the composition until you have the inputs. I just want to be clear and understand that the $\pi_1$ and $\pi_2$ just refer to separate iterations of $\pi$, each of which can have any 2 whole number pairs as inputs. Thanks for your help. – OrdinaryHuman Feb 27 '17 at 0:33

Let $n\in \mathbb N$

Let $(x_n,y_n)=\pi^{-1}(n)$ so $\pi (x_n,y_n) =n$. If $\pi$ is a bijection then this is well defined.

Then define $\pi_1 (n)$ so that $\pi_1 (n)=x_n$.

And define $\pi_2 (n)$ so that $\pi_2 (n)=y_n$. If $\pi$ is a bijection, these are meaning well defined functions.

Perhaps another way of putting it is if $\phi_1 (x,y)= x$ and $\phi_2 (x,y)=y$ are the functions to take and ordered pair and return the individual components, then let $\pi_1 (n)=\phi_1 (\pi^{-1}(n))$ and $\pi_2 (n)=\phi_2 (\pi^{-1})$.