Mathematical Prerequisites: Questions
  1. Indicate whether each of the following is true or false:
    1. Æ Í Æ
    2. Æ Î Æ
    3. Æ Î {Æ}
    4. Æ Í {Æ}
    5. {a,b} Î {a,b,c,{a,b}}
    6. {a,b} Í {a,b,{a,b}}
    7. {a,b} Í Ã ({a,b,{a,b}})
    8. {{a,b}} Í Ã ({a,b,{a,b}})
    9. {a,b,{a,b}} - {a,b} = {a,b}

  2. What are the elements of the following sets?
    1. ({1,3,5} Ç {3,1}) È {3,5,7}
    2. {3} Ç {3,5} Ç ({5,7} È {7,9})
    3. ({1,2,5} - {5,7,9}) Ç ({5,7,9} - {1,2,5})
    4. Ã ({7,8,9}) - Ã ({7,9})
    5. Ã (Æ)
    6. {1} ´ {1,2} ´ {1,2,3}
    7. Æ ´ {1,2}
    8. Ã ({1,2}) ´ {1,2}

  3. Let f: A ® B and g: B ® C. Let h: A ® C be their composition. In each of the following cases state necessary and sufficient conditions on f and g for h to be as specified:
    1. Surjective.
    2. Injective.
    3. Bijective.

  4. Prove that the following are countable:
    1. The union of any three countable sets, not necessarily infinite or disjoint.
    2. The set of all finite subsets of N (the natural numbers).

  5. Give bijections between each of the following pairs of sets (try to use simple functions involving operations such as addition and multiplication).
    1. N and the odd natural numbers.
    2. N and the set of all integers (Z).
    3. N and N ´ N ´ N.

  6. Let C be a set of sets defined as follows:
    1. Æ Î C
    2. If S1 Î C and S2 Î C then {S1,S2} Î C
    3. If S1 Î C and S2 Î C then S1 ´ S2 Î C
    1. Explain why {Æ,{Æ}} Î C.
    2. Does C contain any infinite sets? Explain.
    3. Is C countable or uncountable? Explain.

  7. Show by induction that:

    1 ´ 2 ´ 3 + 2 ´ 3 ´ 4 + ... + n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4

  8. Show by induction that n3+2n is divisible by 3 for all n>=0.

  9. Give examples to show that the intersection of two countably infinite sets can be either finite or countably infinite, and that the intersection of two uncountable sets can be finite, countably infinite, or uncountable.

  10. Show that the difference of an uncountable set and a countable set is uncountable.