PROBLEM SET #1 PART 3 OFFICIAL SOLUTIONS

INNA ZAKHAREVICH

3.1 Solution 1: We know that both A and B are denumerable. That means that there is some bijection f : A → N and some bijection g : B → N. Thus the function h : A × B → N × N defined by h((a, b)) = (f(a), g(b)) is a bijection. So it is enough to show that N × N is denumerable, since then there will be a bijection h′ : N × N → N, and h′ ∘ h will be a bijection from A × B to N.

N × N is the integer lattice with both coordinates nonnegative. Let A_{n} be the set of points (x, y) ∈ N × N such that x + y = n. Then the A_{n} partition N × N. In addition, each A_{n} is finite. Thus N × N = ∪_{i=0}^{∞}A_{n}, which is a denumerable union of finite sets, which is denumerable. Thus N × N is denumerable, so we are done.

Solution 2: We will construct two injections, one from N to N × N, and one the other direction. Then, by Schroeder-Bernstein, we will know that they have the same cardinality, so we will be done. Let f : N → N × N be defined by f(n) = (n, 1). This is obviously an injection. Let g : N × N → N be defined by g((m, n)) = 2^{m}3^{n}. This is an injection because of the unique factorization of the integers.

Thus, since f and g are both injections, we see that Card(N × N) = Card(N) so we are done. 3.2 Solution 1: We construct an injection from Q_{≥0} to Z_{≥0} × Z_{≥0}. Then we will show that the image

of the map is countable. A similar construction will handle the negative rationals.

Any rational number can be written uniquely as p/q where p, q are relatively prime. We map any rational p/q written in this from to (p, q) (with 0 mapped to (0, 1)). This will be a subset of the positive integer lattice. We then define sets A_{n} to be all pairs (x, y) such that x, y are relatively prime and x + y = n. These are finite and partition the lattice into countably many sets. Thus ∪_{i=0}^{∞}A_{n} will be denumerable, so the positive rationals will be denumerable.

Since the union of two denumerable sets is denumerable, the union of the positive and negative rationals is denumerable, so Q is denumerable.

Solution 2: We construct a bijection from the positive rationals to the positive integers. A similar construction will work for the negatives, so by the same logic as the previous solution we will be done.

For any rational number m/n there exists a unique prime factorization of the form 2^{α_{1}}3^{α_{2}} ⋯ p^{α_{k}} ⋯ where p is the kth prime, and the α_{i} are integers which can be negative, and only finitely many of which are nonzero. Thus for every rational number m/n in Q we have constructed a unique integer sequence {α_{i}}_{i=1}^{∞}. We can map this sequence to a positive sequence by mapping every negative α_{i} to −2α_{i} + 1 and every positive α_{i} to 2α_{i}. Thus we have injectively mapped the positive rationals into the set of positive integer sequences, only finitely many elements of each of which are nonzero. Now map each of these sequences {β_{i}} to the integer 2^{β_{1}}3^{β_{2}} · · ·. This will be injective because of unique prime factorization, and it will be surjective because for every integer we can reverse the process and obtain a rational that will map to it. Therefore there exists a bijection between Q_{≥0} and N. So we are done.

3.3 We know that {0, 1}^{A} is the set of all functions from A to {0, 1}. For every such function f, construct the following subset X of A: X = {a ∈ A : f(a) = 1}. This is clearly injective and surjective. Thus it is a bijection, so Card(P(A)) = Card({0, 1}^{A}).

3.4 First note that if A is an infinite set, then there exists a denumerable subset B of A. We construct it in the following manner: let B_{1} = {b} be any element of A. Then define B_{n} = B_{n−1} ∪ {b′} where b′ ∈ A\B_{n−1}. Finally, set S = ∪B_{n}. It is easy to see that this is countable.

Let B be a countable subset of E\D (which exists because E\D is infinite). We know that there is a bijection g between B ∪ D and B, since both of these are countable. So we define a bijection f : E → E\D by

f(e) = \{ \begin{matrix}g(e) & if e ∈ B ∪ D \\ e & if e ∈ E\(B ∪ D). \end{matrix}

This is clearly a bijection. Thus Card(E\D) = Card(E). 3.5 Note that if we can construct a g : B → A that is injective, we will be done. Suppose that b ∈ B.

Let A_{b} = f_{s}^{−1}(b). The A_{b} partition A, since no element can have two images under f. In addition, A_{b} is nonempty for all b, since f_{s} is surjective. By the Axiom of Choice, we can choose a subset X of A such that X contains one element from each of the A_{b}. Define g(b) = X ∩ A_{b}. This is clearly an injection. Thus there exists an injection from A to B, and an injection from B to A, so by Schroeder-Bernstein Card(A) = Card(B).