\documentclass[12pt]{article}
\title{Tips for Writing Proofs}
\author{Dr. Holmes}
\begin{document}
\maketitle
Always be careful to distinguish between statements you want to prove
(``goals'') and statements you know are true or can assume are true in
the current part of your proof (``hypotheses'', ``premises'' or
``assumptions'' -- these words all mean the same thing, but I might
use any of them so I'm listing all of them).
The logical form of a sentence, whether it is a goal or an assumption,
can give you guidance as to what to do next. So it's a good idea to
work on recognizing the logical forms of statements. Sometimes it is
necessary to paraphrase an English sentence to make its logical form
more obvious before you can apply these guidelines.
\section{Conjunction}
Sentences in ``and'', whether hypotheses or goals, are refreshingly
simple to deal with. To prove ``$P$ and $Q$'', prove $P$, then prove $Q$
(just break it apart). If you can assume ``$P$ and $Q$'', you can assume
$P$, and you can assume $Q$.
\section{Implication}
Always carefully distinguish between ``If $P$, then $Q$'' (or, equivalently,
``$P$ implies $Q$'', ``$Q$ if $P$'', and other variants) and ``$P$ and $Q$'';
these are totally different, but students seem to confuse them.
Also, don't confuse ``If $P$, then $Q$'' with either ``If $Q$, then
$P$'' (its converse) or ``If $\neg P$, then $\neg Q$'' (its inverse).
The converse and the inverse are equivalent to each other, but not to
the original implication. Of course, the contrapositive ``If $\neg
Q$, then $\neg P$'' is equivalent to the original implication.
To prove a sentence of the form ``If $P$, then $Q$'', the strategy is to
add $P$ as a new assumption, and show that $Q$ can be proved with this
new assumption: if your goal is ``If $P$, then $Q$'', add $P$ as an
assumption and your new goal is $Q$.
If you don't like the assumption of $P$, think of it this way: our
goal is to prove ``If $P$, then $Q$''. Either $P$ is false or it is
true. If $P$ is false, ``If $P$, then $Q$'' is true (look at the
truth table for $\rightarrow$), so we have nothing to do. If $P$ is
true, we need $Q$ to be true, so we need to show that we can prove $Q$
if we assume $P$ (and we don't need to worry about the easy case where
$P$ is false).
An assumption of the form ``If $P$, then $Q$'' can be used as follows:
suppose that we have assumed or proved $P$ and $P \rightarrow Q$: we
can conclude $Q$. This is called the rule of {\em modus ponens\/} in
traditional logic.
Remember that $P \rightarrow Q$ is equivalent to $\neg Q \rightarrow \neg P$
(an implication is equivalent to its contrapositive.
This means that we can also prove ``If $P$, then $Q$'' by assuming $\neg Q$ and
using this assumption to deduce $\neg P$.
It also means that if we have proved or assumed $P \rightarrow Q$ and
$\neg Q$, we can conclude $\neg P$: this is the classical logical rule
called {\em modus tollens\/}.
\section{Disjunction}
To prove a statement of the form ``$P$ or $Q$'', show that if $P$ is
false, $Q$ must be true, or show that if $Q$ is false, $P$ must be
true. Of course, it is also sufficient to show just that $P$ is true,
or just that $Q$ is true!
To use a hypothesis of the form ``$P$ or $Q$'', use the method of
proof by cases: if we know ``$P$ or $Q$'', and we can show that
assuming $P$ leads to a conclusion $R$, and we can show that assuming
$Q$ leads to the same conclusion $R$, we can draw the conclusion $R$.
It is useful to remember that for any statement $P$, we have ``$P$ or
not $P$'' (the law of excluded middle). Statements of this kind are often
useful as the basis for a proof by cases.
\section{Negation}
To prove $\neg P$, assume $P$ and show that a contradiction follows.
Since any statement $P$ is equivalent to $\neg\neg P$ (the law of
double negation), this means that we can prove any statement by the
method of proof by contradiction: to prove $P$, assume $\neg P$ and
show that a contradiction follows.
Assumptions or theorems of the form $\neg P$ can be used in two ways:
if you have proved or assumed both $P$ and $\neg P$ you have arrived at
a contradiction! In addition, if you have a premise $P \vee Q$ and you
show $\neg P$, you can conclude $Q$ (this has already been mentioned
above under disjunction).
\section{Biconditional}
To prove ``$P$ if and only if $Q$'', prove ``If $P$ then $Q$'', then
prove ``If $Q$ then $P$''. Since either or both of these can be
replaced by its contrapositive, there are four different ways to prove
a biconditional -- but notice that in any case the proof of a
biconditional has two parts, one for each direction of implication.
\section{Universal Quantifier}
To prove any statement of the form ``for any $x \in A$, $Px$''
start out by saying ``Let $x$ be an arbitary element of $A$'' then
prove $Px$.
If you have a theorem or assumption ``for any $x \in A$, $Px$'', and
$t$ is any element of $A$ at all, you can conclude $Pt$ ($Pt$ is the result of
replacing all references to $x$ in the possibly quite complicated
sentence $Px$ with references to $t$).
\section{Existential Quantifier}
To prove any statement of the form ``there is an $x \in A$ such that
$Px$'', prove $Pt$ for some particular object $t \in A$ ($Pt$ is again
the result of replacing all references to $x$ in the possibly quite
complicated sentence $Px$ with references to $t$).
If you have a theorem or assumption $Pt$, with $t \in A$, you can draw
the conclusion ``there is $x \in A$ such that $Px$''.
\section{Definitions:}
If a defined concept appears in a goal you are trying to prove or a
theorem or assumption you are trying to use, and the statement's
logical form doesn't give you any help, you can use the definition to
expand the statement.
You can see all these ideas in full symbolic form in the section on
``natural deduction'' in my current M387 notes. This is not to say I
recommend trying to look them up there.
Updated versions of this document will contain sample proofs with
discussion of the application of these rules: the proof that a
function with an inverse is a bijection would be a good example, and perhaps also the proofs that the compositions of injections are injections and the compositions of bijections are bijections.
\end{document}