- Prove (without looking up Euclid’s proof) that there are infinitely many primes.
*Hint*. See Example 2.1.2.40 and Exercise 2.1.2.42. - Modify the pairing function of Grzegorczyk (1953) (2.1.4.5) to make it onto.
- Give a direct proof that the
*J*in 2.1.4.6 is 1-1. - Give a direct proof that the
*J*in 2.1.4.8 is 1-1. - Show that
*J*given byis an onto pairing function in . Show that its projections are in .

*Hint*. View^{2}is the union of all the finite groups of pairs, for*i*= 0, 1, 2, . . . ,*G*_{i}= {〈*x*,*y*〉 ∈^{2}:*x*+*y*=*i*}Now enumerate

^{2}by listing pairs 〈*x*,*y*〉, first, by ascending order (with respect to*i*) of their group-number*i*, and then, within each group*G*_{i}, listing them in ascending order of the*y*-component. Show that the position*n*= 0, 1, 2, . . . of 〈*x*,*y*〉 in this enumeration is precisely*J*(*x*,*y*), which settles onto-ness. Of course, projections*K*and*L*exist (why?). ...

Start Free Trial

No credit card required