Answers

Answers to Selected Exercises

Section 2.1

1. Only (a), (c), and (e) are statements.

2. (a) false (b) false (c) false (d) true

3. (a) $\pi\notin\mathbb{Z}$ (b) $1^3+2^3+3^3 \neq 3^2\cdot4^2/4$ (c) $u$ is not a vowel

   (d) This statement is either true or false.

4. (a) true (b) true (c) true (d) false (e) false (f) true

5. By definition, a rational number can be written as a ratio of two integers. After multiplying the numerator by 7, we still have a ratio of two integers. Conversely, given any rational number $x$, we can multiply the denominator by 7, we obtain another rational number $y$ such that $7y=x$. Hence, the two sets $7\mathbb{Q}$ and $\mathbb{Q}$ contain the same collection of rational numbers. In contrast, $0\mathbb{Q}$ contains only one number, namely, 0. Therefore, $0\mathbb{Q}\neq\mathbb{Q}$.

Section 2.2

1. (a) $p\wedge q$ (b) $\overline{q}\wedge r$ (c) $\overline{p}\vee \overline{q}$ (d) $(p\vee q) \wedge \overline{p\wedge q}$

2. (a) $p\wedge q$; always false regardless of the value of $r$.

   (b) $p\vee q$; always true regardless of the value of $r$.

   (c) $(p\wedge q)\vee r$; true if $r$ is true, and false if $r$ is false.

   (d) $\overline{q}\wedge r$; true if $r$ is true, and false if $r$ is false.

3. (a) false (b) true

4. (a) $(4\leq x)\wedge (x\leq 7)$ (b) $(4 < x)\wedge (x\leq 7)$ (c) $(4\leq x)\wedge (x < 7)$

Section 2.3

1. (a) $p\Rightarrow q$ (b) $r\Rightarrow p$ (c) $\overline{p}\Rightarrow q$ (d) $\overline{p}\Rightarrow r$ (e) $(\overline{p}\wedge q)\Rightarrow r$

2. (a) $p\Rightarrow q$, which is false.

   (b) $p\Rightarrow r$, which is true if $r$ is true, and is false if $r$ is false.

   (c) $(p\vee q)\Rightarrow r$, which is true if $r$ is true, and is false if $r$ is false.

3. (a) $x^3-3x^2+x-3=0 \Rightarrow x=3$

   (b) $x^3-3x^2+x-3=0 \Rightarrow x=3$

   (c) $x=3 \Rightarrow x^3-3x^2+x-3=0$

4.  $\begin{array}[t]{ {|c | c | c | c |}} \hline p & q & r & p\wedge q & (p\wedge q)\vee r \\ \hline T &T &T & T & \;T \\ T &T &F & T & \;T \\ T &F &T & F & \;T \\ T & F & F & F & \;F \\ F &T &T & F & \;T \\ F &T &F & F & \;F \\ F &F &T & F & \;T \\ F &F &F & F & \;F \\ \hline \end{array} \hspace {0.5in} \begin{array}[t]{ {|c | c | c | c | c |}} \hline p & q & r & p\vee q & p\wedge r & (p\vee q)\Rightarrow(p\wedge r) \\ \hline T &T &T & T & T & T \\ T &T &F & T & F & F \\ T &F &T & T & T & T \\ T &F &F & T & F & F \\ F & T & T & T & F & F \\ F & T & F & T & F & F \\ F & F & T & F & F & T \\ F & F & F & F & F & T \\ \hline \end{array}$

5. (a) Using a truth table, we find that the implication $(p\wedge q) \Rightarrow(q\vee r)$ is always true. Hence, no truth value of $p$ would make $(p\wedge q)\Rightarrow(q\vee r)$ false.

   (b) From a truth table, we find that, $(q\wedge r)\Rightarrow (p\wedge q)$ is false only when $p$ is false. We can draw the same conclusion without using any truth table. An implication is false only when its hypothesis (in this case, $q\wedge r$) is true and its conclusion (in this case, $p\wedge q$) is false. For $q\wedge r$ to be true, we need both $q$ and $r$ to be true. Now $q$ is true and $p\wedge q$ is false require $p$ to be false.

Section 2.4

1. (a) $p\Leftrightarrow q$ (b) $r\Leftrightarrow\overline{p}$ (c) $r\Leftrightarrow(q\wedge\overline{p})$ (d) $r\Leftrightarrow(p\wedge q)$

2. (a) $p\Leftrightarrow q$, which is false.

   (b) $p\Leftrightarrow r$, which is true if $r$ is true, and is false if $r$ is false.

   (c) $(p\vee q)\Leftrightarrow r$, which is true if $r$ is true, and is false if $r$ is false.

3. (a) true (b) false (c) false (d) false

4. We say $n$ is odd if and only if $n=2q+1$ for some integer $q$.

Section 2.5  

1. $\begin{array}[t]{ {|c | c | c | c | c | c |}} \hline p & q & p\vee q & \overline{p\vee q} & \overline{p} & \overline{q} & \overline{p}\wedge\overline{q} \\ \hline T & T & T & F & F & F & F \\ T & F & T & F & F & T & F \\ T & T & T & F & T & F & F \\ T & F &F & T & T & T & T \\ \hline \end{array}$

2. Only (b) is a tautology, as indicated in the truth tables below.

   (a) $\begin{array}[t]{|*{5}{c|}} \hline p & q & \overline{p} & \overline{p}\vee q & (\overline{p}\vee q)\Rightarrow p \\ \hline T & T & F &  T & \qquad\;T \\ T & F & F & F & \qquad\;T \\ F & T & T & T & \qquad\; F \\ F & F & T & T & \qquad\; F \\ \hline \end{array}$

   (b) $\begin{array}[t]{|*{6}{c|}} \hline p & q & p\Rightarrow q & \overline{q} & p\Rightarrow\overline{q} & (p\Rightarrow q)\vee(p\Rightarrow\overline{q}) \\ \hline T &T &T & F & F &T \\ T &F &F & T & T &T \\ F &T &T & F & T &T \\ F &F &F & T & T &T \\ \hline \end{array}$

   (c) $\begin{array}[t]{|*{5}{c|}} \hline p & q & r & p\Rightarrow q & (p\Rightarrow q)\Rightarrow r \\ \hline T &T &T & T & \qquad\quad T \\ T & T & F & T & \qquad\quad F \\ T &F &T & F & \qquad\quad T \\ T &F &F & F & \qquad\quad T \\ F &T &T & T & \qquad\quad T \\ F &T &F & T & \qquad\quad F \\ F &F &T & T & \qquad\quad T \\ F &F &F & T & \qquad\quad F \\ \hline \end{array}$

