Skip to main content
\(\newcommand{\versionNum}{$4.0$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section3.3Indirect proofs: contradiction and contraposition

Suppose we are trying to prove that all thrackles are polycyclic  1 . A direct proof of this would involve looking up the definition of what it means to be a thrackle, and of what it means to be polycyclic, and somehow discerning a way to convert whatever thrackle's logical equivalent is into the logical equivalent of polycyclic. As happens fairly often, there may be no obvious way to accomplish this task. Indirect proof takes a completely different tack. Suppose you had a thrackle that wasn't polycyclic, and furthermore, show that this supposition leads to something truly impossible. Well, if it's impossible for a thrackle to not be polycyclic, then it must be the case that all of them are. Such an argument is known as proof by contradiction.

Quite possibly the sweetest indirect proof known is Euclid's proof that there are an infinite number of primes.

Proof

If you are working on proving a UCS and the direct approach seems to be failing you may find that another indirect approach, proof by contraposition, will do the trick. In one sense this proof technique isn't really all that indirect; what one does is determine the contrapositive of the original conditional and then prove that directly. In another sense this method is indirect because a proof by contraposition can usually be recast as a proof by contradiction fairly easily.

The easiest proof I know of using the method of contraposition (and possibly the nicest example of this technique) is the proof of the lemma we stated in Section 1.6 in the course of proving that \(\sqrt{2}\) wasn't rational. In case you've forgotten we needed the fact that whenever \(x^2\) is an even number, so is \(x\).

Let's first phrase this as a UCS. \begin{equation*} \forall x \in \Integers, \; x^2 \, \mbox{even} \; \implies x \, \mbox{even} \end{equation*}

Perhaps you tried to prove this result earlier. If so you probably came across the conceptual problem that all you have to work with is the evenness of \(x^2\) which doesn't give you much ammunition in trying to show that \(x\) is even. The contrapositive of this statement is: \begin{equation*} \forall x \in \Integers, \; x \, \mbox{not even} \; \implies x^2 \, \mbox{not even} \end{equation*}

Now, since \(x\) and \(x^2\) are integers, there is only one alternative to being even — so we can re-express the contrapositive as \begin{equation*} \forall x \in \Integers, \; x \, \mbox{odd} \; \implies x^2 \, \mbox{odd} . \end{equation*}

Without further ado, here is the proof:

Proof

Let's have a look at a proof of the same statement done by contradiction.

Proof

The main problem in applying the method of proof by contradiction is that it usually involves “cleverness.” You have to come up with some reason why the presumption that the theorem is false leads to a contradiction — and this may or may not be obvious. More than any other proof technique, proof by contradiction demands that we use drafts and rewriting. After monkeying around enough that we find a way to reach a contradiction, we need to go back to the beginning of the proof and highlight the feature that we will eventually contradict! After all, we want it to look like our proofs are completely clear, concise and reasonable even if their formulation caused us some sort of Gordian-level mental anguish.

We'll end this section with an example from Geometry.

Proof
Exercise3.3.4

Where should we place the point \(B'\) in order to create a triangle \(\triangle AB'C\) having greater area than any triangle such as \(\triangle ABC\) which is not isosceles?

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

Subsection3.3.1Exercises

  1. Prove that if the cube of an integer is odd, then that integer is odd. \hint{The best hint for this problem is simply to write down the contrapositive statement. It is trivial to prove!}

  2. Prove that whenever a prime \(p\) does not divide the square of an integer, it also doesn't divide the original integer. (\(p \nmid x^2 \; \implies \; p \nmid x\)) \hint{The contrapositive is \((p \divides x) \; \implies \; (p \divides x^2)\).}

  3. Prove (by contradiction) that there is no largest integer. \hint{Well, if there was a largest integer — let's call it \(L\) (for largest) — then isn't \(L+1\) an integer, and isn't it bigger? That's the main idea. A more formal proof might look like this:

    Proof
    }

  4. Prove (by contradiction) that there is no smallest positive real number. \hint{Assume there was a smallest positive real number — might as well call it \(s\) (for smallest) — what can we do to produce an even smaller number? (But be careful that it needs to remain positive — for instance \(s-1\) won't work.)}

  5. Prove (by contradiction) that the sum of a rational and an irrational number is irrational. \hint{Suppose that x is rational and y is irrational and their sum (let's call it z) is also rational. Do some algebra to solve for y, and you will see that y (which is, by presumption, irrational) is also the difference of two rational numbers (and hence, rational — a contradiction.) }

  6. Prove (by contraposition) that for all integers \(x\) and \(y\), if \(x+y\) is odd, then \(x\neq y\). \hint{Well, the problem says to do this by contraposition, so let's write down the contrapositive: \begin{equation*} \forall x, y \in \Integers, \; x=y \, \implies \, x+y \; \mbox{is even} . \end{equation*} But proving that is obvious! }

  7. Prove (by contraposition) that for all real numbers \(a\) and \(b\), if \(ab\) is irrational, then \(a\) is irrational or \(b\) is irrational. \hint{The contrapositive would be: \begin{equation*} \forall a,b \in \Reals, \; (a \in \Rationals \land b \in \Rationals) \, \implies ab \in \Rationals. \end{equation*} Wow! Haven't we proved that before?}

  8. A Pythagorean triple is a set of three natural numbers, \(a\), \(b\) and \(c\), such that \(a^2 + b^2 = c^2\). Prove that, in a Pythagorean triple, at least one of \(a\) and \(b\) is even. Use either a proof by contradiction or a proof by contraposition. \hint{If both \(a\) and \(b\) are odd then their squares will be 1 mod 4 — so the sum of their squares will be 2 mod 4. But \(c^2\) can only be 0 or 1 mod 4, which gives us a contradiction.}

  9. Suppose you have 2 pairs of positive real numbers whose products are 1. That is, you have \((a,b)\) and \((c,d)\) in \(\Reals^2\) satisfying \(ab=cd=1\). Prove that \(a \lt c\) implies that \(b > d\). \hint{

    Proof
    }