Assignment 6. Infinite Sets

For submission

1. Consider the following sets:

A = {1, 2, 3, 1}
B = {1, 2, 3}
C = {3, 2, 1}
D = {1, 2, 3, 4, 1}

a. Which of these are the same sets?
b. Which is a subset of which?
c. Which is a proper subset of which?

2. Consider the following relations on sets:

a. The square function on natural numbers ℕ. f(x) = x². Is it a one-to-one function? Why?
b. The square function on integers ℤ. f(x) = x². Is it a one-to-one function? Why?
c. In ℤ, the square root of 4 is 2 and also -2. Is the square root a function? Why?

3. Show that the set of on natural numbers ℕ {1, 2, 3, ...} can be put in one-to-one correspondence with the set of the powers of ten {10, 100, 1000, 10000, ...}

4. a. Which is a set bigger than the natural numbers that cannot be put in one-to-one correspondence with it?

b. Consider the set of your answer to a. Is there a set bigger than it that cannot be put in one-to-one correspondence with it? Which is it?

For discussion

Not for submission

A. Can you show that all natural numbers {1, 2, 3, 4, 5, ...} can be placed in one-to-one correspondence with the set of all integers {... -2, -1, 0, 1, 2, 3, ...}?

B. Can you show that all positive rational numbers, {1, 1/2, 2, 1/3, 2/3, ...} can be placed in one-to-one correspondence with the set of all positive and negative rational numbers, {1, 1/2, 2, 1/3, 2/3, ... -1, -1/2, -2, -1/3, -2/3, ...}?

C. Can you show that the set of all pairs of natural numbers {<1,1>, <1,2>, <1,3>, ..., <2,1>, <2,2>, ...} can be placed in one-to-one correspondence with the natural numbers?

D. Can you show that the set of all finite subsets of natural numbers can be placed in one-to-one correspondence with the natural numbers?
(Hint: The prime numbers are 2, 3, 5, 7, ... and each composite number can be written uniquely as a product of prime numbers. e.g. 5,445,468 = 2² x 3⁴ x 7⁵.)

E. Can you show that the set of infinite subsets of the natural numbers can be placed in one-to-one correspondence with the natural numbers?
(Hint: diagonalization?)

F. Can you find variants of the Ross-Littlewood Urn Supertask that leaves the urn at the end of the supertask filled with infinitely many balls; or just filled with 10 balls.