3. The proofs are displayed below without explanations. Be sure to fill them in.

   (b) $\begin{array}[t]{lcl@{\quad(\hskip1.5in)}} (p\wedge q)\Rightarrow r &\equiv& \overline{p\wedge q}\vee r \\ &\equiv& (\overline{p}\vee\overline{q})\vee r \\ &\equiv& \overline{p}\vee(\overline{q}\vee r) \\ &\equiv& p\Rightarrow(\overline{q}\vee r) \end{array}$

   (c) $\begin{array}[t]{lcl@{\quad(\hskip1.5in)}} (p\Rightarrow\overline{q}) \wedge (p\Rightarrow\overline{r}) &\equiv& (\overline{p}\vee\overline{q}) \wedge (\overline{p}\vee\overline{r}) \\ &\equiv& \overline{p}\vee(\overline{q}\wedge\overline{r}) \\ &\equiv& \overline{p}\vee\overline{q\vee r} \\ &\equiv& \overline{p\wedge(q\vee r)} \end{array}$

4. (a)

   Converse:	If triangle $ABC$ is a right triangle, then $ABC$ is isosceles
   	and contains an angle of 45 degrees.
   Inverse:	If triangle $ABC$ is not isosceles or does not contain an angle
   	of 45 degrees, then $ABC$ is not a right triangle.
   Contrapositive:	If triangle $ABC$ is not a right triangle, then $ABC$ is not isosceles
   	or does not contain an angle of 45 degrees.

   (b)

   Converse:	If quadrilateral $ABCD$ is both a rectangle and a rhombus,
   	then $ABCD$ is a square.
   Inverse:	If quadrilateral $ABCD$ is not a square,
   	then it is not a rectangle or not a rhombus.
   Contrapositive:	If quadrilateral $ABCD$ is not a rectangle or not a rhombus,
   	then $ABCD$ is not a square.

5. (a) true (b) true (c) false

6. Only (b).

7. (a) $p\wedge q$ (b) $p\wedge\overline{q}$ (c) $p\wedge q$

Section 2.6

1. (a) There exists an integer $n$ such that $n$ is prime and $n$ is even.

   (b) For all integers $n$, if $n>2$, then $n$ is prime or $n$ is even.

   (c) There exists an integer $n$ such that $n$ is prime, and either $n$ is even or $n>2$.

   (d) For all integers $n$, if $n$ is prime and $n$ is even, then $n\leq2$.

2. (a) true (b) true (c) false (d) false (e) true

3. (a) $\exists x<0\,\exists y,z\in\mathbb{R}\,(y<z \wedge xy\leq xz)$

   (b) $\exists x\in\mathbb{Z}\,[\overline{p(x)}\wedge\overline{q(x)}]$

   (c) $\exists x,y\in\mathbb{R}\,[p(x,y)\wedge\overline{q(x,y)}]$

4. (a)

   $\forall x,y\in\mathbb{R}\,(x+y=y+x)$

   $\exists x,y\in\mathbb{R}\,(x+y\neq y+x)$

   There exist real numbers $x$ and $y$ such that $x+y\neq y+x$.

   (b)

   $\forall x\in\mathbb{R}^+\,\exists y\in\mathbb{R}\,(y^2=x)$

   $\exists x\in\mathbb{R}^+\,\forall y\in\mathbb{R}\,(y^2\neq x)$

   There exists a positive real number $x$ such that for all real numbers $y$, $y^2\neq x$.

   (c)

   $\exists y\in\mathbb{R}\,\forall x\in\mathbb{Z}\,(2x^2+1>x^2y)$

   $\forall y\in\mathbb{R}\,\exists x\in\mathbb{Z}\,(2x^2+1\leq x^2y)$

   For every real number $y$, there exists an integer $x$ such that $2x^2+1\leq x^2y$.

5. The statement “a square must be a parallelogram” means, symbolically, $$\forall PQRS\,(PQRS \mbox{ is a square} \Rightarrow PQRS \mbox{ is a parallelogram}),$$ but the statement “a square must not be a parallelogram” means $$\forall PQRS\,(PQRS \mbox{ is a square} \Rightarrow PQRS \mbox{ is not a parallelogram}).$$ The second statement is not the negation of the first. The correct negation, in symbol, is $$\exists PQRS\,(PQRS \mbox{ is a square} \wedge PQRS \mbox{ is a parallelogram}).$$ In words, it means “there exists a square that is not a parallelogram.”

Section 3.1

1. Placing six dominoes horizontally in each row covers the entire chessboard.

2. Let $f(x)=x^3-12x+2$. From the following chart $$\begin{array}{|c||*{9}{r|}} \hline x & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \\ \hline f(x) & -14 & 12 & 18 & 13 & 2 & -9 & -14 & -7 & 18 \\ \hline \end{array}$$ we conclude there $x^3-12x+2=0$ has a solution between $-4$ and $-3$, another one between 0 and 1, and a third one between 3 and 4. So it has at least three real solutions.

   Remark. The Fundamental Theorem of Algebra asserts that a real polynomial of degree $n$ has at most $n$ real roots. Hence, the given equation has exactly three real solutions.

3. $n=3$.

Section 3.2

1. No, $2^3+1=9$ is composite.

2. According to (i), the number $\sqrt{2}$ is irrational. It follows from (ii) that $\sqrt[4]{2} = \sqrt{\sqrt{2}}$ is also irrational. Applying (ii) one more time, we conclude that $\sqrt[8]{2} = \sqrt{\sqrt[4]{2}}$ is irrational.

3. (a) The statement is false, because $(-3)^2 > (-2)^2$, but $-3\not>-2$.

   (b) The statement is false, because when $n=41$, $$n^2+n+41 = 41^2+41+41 = 41(41+1+1) = 41\cdot 43$$ is composite.

Section 3.3

(a) We will prove the contrapositive of the given statement. That is, we will prove that if $n$ is odd, then $n^2$ is odd. If $n$ is odd, we can write $n=2q+1$ for some integer $q$. Then $$n^2 = (2q+1)^2 = 4q^2+4q+1 = 2(2q^2+2q)+1,$$ where $2q^2+2q$ is an integer. This shows that $n^2$ is odd.

(b) Suppose the given statement is false. That is, suppose $n^2$ is even, but $n$ is odd. Since $n$ is odd, $n=2q+1$ for some integer $q$. Then $$n^2 = (2q+1)^2 = 4q^2+4q+1 = 2(2q^2+2q)+1,$$ where $2q^2+2q$ is an integer. This shows that $n^2$ is odd, which contradicts the assumption that $n^2$ is even. Therefore, the given statement must be true.

Suppose there exist some numbers $a\neq b$ such that $a^2+b^2=2ab$. Then $$0 = a^2-2ab+b^2 = (a-b)^2$$ would have implied that $a=b$. This contradicts the assumption that $a\neq b$. Therefore, $a^2+b^2\neq 2ab$.

Suppose $(p\Rightarrow q) \vee (p\Rightarrow \overline{q})$ is false for some logical statements $p$ and $q$. For a disjunction to be false, we need

$p\Rightarrow q$ to be false, and

$p\Rightarrow \overline{q}$ to be false.

They in turn require

$p$ to be true and $q$ to be false, and

$p$ to be true and $\overline{q}$ to be false.

Having $\overline{q}$ false would imply $q$ is true, which contradicts what we found. Therefore, the given logical formula is always true, hence, a tautology.

Section 3.4

