\documentclass{article}
\usepackage{amssymb}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Created=Thursday, August 25, 2016 21:02:36}
%TCIDATA{LastRevised=Thursday, August 25, 2016 21:05:15}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{CSTFile=40 LaTeX article.cst}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\input{tcilatex}
\begin{document}
We now consider another technique, which is often used in association with
the word \textquotedblleft not\textquotedblright .
\bigskip
\begin{criterion}[Proof by contradiction]
To prove $p\Rightarrow q$, one may assume that the negation of $q$ is true.
Then work forward with the goal of \textquotedblleft
proving\textquotedblright\ a statement that cannot be true. The
justification for this method is given in the truth table labelled
\CustomNote[%
%TCIMACRO{\hyperref{Contradiction Method}{}{}{ContradictionTT}}%
%BeginExpansion
\msihyperref{Contradiction Method}{}{}{ContradictionTT}%
%EndExpansion
]{Note}{%
{}
\par
\begin{example}[Contradiction method]
Show that $p\Rightarrow q$ and $\symbol{126}\left( p\wedge \symbol{126}%
q\right) $ are equivalent.
\par
\begin{proof}[Solution]
The
%TCIMACRO{\hyperref{truth table}{}{}{IfThenTruthTable} }%
%BeginExpansion
\msihyperref{truth table}{}{}{IfThenTruthTable}
%EndExpansion
for $p\Rightarrow q$ appears above. We have
\par
\begin{tabular}{lllll}
$p$ & $q$ & $\symbol{126}q$ & $p\wedge \symbol{126}q$ & $\symbol{126}\left(
p\wedge \symbol{126}q\right) $ \\
T & T & F & F & T \\
T & F & T & T & F \\
F & T & F & F & T \\
F & F & T & F & T%
\end{tabular}%
\par
The statements have the same truth table and so are equivalent.
\end{proof}
\end{example}
}. That truth table shows the equivalence of $p\Rightarrow q$ and $\symbol{%
126}\left( p\wedge \symbol{126}q\right) $.
\end{criterion}
\bigskip
Although it may be used in other situations, there are three main situations
in which contradiction is indicated.
\begin{enumerate}
\item One has a negation in the conclusion.
\item One has an existential quantifier in the conclusion, and construction
fails to yield a proof.
\item One wishes to show a number is the largest or the smallest number in a
set.
\end{enumerate}
\bigskip
Let's see a simple example. We shall use the abbreviations \textquotedblleft
bwoc\textquotedblright\ for \textquotedblleft by way of
contradiction\textquotedblright\ and \textquotedblleft C!\textquotedblright\
for contradiction.
\bigskip
\begin{theorem}
If $a,b$ and $c$ are integers, $a$ divides $b$ but $a$ does not divide $b+c$%
, then $a$ does not divide $c$.
\begin{proof}
The appearance of a negation in the conclusion suggests the use of
contradiction. So assume bwoc that $a$ divides $c$. Since $a$ also divides $%
b $, it is easy to see that $a$ divides $b+c$. C! $\blacksquare $
\end{proof}
\end{theorem}
\bigskip
The proof above reaches a contradiction by proving a statement that negates
a part of the hypothesis. This is a common way of getting a contradiction,
but it is not the only way.
\bigskip
\begin{exercise}
Prove each of the following:
\begin{enumerate}
\item If $x$ is a rational number and $y$ is not a rational number, then $%
x+y $ is not a rational number.
\item If $x$ is a rational number, $x\neq 0$ and $y$ is not a rational
number, then $xy$ is not a rational number.
\item If $m$ is an integer, $n$ is an even integer, and $4$ does not divide $%
mn$, then $m$ is an odd integer.
\end{enumerate}
\end{exercise}
\bigskip
\end{document}