91Ó°ÊÓ

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 onto, is \(c \cdot f\) also onto? Justify your answer.

Show that if 101 integers are chosen from 1 to 200 inclusive, there must be 2 with the property that one is divisible by the other.

Each of exercises 35-39 refers to the Euler phi function, denoted \(\phi\), which is defined as follows: For each integer \(n \geq 1, \phi(n)\) is the number of positive integers less than or equal to \(n\) that have no common factors with \(n\) except \(\pm 1\). For example, \(\phi(10)=4\) because there are four positive integers less than or equal to 10 that have no common factors with 10 except \(\pm 1\); namely, 1,3 , 7 , and 9 . Prove that if \(p\) is a prime number and \(n\) is an integer with \(n \geq 1\), then \(\phi\left(p^{n}\right)=p^{n}-p^{n-1}\).

Prove that if \(A\) and \(B\) are any countably infinite sets, then \(A \times B\) is countably infinite.

Each of exercises 35-39 refers to the Euler phi function, denoted \(\phi\), which is defined as follows: For each integer \(n \geq 1, \phi(n)\) is the number of positive integers less than or equal to \(n\) that have no common factors with \(n\) except \(\pm 1\). For example, \(\phi(10)=4\) because there are four positive integers less than or equal to 10 that have no common factors with 10 except \(\pm 1\); namely, 1,3 , 7 , and 9 . Prove that there are infinitely many integers \(n\) for which \(\phi(n)\) is a perfect square.

Each of exercises 35-39 refers to the Euler phi function, denoted \(\phi\), which is defined as follows: For each integer \(n \geq 1, \phi(n)\) is the number of positive integers less than or equal to \(n\) that have no common factors with \(n\) except \(\pm 1\). For example, \(\phi(10)=4\) because there are four positive integers less than or equal to 10 that have no common factors with 10 except \(\pm 1\); namely, 1,3 , 7 , and 9 . Use the inclusion/exclusion principle to prove the following: If \(n=p q\), where \(p\) and \(q\) are distinct prime numbers, then \(\phi(n)=(p-1)(q-1)\).

What is the largest number of elements that a set of integers from 1 through 100 can have so that no one element in the set is divisible by another? (Hint: Imagine writing all the numbers from 1 through 100 in the form \(2^{k} \cdot m\), where \(k \geq 0\) and \(m\) is odd.)

Exercises \(40-47\) refer to the following definition: Definition: If \(f: X \rightarrow Y\) is a function and \(A \subseteq X\) and \(C \subseteq Y\) then $$ f(A)=\\{y \in Y \mid y=f(x) \text { for some } x \text { in } A\\} $$ and $$ f^{-1}(C)=\\{x \in X \mid f(x) \in C\\} $$ Determine which of the properties in \(40-47\) are true for all functions \(f\) from a set \(X\) to a set \(Y\) and which are false for some function \(f\). Justify your answers. For all subsets \(A\) and \(B\) of \(X, f(A \cup B)=f(A) \cup f(B)\).

In Example \(7.2 .8\) a one-to-one correspondence was defined from the power set of \(\\{a, b\\}\) to the set of all strings of 0 's and 1's that have length 2 . Thus the elements of these two sets can be matched up exactly, and so the two sets have the same number of elements. a. Let \(X=\left\\{x_{1}, x_{2}, \ldots, x_{n}\right\\}\) be a set with \(n\) elements. Use Example \(7.2 .8\) as a model to define a one-to-one correspondence from \(\mathscr{P}(X)\), the set of all subsets of \(X\), to the set of all strings of 0 's and l's that have length \(n\). b. Use the one-to-one correspondence of part (a) to deduce that a set with \(n\) elements has \(2^{n}\) subsets. (This provides an alternative proof of Theorem 5.3.5.)