1. We proceed by induction on $n$. When $n=1$, the left-hand side of the identity reduces to $1^3=1$, and the right-hand side becomes $\frac{1^2\cdot2^2}{4}=1$. Hence, the identity holds when $n=1$. Assume the identity holds when $n=k$ for some integer $k\geq1$; that is, assume $$1^3+2^3+3^3+\cdots+k^3 = \frac{k^2(k+1)^2}{4}$$ for some integer $k\geq1$. We want to show that it also holds when $n=k+1$; that is, we want to show that $$1^3+2^3+3^3+\cdots+(k+1)^3 = \frac{(k+1)^2(k+2)^2}{4}.$$ Using the inductive hypothesis, we find $$\begin{aligned} 1^3+2^3+3^3+\cdots+(k+1)^3 &=& 1^3+2^3+3^3+\cdots+k^3+(k+1)^3 \\ &=& \frac{k^2(k+1)^2}{4} + (k+1)^3 \\ &=& \frac{(k+1)^2[k^2+4(k+1)]}{4} \\ &=& \frac{(k+1)^2(k^2+4k+4)}{4} \\ &=& \frac{(k+1)^2(k+2)^2}{4}. \end{aligned}$$ Therefore, the identity also holds when $n=k+1$. This completes the induction.

Section 3.5

1. We proceed by induction on $n$. When $n=1$, the product $n(n+1)(n+2)$ becomes $1\cdot2\cdot3=6$, which is obviously a multiple of 3. Hence, the claim holds when $n=1$. Assume the claim holds when $n=k$ for some integer $k\geq1$; that is, assume that $k(k+1)(k+2)$ is a multiple of 3 for some integer $k\geq1$. Then we can write $$k(k+1)(k+2) = 3q$$ for some integer $q$. We want to show that the claim is still valid when $n=k+1$. That is, we want to show that $(k+1)(k+2)(k+3)$ is also a multiple of 3. So we want to find an integer $Q$ such that $$(k+1)(k+2)(k+3) = 3Q.$$ We note that, using the inductive hypothesis, $$\begin{aligned} (k+1)(k+2)(k+3) &=& k(k+1)(k+2) + 3(k+1)(k+2) \\ &=& 3q + 3(k+1)(k+2) \\ &=& 3\,[q+(k+1)(k+2)], \end{aligned}$$ where $q+(k+1)(k+2)$ is an integer. Hence, $(k+1)(k+2)(k+3)$ is a multiple of 3. This completes the induction.

2. (b) $S_n=1-\frac{1}{(n+1)!}$ for all integers $n\geq1$.

3. (b) $T_n = \frac{n+1}{2n+3}$ for all integers $n\geq0$.

Section 3.6

1. We proceed by induction on $n$. When $n=1$, the left-hand side of the identity reduces to $F_1^2=1^2=1$, and the right-hand side becomes $F_1F_2=1\cdot1=1$. Hence, the identity holds when $n=1$. Assume the identity holds when $n=k$ for some integer $k\geq1$; that is, assume $$F_1^2+F_2^2+F_3^2+\cdots+F_k^2 = F_k F_{k+1}$$ for some integer $k\geq1$. We want to show that it also holds when $n=k+1$; that is, we want to show that $$F_1^2+F_2^2+F_3^2+\cdots+F_{k+1}^2 = F_{k+1} F_{k+2}.$$ Using the inductive hypothesis, we find $$\begin{aligned} F_1^2+F_2^2+F_3^2+\cdots+F_{k+1}^2 &=& F_1^2+F_2^2+F_3^2+\cdots+F_k^2+F_{k+1}^2 \\ &=& F_k F_{k+1} + F_{k+1}^2 \\ &=& F_{k+1} (F_k+F_{k+1}) \\ &=& F_{k+1} F_{k+2}. \end{aligned}$$ Therefore, the identity also holds when $n=k+1$. This completes the induction.

Section 4.1

1. (a) $\{-5,-4,-3,-2,-1,0,1,2,3\}$ (b) $\{1,2,3\}$ (c) $\{0,-2,3\}$ (d) $\{-3,3\}$

2. (a) $\{n\in\mathbb{Z} \mid n<0\}$

   (b) $\{n\in\mathbb{Z} \mid \mbox{\)n\(is a perfect cube}\}$

   (c) $\{n\in\mathbb{Z} \mid \mbox{\)n\(is a perfect square}\}$

3. (a) $\mathbb{Z}^-$ (d) $5\mathbb{Z}$ (f) $4+6\mathbb{Z}$

   Remark. We cannot write (b) as $\mathbb{Z}^3$ and (c) as $\mathbb{Z}^2$, because $\mathbb{Z}^3$ and $\mathbb{Z}^2$ mean something else. If we drop 0 from (e), then $\{4,8,12,\ldots\}=4\mathbb{N}$. However, the inclusion of 0 makes it harder to describe (d) in the form of $4S$.

4. (a) $(-4,7)$ (b) $(-4,7]$ (c) $(0,7]$

5. (a) 10 (b) 11 (c) 7

6. (a) true (b) true (c) true (d) false

7. (a) It is incorrect to write $(3,7]=3<x\leq7$ because $(3,7]$ is a set, but $3<x\leq7$ is a logical statement.

   (b) No, because both $\{x\in\mathbb{R}\mid x^2<0\}$ and $\emptyset$ are sets, so we should use an equal sign to compare them. The notation $\equiv$ only applies to logical statements. The correct way to say it is “$\{x\in\mathbb{R}\mid x^2<0\} = \emptyset$.”

Section 4.2

1. (a) true (b) true (c) true (d) true (e) true (f) false

2. We have $\mathbb{Z}\subseteq\mathbb{N}$ because every integer $n$ is also a rational number, as we can write it as the rational number $\frac{n}{1}$.

3. Yes, this is the transitive property.

4. (e) $\big\{\emptyset,\{a\},\{\{b\}\},\{a,\{b\}\}\big\}$

5. (a) False, because the set $\{a\}$ cannot be found in $\{a,b,c\}$ as an element.

   (b) False, because $a$, the sole element in $\{a\}$, cannot be found in $\{\{a\},b,c\}$ as an element.

   (c) False. For $\{a\}\in\wp(\{\{a\},b,c\})$, the set $\{a\}$ must be a subset of $\{\{a\},b,c\}\}$. This means $a$ must belong to $\{\{a\},b,c\}$, which is not true.

Section 4.3

1. (a) $\{-4,-3,-2,-1,0,1,2,3,4\}$

   (b) $\{-3,-2,-1,0,1,2,3,4\}$

   (c) $\{-3,-2,-1,0,1,2,3,\ldots\}$

2. (a) false (b) false

3. (a) $E\cap D$ (b) $\overline{E}\cup B$

4. For example, take $A=\{x\}$, and $B=\{\{x\},x\}$.

