190Assignment4
Assignment 4
1. Mindscape 20, §3.1 of text
Every student at a certain college is assigned to a dorm room. Does this imply that there is a one-to-one correspondence between dorm rooms and students? Explain your answer.
This does not imply that there is a one-to-one correspondence between dorm rooms and students. It could be the case that there are more rooms than students.
2. Mindscape 33, §3.2 of text
Suppose you have infinitely many large boxes (one for each natural number. In each box, you have infinitely many marbles (one for each natural number) – so the boxes are really big! Does the set of all marbles have the same cardinality as the set of natural numbers? Justify your answer.
The set of all marbles has the same cardinality as the number of marbles in this set. This is because each marble can have a unique associated number. Take the following example
... 9 8 7 12 4 3 6 11 1 2 5 10 ...
1, 2, 5 etc represent the first marble in the next box. 1 is the first marble in the first box, 4 is the second marble in the first box, 9 is the third in the first box and so on. As such any marble in any of the infinite set of boxes can have a unique natural number constructed for it.
3. Mindscape 14, §3.3 of text
Suppose you had infinitely many people, each one wearing a uniquely numbered button: 1,2,3,4,5,….(you can use the people in the Hotel Cardinality if you don’t know enough people yourself). You also have lots of 5 cent pieces (infinitely many, although you are not very rich, because you forgot to return the 5 cent pieces to the bank when the coins were withdrawn from circulation). Now you give each person 5 cents; then ask every person to flip his or her coin at the same time. Then ask them to shout out in order what they flipped (H for heads and T for tails). So you might hear HHTHHTTTHTTHTH… or you might hear THTTTHTHTHHHHTHTH…, and so forth. Consider the set of all possible outcomes of their flipping (all possible sequences of H’s and T’s). Does the set of possible outcomes have the same cardinality as the natural numbers? Justify your answer.
The set of all possible outcomes does have the same cardinality as the set of natural numbers. An easy way of seeing this relationship is thinking about the outcomes as binary numbers. The first possibility, where all flips were heads could correspond to 0. The second possiblity, where only the first person had a tails would correspond to one. HTHHHH... would correspond to 2, THTHHHH... would correspond to 3 and so on. Depending on the definition of natural numbers, 0 may not be included. In this case the natural numbers can just be shifted to correspond to the previous set of heads and tails.
4. Mindscape 7, §3.5 of text
Prove that a circle of radius 1cm has the same number of points as a square of side length 10cm. Stated precisely, prove that the cardinality of points on the circle is the same as the cardinality of points on the square. Describe a one-to-one correspondence between these two sets. You may find it helpful to draw a picture.
By circumscribing the square around the circle, it is easy to see a one-to-one correspondence. Taking the shared center of these two shapes and drawing a line to any point on the square, the line will pass through a corresponding unique point on the circle. The same is true for any point on the circle.
For Example.
__________/__ | ___ / | | / X | | / / \ | | | / | | | \ / | | \___/ | |_____________|