Section3.3Proof via Contrapositive (And Other Methods)
Guiding Questions.
In this section, we’ll seek to answer the questions:
How can we use the contrapositive to prove a conditional statement?
How can we prove a statement whose hypothesis or conclusion contains cases?
Subsection3.3.1Proof via the Contrapositive
We saw in Problem 1.2.26 that a conditional statement \(P\Rightarrow Q\) and its contrapositive \(\neg Q\Rightarrow \neg P\) are logically equivalent. Thus, we may choose to use direct proof on either \(P\Rightarrow Q\) or \(\neg Q\Rightarrow \neg P\text{.}\) However, as we saw in Problem 1.3.7, negating a quantified statement must be done carefully.
Theorem3.3.1.
If \(m\in\Z\) such that \(m^2\) is even, then \(m\) is even.
Problem 3.3.2 gives a glimpse into when you might consider using the contrapositive for a proof: when your conclusion is a negative statement, i.e., it states what does not happen. This is because there are often lots of ways for something not to happen (e.g., \(ab\) could be almost any real number, except 0), while there may be a relatively small number of ways for something to happen (e.g., \(ab = 0\) can only happen in one way). Thus, if we can negate our negative statement into a positive statement, the theorem may become more tractable.
Subsection3.3.2Proofs with Cases, and Biconditional Proofs
In Problem 3.3.2 we also saw that our hypotheses or conclusions can sometimes involve multiple cases. When the conclusion involves multiple cases joined by disjunction, it is typically advantageous to assume that all but one of them is false, and show that the only remaining possibility must be true 1
For, if any one of the other cases were true, the compound OR statement would be true, and the theorem would be proved!
.
In this section, we will explore what happens when the hypotheses of a conditional statement contains multiple cases. We begin with a definition.
Definition3.3.3.
Let \(x\) be a real number. The absolute value of \(x\), denoted \(|x|\) is defined to be
\begin{equation*}
|x| = \begin{cases} x, \amp x \ge 0\\ -x, \amp x \lt 0.\end{cases}
\end{equation*}
To prove Theorem 3.3.4 and others involving absolute value, you should consider two cases: one in which \(x\ge 0\text{,}\) and another in which \(x \lt 0\text{.}\)
Theorem3.3.4.
For every real number \(x\text{,}\)\(|-x| = |x|\text{.}\)
Before we consider another proof requiring cases, we need to talk about biconditional proofs. These are proofs of statements of the form \(P\Leftrightarrow Q\text{,}\) and are enormously important in mathematics, as they often give an equivalent characterization for a definition or concept.
Biconditional Proofs.
Following Problem 1.2.23, we prove a statement of the form \(P\Leftrightarrow Q\) by proving both\(P\Rightarrow Q\) and \(Q\Rightarrow P\text{.}\) Our proof thus contains two subproofs: the first assumes \(P\) and deduces \(Q\text{,}\) while the second assumes \(Q\) and deduces \(P\text{.}\) We often call \(P\Rightarrow Q\) the forward direction and \(Q\Rightarrow P\) the backward direction.
Each subproof may use any valid proof technique (including the contrapositive!). For maximum clarity, state the relevant hypotheses at the start of each subproof.
Before we prove biconditional statements involving cases, let’s prove one that does not involve cases.
Theorem3.3.5.
Let \(m\in\Z\text{.}\) Then \(m\) is even if and only if \(m+1\) is odd.
We now consider two familiar theorems about absolute value that will require some cases.
Theorem3.3.6.
Let \(a\) be a positive real number and \(x\) a real number. Then \(|x| = a\) if and only if \(x= a\) or \(x = -a\text{.}\)
Theorem3.3.7.
Let \(a\) be a positive real number. For all real numbers \(x\text{,}\)\(|x| \lt a\) if and only if \(-a \lt x \lt a\text{.}\)
Theorem3.3.8.
Let \(m\) be an integer. Then \(m^2 + m\) is even.
For the following theorem, establish your cases based on the existence (or not) of a vertex of degree zero.
Theorem3.3.9.
Let \(G\) be a graph with \(n\) vertices. Then \(G\) has two vertices whose degrees are equal.