5. Assume $A\subseteq C$ and $B\subseteq C$, we want to show that $A\cup B \subseteq C$. In this regard, let $x\in A\cup B$, we want to show that $x\in C$ as well. Since $x\in A\cup B$, the definition of set union asserts that either $x\in A$ or $x\in B$.

   • Case 1: If $x\in A$, then $A\subseteq C$ implies that $x\in C$.

   • Case 2: If $x\in B$, then $B\subseteq C$ implies that $x\in C$.

   In both cases, we find $x\in C$. This proves that $A\cup B\subseteq C$.

6. (a) The notation $\cap$ is used to connect two sets, but “$x\in A$” and “$x\in B$” are both logical statements. We should also use $\Leftrightarrow$ instead of $\equiv$. The statement should have been written as “$x\in A \,\wedge\, x\in B \Leftrightarrow x\in A\cap B$.”

   (b) If we read it aloud, it sounds perfect: $$\mbox{If $x$ belongs to $A$ and $B$, then $x$ belongs to $A\cap B$}.$$ The trouble is, every notation has its own meaning and specific usage. In this case, $\wedge$ is not exactly a replacement for the English word “and.” Instead, it is the notation for joining two logical statements to form a conjunction. Before $\wedge$, we have “$x\in A$,” which is a logical statement. But, after $\wedge$, we have “$B$,” which is a set, and not a logical statement. It should be written as “$x\in A\,\wedge\,x\in B \Rightarrow x\in A\cap B$.”

Section 4.4

1. (a) $\{(-2,0), (-2,4), (2,0), (2,4)\}$

   (b) $\{(-2,-3), (-2,0), (-2,3), (-2,-3), (-2,0), (-2,3)\}$

2. $2\cdot2\cdot2\cdot3 = 24$.

3. (a) $\{(-2,\emptyset),(-2,\{-2\}),(-2,\{2\}),(-2,\{-2,2\}), ( 2,\emptyset),( 2,\{-2\}),( 2,\{2\}),( 2,\{-2,2\})\}$

Section 4.5

1. $\bigcap_{n=1}^\infty A_n = [0,2)$, $\bigcup_{n=1}^\infty A_n = (-1,\infty)$.

2. $\bigcap_{n=0}^\infty C_n = \emptyset$, $\bigcup_{n=0}^\infty C_n = \mathbb{N}\cup\{0\}$.

3. $\bigcap_{n\in\mathbb{N}} E_n = E_0 = \{0\}$, $\bigcup_{n\in\mathbb{N}} E_n = \mathbb{Z}$.

4. $\bigcup_{i\in I} A_i = [1,\infty)$, $\bigcap_{i\in I} A_i = \{1\}$.

5. $\bigcap_{x\in(1,2)} (1-2x,x^2) = [-1,1]$, $\bigcup_{x\in(1,2)} (1-2x,x^2) = (-3.4)$.

6. $\bigcap_{r\in(0,\infty)} A_r = \{(0,0)\}$, $\bigcup_{r\in(0,\infty)} A_r = \mathbb{R}^*\times\mathbb{R}^+ \cup \{(0,0)\}$.

Section 5.1

1. (a) 3 (b) 3 (c) 3 (d) 1

2. We claim that the subset $(3,5)$ does not have a smallest element. To see why, suppose it has a smallest element $x$. The midpoint between 3 and $x$ is the number $\frac{3+x}{2}$, and $$3 < \frac{3+x}{2} < x < 5.$$ This means $\frac{3+x}{2}$ is also inside the interval $(3,5)$, and is smaller than $x$. This contradicts the minimality of $x$. Thus, the interval $(3,5)$ does not have a smallest element. Consequently, the interval $(3,5]$ is not well-ordered.

3. We know that $\mathbb{N}$ is well-ordered. Since $2\mathbb{N}$ is a subset of $\mathbb{N}$, and $2\mathbb{N}$ is clearly nonempty, we conclude from Problem [ex:PWO-04] that $2\mathbb{N}$ is also well-ordered.

Section 5.2

1. (a) 23, 1 (b) $-11$, 1 (c) $-6$, 13

2. This is an immediate consequence of Corollary [cor:divalgo].

3. (a) Let $n$ be any integer. Then $n\bmod3=0,1,2$.

   • Case 1: if $n\bmod3=0$, then $n=3q$ for some integer $q$, and $$n^3-n = (3q)^3-3q = 27q^3-3q = 3(9q^2-q),$$ where $9q^2-q$ is an integer.

   • Case 2: if $n\bmod3=1$, then $n=3q+1$ for some integer $q$, and $$n^3-n = (3q+1)^3-(3q+1) = 27q^3+27q^2+6q = 3(9q^3+9q^2+2q),$$ where $9q^3+9q^2+2q$ is an integer.

   • Case 2: if $n\bmod3=2$, then $n=3q+2$ for some integer $q$, and $$n^3-n = (3q+2)^3-(3q+2) = 27q^3+54q^2+33q+6 = 3(9q^3+18q^2+11q+2),$$ where $9q^3+18q^2+11q+2$ is an integer.

   In all three cases, we have shown that $n^3-n$ is a multiple of 3.

   (b) We note that $$n^3-n = n(n^2-1) = n(n-1)(n+1) = (n-1)n(n+1)$$ is a product of three consecutive integers. As we have seen in Problem [ex:divalgo-04], any three consecutive integers must contain a multiple of 3. It follows that their product is also a multiple of 3.

4. (a) $s+t$ (b) 4

Section 5.3

Assume $a\mid b$ and $c\mid (-a)$. There exist integers $x$ and $y$ such that $b=ax$ and $-a=cy$. Then $$b = ax = (-a)(-x) = cy\cdot(-x) = (-c)\cdot xy,$$ where $xy$ is an integer. Thus, $(-c)\mid b$.

There are three cases, depending on the remainder when an integer is divided by 3.

$(3q)^2 = 9q^2 = 3\cdot3q^2$.

$(3q+1)^2 = 9q^2+6q+1 = 3(3q^2+2q)+1$.

$(3q+2)^2 = 9q^2+12q+4 = 9q^2+12q+3+1 = 3(3q^2+4q+1)+1$.

In each case, we have shown that the square of an integer is of the form $3k$ or $3k+1$.

Section 5.4

1. (a) $1\cdot 27+ 0\cdot 81= 27$ (b) $-3\cdot 24+ 1\cdot 84= 12$ (c) $-35\cdot1380+16\cdot3020= 20$

2. 1, 2, 17, and 34.

Section 5.5

1. Since $$-3\cdot(2n+1)+2\cdot(3n+2) = 1,$$ we deduce that $\gcd(2n+1,3n+2)=1$.

2. Let $a$, $b$, and $c$ be positive integers such that $a\mid c$, $b\mid c$, and $\gcd(a,b)=1$. Then there exist integers $x$ and $y$ such that $c=ax$ and $c=by$; and there exist integers $s$ and $t$ such that $sa+tb=1$. It follows that $$c = c\cdot 1 = c(sa+tb) = csa+ctb.$$ Using $c=ax$ and $c=by$, we find $$c = csa+ctb = by\cdot sa+ax\cdot tb = ab(ys+xt),$$ where $ys+xt$ is an integer. Thus, $ab\mid c$.

Section 5.6

