91Ó°ÊÓ

Use an appropriate bijection to prove that each of the following sets has cardinality \(\boldsymbol{c}\). (a) \((0, \infty)\) (c) \(\mathbb{R}-\\{0\\}\) (b) \((a, \infty),\) for any \(a \in \mathbb{R}\) (d) \(\mathbb{R}-\\{a\\},\) for any \(a \in \mathbb{R}\)

Is the set of irrational numbers countable or uncountable? Prove that your answer is correct.

Let \(E^{+}\) be the set of all even natural numbers. Prove that \(\mathbb{N} \approx E^{+}\).

Do two uncountable sets always have the same cardinality? Justify your conclusion.

Complete the proof of Theorem 9.17 by proving the following: Let \(A\) and \(B\) be disjoint countably infinite sets and let \(f: \mathbb{N} \rightarrow A\) and \(g: \mathbb{N} \rightarrow\) \(B\) be bijections. Define \(h: \mathbb{N} \rightarrow A \cup B\) by $$ h(n)=\left\\{\begin{array}{ll} f\left(\frac{n+1}{2}\right) & \text { if } n \text { is odd } \\ g\left(\frac{n}{2}\right) & \text { if } n \text { is even. } \end{array}\right. $$ Then the function \(h\) is a bijection.

Prove Theorem 9.18 . The set \(\mathbb{Q}\) of all rational numbers is countable.

Prove that if \(A\) is countably infinite and \(B\) is finite, then \(A-B\) is countably infinite.

Let \(B\) be a finite, nonempty set and assume that \(f: B \rightarrow A\) is a surjection. Prove that there exists a function \(h: A \rightarrow B\) such that \(f \circ h=I_{A}\) and \(h\) is an injection. Hint: Since \(B\) is finite, there exists a natural number \(m\) such that \(\mathbb{N}_{m} \approx B\). This means there exists a bijection \(k: \mathbb{N}_{m} \rightarrow B .\) Now let \(h=k \circ g,\) where \(g\) is the function constructed in Exercise (9).

For this activity, we will consider subsets of \(\mathbb{N}_{30}\) that contain eight elements. (a) One such set is \(A=\\{3,5,11,17,21,24,26,29\\} .\) Notice that $$ \\{3,21,24,26\\} \subseteq A \quad \text { and } \quad 3+21+24+26=74 $$ \\{3,5,11,26,29\\}\(\subseteq A\) and \(\quad 3+5+11+26+29=74\) Use this information to find two disjoint subsets of \(A\) whose elements have the same sum. (b) Let \(B=\\{3,6,9,12,15,18,21,24\\}\). Find two disjoint subsets of \(B\) whose elements have the same sum. Note: By convention, if \(T=\\{a\\},\) where \(a \in \mathbb{N},\) then the sum of the elements in \(T\) is equal to \(a\). (c) Now let \(C\) be any subset of \(\mathbb{N}_{30}\) that contains eight elements. i. How many subsets does \(C\) have? ii. The sum of the elements of the empty set is \(0 .\) What is the maximum sum for any subset of \(\mathbb{N}_{30}\) that contains eight elements? Let \(M\) be this maximum sum. iii. Now define a function \(f: \mathcal{P}(C) \rightarrow \mathbb{N}_{M}\) so that for each \(X \in\) \(\mathcal{P}(C), f(X)\) is equal to the sum of the elements in \(X\). Use the Pigeonhole Principle to prove that there exist two subsets of \(C\) whose elements have the same sum. (d) If the two subsets in part (11(c)iii) are not disjoint, use the idea presented in part (11a) to prove that there exist two disjoint subsets of \(C\) whose elements have the same sum. (e) Let \(S\) be a subset of \(\mathbb{N}_{99}\) that contains 10 elements. Use the Pigeonhole Principle to prove that there exist two disjoint subsets of \(S\) whose elements have the same sum.

Another Proof that \(\mathrm{Q}^{+}\) Is Countable. For this activity, it may be helpful to use the Fundamental Theorem of Arithmetic (see Theorem 8.15 on page 432 ). Let \(Q^{+}\) be the set of positive rational numbers. Every positive rational number has a unique representation as a fraction \(\frac{m}{n},\) where \(m\) and \(n\) are relatively prime natural numbers. We will now define a function \(f: \mathbb{Q}^{+} \rightarrow \mathbb{N}\) as follows: If \(x \in Q^{+}\) and \(x=\frac{m}{n},\) where \(m, n \in \mathbb{N}, n \neq 1\) and \(\operatorname{gcd}(m, n)=1,\) we write $$ \begin{array}{l} m=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{r}^{\alpha_{r}} \\ n=q_{1}^{\beta_{1}} q_{2}^{\beta_{2}} \cdots q_{s}^{\beta_{x}} \end{array} $$ where \(p_{1}, p_{2}, \ldots, p_{r}\) are distinct prime numbers, \(q_{1}, q_{2}, \ldots, q_{s}\) are distinct prime numbers, and \(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{r}\) and \(\beta_{1}, \beta_{2}, \ldots, \beta_{s}\) are natural numbers. We also write \(1=2^{0}\) when \(m=1\). We then define $$ f(x)=p_{1}^{2 \alpha_{1}} p_{2}^{2 \alpha_{2}} \cdots p_{r}^{2 \alpha_{r}} q_{1}^{2 \beta_{1}-1} q_{2}^{2 \beta_{2}-1} \cdots q_{3}^{2 \beta_{s}-1} $$ If \(x=\frac{m}{1},\) then we define \(f(x)=p_{1}^{2 \alpha_{1}} p_{2}^{2 \alpha_{2}} \cdots p_{r}^{2 \alpha_{r}}=m^{2}\). (a) Determine \(f\left(\frac{2}{3}\right), f\left(\frac{5}{6}\right), f(6), f\left(\frac{12}{25}\right), f\left(\frac{375}{392}\right),\) and \(f\left(\frac{2^{3} \cdot 11^{3}}{3 \cdot 5^{4}}\right)\). (b) If possible, find \(x \in \mathbb{Q}^{+}\) such that \(f(x)=100\). (c) If possible, find \(x \in \mathrm{Q}^{+}\) such that \(f(x)=12\). (d) If possible, find \(x \in Q^{+}\) such that \(f(x)=2^{8} \cdot 3^{5} \cdot 13 \cdot 17^{2}\). (e) Prove that the function \(f\) is an injection. (f) Prove that the function \(f\) is a surjection. (g) What has been proved?