Skip to main content
\(\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}}\)
Mathematics LibreTexts

7.1: If-and-Only-If Proof

  • Page ID
    24835
  • \( \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}}\)

    Some propositions have the form P if and only if Q.

    We know from Section 2.4 that this statement asserts that both of the following conditional statements are true:

    If P, then Q. If Q, then P.

    So to prove “P if and only if Q,” we must prove two conditional statements. Recall from Section 2.4 that \(Q \Rightarrow P\) is called the converse of \(P \Rightarrow Q\). Thus we need to prove both \(P \Rightarrow Q\) and its converse. These are both conditional statements, so we may prove them with either direct, contrapositive or contradiction proof. Here is an outline:

    Outline for If-and-Only-If Proof

    Proposition P if and only if Q.

    Proof.

    [Prove \(P \Rightarrow Q\) using direct, contrapositive or contradiction proof.]

    [Prove \(Q \Rightarrow P\) using direct, contrapositive or contradiction proof.]

    Let’s start with a very simple example. You already know that an integer n is odd if and only if \(n^2\) is odd, but let’s prove it anyway, just to illustrate the outline. In this example we prove (n is odd) \(\Rightarrow\) (\(n^2\) is odd) using direct proof and (\(n^2\) is odd) \(\Rightarrow\) (n is odd) using contrapositive proof.

    Proposition The integer n is odd if and only if \(n^2\) is odd.

    Proof. First we show that n being odd implies that \(n^2\) is odd. Suppose n is odd. Then, by definition of an odd number, \(n = 2a + 1\) for some integer a. Thus \(n^2 =(2a+1)^2 = 4a^2+4a+1 = 2(2a^2+2a)+1\). This expresses \(n^2\) as twice an integer, plus 1, so \(n^2\) is odd.

    Conversely, we need to prove that \(n^2\) being odd implies that n is odd. We use contrapositive proof. Suppose n is not odd. Then n is even, so \(n = 2a\) for some integer a (by definition of an even number). Thus \(n^2 = (2a)^2 = 2(2a^2)\), so \(n^2\) is even because it’s twice an integer. Thus \(n^2\) is not odd. We’ve now proved that if n is not odd, then \(n^2\) is not odd, and this is a contrapositive proof that if \(n^2\) is odd then n is odd.

    In proving "P if and only if Q," you should begin a new paragraph when starting the proof of \(Q \Rightarrow P\). Since this is the converse of \(P \Rightarrow Q\), it’s a good idea to begin the paragraph with the word "Conversely" (as we did above) to remind the reader that you’ve finished the first part of the proof and are moving on to the second. Likewise, it’s a good idea to remind the reader of exactly what statement that paragraph is proving.

    The next example uses direct proof in both parts of the proof.

    Proposition Suppose a and b are integers. Then \(a \equiv b \pmod{6}\). if and only if \(a \not\equiv b \pmod{2}\) and \(a \not\equiv b \pmod{3}\).

    Proof. First we prove that if \(a \equiv b \pmod{6}\), then \(a \not\equiv b \pmod{2}\) and \(a \not\equiv b \pmod{3}\). Suppose \(a \equiv b \pmod{6}\). This means \(6|(a-b)\), so there is an integer n for which \(a-b = 6n\).

    From this we get \(a-b = 2(3n)\), which implies \(2|(a-b)\), so \(a \not\equiv b \pmod{2}\). But we also get \(a-b = 3(2n)\), which implies \(3|(a-b)\), so \(a \not\equiv b \pmod{3}\). Therefore \(a \not\equiv b \pmod{2}\) and \(a \not\equiv b \pmod{3}\).

    Conversely, suppose \(a \not\equiv b \pmod{2}\) and \(a \not\equiv b \pmod{3}\). Since \(a \not\equiv b \pmod{2}\) we get \(2|(a-b)\), so there is an integer k for which \(a-b = 2k\). Therefore \(a-b\) is even. Also, from \(a \not\equiv b \pmod{3}\) we get \(3|(a-b)\), so there is an integer l for which

    \(a-b=3l\).

    But since we know \(a-b\) is even, it follows that l must be even also, for if it were odd then \(a-b = 3l\) would be odd (because \(a-b\) would be the product of two odd integers). Hence \(l = 2m\) for some integer m. Thus \(a-b = 3l = 3 \cdot 2m = 6m\). This means \(6|(a-b)\), so \(a \equiv b \pmod{6}\).

    Since if-and-only-if proofs simply combine methods with which we are already familiar, we will not do any further examples in this section. But it is of utmost importance that you practice your skill on some of this chapter’s exercises.