## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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 2 is the union of all the finite groups of pairs, for i = 0, 1, 2, . . . ,

Gi = {〈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 Gi, 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?). ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required