0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – OrdinaryHuman Feb 26 '17 at 23:56
  • $\begingroup$ $\pi_1(z)$ is a natural number. Think of $\pi$ as a function with one parameter that is a pair of natural numbers. $\endgroup$ – Rob Arthan Feb 27 '17 at 0:09
  • $\begingroup$ 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? $\endgroup$ – OrdinaryHuman Feb 27 '17 at 0:14
  • $\begingroup$ No: you have to work out what the function $\pi_1$ and $\pi_2$ are and then show that they are both computable. $\endgroup$ – Rob Arthan Feb 27 '17 at 0:28
  • $\begingroup$ 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. $\endgroup$ – OrdinaryHuman Feb 27 '17 at 0:33
0
$\begingroup$

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}) $.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.