1.7: A.7- Proof by Contradiction
- Page ID
- 121753
\( \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 the first instance, proof by contradiction is an inference pattern that is used to prove negative claims. Suppose you want to show that some claim \(p\) is false, i.e., you want to show \(\lnot p\). The most promising strategy is to (a) suppose that \(p\) is true, and (b) show that this assumption leads to something you know to be false. “Something known to be false” may be a result that conflicts with—contradicts—\(p\) itself, or some other hypothesis of the overall claim you are considering. For instance, a proof of “if \(q\) then \(\lnot p\)” involves assuming that \(q\) is true and proving \(\lnot p\) from it. If you prove \(\lnot p\) by contradiction, that means assuming \(p\) in addition to \(q\). If you can prove \(\lnot q\) from \(p\), you have shown that the assumption \(p\) leads to something that contradicts your other assumption \(q\), since \(q\) and \(\lnot q\) cannot both be true. Of course, you have to use other inference patterns in your proof of the contradiction, as well as unpacking definitions. Let’s consider an example.
If \(A \subseteq B\) and \(B = \emptyset\), then \(A\) has no elements.
Proof. Suppose \(A \subseteq B\) and \(B = \emptyset\). We want to show that \(A\) has no elements.
Since this is a conditional claim, we assume the antecedent and want to prove the consequent. The consequent is: \(A\) has no elements. We can make that a bit more explicit: it’s not the case that there is an \(x \in A\).
\(A\) has no elements iff it’s not the case that there is an \(x\) such that \(x \in A\).
So we’ve determined that what we want to prove is really a negative claim \(\lnot p\), namely: it’s not the case that there is an \(x \in A\). To use proof by contradiction, we have to assume the corresponding positive claim \(p\), i.e., there is an \(x \in A\), and prove a contradiction from it. We indicate that we’re doing a proof by contradiction by writing “by way of contradiction, assume” or even just “suppose not,” and then state the assumption \(p\).
Suppose not: there is an \(x \in A\).
This is now the new assumption we’ll use to obtain a contradiction. We have two more assumptions: that \(A \subseteq B\) and that \(B = \emptyset\). The first gives us that \(x \in B\):
Since \(A \subseteq B\), \(x \in B\).
But since \(B = \emptyset\), every element of \(B\) (e.g., \(x\)) must also be an element of \(\emptyset\).
Since \(B = \emptyset\), \(x \in \emptyset\). This is a contradiction, since by definition \(\emptyset\) has no elements.
This already completes the proof: we’ve arrived at what we need (a contradiction) from the assumptions we’ve set up, and this means that the assumptions can’t all be true. Since the first two assumptions (\(A \subseteq B\) and \(B = \emptyset\)) are not contested, it must be the last assumption introduced (there is an \(x \in A\)) that must be false. But if we want to be thorough, we can spell this out.
Thus, our assumption that there is an \(x \in A\) must be false, hence, \(A\) has no elements by proof by contradiction. ◻
Every positive claim is trivially equivalent to a negative claim: \(p\) iff \(\lnot\lnot p\). So proofs by contradiction can also be used to establish positive claims “indirectly,” as follows: To prove \(p\), read it as the negative claim \(\lnot\lnot p\). If we can prove a contradiction from \(\lnot p\), we’ve established \(\lnot\lnot p\) by proof by contradiction, and hence \(p\).
In the last example, we aimed to prove a negative claim, namely that \(A\) has no elements, and so the assumption we made for the purpose of proof by contradiction (i.e., that there is an \(x \in A\)) was a positive claim. It gave us something to work with, namely the hypothetical \(x \in A\) about which we continued to reason until we got to \(x \in \emptyset\).
When proving a positive claim indirectly, the assumption you’d make for the purpose of proof by contradiction would be negative. But very often you can easily reformulate a positive claim as a negative claim, and a negative claim as a positive claim. Our previous proof would have been essentially the same had we proved “\(A = \emptyset\)” instead of the negative consequent “\(A\) has no elements.” (By definition of \(=\), “\(A = \emptyset\)” is a general claim, since it unpacks to “every element of \(A\) is an element of \(\emptyset\) and vice versa”.) But it is easily seen to be equivalent to the negative claim “not: there is an \(x \in A\).”
So it is sometimes easier to work with \(\lnot p\) as an assumption than it is to prove \(p\) directly. Even when a direct proof is just as simple or even simpler (as in the next example), some people prefer to proceed indirectly. If the double negation confuses you, think of a proof by contradiction of some claim as a proof of a contradiction from the opposite claim. So, a proof by contradiction of \(\lnot p\) is a proof of a contradiction from the assumption \(p\); and proof by contradiction of \(p\) is a proof of a contradiction from \(\lnot p\).
\(A \subseteq A \cup B\).
Proof. We want to show that \(A \subseteq A \cup B\).
On the face of it, this is a positive claim: every \(x \in A\) is also in \(A \cup B\). The negation of that is: some \(x \in A\) is \(\notin A \cup B\). So we can prove the claim indirectly by assuming this negated claim, and showing that it leads to a contradiction.
Suppose not, i.e., \(A \nsubseteq A \cup B\).
We have a definition of \(A \subseteq A \cup B\): every \(x \in A\) is also \(\in A \cup B\). To understand what \(A \nsubseteq A \cup B\) means, we have to use some elementary logical manipulation on the unpacked definition: it’s false that every \(x \in A\) is also \(\in A \cup B\) iff there is some \(x \in A\) that is \(\notin C\). (This is a place where you want to be very careful: many students’ attempted proofs by contradiction fail because they analyze the negation of a claim like “all \(A\)s are \(B\)s” incorrectly.) In other words, \(A \nsubseteq A \cup B\) iff there is an \(x\) such that \(x \in A\) and \(x \notin A \cup B\). From then on, it’s easy.
So, there is an \(x \in A\) such that \(x \notin A \cup B\). By definition of \(\cup\), \(x \in A \cup B\) iff \(x \in A\) or \(x \in B\). Since \(x \in A\), we have \(x \in A \cup B\). This contradicts the assumption that \(x \notin A \cup B\). ◻
Prove indirectly that \(A \cap B \subseteq A\).
If \(A \subseteq B\) and \(B \subseteq C\) then \(A \subseteq C\).
Proof. Suppose \(A \subseteq B\) and \(B \subseteq C\). We want to show \(A \subseteq C\).
Let’s proceed indirectly: we assume the negation of what we want to etablish.
Suppose not, i.e., \(A \nsubseteq C\).
As before, we reason that \(A \nsubseteq C\) iff not every \(x \in A\) is also \(\in C\), i.e., some \(x \in A\) is \(\notin C\). Don’t worry, with practice you won’t have to think hard anymore to unpack negations like this.
In other words, there is an \(x\) such that \(x \in A\) and \(x \notin C\).
Now we can use this to get to our contradiction. Of course, we’ll have to use the other two assumptions to do it.
Since \(A \subseteq B\), \(x \in B\). Since \(B \subseteq C\), \(x \in C\). But this contradicts \(x \notin C\). ◻
If \(A \cup B = A \cap B\) then \(A = B\).
Proof. Suppose \(A \cup B = A \cap B\). We want to show that \(A = B\).
The beginning is now routine:
Assume, by way of contradiction, that \(A \neq B\).
Our assumption for the proof by contradiction is that \(A \neq B\). Since \(A = B\) iff \(A \subseteq B\) an \(B \subseteq A\), we get that \(A \neq B\) iff \(A \nsubseteq B\) or \(B \nsubseteq A\). (Note how important it is to be careful when manipulating negations!) To prove a contradiction from this disjunction, we use a proof by cases and show that in each case, a contradiction follows.
\(A \neq B\) iff \(A \nsubseteq B\) or \(B \nsubseteq A\). We distinguish cases.
In the first case, we assume \(A \nsubseteq B\), i.e., for some \(x\), \(x \in A\) but \(\notin B\). \(A \cap B\) is defined as those elements that \(A\) and \(B\) have in common, so if something isn’t in one of them, it’s not in the intersection. \(A \cup B\) is \(A\) together with \(B\), so anything in either is also in the union. This tells us that \(x \in A \cup B\) but \(x \notin A \cap B\), and hence that \(A \cap B \neq B \cap A\).
Case 1: \(A \nsubseteq B\). Then for some \(x\), \(x \in A\) but \(x \notin B\). Since \(x \notin B\), then \(x \notin A \cap B\). Since \(x \in A\), \(x \in A \cup B\). So, \(A \cap B \neq B \cap A\), contradicting the assumption that \(A \cap B = A \cup B\).
Case 2: \(B \nsubseteq A\). Then for some \(y\), \(y \in B\) but \(y \notin A\). As before, we have \(y \in A \cup B\) but \(y \notin A \cap B\), and so \(A \cap B \neq A \cup B\), again contradicting \(A \cap B = A \cup B\). ◻