Let

N={0,1,2,dots}

and let

\\\\psi

be a function from

N\\\\times N

into

N

such that\

R1\\\\psi (a,0)=a+1\ R2\\\\psi (0,b+1)=\\\\psi (1,b)\ R3\\\\psi (a+1,b+1)=\\\\psi (\\\\psi (a,b+1),b)

\ (1) Find

\\\\psi (2,1)

.\ (2) Show that for all

a,binN,\\\\psi (a,b)

can be calculated in a finite number of steps using (R1),(R2), and (R3). (Hint: Use double induction. Let

S(b)

say: For all

ainN

,

\\\\psi (a,b)

can be calculated in a finite number of steps using (R1), (R2), and (R3). Prove

S(b)

by induction. In proving

S(b+1)

, let

T(a)

say:

\\\\psi (a,b+1)

can be calculated in a finite number of steps using (R1), (R2), and (R3). Prove

T(a)

by induction.)\ (3) Guess at, and then prove by induction, a formula for

\\\\psi (a,2)

.\ (4) Find

\\\\psi (5,4)

.

8. Let N={0,1,2,} and let be a function from NN into N such that R1(a,0)=a+1R2(0,b+1)=(1,b);R3(a+1,b+1)=((a,b+1),b). (1) Find (2,1). (2) Show that for all a,bN,(a,b) can be calculated in a finite number of steps using (R1), (R2), and (R3). (Hint: Use double induction. Let S(b) say: For all aN, (a,b) can be calculated in a finite number of steps using (R1), (R2), and (R3). Prove S(b) by induction. In proving S(b+1), let T(a) say: (a,b+1) can be calculated in a finite number of steps using (R1), (R2), and (R3). Prove T(a) by induction.) (3) Guess at, and then prove by induction, a formula for (a,2). (4) Find (5,4)