Exercise 4.11

Question

Given $m \in {\mathbb{Z}}$, we say that $m$ is 	extbf{\emph{even}} if $m/2 \in {\mathbb{Z}}$, and $m$ is 	extbf{\emph{odd}} otherwise.
\begin{enumerate}[label=(\alph*)]
\item Show that if $m$ is odd, $m = 2n+1$ for some $n \in {\mathbb{Z}}$.
  [Hint: Choose $n$ so that $n < m/2 < n+1$.]
\item Show that if $p$ and $q$ are odd, so are $p \cdot q$ and $p^n$, for any $n \in {{\mathbb{Z}}_+}$.
\item Show that if $a > 0$ is rational, then $a=m/n$ for some $m,n \in {{\mathbb{Z}}_+}$ where not both $n$ and $m$ are even.
  [Hint: Let $n$ be the smallest element of the set $\left\{x \mid x \in {{\mathbb{Z}}_+} 	ext{ and } x \cdot a \in {{\mathbb{Z}}_+}ight\}$.]
\item \emph{Theorem: $\sqrt{2}$ is irrational.}
\end{enumerate}

Dan Whitman · Accepted Answer

\begin{lemma}\label{lem:intreal:ltleq} If $n,m \in {\mathbb{Z}}$ and $n < m$, then $n+1 \leq m$ and $n \leq m-1$. \end{lemma} \begin{proof} Suppose that $n+1 > m$ so that $n < m < n+1$, which violates Corollary~ ef{cor:intreal:intbet} since $m \in {\mathbb{Z}}$. Thus it has to be that $n+1 \leq m$. From this it immediately follows that $n = n+1-1 \leq m-1$ by simply subtracting 1 from both sides of the previous inequality. \end{proof} \begin{lemma}\label{lem:intreal:even} An integer $m$ is even if and only if $m = 2n$ for some integer $n$. \end{lemma} \begin{proof} $(\Rightarrow)$ Supposing that $m$ is even, then $n = m/2 \in {\mathbb{Z}}$. Then clearly $m = 2n$. $(\Leftarrow)$ Now suppose that $m = 2n$ for some integer $n$. Then clearly $m/2 = n$ is an integer so that $m$ is even by definition. \end{proof} \begin{lemma}\label{lem:intreal:squodd} An integer $a$ is odd if and only if $a^2$ is also odd. \end{lemma} \begin{proof} $(\Rightarrow)$ Suppose that $a$ is odd so that $a = 2n+1$ for some integer $n$ (this is shown in part~(a) below, which does not depend on this lemma). Then \begin{gather*} a^2 = a \cdot a = (2n+1)(2n+1) = 4n^2 + 2n + 2n + 1 = 4n^2 + 4n + 1 = 2\left[2(n^2 + n) ight] + 1 \, \end{gather*} noting that clearly $2(n^2+n)$ is an integer since $n$ is. Hence $a^2$ is odd again by what will be shown in part~(a). $(\Leftarrow)$ We prove this by contrapositive, so suppose that $a$ is not odd so that it must be even. Therefore $a = 2n$ for some integer $n$ by Lemma~ ef{lem:intreal:even}. Then $a^2 = a \cdot a = (2n)(2n) = 4n^2 = 2(2n^2)$ so that $a^2$ is even since clearly $2n^2$ is an integer since $n$ is. Thus $a^2$ is not odd. \end{proof} extbf{Main Problem.} \begin{enumerate}[label=(\alph*)] \item Here we show the converse as well, i.e. we show that $m$ is odd if and only if $m = 2n+1$ for some $n \in {\mathbb{Z}}$. \begin{proof} $(\Rightarrow)$ Suppose that $m$ is odd so that by definition $m/2 otin {\mathbb{Z}}$. It then follows from Exercise~4.9 part~(b) that there is a unique integer $n$ such that $n < m/2 < n+1$. We then have that $2n < m < 2(n+1) = 2n+2$ since obviously $2 > 0$. Hence by Lemma~ ef{lem:intreal:ltleq} we have that $2n + 1 \leq m$ and also $m \leq 2n+2-1 = 2n+1$. Therefore it has to be that $m = 2n+1$ as desired. $(\Leftarrow)$ Now suppose that there is an $n \in {\mathbb{Z}}$ such that $m = 2n+1$. Then we have that \begin{gather*} \frac{m}{2} = \frac{2n+1}{2} = n + \frac{1}{2} \,. \end{gather*} We then clearly have that $n = n+0 < n+1/2 < n+1$ since $0 < 1/2 < 1$ so that $m/2 = n+1/2$ cannot be an integer by Corollary~ ef{cor:intreal:intbet}. Hence $m$ is odd by definition. \end{proof} \item \begin{proof} Suppose that $p$ and $q$ are odd so that $p = 2k+1$ and $q = 2m+1$ for some $k,m \in {\mathbb{Z}}$ by part~(a). We then have that \begin{gather*} p \cdot q = (2k+1)(2m+1) = 4km + 2m + 2k + 1 = 2(2km + m + k) + 1 \end{gather*} so that $p \cdot q$ is odd by what was shown in part~(a) since clearly $2km+m+k \in {\mathbb{Z}}$ by Exercise~4.5 since $k$ and $m$ are integers. Now we show by induction on $n$ that $p^n$ is odd for any $n \in {{\mathbb{Z}}_+}$. First, for $n=1$ we clearly have $p^n = p^1 = p$ is odd by supposition. Then, if we assume that $p^n$ is odd, we have that the product $p^{n+1} = p^n \cdot p$ is odd as well by what was just shown since both $p^n$ and $p$ are odd. This completes the induction. \end{proof} \item \begin{proof} Suppose that $a > 0$ is rational. Then $a = p/q$ for some integers $p$ and $q$. Clearly it cannot be that $q = 0$, and if $q < 0$ then $q = -b$ for some $b \in {{\mathbb{Z}}_+}$. Then we have $a = p/q = p/(-b) = (-p)/b$ so that $ab = -p$. Furthermore, since $a$ and $b$ are both positive, we have that $ab = -p$ is positive by Exercise~4.2 part~(h). Thus clearly $-p \in {{\mathbb{Z}}_+}$ since $p \in {\mathbb{Z}}$. Now, let $X = \left\{x \in {{\mathbb{Z}}_+} \mid a x \in {{\mathbb{Z}}_+} ight\}$. Since we just showed that $b \in {{\mathbb{Z}}_+}$ and $a b = -p \in {{\mathbb{Z}}_+}$ it follows that $b \in X$. Since clearly $X \subset {{\mathbb{Z}}_+}$ and $X$ is nonempty (since $b \in X$), it has a smallest element $n$ by the well-ordering property. Letting $m = an$, we clearly have that $m \in {{\mathbb{Z}}_+}$ since $n \in X$. Then, we have $a = m/n$, noting again that $m,n \in {{\mathbb{Z}}_+}$. To show that not both $m$ and $n$ are even, suppose to the contrary that they \emph{are} both even. Then by Lemma~ ef{lem:intreal:even} we have that $m = 2k$ and $n = 2l$ for some $k,l \in {\mathbb{Z}}$. Clearly then $k = m/2$ and $l = n/2$ so that both $k$ and $l$ are positive by Exercise~4.2 part~(h) since $m$ and $n$ (and $1/2$) are. Hence $k,l \in {{\mathbb{Z}}_+}$. We have $a = m/n = 2k/2l = k/l$ so that $al = k$, which implies that $l \in X$ since $l$ and $al=k$ are both in ${{\mathbb{Z}}_+}$. However, we also have that $l = n/2 < n$ since $n > 0$, which contradicts the fact that $n$ is the smallest element of $X$. Thus it has to be the case that not both $m$ and $n$ are even. \end{proof} \item This is one of the most famous proofs in all of mathematics, and is often used as an example of mathematical proofs since it can be understood by most laymen. \begin{proof} Obviously we take $\sqrt{2}$ to be the unique positive real number such that $(\sqrt{2})^2 = 2$ as was shown to exist in Exercise~4.10. Suppose to the contrary that $\sqrt{2}$ is rational so that $\sqrt{2} = a/b$ for $a,b \in {{\mathbb{Z}}_+}$ where not both $a$ and $b$ are even by part~(c) since $\sqrt{2} > 0$. We therefore have that $2 = (\sqrt{2})^2 = (a/b)^2 = a^2 / b^2$ so that $2b^2 = a^2$. Since $b^2$ is an integer (clearly, since $b$ is and $b^2 = b \cdot b$) it follows from Lemma~ ef{lem:intreal:even} that $a^2$ is even. This means that $a$ itself is even by Lemma~ ef{lem:intreal:squodd}. Hence $a = 2n$ for some integer $n$ so that $a^2 = (2n)^2 = 4n^2$. From before, we then have $2b^2 = a^2 = 4n^2$ so that clearly $b^2 = 2n^2$, from which it follows as before that $b^2$ and therefore $b$ itself is even by Lemmas~ ef{lem:intreal:even} and ef{lem:intreal:squodd}. However, this is a contradiction since we previously established that $a$ and $b$ cannot both be even! So it has to be that $\sqrt{2}$ is not rational and is therefore irrational as desired. \end{proof} \end{enumerate}

Exercise 4.11

Answers

Comments

Exercise 4.11

Answers

Comments

Add answer