Solow_reading_assignment_chapter_9.tex

\activitytitle{Reading assignment Chapter 9}{Due on Tuesday, October 31.  20 points}

Read Chapter 9 in the book by Daniel Solow.
It is about proof by contradiction.
We have seen a few examples of this in class, in this form:  If you want to prove that the logical statement $P$ is true, pretend for a minute that $\lnot P$ is true, and make a series of logical deductions that lead to a statement you know is false.  Then you know that $\lnot P$ is false, and so $P$ is true.

Chapter 9 is mostly about proving implications like $P \to Q$.
Recall that in a direct proof, you suppose that $P$ is true and make a series of logical deductions to show that $Q$ is true.
We have discussed the contrapositive method in class, where you suppose that $\lnot Q$ is true and make a series of deductions to show that $\lnot P$ is true.  
In both cases, you are trying to show that it cannot happen that $P$ is true and $\lnot Q$ is true at the same time.
One way to look at proof by contradiction is that you pretend for a minute that $P \wedge \lnot Q$ is true and make a series of logical deductions that lead to a false statement, so you know that $P \wedge \lnot Q$ is false.
The beauty of this method is that you have two statements to work forward from: $P$ and $\lnot Q$.
The downside is that you can't work backward; you are trying to argue toward a false statement, and you don't know for sure what that is.

Note that in doing a proof of $P \to Q$ by contradiction, you will need to negate $\lnot Q$, and when $Q$ has quantifiers you will need to be extra careful.

\vspace{0.1in}
\noindent
{\bf Specific requirements}
\vspace*{-0.15in}

\begin{itemize}
\item Write a defintion of what a ``contradiction'' is from your reading of the chapter.

\item In Section 9.4, please completely rewrite the proof of proposition 14 in your own words and with your own structure.
The next two pages have an analysis of proof, but instead of reading that, work through the proof on your own and make sense of it.  Be patient, get it done.

\item Do exercise 9.2.  In every case, explicitly write out $P$ and $Q$ and then $P$ and $\lnot Q$ to answer the question.

\item Prove the result in exercise 9.3.  Identify $P$ and $Q$ and $\lnot Q$ and work from $P$ and $\lnot Q$ to arrive at a false statement.  Ignore (a) and (b).

\item Do exercise 9.7 in this way.
Identify $P$ and $Q$ and describe how you would use the ``construct'' and ``choose'' methods to do a direct proof.
Then, write out $\lnot Q$ and describe how you would do a proof by contradiction.

\item Do exercise 9.11 as a proof by contradiction.

\item Do exercise 9.15 as a proof by contradiction.

\item Do exercise 9.23 by once again identifying $P$, $Q$, and $\lnot Q$ and then reading the proof.

\item At the end, tally up how much time you have spent on this chapter.
Write this number in your notebook.
Bring your notebook to class and turn it in for grading.
\end{itemize}

\noindent
{\bf General comments}

Set yourself up in a place where you won't be disturbed.
Read slowly, and write notes in your own words that reflect your understanding of the material.