Many of these problems involve writing proofs. Before we jump into the problems, here are a few reminders:
You should explicitly state the claim before you begin a proof. This is true not only in writing up a proof, but also when planning the proof. If you don't have a clear idea of the claim you're trying to prove, it's much harder to figure out how to prove it.
At the bottom of the page, there is example LaTeX code showing how to correctly format your answers to this problem set. Among other things, it includes formatting of claims and proofs, in a style very similar to that used throughout Chapter 4 in the book.
Okay, here's the assignment...
Do these problems from the book, listed on pages 439–440.
Below is an example of how to typeset a set of proofs really nicely for this problem set. You can copy and paste it directly into your own LaTeX source document, or download complete starter code and rendered PDF. There are even some hints for the problem set in here; the code below is copied directly from my solution set.
In the preamble (the part before the \begin{document}
), you'll want to include some extra packages and definitions:
\usepackage{amsfonts,amssymb} \def\Z{\mathbb{Z}} % Set of integers \def\Q{\mathbb{Q}} % Set of rationals \def\R{\mathbb{R}} % Set of reals \def\limp{\Rightarrow} % Logical implication \def\mod{\,\%\,} % Format mod as a percent sign, with nice spacing % This overrides the default definition of \mod.
Then, in the body of the document, you'll want something like this:
\begin{enumerate} % \\ at the end of the line creates a single linebreak, not a new paragraph. % Right -vv- here \item \qnum{4.36} \textbf{Claim:} $x,y \in \Q \limp x-y \in \Q$. \\ \textbf{Proof:} If $x$ and $y$ are both rational, then ... \item \qnum{4.38} \begin{itemize} \item The claim that ``if $xy$ and $x$ are both rational, then $y$ is too'' is \textbf{Tralse}. \textbf{Proof:} ... \item The claim that ``if $x-y$ and $x$ are both rational, then $y$ is too'' is \textbf{Falrue}. \textbf{Proof:} ... \end{itemize} \item \qnum{4.40} \textbf{Claim:} For all integers $n$, $3 \nmid (n^2+1)$. \\ \textbf{Proof:} Let $n$ be some integer. We proceed by cases, depending on ... \begin{itemize} \item Say [...]. Then ... \item Say [...]. Then ... \end{itemize} Having exhausted all cases for integers $n$, we conclude that the claim is true for all integers $n$. \item \qnum{4.47} \textbf{Claim:} for $x,y \in \R^{\ge 0}$, we have $\sqrt{xy} \le (x+y)/2$. \\ \textbf{Proof:} We know that $r^2 \ge 0$ for any real number $r$, and therefore: \begin{alignat*}{2} && (x-y)^2 &\ge 0 \\ \limp \; && \ldots &\ge \ldots \\ \intertext{I can insert a comment in the middle of a derivation like so...} \limp \; && \ldots &\ge \ldots \\ \limp \; && (x+y) / 2 &\ge \sqrt{xy} \end{alignat*} \item \qnum{4.48} \textbf{Claim:} for $x,y \in \R^{\ge 0}$, $\sqrt{xy} = (x+y)/2 \, \iff \, x = y$. \\ \textbf{Proof:} We prove both directions of the mutual implication separately: \begin{itemize} \item \textit{Sub-claim:} for $x,y \in \R^{\ge 0}$, $\sqrt{xy} = (x+y)/2 \, \limp \, x = y$. \\ \textit{Proof:} ... \item \textit{Sub-claim:} for $x,y \in \R^{\ge 0}$, $x = y \, \limp \, \sqrt{xy} = (x+y)/2$. \\ \textit{Proof:} ... \end{itemize} \item \qnum{4.51} \textbf{Claim:} For $n \in \Z^{\ge 0}$, if $n \mod 4 \in \{2,3\}$, then $n$ is not a perfect square. \\ \textbf{Proof:} We prove the contrapositive. If $n$ is a perfect square, then ... \item \qnum{4.56} \textbf{Claim:} For $x,y \in \R^{> 0}$, if $x^2-y^2 = 1$, then $x$ or $y$ (or both) is not an integer. \\ \textbf{Proof:} Say that $x^2-y^2 = 1$, and let us assume, for the sake of contradiction, that $x$ and $y$ are both positive integers. Then ... % ... blah blah blah ... ... this is a contradiction, and therefore $x$ and $y$ cannot both be integers. \item \qnum{4.61} \textbf{False claim:} If $xy$ is rational, then $x$ and $y$ are rational. \\ \textbf{Disproof:} ... \end{enumerate}