Graded: 2.1 #38, 2.3 #40

2.1 #30

If $A\times B=\varnothing$, then either $A=\varnothing$ or $B=\varnothing$.

$\bigstar$ 2.1 #38

The statement we wish to prove can be stated more clearly as: “If $A\ne B$, where $A,B\ne\varnothing$, then $A\times B\ne B\times A$.”

Suppose $A\ne B$, where $A,B\ne\varnothing$. Then either there is some $a\in A$ such that $a\not\in B$, or there is some $b\in B$ such that $b\not\in A$. Without loss of generality, let us assume there is some $a\in A$ such that $a\not\in B$. Let $b$ be any element of $B$. Then $(a,b)\in A\times B$, but $(a,b)\not\in B\times A$. This shows that $A\times B\ne B\times A$. $\blacksquare$

2.2 #2

a) $A\cap B$

b) $A-B$ or $A\cap\overline B$

c) $A\cup B$

d) $\overline A\cup\overline B$ or $\overline{A\cap B}$

2.2 #16

a) Let $x\in A\cap B$. Then, by definition, $x\in A$ and $x\in B$. In particular, $x\in A$. This shows that $A\cap B\subseteq A$.

b) Let $x\in A$. Then it is true that $x\in A\vee x\in B$, so, by definition, $x\in A\cup B$. This shows that $A\subseteq A\cup B$.

c) Let $x\in A-B$. Then, by definition, $x\in A$ and $x\not\in B$. In particular, $x\in A$. This shows that $A-B\subseteq A$.

d) \begin{align*} A\cap(B-A) &= \{x ~|~ x\in A\text{ and }x\in B-A\} \\ &= \{x ~|~ x\in A\text{ and }x\in B\text{ and }x\not\in A\} \\ &= \varnothing, \end{align*} because it is impossible for an element $x$ to satisfy both $x\in A$ and $x\not\in A$.

e) We will show that $A\cup(B-A)\subseteq A\cup B$ and that $A\cup B\subseteq A\cup(B-A)$.

If $x\in A\cup(B-A)$, then either $x\in A$ or $x\in B-A$. In the first case, $x\in A\implies x\in A\cup B$. In the second case, $x\in B-A\implies x\in B\implies x\in A\cup B$. In either case, $x\in A\cup B$. This shows that $A\cup(B-A)\subseteq A\cup B$.

Going the other way, suppose $x\in A\cup B$. Then either $x\in A$ or $x\in B$. Now we consider two cases: either $x\in A$ or $x\not\in A$. If $x\in A$, then $x\in A\cup(B-A)$. If $x\not\in A$, then $x\in B$, so $x\in B-A$; thus $x\in A\cup(B-A)$. In either case, $x\in A\cup(B-A)$. This shows that $A\cup B\subseteq A\cup(B-A)$.

2.2 #40

Yes, $\oplus$ is associative. We demonstrate this with a membership table:

$$\begin{array}{ccc|cccc} A & B & C & B\oplus C & A\oplus(B\oplus C) & A\oplus B & (A\oplus B)\oplus C \\ \hline 1&1&1&0&1&0&1 \\ 1&1&0&1&0&0&0 \\ 1&0&1&1&0&1&0 \\ 1&0&0&0&1&1&1 \\ 0&1&1&0&0&1&0 \\ 0&1&0&1&1&1&1 \\ 0&0&1&1&1&0&1 \\ 0&0&0&0&0&0&0 \end{array}$$

The columns for $A\oplus(B\oplus C)$ and $(A\oplus B)\oplus C$ are the same, showing that $$A\oplus(B\oplus C)=(A\oplus B)\oplus C$$ is a valid identity.

Remark. This shows that we can write $A\oplus B\oplus C$ without parentheses and not create an ambiguity. However, the description of $A\oplus B\oplus C$ is not immediately intuitive: it consists of all elements that belong to exactly 1, or all 3, of the sets $A,B,C$.

2.3 #6

a) D: $\mathbb Z^+\times\mathbb Z^+$, R: $\mathbb Z^+$

b) D: $\mathbb Z^+$, R: {1,2,3,4,5,6,7,8,9}

c) D: { bit strings }, R: $\mathbb Z$

