Discrete Mathematics - Mathematics 140 - Fall 2005

Notation: N denotes the set of all natural numbers, Z the set of all integers. U denotes union.

Definition: A set S is finite if for some natural number n there exists a bijection from S to the set {1, 2, ..., n}.

1. Show that if A, B, C are sets such that |A| = |B| and |B| = |C|, then |A| = |C|. (This is not as silly as it seems! You have to construct a bijection from A to C. Hint: use the fact that the composition of two bijections is a bijection.
2. Show that the set of all multiples of 7 is a denumerable set. Show that the map you construct is indeed a bijection. Hint: show the set in question has the same cardinality as Z, and then use the problem above, together with the theorem we proved in class, which said that Z is denumerable.
3. Show that if f: N --> S is a bijection, and x is an element of S, then there exists a bijection g: N --> S-{x}. Just construct the desired bijection; no need to prove that it is 1-1 and onto.
4. Show that if S and T are disjoint denumerable sets, then S U T is denumerable. Just construct the desired bijection; no need to prove that it is 1-1 and onto.
5. Show that if S and T are disjoint finite sets, then S U T is finite. Just construct the desired bijection; no need to prove that it is 1-1 and onto.
6. Show that if S and T are disjoint sets, S is finite, and T is denumerable, then S U T is denumerable. Just construct the desired bijection; no need to prove that it is 1-1 and onto.
7. Show that if S and T are disjoint countable sets, then S U T is countable. Hint: Use the problems above.