1. (a) $3^2\cdot5^2\cdot7$ (b) $2\cdot3^2\cdot7^2\cdot11$

2. (a) 81 (b) 168

3. Every 50 days.

4. Assume $x\in 10\mathbb{Z}\cap15\mathbb{Z}$, then $x\in10\mathbb{Z}$ and $x\in15\mathbb{Z}$. This means $x$ is a multiple of both 10 and 15. Consequently, $x$ is a multiple of $\lcm(10,15)=30$, which means $x\in30\mathbb{Z}$. Thus, $10\mathbb{Z}\cap15\mathbb{Z} \subseteq 30\mathbb{Z}$.

   Next, assume $x\in 30\mathbb{Z}$, then $x$ is a multiple of 30. Consequently, $x$ is a multiple of 10, as well as a multiple of 15. This means $x\in10\mathbb{Z}$, and $x\in15\mathbb{Z}$. As a result, $x\in 10\mathbb{Z}\cap15\mathbb{Z}$. Thus, $30\mathbb{Z} \subseteq 10\mathbb{Z}\cap15\mathbb{Z}$. Together with $10\mathbb{Z}\cap15\mathbb{Z} \subseteq 30\mathbb{Z}$, we conclude that $10\mathbb{Z}\cap15\mathbb{Z} = 30\mathbb{Z}$.

5. (a) When $p$ is divided by 4, its remainder is 0, 1, 2, or 3. But $p$ is odd, hence, $p$ is of the form $4k+1$ or $4k+3$ for some integer $k$. Since $p\geq3$, we also need $k$ to be a nonnegative integer.

   (b) When $p$ is divided by 6, its remainder is 0, 1, 2, 3, 4, or 5. But $p$ is odd, hence, $p$ is of the form $6k+1$, $6k+3$, or $6k+5$. We rule out the form $6k+3$ because this would make $p$ a multiple of 3. Hence, $p$ is of the form $6k+1$ or $6k+5$ for some nonnegative integer $k$.

Section 5.7

1. The addition and multiplication tables for $\mathbb{Z}_8$ are listed below. $$\begin{array}{|c||*{8}{c|}}\hline + & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 0 \\ \hline 2 & 2 & 3 & 4 & 5 & 6 & 7 & 0 & 1 \\ \hline 3 & 3 & 4 & 5 & 6 & 7 & 0 & 1 & 2 \\ \hline 4 & 4 & 5 & 6 & 7 & 0 & 1 & 2 & 3 \\ \hline 5 & 5 & 6 & 7 & 0 & 1 & 2 & 3 & 4 \\ \hline 6 & 6 & 7 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 7 & 7 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \end{array} \qquad\qquad \begin{array}{|c||*{8}{c|}}\hline \cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 2 & 0 & 2 & 4 & 6 & 0 & 2 & 4 & 6 \\ \hline 3 & 0 & 3 & 6 & 1 & 4 & 7 & 2 & 5 \\ \hline 4 & 0 & 4 & 0 & 4 & 0 & 4 & 0 & 4 \\ \hline 5 & 0 & 5 & 2 & 7 & 4 & 1 & 6 & 3 \\ \hline 6 & 0 & 6 & 4 & 2 & 0 & 6 & 4 & 2 \\ \hline 7 & 0 & 7 & 2 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array}$$ Only 1, 3, 5, and 7 have multiplicative inverses. In fact,$1^{-1}=1$, $3^{-1}=3$, $5^{-1}=5$, and $7^{-1}=7$.

2. The sum is 9, and the product is 7.

3. From the following computation $$\begin{array}{|c|l|} \hline \mbox{$m$ (mod~7)} & \hfil\mbox{$m^2+1$ (mod~7)} \\ \hline 0 & 0^2+1 = 1 \\ \pm1 & 1^2+1 = 2 \\ \pm2 & 2^2+1 = 5 \\ \pm3 & 3^2+1 = 10 \equiv 3 \\ \hline \end{array}$$ we determine that $m^2+1\not\equiv0$ (mod 7). Hence, $m^2+1$ is not a multiple of 7 for all integers $m$.

4. Both methods give $4^{45}=1$ in $\mathbb{Z}_{11}$.

5. (a) 9

Section 6.1

1. -24pt $\begin{array}[t]{|c||*{6}{c|}} \hline x & 5.7 & \pi & e & -7.2 & -0.8 & 9 \\ \hline \lfloor x \rfloor & 5 & 3 & 2 & -8 & -1 & 9 \\ \lceil x \rceil & 6 & 4 & 3 & -7 &\phantom{-}0 & 9 \\ {[x]} & 6 & 3 & 3 & -7 & -1 & 9 \\ \hline \end{array}$

2. $[0,\infty)$.

Section 6.2

1. $\big[\frac{7}{3},\infty\big)$.

2. Only $g$ is a well-defined function. The image $f(4)$ is undefined, and there are two values for $h(3)$. Hence, both $f$ and $h$ are not well-defined functions.

3. (a) Yes, because no division by zero will ever occur.

4. -24pt $\begin{array}[t]{|c||c|c|c|c|} \hline x & 1 & 2 & 3 & 4 \\ \hline p(x) & 3 & 1 & 2 & 2 \\ \hline \end{array}$ 0.4in $\begin{array}[t]{|c||c|c|c|c|} \hline x & 1 & 2 & 3 & 4 \\ \hline q(x) & 2 & 3 & 1 & 3 \\ \hline \end{array}$

5. (a) 7 (b) 7 (c) 3

Section 6.3

1. (a) No. For example, $f(0)=f(2)=1$.

   (b) Yes, since $g'(x)=3x^2-4x=x(3x-4)>0$ for $x>2$.

2. Because the domain and the codomain are half-open intervals, we need to be careful with the inclusion and exclusion of the endpoints. We can use the graph displayed below on the left.

   We find $f(x) = \frac{3}{2}\,x+\frac{1}{2}$.

3. (a) One-to-one (b) Not one-to-one

4. (a) Not one-to-one (b) One-to-one

5. There are twelve one-to-one functions from $\{1,2\}$ to $\{a,b,c,d\}$. The images of 1 and 2 under them are listed below. $$\begin{array}{|c||*{12}{c|}} \hline & f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 & f_9 & f_{10} & f_{11} & f_{12} \\ \hline\hline 1 & a & a & a & b & b & b & c & c & c & d & d & d \\ \hline 2 & b & c & d & a & c & d & a & b & d & a & b & c \\ \hline \end{array}$$

6. (a) One-to-one (b) Not one-to-one (c) Not one-to-one

Section 6.4

1. (a) Yes! It is not easy to express $x$ in terms of $y$ from the equation $y=x^3-2x^2+1$. However, from its graph, we can tell that the $y$-values cover all the possible real values in the codomain.

   (b) No, because $g(x)\geq1$.

2. (b) Not onto (c) Onto

3. (b) Not onto (c) Onto

4. No, because we have at most two distinct images, but the codomain has four elements.

5. (a) Onto (b) Not onto (c) Not onto

Section 6.5

