91Ó°ÊÓ

Suppose a computer takes 1 nanosecond \(\left(=10^{-9}\right.\) second \()\) to execute each operation. Approximately how long will it take for the computer to execute the following numbers of operations? Convert your answers into seconds, minutes, hours, days, weeks, or years, as appropriate. For example, instead of \(2^{50}\) nanoseconds, write 13 days. a. \(\log _{2} 200\) b. 200 c. \(200 \log _{2} 200\) d. \(200^{2}\) e. \(200^{8}\) f. \(2^{200}\)

As in Example 10.1.2, the congruence modulo 2 relation \(E\) is defined from \(\mathbf{Z}\) to \(\mathbf{Z}\) as follows: For all integers \(m\) and \(n, m E n \Leftrightarrow m-n\) is even. a. Is \(0 E 0\) ? Is \(5 E 2\) ? Is \((6,6) \in E\) ? Is \((-1,7) \in E\) ? b. Prove that for any even integer \(n, n E 0\).

. The congruence modulo 3 relation, \(T\), is defined from \(\mathbf{Z}\) to \(\mathbf{Z}\) as follows: For all integers \(m\) and \(n, m T n \Leftrightarrow 3 \mid(m-n)\). a. Is \(10 T\) l? Is \(1 T\) lo? Is \((2,2) \in T\) ? Is \((8,1) \in T\) ? b. List five integers \(n\) such that \(n T 0\). c. List five integers \(n\) such that \(n T 1\). d. List five integers \(n\) such that \(n T 2\). \(\boldsymbol{H}\) e. Make and prove a conjecture about which integers are related by \(T\) to 0 , which integers are related by \(T\) to 1 , and which integers are related by \(T\) to 2 .

Define a binary relation \(P\) on \(Z\) as follows: For all \(m, n \in \mathbf{Z}\), \(m P n \Leftrightarrow m\) and \(n\) have a common prime factor. a. Is \(15 P 25 ?\) b. \(22 P 27\) ? c. Is \(0 P 5 ?\) d. Is \(8 P 8\) ?

\(H\) 12. Let \(A=\\{4,5,6\\}\) and \(B=\\{5,6,7\\}\) and define binary relations \(R, S\), and \(T\) from \(A\) to \(B\) as follows: For all \((x, y) \in A \times B, \quad(x, y) \in R \quad \Leftrightarrow x \geq y\), For all \((x, y) \in A \times B, \quad x S y \quad \Leftrightarrow \quad 2 \mid(x-y) .\) \(T=\\{(4,7),(6,5),(6,7)\\} .\) a. Draw arrow diagrams for \(R, S\), and \(T\). b. Indicate whether any of the relations \(R, S\), and \(T\) are functions.

Find four binary relations from \((a, b)\) to \((x, y)\) that are not functions from \(\\{a, b\\}\) to \(\\{x, y\\}\). \(H\)

Exercises 29-33 refer to unions and intersections of relations. Since binary relations are subsets of Cartesian products, their unions and intersections can be calculated as for any subsets. Given two relations \(R\) and \(S\) from \(A\) to \(B\), \(R \cup S=\\{(x, y) \in A \times B \mid(x, y) \in R\) or \((x, y) \in S\\}\) \(R \cap S=\\{(x, y) \in A \times B \mid(x, y) \in R\) and \((x, y) \in S\\}\). 29\. Let \(A=\\{2,4\\}\) and \(B=\\{6,8,10\\}\) and define binary rela tions \(R\) and \(S\) from \(A\) to \(B\) as follows: For all \((x, y) \in A \times B, \quad x R y \Leftrightarrow x \mid y\), For all \((x, y) \in A \times B, \quad x S y \quad \Leftrightarrow \quad y-4=x .\) State explicitly which ordered pairs are in \(A \times B, R, S\), \(R \cup S\), and \(R \cap S\).

Define \(R\) and \(S\) from \(\mathbf{R}\) to \(\mathbf{R}\) as follows: $$ \begin{aligned} &R=\\{(x, y) \in \mathbf{R} \times \mathbf{R} \mid x

a. Let \(x\) be any positive real number. Use mathematical induction to prove that for all integers \(n \geq 1\), if \(x \leq 1\) then \(x^{n} \leq 1\). b. Explain how it follows from part (a) that if \(x\) is any positive real number, then for all integers \(n \geq 1\), if \(x^{n}>1\) then \(x>1\). c. Explain how it follows from part (b) that if \(x\) is any positive real number, then for all integers \(n \geq 1\), if \(x>1\) then \(x^{1 / n}>1\). d. Let \(p, q\), and \(s\) be positive integers, let \(r\) be a nonnegative integer, and suppose \(p / q>r / s\). Use part (c) and the result of exercise 15 to show that for any real number \(x\), if \(x>1\) then \(x^{p / q}>x^{r / s}\).