Skip to main content

Discrete Structures Course Notes

Mike Janssen

Section 3.3 Proof 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?
    🔗
🔗
🔗

Subsection 3.3.1 Proof 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.
🔗

Problem 3.3.2.

In this problem, we will consider the statement:
\(a,b\in \R\text{,}\)\(a\ne 0\)\(b\ne 0\text{,}\)\(ab \ne 0\text{.}\)
🔗
🔗
  1. Attempt to sketch a direct proof of the statement. Comment on your success.
    🔗
  2. Carefully state the contrapositive of the statement.
    🔗
  3. Explain why the contrapositive you stated in the previous question is equivalent to the statement
    \(a,b\in \R\text{,}\)\(ab = 0\)\(a\ne 0\text{,}\)\(b =0\text{.}\)
    🔗
    Hint: look in Section 1.2.
    🔗
  4. Prove the statement given in Question 3.
    🔗
🔗
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.
🔗
🔗

Subsection 3.3.2 Proofs 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.
🔗

Definition 3.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{.}\)
🔗
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.
🔗
We now consider two familiar theorems about absolute value that will require some cases.
🔗
For the following theorem, establish your cases based on the existence (or not) of a vertex of degree zero.
🔗
🔗
🔗
PrevTopNext