Discrete Mathematics - Mathematics 140 - Fall 2005

Notation: N denotes the set of all natural numbers, Z the set of all integers, R the set of all real numbers.

Definition: Let A and B be sets. If there exists a one-to-one function f : A --> B, then we write |A|  £  |B|.

1. Prove that |N| £  |R|.
2. 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 one-to-one map from A to C. Hint: use the fact that the composition of two injections is an injection.
3. Give an example of infinite sets A and B such that A is a proper subset of B and |A| ¹ |B|. Just answer, without proof.
4. Give an example of infinite sets A and B such that A is a proper subset of B and |A| = |B|. Just answer, without proof.
5. Use a diagonalization argument to prove that [1,3] is not denumerable.
6. Construct a bijection from [1,3] to [7,12].
7.  
   1. Prove that if |A| = |B| and A is not denumerable, then B is not denumerable. 
   2. Use part (a) and the above two problems to prove that [7,12] is not denumerable; do not use a diagonalization argument. 
8. Determine whether each of the following is true or false. Just answer, without explanation. (This problem is to help you develop your intuition about countable/uncountable sets.)
   1. Every subset of R is uncountable.
   2. [0, 0.0000000001] is uncountable.
   3. Every subset of N is denumerable.
   4. Every subset of N is countable.
   5. Every set that has an uncountable subset is uncountable.
   6. Every set that has a denumerable subset is denumerable.
   7. The union of any two denumerable sets is denumerable.
   8. The union of any twenty denumerable sets is denumerable.
   9. The union of denumerably many denumerable sets is denumerable.
   10. The union of any set with an uncountable set is uncountable.
   11. The union of infinitely many finite sets is countable.
   12. The union of infinitely many finite sets is uncountable.