18.099: Problem Set 3 Due: Tuesday, September 23.

Two sets A and B are said to have the same cardinality if there exists a bijection between them.

1. Do the sets [0, 1] and (0, 1] have the same cardinality?

2. Suppose that B ⊂ A and that there exists an injective map f: A → B. Show that A and B have the same cardinality. (Hint: First, define a sequence of subsets

A_{1} ⊃ B_{1} ⊃ A_{2} ⊂ B_{2} ⊃ A_{3} ⊃ B_{3} ⊃ …

as follows. Let A_{1} = A, B_{1} = B, and for n > 1, let A_{n} = f(A_{n−1}) and B_{n} = f(B_{n−1}). Then, show that the map h: A → B given by

h(x) = \begin{cases}f(x) & if x ∈ A_{n} ∖ B_{n} for some n, \\ x & otherwise, \end{cases}

is bijective.)

3. Prove the following theorem. Theorem (Schroeder-Bernstein). Let A and B be two sets and suppose that there exists injective maps f: A → B and g: B → A. Then A and B have the same cardinality.