d) D: $\mathbb Z^+$, R: $\mathbb Z^+$

e) D: { bit strings }, R: {“”,1,11,111,1111,…}

2.3 #20

a) $f(n) = n+1$

b) $f(n) = \lfloor n/2 \rfloor$

c) $f(n) = n$

d) $f(n) = 7$

2.3 #22

a) Yes: for every $y$, there is exactly one $x$ for which $-3x+4=y$ (given by $x=(4-y)/3$)

b) No; not injective (since $f(1)=f(-1)$), and also not surjective (since there is no $x$ for which $f(x)=8$).

c) No; not a function on the domain $\mathbb R$, since $f(-2)$ is undefined.

d) Yes: for every $y$, there is exactly one $x$ for which $x^5+1=y$ (given by $x=(y-1)^{1/5}$)

2.3 #24

We use the definitions on p. 143.

Let $f:\mathbb R\to\mathbb R$ and let $f(x) > 0$ for all $x\in\mathbb R$. Let $g(x)=\dfrac 1{f(x)}$.

Suppose $f$ is strictly increasing. Then, given $x,y\in\mathbb R$ such that $x < y$, we have $$f(x) < f(y).$$ Dividing both sides by $f(x)f(y)$, we then have $$\frac 1{f(y)} < \frac 1{f(x)},$$ i.e. $g(x) > g(y)$. This shows that $g$ is strictly decreasing.

Conversely, suppose $g$ is strictly decreasing. Then, given $x,y\in\mathbb R$ such that $x < y$, we have $g(x) > g(y)$. We can reverse the steps of the previous argument to deduce that $f(x) < f(y)$. This shows that $f$ is strictly increasing. $\blacksquare$

$\bigstar$ 2.3 #40

a) Let $y\in f(S\cup T)$. Then there is some $x\in S\cup T$ such that $f(x)=y$. Either $x\in S$ or $x\in T$. If $x\in S$, then $y\in f(S)$. If $x\in T$, then $y\in f(T)$. Either way, $y\in f(S)\cup f(T)$. This shows that $f(S\cup T)\subseteq f(S)\cup f(T)$.

Going the other way, suppose $y\in f(S)\cup y\in f(T)$. Then either $y\in f(S)$ or $y\in f(T)$. If $y\in f(S)$, then there is some $x\in S$ such that $f(x)=y$. If $y\in f(T)$, then there is some $x\in T$ such that $f(x)=y$. In either case, $x\in S\cup T$ and $f(x)=y$. Therefore, $y\in f(S\cup T)$. This shows that $f(S)\cup f(T)\subseteq f(S\cup T)$.

Since $f(S\cup T)\subseteq f(S)\cup f(T)$ and $f(S)\cup f(T)\subseteq f(S\cup T)$, we conclude that $f(S\cup T) = f(S)\cup f(T)$. $\blacksquare$

b) Let $y\in f(S\cap T)$. Then there is some $x\in S\cap T$ such that $f(x)=y$. In particular, $x\in S$, so $y\in f(S)$, and $x\in T$, so $y\in f(T)$. Thus $y\in f(S)\cap f(T)$. This shows that $f(S\cap T) \subseteq f(S)\cap f(T)$. $\blacksquare$

Remark. It is not necessarily true that $f(S)\cap f(T)\subseteq f(S\cap T)$. Be sure you see why.

2.3 #70

Given two invertible functions $h:A\to B$ and $j:B\to A$, they are inverses of each other if $j\circ h=\iota_A$ and $h\circ j=\iota_B$, where $\iota_X$ stands for the identity function on $X$. This is the test we’ll apply.

Let $f:Y\to Z$ and $g:X\to Y$ be invertible. Let $h$ denote the function $f\circ g:X\to Z$ and let $j$ denote the function $g^{-1}\circ f^{-1}:Z\to X$. Then, for all $x\in X$, we have \begin{align*} j\circ h(x) &= g^{-1}(f^{-1}(f(g(x)))) \\ &= g^{-1}(\iota_Y(g(x))) \\ &= g^{-1}(g(x)) \\ &= \iota_X(x) \\ &= x, \end{align*} so $j\circ h = \iota_X$. A similar argument shows that $h\circ j = \iota_Z$. Thus, $h$ and $j$ are inverses. $\blacksquare$

