Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Hints for the exercises on functions
Computer Laboratory > Course material > Discrete Mathematics > Hints for the exercises on functions

Please do try the questions by yourself before resorting to these hints!

  1. 22 = 4, 23 = 8, 32 = 9 and 33 = 27.
  2. [X] ↔ X∩B. [X] = [Y] ⇔ X∩B = Y∩B.
  3. Bijective.
  4. (a, (b,c)) ↔ ((a,b), c).
    Requires |A| = 0, 1 or ∞ (but don't even think of writing infinity like this!).
    Requires |A| = 0, 2 or ∞.
    Currying.
    |C| = 1 or |B||A| = |B|.|A|.
    (f: A+B→C) ↔ (λa.f(0,a), λb.f(1,b)).
  5. Suppose that g exists with the given property. a1 R a2 ⇒ [a1] = [a2] ⇒ p(a1) = p(a2) ⇒ g(p(a1)) = g(p(a2)) ⇒ q(f(a1)) = q(f(a2)) ⇒ [f(a1)] = [f(a2)] ⇒ f(a1) S f(a2).
    Define g([a]) = q(f(a)). Check that it is well defined and satisfies p ο g = f ο q.
  6. Consider Hasse diagrams.
  7. (|B|+1)|A|.
  8. Countable union of countable sets.
  9. f ↔ {n | f(n) = 1}.
  10. Countably infinite, uncountable, finite (=2), uncountable, countable.
  11. The interior of each disc contains a point with rational coordinates.
    Circles can be nested arbitrarily.