Skip to main content
Mathematics LibreTexts

0.2: Introduction to Proofs/Contradiction

  • Page ID
    10958
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)

    In this section, we will explore different techniques of proving a mathematical statement "If \(p\) then \(q\)." (\(p \to q\)).

    From  DR. THI DINH'S PROOF WRITING HANDBOOK THIS BIBLE:

     

    In the beginning...

    Let \(P\) and \(Q\) be statement variables. When needed, suppose that P = P(x) depends on a variable x. The symbol "\(\forall\)" means "for all" or "for any". The symbol \(\exists\) means "there exists". 

     

    Type of statement What must we do to prove that it is true

    (1) If \(P\), then \(Q\)

    (2) \(\forall P\), \(Q\)

    Suppose that \(P\) is true.

    Prove that \(Q\) is true.

    (3) \(\exists x P(x) \) such that \(Q\)

    Choose \(x\) so that \(P(x)\) is true. Prove that \(Q\) is true.

    Note: You need not explain how you find \(x\).

    The first (and only) commandment

    To prove that a statement is false, thou shalt write out the negation of the statement and prove that.

    The five cardinal sins

    • When proving any of the types of statements (1), (2), or (3):

    1. Thou shalt not: suppose that \(Q\) is true.

    2. Thou shalt not: overuse symbols and violate the rules of English grammar. You must write in full sentences and use symbols correctly.

    • When proving a statement of the form (2) \(P, Q\):

    3. Thou shalt not: choose or exhibit an example in place of a proof.

    • When proving a statement of the form (3) "\(\forall x P(x)\) such that \(Q \):

    4. Thou shalt not: attempt to construct all possible \(x\) so that \(P(x)\) and \(Q\) are true.

    • When proving a statement by contradiction:

    5. Thou shalt not: claim a contradiction has been reached without explanation. You must clearly identify the contradiction being made by making a statement of the form "\(P\) and NOT \(P\), which is a contradiction".

    Direct Proof

    In this technique, we shall assume \(p\) and show that \(q\) is true.

    Theorem \(\PageIndex{1}\)

    Let \(n\) be an integer. If \(n\) is even then \(n^2\) is even.

    Proof

    Assume that \(n\) is even. Then \(n=2m\) for some integer \(m \).

    Consider \(n^2=(2m)^2=4m^2=2(2m^2).\) Since \( m \) is an integer, \( (2m^2)\) is an integer.

    Thus \(n^2\) is even.

    Example \(\PageIndex{1}\)

    Show that for all integers \( n\), if \(n\) is odd then \(n^2\) is odd.

    Answer

    Assume that \(n\) is odd. Then \(n=2m+1\) for some integer \(m \).

    Consider \(n^2=(2m+1)^2=4m^2+4m+1=2(2m^2+2m)+1.\)

    Since \( m \) is an integer, \( (2m^2+2m)\) is an integer.

    Thus \(n^2\) is odd.

    Proof by Contrapositive

    In this technique, we shall assume \(\neg  p\) and show that \( \neg q\) is true.

    Theorem \(\PageIndex{2}\)

    Let \(n\) be an integer. If \(n^2\) is even then \(n\) is even.

    Proof

    We shall prove this statement by assuming \(n\) is odd. Then \(n=2m+1\) for some integer \(m \).

    Consider \(n^2=(2m+1)^2=4m^2+4m+1=2(2m^2+2m)+1.\)

    Since \( m \) is an integer, \( (2m^2)+2m\) is an integer.

    Thus \(n^2\) is odd.

    Example \(\PageIndex{2}\)

    Show that for all integers \( n\), if \(n^2\) is odd then \(n\) is odd.

    Answer

    We shall prove this statement by assuming \(n\) is even. Then \(n=2m\) for some integer \(m \).

    Consider \(n^2=(2m)^2=4m^2=2(2m^2).\)

    Since \( m \) is an integer, \( (2m^2)\) is an integer. Thus \(n^2\) is even.

    Proof by Contradiction

    In this technique, we shall assume the negation of the given statement is true and come to a contradiction.

    Theorem \(\PageIndex{3}\)

    \(\sqrt{2}\) is irrational.

    Proof

    Assume that \(\sqrt{2}\) is rational. Then \(\sqrt{2}= \dfrac {b}{a}\), where \(b\in \mathbb{Z}, a \in \mathbb{Z}\setminus \{0\}\), with no common factors between \(a\) and \(b\). Now, \( \sqrt{2} a=b\). Then \( 2a^2=b^2\). Since \(2\) divides \(2a^2\), \(2\) divides \(b^2\). Thus \(b^2\) is even. Therefore, \(b\) is even (by theorem 2). Since \( b\) is even, \(2 \) divides \(b\). Therefore, \(2^2 \) divides \(b^2\).

    Since \(2a^2=b^2\), \(2^2 \) divides \(2a^2\). Therefore, \(2 \) divides \(a^2\). Which implies \(a\) is even. This contradicts the fact that \(a\) and \(b\) have no common factors. Thus \(\sqrt{2}\) is irrational.

    Proof by Counterexample

    Example \(\PageIndex{3}\):

    Decide whether the statement is true or false and justify your answer:

    For all integers \(a,b,u,v\), and \(u\ne 0, v \ne 0\), if \(au+bv =0\) then \(a=b=0.\)

    Solution: The statement is false.

    Counterexample: Choose \(a=1,b=-1, u=2,v=2\), then \(au+bv =0\), but \(a\ne 0. b \ne 0, a \ne b.\)

    Proof by induction

    In mathematics, we use induction to prove mathematical statements involving integers. There are two types of induction: regular and strong. The steps start the same but vary at the end. Here are the steps. In mathematics, we start with a statement of our assumptions and intent:

    Let \(p(n) \forall n \geq n_0, \, n, \, n_0 \in \mathbb{Z}\) be a statement. We would show that p(n) is true for all possible values of n.

    1. Show that p(n) is true for the smallest possible value of n: In our case \(p(n_0)\). AND
    2. For Regular Induction: Assume that the statement is true for \(n = k,\) for some integer \(k \geq n_0\). Show that the statement is true for n = k + 1.

    OR

    For Strong Induction: Assume that the statement p(r) is true for all integers r, where \(n_0 ≤ r ≤ k \) for some \(k ≥ n_0\). Show that p(k+1) is true.

    If these steps are completed, and the statement holds, we are saying that, by mathematical induction, we can conclude that the statement is true for all values of \(n \geq n_0.\)

    Example \(\PageIndex{4}\):

    Prove that \(1 + 2 + ... + n = \displaystyle \frac{n(n + 1)}{2}, \, \forall n \in \mathbb{Z}\).

    Solution:

    Base step: Choose \(n = 1\). Then L.H.S =\(1\) and R.H.S \( = \frac{(1)(1 + 1)}{2}=1\)

    Induction Assumption: Assume that \( 1 + 2 + ... +k= \displaystyle\frac{k(k + 1)}{2}\), for \(k \in \mathbb{Z}\).

    We shall show that \(1 + 2 + ... + k + (k + 1) = \displaystyle\frac{(k + 1)[(k + 1) + 1]}{2} = \frac{(k + 1)(k + 2)}{2}\)

    Consider, \begin{align*}1 + 2 + ... + k + (k + 1) &= \displaystyle \frac{k(k + 1)}{2} + (k + 1)\\&= (k + 1) \left( \displaystyle\frac{k}{2} + \displaystyle\frac{1}{1}\right)\\&= (k + 1) \left( \displaystyle\frac{k + 2}{2}\right)\\&= \displaystyle \frac{(k + 1)(k + 2)}{2}.\end{align*}

    Thus, by induction we have \(1 + 2 + ... + n = \displaystyle\frac{n(n + 1)}{2}, \, \forall n \in \mathbb{Z}\).

    Example \(\PageIndex{5}\)

    Prove   for .

    Solution

    Let . Then is true, since clearly . Thus, the statement is true for .

    Assume that is true for some .

    We will show that .

    Consider .

    Since and , we have .

    Thus the statement is true for all .

    By induction, for all .◻


    This page titled 0.2: Introduction to Proofs/Contradiction is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

    • Was this article helpful?