TL203F Algorithms, Logic and Complexity

Homework 2

In the first week we covered sets, functions, and enumerable sets from Chapter 1. In the coming week we will finish up enumerable sets and then see how we use diagonalization to prove that some sets are nonenumerable (from Chapter 2).


  1. Most sets do not include themselves, e.g. the set of students in a course does not include itself as an element. However the set of all sets must include itself (otherwise it wouldn't include all sets). So let us define R to be the set that contains all sets that do not contain themselves. Now the question is: Does R include itself? Discuss this question and what effect it has had.

  2. Problem 1.6 on page 15 in the textbook.

  3. Show that the set Z2 = { (m, n) | m, nZ } is enumerable, where Z is the set of integers (positive and negative).

  4. The textbook discusses coding sequences using prime decomposition on page 13.
    1. What is the code number for the sequence (6, 0, 3, 1, 4)?
    2. Which sequence has the code number 1832787?
    (There are several free ways to do calculations with large integers, e.g. WolframAlpha, Sage Notebook, and SymPy Live)

  5. Let S be the set of all possible programs in Python. Show that S is enumerable.

Hand this homework in before 12:00 on friday January 17th.

hh (hja), January 10th, 2014.