1. (a) $f_1(A)=\{a,b\}$, $f_1^{-1}(B)=\{2,3,4,5\}$

   (b) $f_2(A)=\{a,c\}$, $f_2^{-1}(B)=\{2,4\}$

   (c) $f_3(A)=\{b,d\}$, $f_3^{-1}(B)=\emptyset$

   (d) $f_4(A)=\{e\}$, $f_4^{-1}(B)=\{5\}$

2. The images of $s$ are tabulated below. $$\begin{array}{|c||*{12}{c|}} \hline x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline s(x) & 7 & 11 & 3 & 7 & 11 & 3 & 7 & 11 & 3 & 7 & 11 & 3 \\ \hline \end{array}$$ (a) $\{3,11\}$ (b) $\{0,3,6,9\}$ (c) $\{3,7,11\}$

3. (a) $[20,26)$; $\{20,23,26\}$ (b) $[-3,-\frac{4}{3}\big)$; $\{-2\}$

4. (a) $\big\{\frac{3}{5},\frac{9}{5},\frac{27}{5}, 3,9,27,15,45,135\big\}$ (b) $\{(-3,2)\}$ (c) $\mathbb{N}\times\{0\}$

5. For a function to be well-defined, each row sum must be 1. For the function to be one-to-one, each column sum must be at most 1. For the function to be onto, each column sum must be at least 1 (hence, no column sum is zero).

6. Let $y\in f(C_1)-f(C_2)$, we want to show that $y\in f(C_1-C_2)$ as well. Since $y\in f(C_1)-f(C_2)$, we know there exists $x\in A$ such that $f(x)=y$. Having $y\in f(C_1)-f(C-2)$ means $y\in f(C_1)$ but $y\notin f(C_2)$. Hence, $x\in C_1$ but $x\notin C_2$. In other words, $x\in C_1-C_2$. This leads to $y=f(x)\in f(C_1-C_2)$. This completes the proof that $f(C_1)-f(C_2) \subseteq f(C_1-C_2)$.

7. $\{0,1,4,9\}$; $\{0,\pm1,\pm2,\pm3\}$.

Section 6.6

1. Only (e) is bijective.

2. Their inverse functions ${f^{-1},g^{-1}}:{(4,7)}\to{(1,3)}$ are defined by $$f^{-1}(x) = \frac{2}{3}\left(x-\frac{ 5}{2}\right), \qquad\mbox{and}\qquad g^{-1}(x) = -\frac{2}{3}\left(x-\frac{17}{2}\right).$$

3. ${g^{-1}}:\to{[4,7]}{[1,3]}$, where $g^{-1}(x) = \cases{ x-3 & if\)4x < 5\(, \cr \textstyle \frac{1}{2}(11-x) & if\)5x7\(. \cr}$

4. ${s^{-1}}:{(-\infty,-3)}\to{\mathbb{R}}$, where $s^{-1}(x) = \frac{1}{2}\, \ln\left(\frac{4-x}{7}\right)$.

5. (a) ${u^{-1}}:{\mathbb{Q}}\to{\mathbb{Q}}$, $u^{-1}(x)=(x+2)/3$

6. The images under ${\alpha^{-1}}:{\{a,b,c,d,e,f,g,h\}}\to {\{1,2,3,4,5,6,7,8\}}$ are given below. $$\begin{array}{|c||*{8}{c|}} \hline x & a & b & c & d & e & f & g & h \\ \hline \alpha^{-1}(x)& 2 & 5 & 8 & 3 & 6 & 7 & 1 & 4 \\ \hline \end{array}$$

Section 6.7

1. Both $f\circ g$ and $g\circ f$ are from $\mathbb{R}$ to $\mathbb{R}$, where $(f\circ g)(x)=15x^2+19$, and $(g\circ f)(x)=75x^2-30x+7$.

2. We do not need to find the formula of the composite function, as we can evaluate the result directly: $f(g(f(0))) = f(g(1)) = f(2) = -5$.

3. (a) ${g\circ f}:{\mathbb{Z}}\to{\mathbb{Q}}$, $(g\circ f)(n)=1/(n^2+1)$

   (b) ${g\circ f}:{\mathbb{R}}\to{(0,1)}$, $(g\circ f)(x)=x^2/(x^2+1)$

4. (a) ${g\circ f}:{\{1,2,3,4,5\}}\to{\{1,2,3,4,5\}}$,

   $\phantom{(a)}$ $(g\circ f)(1)=2$, $(g\circ f)(2)=5$, $(g\circ f)(3)=1$, $(g\circ f)(4)=3$, $(g\circ f)(5)=4$

5. ${g\circ f}:{\mathbb{Z}}\to{\mathbb{Z}}$, $(g\circ f)(n) = \cases{ 3(2n-1) & if\)n0\(, \cr 2n+1 & if\)n < 0\(. \cr}$

6. (a) ${f\circ g}:{\mathbb{Z}}\to{\mathbb{Z}}$, $(f\circ g)(n) = 3-n$

   $\phantom{(a)}$ {(f\circ g)^{-1}}:{\mathbb{Z}}\to{\mathbb{Z}}\), $(f\circ g)^{-1}(n) = 3-n$

   $\phantom{(a)}$ ${f^{-1}:}{\mathbb{Z}}\to{\mathbb{Z}}$, $f^{-1}(n) =2-n$

   $\phantom{(a)}$ ${g^{-1}}:{\mathbb{Z}}\to{\mathbb{Z}}$, $g^{-1}(n) = n-1$

   $\phantom{(a)}$ ${g^{-1}\circ: f^{-1}}{\mathbb{Z}}\to{\mathbb{Z}}$, $(g^{-1}\circ f^{-1})(n) = 3-n$

Section 7.1

1. (a)

   $\begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 6 \end{array} \\ \noalign{\medskip} \begin{array}{c} 1 \\ 2 \\ 3 \\ 6 \end{array} & \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right) \end{array}$

   (b)

   0pt

   (140,60)(-10,-10) (0, 0)(40,0)4 (0,40)(40,0)4 (-10,-20)(20,20)1 (-10,40)(20,20)1 ( 30,-20)(20,20)2 ( 30,40)(20,20)2 ( 70,-20)(20,20)3 ( 70,40)(20,20)3 (110,-20)(20,20)6 (110,40)(20,20)6 ( 0,0)( 1,1) 40 ( 40,0)(-1,1) 40 ( 0,0)( 2,1) 80 ( 40,0)( 1,1) 40 ( 0,0)( 3,1)120 ( 40,0)( 2,1) 80 ( 80,0)(-2,1) 80 (120,0)(-3,1)120 ( 80,0)(-1,1) 40 (120,0)(-2,1) 80 ( 80,0)( 1,1) 40 (120,0)(-1,1) 40

   0.6in

   0pt $\begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 6 \end{array} \\ \noalign{\medskip} \begin{array}{c} 1 \\ 2 \\ 3 \\ 6 \end{array} & \left(\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array}\right) \end{array}$

   (c)

   0pt

   (140,60)(-10,-10) (0, 0)(40,0)4 (0,40)(40,0)4 (-10,-20)(20,20)1 (-10,40)(20,20)1 ( 30,-20)(20,20)2 ( 30,40)(20,20)2 ( 70,-20)(20,20)3 ( 70,40)(20,20)3 (110,-20)(20,20)6 (110,40)(20,20)6 ( 0,0)( 1,1) 40 ( 0,0)( 2,1) 80 ( 40,0)( 1,1) 40 ( 0,0)( 3,1)120 ( 40,0)( 2,1) 80 ( 80,0)( 1,1) 40

   0.6in

   0pt $\begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 6 \end{array} \\ \noalign{\medskip} \begin{array}{c} 1 \\ 2 \\ 3 \\ 6 \end{array} & \left(\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array}\right) \end{array}$

