Computers and Reality - Cognitive Science 110 - Spring 2007

In the following, Z represents the set of all integers, N the set of all natural numbers.

Review of terminology:
Injective function  =  1-1 function  (different inputs do not give the same output)
Surjective function  =  onto function  (f : A --> B; range(f) = all of B)
Bijection =  a function that's injective and surjective  =   a one-to-one correspondence

1. Let A = {23, 45, 56, 78, 95, 32}, B= {1, 2, 3, 4, 5, 6, 7, 8, 9}.
   Define f : A --> B by: f(x) = the rightmost digit of x (e.g., f(23) = 3).
   1. Is f injective? Explain.
   2. Is f surjective? Explain.
   3. Is f a bijection? Explain.
2.  
   1. Give an example of a function f and two finite sets S and T such that f : S --> T is 1-1 but not onto.
   2. Give an example of a function f and two finite sets S and T such that f : S --> T is onto but not 1-1.
3. Let f : Z --> N be given by f(x) = 3x+1. Is f 1-1, onto, both, or neither? Explain.
4. Let f : Z --> N be given by f(x) = x^2. Is f 1-1, onto, both, or neither? Explain.
5. Let f : Z --> N be given by f(x) = |x|. Is f 1-1, onto, both, or neither? Explain.

   Definition: We say two sets S and T have the same size if there exists a bijection from one to the other.
   

6.  
   1. Suppose S and T are finite sets, and suppose f : S --> T is a 1-1 function. How do S and T compare in size?
   2. Suppose S and T are finite sets, and suppose f : S --> T is an onto function. How do S and T compare in size?
7.  
   1. Suppose S and T are infinite sets, and suppose f : S --> T is 1-1 but not onto. Can S and T have the same size? If so, give an example; if not, explain your reasoning.
   2. Suppose S and T are infinite sets, and suppose f : S --> T is onto but not 1-1. Can S and T have the same size? If so, give an example; if not, explain your reasoning.