\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}[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}