Remark. Don’t let the fancy notation obscure the ideas. The point is that if $g$ maps $x$ to $y$, and $f$ maps $y$ to $z$, then to get back from $z$ to $x$, we must first apply $f^{-1}$ and then $g^{-1}$. Thus the inverse of $f\circ g$ is $g^{-1}\circ f^{-1}$.

I sometimes explain this to my classes using the metaphor of socks and shoes. When you get dressed, you put on socks first and then shoes. To invert this operation, you take off shoes first, then socks. For the same reason, to invert $f\circ g$, you must invert each function and reverse their order.

2.3 #72

Let $f:A\to B$, where $A$ and $B$ are finite sets such that $|A|=|B|=n$. We may name the elements of $A$: $$A=\{x_1,x_2,\ldots,x_n\}.$$

If $f$ is one-to-one, then $f(x_1),f(x_2),\ldots,f(x_n)$ are $n$ pairwise distinct elements of $B$. Since $B$ has only $n$ elements, every element of $B$ must be $f(x_i)$ for some $i$ (where $1\le i\le n$). Thus $f$ is onto.

If $f$ is not one-to-one, then some two of $f(x_1),f(x_2),\ldots,f(x_n)$ are equal, so the range of $f$ contains at most $n-1$ distinct elements of $B$. Thus $f$ is not onto. By contraposition, if $f$ is onto, then $f$ is one-to-one. $\blacksquare$

Remark. This proof is only valid if $A,B$ are finite sets. In $\S$2.1 #20, you constructed some examples of functions between infinite sets that are one-to-one but not onto or vice versa.

2.4 #12

a) It is true that $0 = -3(0) + 4(0)$.

b) It is true that $1 = -3(1) + 4(1)$.

c) It is true that $(-4)^n = -3(-4)^{n-1} + 4(-4)^{n-2}$.

Proof: \begin{align*} -3(-4)^{n-1} + 4(-4)^{n-2} &= (-3)(-4)(-4)^{n-2} + 4(-4)^{n-2} \\ &= (12+4)(-4)^{n-2} \\ &= (-4)^2(-4)^{n-2} \\ &= (-4)^n. \end{align*}

d) It is true that $2(-4)^n + 3 = -3[2(-4)^{n-1}+3] + 4[2(-4)^{n-2}+3]$. [Proof omitted; similar to (c).]

2.4 #14

There are many possible answers. Here are some:

a) $a_n = a_{n-1}$

b,c) $a_n = a_{n-1} + 2$

d) $a_n = 5a_{n-1}$

e) $a_n = a_{n-1} + 2n – 1$ or $a_n = (\sqrt{a_{n-1}} + 1)^2$

f) $a_n = a_{n-1} + 2n$

g) $a_n = a_{n-1} + 1 – (-1)^{n-1} + (-1)^n$ or $a_n = a_{n-1} + 1 + 2(-1)^n$

h) $a_n = na_{n-1}$

2.4 #34

a) $(1-1)+(1-2)+(2-1)+(2-2)+(3-1)+(3-2) = 3$

This is not quite like the similar sum we did in class, because not everything cancels.

b) 78

c) $\displaystyle \sum_{i=1}^3\sum_{j=0}^2 j = \sum_{i=1}^3 (0+1+2) = \sum_{i=1}^3 3 = 3(3) = 9$

d) \begin{align*} \sum_{i=0}^2\sum_{j=0}^3 i^2j^3 &= \sum_{i=0}^2 i^2(0^3+1^3+2^3+3^3) \\ &= \sum_{i=0}^2 36i^2 \\ &= 36(0^2+1^2+2^2) \\ &= 180 \end{align*}

2.4 #36

The sum telescopes:

\begin{align*} \sum_{k=1}^n \frac 1{k(k+1)} &= \sum_{k=1}^n \left[ \frac 1k-\frac 1{k+1} \right] \\ &= \frac 11 – \frac 12 + \frac 12 – \frac 13 + \frac 13 – \frac 14 + \cdots + \frac 1n – \frac 1{n+1} \\ &= 1 – \frac 1{n+1}. \end{align*}

Note that the answer is in terms of $n$, not $k$.