Let f(x) = x (the identity function), and g(x) = x+2. According to the way we numbered URM programs in class (rather than the book's numbering), does f have an index less than 20? How about g? Justify your answer. (See page 77 for the definition of index.)
We proved in an earlier homework (p. 45, Problem 1) that the inverse of every total, injective, unary, computable function is computable. Show, using Church's Thesis, that the hypothesis of "total" is not necessary; i.e., prove that the inverse of every injective, unary, computable function is computable. Where do you use the hypothesis of "injective"?
Show that if f : S --> S' is a bijection and S is denumerable, then S' is denumerable.
It can be shown that every infinite subset of N is denumerable. Assuming this, show that every infinite subset of a denumerable set is denumerable.