O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

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

    images

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

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

    Gi = {〈x, y〉 ∈ images2 : x + y = i}

    Now enumerate images2 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.

Start Free Trial

No credit card required