Graded: 1.7 #8, 1.8 #34
$\bigstar$ 1.7 #8
Various methods of proof are possible. Here are two of them:
Method 1. We argue by contradiction. Suppose that $n$ and $n+2$ are both perfect squares. Then there are integers $a$ and $b$ such that $n=a^2$ and $n+2=b^2$. Therefore, \begin{align*} 2 &= (n+2)-n \\ &= b^2-a^2 \\ &= (b-a)(b+a). \end{align*} Both $b-a$ and $b+a$ are integers, and their product is 2; thus $b-a$ and $b+a$ are either 1 and 2 (in either order) or $-1$ and $-2$ (in either order). In particular, their sum, which is $2b$, is equal to either 3 or $-3$. But $b$ is an integer, so we have arrived at a contradiction. We conclude that $n$ and $n+2$ cannot both be perfect squares. $\blacksquare$
Method 2. We argue by contradiction. Suppose that $n$ and $n+2$ are both perfect squares. In class, we showed that every perfect square can be written in the form $4k$ or $4k+1$, where $k$ is an integer. Thus there are integers $k_1,k_2$ such that $n=4k_1$ or $n=4k_1+1$, and such that $n+2=4k_2$ or $n+2=4k_2+1$. We now consider cases. If $n=4k_1$ and $n+2=4k_2$, then $2=4(k_2-k_1)$, and so $k_2-k_1=\frac 12$. But $k_1,k_2$ are integers, so we have arrived at a contradiction. If $n=4k_1+1$ and $n+2=4k_2+1$, then we arrive at the same contradiction. Finally, if $n=4k_1$ and $n+2=4k_2+1$, or if $n=4k_1+1$ and $n+2=4k_2$, then $n$ and $n+2$ are not of the same parity, which is again a contradiction. We conclude that $n$ and $n+2$ cannot both be perfect squares. $\blacksquare$
1.7 #16
We prove the contrapositive form of the theorem, which states that if neither $m$ nor $n$ is even, then $mn$ is not even.
Suppose that neither $m$ nor $n$ is even; that is, $m$ and $n$ are odd. Then there are integers $k,\ell$ such that $m=2k+1$ and $n=2\ell+1$. We then have \begin{align*} mn &= (2k+1)(2\ell+1) \\ &= 4k\ell+2k+2\ell+1 \\ &= 2(2k\ell+k+\ell)+1. \end{align*} Here $2k\ell+k+\ell$ is an integer, so $mn$ is odd. We have proved the contrapositive, so we have proved the original theorem. $\blacksquare$
1.7 #26
The theorem is stated as a biconditional (“if and only if”), so we must argue in both directions.
First direction: Let $n$ be even. Then there is an integer $k$ such that $n=2k$, so \begin{align*} 7n+4 &= 7(2k)+4 \\ &= 14k+4 \\ &= 2(7k+2). \end{align*} Since $7k+2$ is an integer, $7n+4$ is even.
Second direction: We must show that if $7n+4$ is even, then $n$ is even. Instead, we will show the (equivalent) contrapositive, which states that if $n$ is odd, then $7n+4$ is odd.
Let $n$ be odd. Then there is an integer $k$ such that $n=2k+1$, so \begin{align*} 7n+4 &= 7(2k+1)+4 \\ &= 14k+11 \\ &= 2(7k+5)+1. \end{align*} Since $7k+5$ is an integer, $7n+4$ is odd. $\blacksquare$
1.7 #34
The reasoning cannot be correct, because it concludes that $x=-1$ is a solution, which is not true.
Although each statement implies the next statement, not all of these implications are reversible. In particular, (2) does not imply (1), as shown by the fact that, for $x=-1$, statement (2) is true and (1) is false. From $2x^2-1=x^2$ we can only deduce $\sqrt{2x^2-1}=\pm x$.
Because each statement in the argument does imply the next statement, we do necessarily obtain all solutions of the original equation. However, we may also obtain some values of $x$ that are not solutions of the original equation (these are known as extraneous solutions). In this case, $x=-1$ is an extraneous solution.
1.8 #4
In order to show that $\min(a,\min(b,c))=\min(\min(a,b),c)$, we will show that both sides are equal to the smallest of $a$, $b$, and $c$. The proof is by cases.
Case 1: Suppose $a$ is the smallest of $a,b,c$: that is, $a\le b$ and $a\le c$. Then $\min(b,c)$ is either $b$ or $c$, so $a\le\min(b,c)$; therefore, $\min(a,\min(b,c))=a$. On the other side, $\min(a,b)=a$ and so $\min(\min(a,b),c) = \min(a,c) = a$. We have shown that $$\min(a,\min(b,c))=a=\min(\min(a,b),c).$$
Case 2: Suppose $b$ is the smallest of $a,b,c$: that is, $b\le a$ and $b\le c$. Then $\min(b,c)=b$, so $\min(a,\min(b,c))=\min(a,b)=b$. On the other side, $\min(a,b)=b$, so $\min(\min(a,b),c)=\min(b,c)=b$. We have shown that $$\min(a,\min(b,c))=b=\min(\min(a,b),c).$$
Case 3: Suppose $c$ is the smallest of $a,b,c$. Then we argue as in case 1, reversing the roles of $a$ and $c$.
The cases exhaust all possibilities, and in each case, we have shown that $\min(a,\min(b,c))=\min(\min(a,b),c)$. $\blacksquare$
Remark: The cases are not necessarily mutually exclusive, since two or more of $a,b,c$ could be equal and tied for smallest. However, in a proof by cases, it does not matter whether the cases are mutually exclusive; what matters is whether they exhaust all possibilities.
1.8 #18
Let $r$ be an irrational number. Then $r$ cannot be an integer (since integers are rational), so $r$ is between some two consecutive integers, say, $k$ and $k+1$. Moreover, $r\ne k+\frac 12$ (since $k+\frac 12$ is rational). Thus one of two possibilities occurs: $k<r<k+\frac 12$ or $k+\frac 12<r<k+1$.
If $k<r<k+\frac 12$, then $|r-k|=r-k<\frac 12$, i.e. the distance between $r$ and $k$ is less than $\frac 12$.
If $k+\frac 12<r<k+1$, then $|r-(k+1)|=(k+1)-r<\frac 12$, i.e. the distance between $r$ and $k+1$ is less than $\frac 12$.
Thus, in either case, there is an integer $n$ such that the distance between $r$ and $n$ is less than $\frac 12$.
To show that this integer is unique, we suppose there are two integers, $n_1$ and $n_2$, such that the distance between $r$ and $n_1$ is less than $\frac 12$ and the distance between $r$ and $n_2$ is also less than $\frac 12$. Then, by the triangle inequality (proved in class), we have \begin{align*} |n_1-n_2| &\le |n_1-r| + |r-n_2| \\ &< \frac 12+\frac 12 \\ &= 1. \end{align*} Since $n_1-n_2$ is an integer smaller than 1, it must be 0, i.e. $n_1=n_2$. $\blacksquare$
1.8 #26
To reach nine zeroes, we must have all bits equal at the previous step. That is, the previous configuration must have been nine zeroes or nine ones.
However, there is no configuration from which we can get nine ones, because such a configuration would have to consist of alternating zeroes and ones around the circle. The number of bits around the circle is odd, so that is impossible.
Thus, starting from a position other than nine zeroes or nine ones, we can never reach a position of nine zeroes.
$\bigstar$ 1.8 #34
We argue by contradiction. Suppose $\sqrt[3]2$ is rational. Then there are integers $m,n$ such that $$\sqrt[3]2=\frac mn.$$ Moreover, we may assume that this fraction is in lowest terms, i.e. $m$ and $n$ have no common prime factor.
Cubing both sides and clearing denominators gives $$2n^3 = m^3.$$ The left side is even, so the right side is also even. This implies that $m$ is even (proof by contraposition: if $m$ were odd, then $m^3$ would be odd). Hence, we may write $m=2k$ for some integer $k$. This yields \begin{align*} 2n^3 &= (2k)^3 \\ &= 8k^3, \end{align*} and so $n^3 = 4k^3$. The right side is even, so the left side is also even, making $n$ even by the same reasoning as above. But then $m$ and $n$ have a common factor of 2, which is a contradiction. $\blacksquare$
Remark. This is an adaptation of the proof that $\sqrt 2$ is rational. Similar arguments can be made to show that $\sqrt[k]n$ is always irrational when $n$ is not the $k^{\text{th}}$ power of an integer.
2.1 #7 – see book
2.1 #18
The simplest example is $A=\varnothing$, $B=\{\varnothing\}$.
2.1 #22
Yes: if ${\mathcal P}(A)={\mathcal P}(B)$, then $A=B$.
Proof: Suppose ${\mathcal P}(A)={\mathcal P}(B)$. Note that $A$ is a subset of itself, so $A\in{\mathcal P}(A)$. Therefore, $A\in{\mathcal P}(B)$, which is to say, $A\subset B$. A similar argument (reversing the roles of $A$ and $B$) shows that $B\subset A$. Thus $A=B$. $\blacksquare$
2.1 #41 – see book
2.1 #46
a) If $S\in S$, then, by the definition of $S$, we have $S\not\in S$. This is a contradiction.
b) If $S\not\in S$, then, by the definition of $S$, we have $S\in S$. This is a contradiction.