Math 101 Group Project #2 Cardinality

Let A and B denote sets. We say A and B have the same cardinality and write A ∼ B iff there is a bijection between A and B. We write A ⪯ B and say that A has smaller cardinality than B iff there is a one-to-one function from A to B. A set A is countable iff A ⪯ ℤ^{+}.

1. Let A and B be two disjoint countable sets. Show that their union A ∪ B is countable.

2. As sketched in class, show that the Cartesian product A×B of two countable sets A and B is countable. Give details of what this lets you conclude about the rationals.

3. As sketched in class, show that the open unit interval (0,1) is not countable. Discuss what cardinality you think the set of all colors of the spectrum has. How about the set of all the possible words you could make up to name colors using the English alphabet?

4. A real number a is called algebraic if there is a polynomial p(x) with rational coefficents such that p(a) = 0. Give some examples. Do there exist non-algebraic reals? Show that there are actually uncountably many. They are called transcendental numbers because, as Euler put it, “they transcend the power of algebraic methods.” Even though you can show in this way that there must be lots, it turns out to be quite a bit harder to produce any specific examples.

5. Cantor’s Theorem says that the power set ℘(A) of any set A satisfies A ≺ ℘(A), meaning that A ⪯ ℘(A) but A ≁ ℘(A). Give a proof of this by mimicking the proof we did in class that ℘(ℤ^{+}) is uncountable.

6. Let S be a collection of sets. Show that ∼ defines an equivalence relation on S. An equivalence class of sets under ∼ is sometimes called a cardinal. How many different cardinals do you think there are?

7. Let S be a collection of sets. Must ⪯ define a partial order on S? Explain.

8. The Shröder-Bernstein Theorem states that if A ⪯ B and B ⪯ A, then A ∼ B. Give a proof by filling in the details of the following sketch. Let f : A → B and g : B → A denote bijections. Call x ∈ A the parent of f(x) ∈ B and call y ∈ B the parent of g(y) ∈ B. Each x ∈ A has an infinite sequence of descendants, namely, f(x), g(f(x)), f(g(f(x))), etc. and similarly for y ∈ B. We say each tern in such a sequence is an ancestor of all the following terms. If you keep tracing back the ancestry of an element in either A or B back as far as possible, then there are only three possibilities: you come to an element of A with no parent (these orphans are exactly A − g(B)); or you come to an element of B with no parent; or the lineage goes back forever. Partition A and B accordingly and find three one-to-one functions that combine to give the desired one-to-one correspondence from A to B. Note: try drawing a figure to illustrate what is happening.

9. Show that ℝ has the same cardinality as ℘(ℤ^{+}), the power set of the positive integers. With Cantor’s Theorem in mind, we can think of this as saying that ℝ is bigger than ℤ^{+}. Is there anything in between? That is, does there exist a set X such that ℤ^{+} ⪯ X ⪯ ℝ with neither X ∼ ℤ^{+} nor X ∼ ℝ? In 1878, Cantor conjectured there is no such set X. Hilbert put this conjecture, called the continuum hypothesis, at the top of the famous list he made in 1900 of the most important unsolved problems for the new century. Based on Gödel’s work of 1939, Paul Cohen finally showed in 1963 that this question is formally undecidable. In other words, he proved that, with the axioms, proof techniques, and set theory accepted by most mathematicians, it is impossible to prove the continuum hypothesis and it is impossible to disprove the continuum hypothesis.

10. Make up questions that would be suitable for a hour exam in this course.