# PS05: Proofs

Due Mon 4/13 @ 1:30pm.

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.

• It often takes many attempts before you figure out how to prove something correctly.
• Correctness is not our only criterion, either; clarity is also important. Sometimes, you figure out a way to prove something correctly, but the proof you invent is a big mess. It often takes more work, and perhaps an attempt with a completely different proof technique, to find a proof that is correct and clear.
• The correct order of argument in a proof is sometimes the reverse of the order of the work you used to find the proof. This is discussed briefly on page 460, under the heading “Fallacy: Proving True”.
• It often takes many drafts before you figure out how to write up a proof clearly.

Okay, here's the assignment...

Do these problems from the book, listed on pages 439–440.

1. 4.36
2. 4.38
3. 4.40
4. 4.47
5. 4.48
6. 4.51
7. 4.56
8. 4.61

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}