Computers and Reality - Cognitive Science 110 - Spring 2007

1. Is each of the following true or false?
   1. Every denumerable set is infinite.
   2. Every denumerable set is countable.
   3. Every countable set is infinite.
   4. Every countable set is denumerable.
   5. Every infinite set is denumerable.
   6. Every uncountable set is infinite.
   7. Every infinite countable set is denumerable.
2.  
   1. Give an example of a set that is both countable and denumerable.
   2. Give an example of a set that is countable but not denumerable.
3. Prove that the set of all integers has the same size as the set of all even numbers; do this by giving a bijection from one set to the other.

   
   The goal of the following problems is to get you comfortable with Cantor's diagonalization method, used here to show that there are uncountably many functions.
    

4. Let f and g be functions from N to N. The following questions (in parts a, b, c) are independent of each other.
   1. Suppose we are told that f(5) = 8 and g(100) = 3. Is this enough information to determine whether or not f and g are the same function? (To be the "same function" means: for every input x, f(x) = g(x).)
   2. Suppose we are told that f(5) = 8 and g(5) = 8. Is this enough information to determine whether or not f and g are the same function?
   3. Suppose we are told that f(5) = 8 and g(5) = 3. Is this enough information to determine whether or not f and g are the same function?
5.  Let f₀, f₁, f₂, and g be functions from N to N such that:
    f₀(x) = x^2  ;  f₁(x) = x+1  ;  f₂(x) = 3x  ;  and
    g(0) = 1, g(1) = 3, and g(2) = 4. Is g different from all three functions f₀, f₁, and f₂ ? Explain why or why not.
6. Let f₀, f₁, f₂, f₃, ...  be  functions from N to N. Let g(x) =  f_x(x) + 1.  (For example, g(0) =  f₀(0) + 1, g(18) =  f₁₈(18) + 1.)
   1. Is there enough information to decide whether g(5) is larger or f₅(5) is larger or they are equal?
   2. Is there enough information to decide whether or not g(100) = f₅(100)?
   3. Prove that g and f₅ are different functions.
   4. Show that for every n, g and f_n are different functions (i.e., show g is different from all functions f₀, f₁, f₂, f₃, ... ).
7. Let F be the set of all functions from N to N. Prove that F is uncountable. Hint: Use the previous problem.