COMP 280 Assignment 6

The following problems total to 100 points.

1. (12 points — 3 points each part) Rosen 6th ed. 2.3 #16a-d

   Give an example of a function from ℕ to ℕ that is

   1. one-to-one but not onto.
   2. onto but not one-to-one.
   3. both onto and one-to-one (but different from the identity function).
   4. neither one-to-one nor onto.

2. (12 points — 3 points each part)

   Give an example of a function from ℕ to {true, false} that is

   1. one-to-one but not onto.
   2. onto but not one-to-one.
   3. both onto and one-to-one.
   4. neither one-to-one nor onto.

   If no such function exists, explain why.

3. (8 points) Rosen 6th ed. 2.3 #30

   If f and f∘g are one-to-one, does it follow that g is one-to-one? Justify your answer.

4. (5 points) Rosen 6th ed. 2.3 #36b

   Let f be a function from the set A to the set B. Let S and T be subsets of A. Show that f(S∩T) ⊆ f(S)∩f(T).

5. (5 points) Rosen 6th ed. 2.3 #40a

   Let f be a function from A to B. Let S and T be subsets of B. Show that f^-1(S∪T) = f^-1(S)∪f^-1(T).

6. (5 points)