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:

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:


\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:


% \\ 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}
    \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:} ...

\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 ...
    \item Say [...].  Then ...
    \item Say [...].  Then ...
  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:
           &&    (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}

\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:
    \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:} ...

\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:} ...