2. (a) $\mbox{domain}=\mbox{image}=\{1,2,3,6\}$.

   (b) $\mbox{domain}=\mbox{image}=\{1,2,3,6\}$.

   (c) $\mbox{domain}=\{1,2,3\}$, $\mbox{image}=\{2,3,6\}$.

3. 0pt

   (220,60)(-10,-10) (0, 0)(40,0)6 (0,40)(40,0)6 (-10,-20)(20,20) 1 (-10,40)(20,20) 1 ( 30,-20)(20,20) 2 ( 30,40)(20,20) 2 ( 70,-20)(20,20) 4 ( 70,40)(20,20) 4 (110,-20)(20,20) 5 (110,40)(20,20) 5 (150,-20)(20,20)10 (150,40)(20,20)10 (190,-20)(20,20)20 (190,40)(20,20)20 ( 0,0)( 1,1) 40 ( 40,0)( 1,1) 40 ( 0,0)( 2,1) 80 ( 0,0)( 3,1)120 ( 40,0)( 3,1)120 ( 0,0)( 4,1)160 ( 40,0)( 4,1)160 ( 0,0)( 5,1)200 ( 80,0)( 3,1)120 (120,0)( 1,1) 40 (120,0)( 2,1) 80 (160,0)( 1,1) 40

   0pt $\begin{array}[t]{cc} & \begin{array}{cccccc} 1 & 2 & 4 & 5 & 10 & 20 \end{array} \\ \noalign{\medskip} \begin{array}{c} 1 \\ 2 \\ 4 \\ 5 \\ 10 \\ 20 \end{array} & \left(\begin{array}{cccccc} 0 & 1 & 1 & 1 &\; 1 \;&\; 1 \\ 0 & 0 & 1 & 0 &\; 1 \;&\; 1 \\ 0 & 0 & 0 & 0 &\; 0 \;&\; 1 \\ 0 & 0 & 0 & 0 &\; 1 \;&\; 1 \\ 0 & 0 & 0 & 0 &\; 0 \;&\; 1 \\ 0 & 0 & 0 & 0 &\; 0 \;&\; 0 \end{array}\right) \end{array}$

4. $\begin{array}[t]{cc} & \begin{array}{cccc} \;\;\;\;\emptyset & \{1\} & \{2\} & \{1,2\} \end{array} \\ \noalign{\medskip} \begin{array}{c} \emptyset \\ \{1\} \\ \{2\} \\ \{1,2\} \end{array} & \left(\begin{array}{cccc} 0 &\;\;0\;&\;\;0&\;\;\;0 \\ 0 &\;\;1\;&\;\;0&\;\;\;1 \\ 0 &\;\;0\;&\;\;1&\;\;\;1 \\ 0 &\;\;1\;&\;\;1&\;\;\;1 \end{array}\right) \end{array}$

Section 7.2

1. (a) Reflexive, symmetric, antisymmetric, and transitive.

   (b) Irreflexive, and symmetric.

   (c) Irreflexive, and transitive.

2. (a) Antisymmetric.

   (b) Reflexive, symmetric, and transitive.

   (c) Irreflexive, symmetric, and transitive.

3. Reflexive, symmetric, and transitive.

4. Antisymmetric, and transitive.

5. Irreflexive, and antisymmetric.

6. Symmetric.

