Matematisk Lingvistik VT96:12

Class:   12
Date:    960215
Topic:   Exercise class 4

Exercise class 4

These exercises are supposed to be handed in on Monday February 19.

1. Proof that the set of natural numbers that are dividable by 3 { 3 , 6 , 9 , 12 , 15 , ... } is countably infinite.

2. Proof that the set of powers of two { 1 , 2 , 4 , 8 , 16 , 32 , ... } is countably infinite.

3. Proof that a set containing 100 elements is not infinite. Hint: use definition 4.1, page 57.

4. A hotel has a countably infinite number of single rooms with the numbers 1 , 2 , 3 , 4 , ... At one day when all rooms are occupied a bus with a countably infinite number of tourists arrives followed by another bus with a countably infinite number of STP students. Will the hotel owner manage to give all these people a room in her hotel? If so, how will she manage?

5. The same hotel as in the previous exercise is again completely full when at some day 99% of the guests decides to leave. Only the rooms 1 , 101 , 201 , 301 , ... are occupied. The hotel owner decides to make the guests move to different rooms to make room cleaning more efficient. Everyone will move from his current room X to the room with number ( ( X - 1 ) / 100 ) + 1 . How many rooms will be empty after everyone has moved?

6. The set of binary numbers { 0 , 1 , 10 , 11 , 100 , ...} is countably infinite. This means that we cannot use the diagonal method for proving that the set is uncountable. If we try it anyway, what will go wrong?

7. A little boy gets a countably inifinite number of different Lego bricks for his brithday. Each day he makes a different selection of the bricks and uses this selection for building some nice structure. Is the number of days that he can be occupied with this countably infinite? Motivate your answer.

The exercises 1, 2 and 7 are worth two points. The other exercises are worth 1 point.