Theory of Computation

2.12  ADDITIONAL EXERCISES

1. 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.
2. Modify the pairing function of Grzegorczyk (1953) (2.1.4.5) to make it onto.
3. Give a direct proof that the J in 2.1.4.6 is 1-1.
4. Give a direct proof that the J in 2.1.4.8 is 1-1.
5. Show that J given by

   

   is an onto pairing function in . Show that its projections are in .

   Hint. View ² is the union of all the finite groups of pairs, for i = 0, 1, 2, . . . ,

   G_i = {〈x, y〉 ∈ ² : x + y = i}

   Now enumerate ² 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?). ...