CSPP 512 Mathematics for Computer Science - Summer 2001

Homework 4 (assigned July 9, due July 18)

This homework assignment covers the material in sections 1.6, 2.1, and 2.4 of the textbook.

1. Do problems 17, 19, 20, 22, and 26 on page 47. (Each problem is worth 5 points.)

2. Do problems 2, 6, 8, 12, 14, 18, 19, 32, 36, and 37 on pages 62-63. (Each problem is worth 2 points.)

3. Do problems 58, 59, 61, 64, 67, 68, 72, and 73 on page 63. (Each problem is worth 2 points.)

4. Do problem 83 on page 63. (5 points)

5. Do problems 19, 20, 21, 22, 23, 24, and 26 on page 83. (Each problem is worth 2 points.)

1. Do problem 47 on page 48. (5 points)

2. Do problem 49 on page 49. (5 points)

3. An ancient Sicilian legend says that a barber in a remote village who can only be reached by traveling a dangerous mountain road shaves those people, and only those people, who do not shave themselves. Can there be such a barber? (2 points)

4. (Russell's paradox)
   Let S be the set that contains a set X if X does not belong to itself, so that
   S = {X | X is not in X}.
   (a) Show that the assumption that S is a member of S leads to a contradiction. (2 points)
   (b) Show that the assumption that S is not a member of S leads to a contradiction. (2 points)