Refer to Definitions 1.1(abc) on page 72 for these problems. In part (c) of the definition, X is not necessarily a finite set.
Is the set of natural numbers between 0 and 100 countable?
Is the set of all natural numbers countable?
What is the difference between "countable" and "denumerable"?
What is the difference between "denumerable" and "effectively denumerable"?
Is each of the following true or false? Explain your reasoning.
Every "enumerable" set is effectively denumerable.
Every denumerable set is enumerable.
Every enumerable set is denumerable.
Explain in your own words the Note on top of page 73 and the footnote at the bottom of the same page. In your explanation include answers to the following questions: Why does the book use "the informal notion of effectively computable" ? Why shouldn't we instead require that f and f^(-1) be URM-computable?
(Optional) Can you guess why in Theorem 1.4 the book uses the letter gamma for the bijection from the set of all programs to N? Hint: Read the paragraph after the proof of Theorem 1.4. If that hint didn't help, here's another one: read footnote 2 at the bottom of the same page.
State whether or not (you think) each of the following functions is computable. We have not yet proved any functions to be non-computable. We will do so later. For this problem, if you believe a function is not computable, explain informally why you believe so; but no proof is necessary. If you think a function is computable, give a "proof" by Church's Thesis.
f(x) = 1 if x is in Dom(g), 0 otherwise, where g(x) is a computable function.
f(x) = 1 if px (the xth prime) is in Dom(g), undefined otherwise, where g(x) is a computable function.
f(x) = 1 if px (the xth prime) is not in Dom(g), undefined otherwise, where g(x) is a computable function.
f(x) = 1 if Dom(g) is nonempty, undefined otherwise, where g is a computable unary function.