7. (a) $A$ is not reflexive because $(X,X)\notin A$ if $X\neq\emptyset$.

   (b) $A$ is not irreflexive because $(\emptyset,\emptyset)\in A$.

   (c) No. For example, consider $S=\{a,b,c\}$, $X=\{a\}$, $Y=\{b\}$, and $Z=\{a,c\}$. Then $(X,Y)\in A$, $(Y,Z)\in A$, but $(X,Z)\notin A$.

   (d)

   0pt

   (300,60)(-10,-10) (0, 0)(40,0)8 (0,40)(40,0)8 (-10,-20)(20,20)$\emptyset$ (-10, 40)(20,20)$\emptyset$ ( 30,-20)(20,20)$\{a\}$ ( 30, 40)(20,20)$\{a\}$ ( 70,-20)(20,20)$\{b\}$ ( 70, 40)(20,20)$\{b\}$ (110,-20)(20,20)$\{c\}$ (110, 40)(20,20)$\{c\}$ (140,-20)(40,20)$\{a,b\}$ (140, 40)(40,20)$\{a,b\}$ (180,-20)(40,20)$\{a,c\}$ (180, 40)(40,20)$\{a,c\}$ (220,-20)(40,20)$\{b,c\}$ (220, 40)(40,20)$\{b,c\}$ (260,-20)(40,20)$\{a,b,c\}$ (260, 40)(40,20)$\{a,b,c\}$ ( 0, 0)( 0,1) 40 ( 0, 0)( 1,1) 40 ( 0, 0)(5,1)200 ( 0, 0)( 2,1) 80 ( 0, 0)(6,1)240 ( 0, 0)( 3,1)120 (0,0, 280,40) ( 0, 0)( 4,1)160 ( 40, 0)(-1,1) 40 ( 40, 0)( 1,1) 40 ( 40, 0)( 2,1) 80 ( 40, 0)( 5,1)200 ( 80, 0)(-2,1) 80 ( 80, 0)(-1,1) 40 ( 80, 0)( 2,1) 80 ( 80, 0)( 1,1) 40 (120, 0)(-3,1)120 (120, 0)(-1,1) 40 (120, 0)(-2,1) 80 (120, 0)( 1,1) 40 (160, 0)(-1,1) 40 (160, 0)(-4,1)160 (200, 0)(-3,1)120 (200, 0)(-5,1)200 (240, 0)(-6,1)240 (240, 0)(-5,1)200 (280,0, 0,40)

   18pt

   0pt $\quad \begin{array}[t]{cc} & \begin{array}{*{8}{c}} \rotatebox{90}{\)\(} & \rotatebox{90}{\){a}\(} & \rotatebox{90}{\){b}\(} & \rotatebox{90}{\){c}\(} & \rotatebox{90}{\){a,b}\(} & \rotatebox{90}{\){a,c}\(} & \rotatebox{90}{\){b,c}\(} & \rotatebox{90}{\){a,b,c}\(} \end{array} \\ \noalign{\medskip} \begin{array}{c} \emptyset \\ \{a\} \\ \{b\} \\ \{c\} \\ \{a,b\} \\ \{a,c\} \\ \{b,c\} \\ \{a,b,c\} \end{array} & \setlength{\arraycolsep}{7.7pt} \left(\begin{array}{cccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \end{array}$

8. (a) Symmetric.

   (b) Reflexive, and symmetric.

9. (a) Reflexive, antisymmetric, and transitive.

   (b) Reflexive, symmetric, and transitive.

   (c) Symmetric.

10. (a) Reflexive, antisymmetric, and transitive.

    (b) Symmetric.

    (c) Symmetric, and transitive.

11. (a) Reflexive, and transitive.

    (b) Symmetric,

    (c) Reflexive, symmetric, and transitive.

12. (a) Symmetric, and transitive.

    (b) Reflexive, symmetric, and transitive.

    (c) Reflexive, and transitive.

Section 7.3

1. (a) The equivalence classes are of the form $\{3-k,3+k\}$ for some integer $k$. For instance, $[3]=\{3\}$, $[2]=\{2,4\}$, $[1]=\{1,5\}$, and $[-5]=\{-5,11\}$.

   (b) There are three equivalence classes: $[0]=3\mathbb{Z}$, $[1]=1+3\mathbb{Z}$, and $[2]=2+3\mathbb{Z}$.

2. (a) True

   (b) False

   (c) $[\{1,5\}] = \big\{ \{1\}, \{1,2\}, \{1,4\}, \{1,5\}, \{1,2,4\}, \{1,2,5\}, \{1,4,5\}, \{1,2,4,5\} \big\}$

   (d) $[X] = \{(X\cap T)\cup Y \mid Y\in\wp(\overline{T})\}$. In other words, $S\sim X$ if $S$ contains the same element in $X\cap T$, plus possibly some elements not in $T$.

3. (a) Yes, with $[(a,b)] = \{(x,y) \mid y=x+k \mbox{ for some constant\)k\(}\}$. In other words, the equivalence classes are the straight lines of the form $y=x+k$ for some constant $k$.

   (b) No. For example, $(2,5)\sim(3,5)$ and $(3,5)\sim(3,7)$, but $(2,5)\not\sim(3,7)$. Hence, the relation $\sim$ is not transitive.

4. We find $[0] = \frac{1}{2}\,\mathbb{Z} = \{\frac{n}{2} \mid n\in\mathbb{Z}\}$, and $[\frac{1}{4}] = \frac{1}{4}+\frac{1}{2}\,\mathbb{Z} = \{\frac{2n+1}{4} \mid n\in\mathbb{Z}\}$.

Section 7.4

1. The Hasse diagram is shown below.

   (180,230) (80,20)(80, 70)2(0,0)( 0,70)2(-6,5)60 (20,90)(80,-70)2(0,0)( 0,70)2( 6,5)60 (10,90)(80,-70)2(0,0)(80,70)2( 0,1)50 ( 80, 0)(20,20) 1 ( 0, 70)(20,20) 2 ( 80, 70)(20,20) 3 (160, 70)(20,20) 5 (-10,140)(40,20) 6 ( 70,140)(40,20)10 (150,140)(40,20)15 ( 70,210)(40,20)30

2. Let $a\in B$, since $B\subseteq A$, we also find $a\in A$. Since $(A,\preceq)$ is a poset, the relation $\preceq$ on $A$ is reflexive, hence, $a\preceq a$. This shows that $\preceq$ is still reflexive when restricted to $B$. Antisymmetry and transitivity are proved with a similar argument.

3. (b) The Hasse diagram is shown below.

   (180,160) (10,90)(160,0)2(0,1)50 ( 80,20)(-6,5)60 (100,20)( 6,5)60 (160,90, 20,140) ( 20,90, 160,140) ( 80, 0)(20,20)$0$ ( 0, 70)(20,20)$-1$ (160, 70)(20,20)$1$ ( 0,140)(20,20)$-2$ (160,140)(20,20)$2$

4. $B=\big\{\emptyset,\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}\big\}$.

Section 8.2

1. 6.

2. 70.

3. $7\cdot5+7\cdot4+5\cdot4$

4. $4^5$, $4^5-3\cdot4^2$

5. (a) $52^4$ (b) $39^4$ (c) $4\cdot13^4$ (d) $4\cdot48\cdot52^3$ (e) $52^4-48^4$

6. (a) $9\cdot10^3$ (b) $8\cdot9^3$ (c) $9\cdot10^3-8\cdot9^3$ (d) $9\cdot10$

7. (a) $8^6$ (b) $8\cdot7\cdot6\cdot5\cdot4\cdot3$ (c) 0 (d) $8^6-4^6$ (e) $4\cdot8^4$ (f) $7^5$

Section 8.3

1. $62^8$, $P(62,8)$.

2. $P(14,5)$.

3. $p(7,3)\cdot P(10,3) + P(7,3)\cdot P(11,3) + P(10,3)\cdot P(11,3)$.

4. $P(11,7)\cdot3!/7$.

Section 8.4

1. $\binom{6}{3}\binom{8}{3}$.

2. (a) at least 5 (b) at least 7

3. 10.

4. (a) $\binom{14}{4}$ (b) $\binom{14}{4}-\binom{11}{4}$ (c) $\binom{3}{2}\binom{7}{1}\binom{4}{1} +\binom{3}{1}\binom{7}{2}\binom{4}{1} +\binom{3}{1}\binom{7}{1}\binom{4}{2}$

5. (a) $8!$ (b) $\binom{8}{2}\,P(8,2)\, \big[\binom{6}{2}\,P(8,2)+2\cdot7\cdot6\cdot7+7\cdot6\big]$

6. $\binom{16}{7}$.

7. (a) $\binom{52}{5}$ (b) $4 \,\binom{13}{2}\,13^3$ (c) $13\,\binom{4}{2}\binom{12}{3}\,4^3$ (d) $13\,\binom{4}{3}\binom{12}{2}\,4^2$

   (e) $13\,\binom{4}{3}\,12\,\binom{4}{2}$ (f) $10\cdot(4^5-1)$ (g) $4\,\big[\binom{13}{5}-10\big]$ (h) $4\cdot10$

Section 8.5

1. (a) $x^5+5x^4y+10x^3y^2+10x^2y^3+5xy^4+y^5$

   (b) $s^6-6s^5t+15s^4t^2-20s^3t^3+15s^2t^4-6st^5+t^6$

   (c) $a^4+12a^3b+54a^2b^2+108ab^3+81b^4$

2. (a) $\binom{4}{2}=6$ (b) $-\binom{9}{3}\,3^6\left(\frac{2}{5}\right)^3 =-\frac{489888}{125}$ (c) 0 (d) $-\binom{6}{3}\,3^3\left(\frac{5}{7}\right)^3 =-\frac{67500}{343}$

3. $\sum_{k=0}^n \binom{n}{k} r^k = (1+r)^n$

4. (c) $k^2 = 2\binom{k}{2} + \binom{k}{1}$ (d) $\sum_{k=1}^n k^2 = \frac{1}{6}\,n(n+1)(2n+1)$