91Ó°ÊÓ

Prove that a union of any two countably infinite sets is countably infinite.

Draw arrow diagrams for the Boolean functions defined by the following input/output tables. a. \begin{tabular}{|cc|c|} \hline \multicolumn{2}{|c|}{ Input } & Output \\ \hline \(\boldsymbol{P}\) & \(\boldsymbol{Q}\) & \(\boldsymbol{R}\) \\ \hline 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \hline \end{tabular} b. \begin{tabular}{|ccc|c|} \hline \multicolumn{3}{|c|}{ Input } & Output \\ \hline \(\boldsymbol{P}\) & \(\boldsymbol{Q}\) & \(\boldsymbol{R}\) & \(\boldsymbol{S}\) \\ \hline 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \hline \end{tabular}

A penny collection contains twelve 1967 pennics, seven 1968 pennies, and eleven \(197 !\) pennies. If you are to pick some pennies without looking at the dates, how many must you pick to be sure of getting at least five pennies from the same year?

Prove that a union of any finite set and any countably infinite set is countably infinite.

Let \(A\) be a set of six positive integers each of which is less than 13. Show that there must be two distinct subsets of \(A\) whose elements when added up give the same sum. (For example, if \(A=\\{5,12,10,1,3,4\\}\), then the elements of the subsets \(S_{1}=\\{1,4,10\\}\) and \(S_{2}=\\{5,10\\}\) both add up to 15.)

Prove that \(\mathbf{Z} \times \mathbf{Z}\), the Cartesian product of the set of integers with itself, is countably infinite.

Exercises 32 and 33 use the following definition: If \(f: \mathbf{R} \rightarrow \mathbf{R}\) and \(g: \mathbf{R} \rightarrow \mathbf{R}\) are functions, then the function \((f+g): \mathbf{R} \rightarrow \mathbf{R}\) is defined by the formula \((f+g)(x)=f(x)+g(x)\) for all real numbers \(x\). If \(f: \mathbf{R} \rightarrow \mathbf{R}\) and \(g: \mathbf{R} \rightarrow \mathbf{R}\) are both one-to-one, is \(f+g\) also one-to-one? Justify your answer.

Student \(\mathrm{C}\) tries to define a function \(h: \mathbf{Q} \rightarrow \mathbf{Q}\) by the rule \(h\left(\frac{m}{n}\right)=\frac{m^{2}}{n}\), for all integers \(m\) and \(n\) with \(n \neq 0\). Student D claims that \(h\) is not well defined. Justify student D's claim.

Let \(S\) be a set of ten integers chosen from 1 through 50 . Show that the set contains at least two different (but not necessarily disjoint) subsets of four integers that add up to the same number. (For instance, if the ten numbers are \(\\{3,8,9,18,24,34,35,41,44,50\\}\), the subsets can be taken to be \(\\{8,24,34,35\\}\) and \(\\{9,18,24,50\\}\). The numbers in both of these add up to 101.)

Exercises 34 and 35 use the following definition: If \(f: \mathbf{R} \rightarrow \mathbf{R}\) is a function and \(c\) is a nonzero real number, the function \((c \cdot f): \mathbf{R} \rightarrow \mathbf{R}\) is defined by the formula \((c \cdot f)(x)=c \cdot f(x)\) for all real numbers \(x\). Let \(f: \mathbf{R} \rightarrow \mathbf{R}\) be a function and \(c\) a nonzero real number. If \(f\) is one-to-one, is \(c \cdot f\) also one-to-one? Justify your answer.