Direct and Contrapositive Proofs

Welcome to the next stage of your journey into discrete mathematics. In our previous lesson, we honed our skills in simplifying logical expressions using algebraic laws. This was about transforming statements into equivalent, more manageable forms. Now, we will use those skills to build structured arguments and formally prove that certain statements are true.

This lesson introduces two fundamental proof strategies: direct proof and proof by contrapositive. Think of these as the first two major "recipes" in your mathematical argument toolkit. Your background in software development provides a great parallel: a proof is like a well-commented algorithm that takes a set of initial assumptions (the hypothesis) and follows a sequence of logically justified steps to arrive at a guaranteed result (the conclusion).

By the end of this lesson, you will be able to construct simple but complete mathematical arguments using both of these foundational techniques.

The Anatomy of a Proof

At its core, a mathematical proof is a sequence of logical deductions that begins with a set of assumptions, called the hypothesis, and ends with a conclusion. Each step in between must be justified by a definition, an axiom, or a previously established theorem.

The following flowchart provides a simple mental model for this process.

A basic flowchart illustrating that a proof uses reasons—such as definitions, postulates, and theorems—to logically connect a given hypothesis to a final conclusion.

Most of the statements we will prove in this course are implications, which have the form "if P, then Q". Here, P is the hypothesis, and Q is the conclusion. Our goal is to show that whenever P is true, Q must also be true.

Direct Proof: The Straightforward Path

The most intuitive way to prove an implication $p \to q$ is with a direct proof. The strategy is simple:

Assume the hypothesis, p, is true.
Use definitions, algebraic manipulations (like you learned in the last lesson), and other logical rules to build a bridge from p to q.
Conclude that q must be true.

The Stanford CS103 Guide to Proofs offers an excellent breakdown of this structure. It formalizes the process into an "assume step" and a "want-to-show" step, which is a great way to frame your thinking before you even start the detailed logic.

CS103 Guide to Proofs

This guide clearly lays out the "recipe" for writing a direct proof of an implication.

Please read the section on how to structure the proof. Notice the emphasis on starting by explicitly stating your assumption and your goal (the "want-to-show"). This template provides a clear path for your argument.

Let's see this recipe in action. A classic first example is proving that if an integer n is odd, then its square, n², is also odd. The following video provides a clear, step-by-step walkthrough.

Discrete Math - 1.7.1 Direct Proof

In this video, Kimberly Brehm demonstrates a direct proof using the standard definitions of even and odd integers.

First, watch the brief segment where she defines even and odd integers. These definitions are the essential tools for this proof. Then, watch her complete the direct proof that if n is odd, then n² is odd. Observe how she follows the recipe: Assume: n is an odd integer. Logic/Algebra: Use the definition (n = 2k + 1), square the expression, and algebraically rearrange it back into the form of an odd number. Conclude: n² is odd.

Often, theorems are stated for all members of a set, such as "For any integer n, if n is even, then...". This combines a universal statement with an implication. To prove this, you simply start by choosing an arbitrary element from the set that satisfies the hypothesis and then proceed with a direct proof. The Stanford guide calls this "unpacking."

CS103 Guide to Proofs

This section explains how to handle proofs that start with "For any..." or "For all...".

Read the section on unpacking. The key idea is that to prove a statement like "For any integer n, if P(n) then Q(n)", you can start your proof with "Pick an integer n where P(n) is true" and then prove Q(n).

Proof by Contrapositive: The Indirect Route

Sometimes, trying to go directly from p to q can be difficult or confusing. In these cases, an indirect approach might be much simpler. A proof by contrapositive is a powerful indirect method.

It relies on a key logical equivalence we've seen before: $p \to q \equiv \neg q \to \neg p$ . The statement $\neg q \to \neg p$ is the contrapositive of the original implication.

This truth table demonstrates that a conditional statement (p → q) and its contrapositive (~q → ~p) have identical truth values in all cases, establishing their logical equivalence.

Since the two statements are logically equivalent, proving one is the same as proving the other. The recipe for a proof by contrapositive is:

Identify that you want to prove $p \to q$ .
State that you will prove the contrapositive, $\neg q \to \neg p$ . Writing this down helps clarify your goal.
Assume $\neg q$ is true.
Use a direct proof to show that $\neg p$ must be true.
Conclude that since the contrapositive is true, the original statement must also be true.

CS103 Guide to Proofs

This resource explains the structure of a proof by contrapositive and why it is a valid technique.

Read the section on this proof technique. Pay special attention to the advice to explicitly state the contrapositive before you begin the proof.

Let's apply this to an example: "If $3 n + 2$ is odd, then $n$ is odd." A direct proof is a bit awkward. But the contrapositive is very clean.

Original Statement (p → q): If 3n+2 is odd (p), then n is odd (q).
Contrapositive (¬q → ¬p): If n is not odd (i.e., n is even), then 3n+2 is not odd (i.e., 3n+2 is even).

Proving this contrapositive with a direct proof is straightforward. This video demonstrates the process perfectly.

Discrete Math - 1.7.2 Proof by Contraposition

Kimberly Brehm explains the logic behind proof by contrapositive and walks through a clear example.

First, watch her introduction to the method. Then, see it in action as she proves "If 3n+2 is odd, then n is odd" by proving its contrapositive. Notice how assuming "n is even" gives her a concrete starting point (n=2k) that allows for direct algebraic manipulation.

This method is particularly useful when the negation of the conclusion ( $\neg q$ ) gives you a more concrete or useful starting point than the original hypothesis (p).

Conclusion

In this lesson, we explored the fundamental structure of mathematical proofs and learned two essential techniques for proving implications. These methods provide the logical framework for establishing truth in mathematics and, by extension, for reasoning about the correctness of any logical system, including software.

Key Takeaways:

A proof is a logical argument that moves from a hypothesis to a conclusion, with each step justified by a definition or a known rule.
A direct proof of $p \to q$ involves assuming p is true and using a chain of deductions to show q must be true.
A proof by contrapositive of $p \to q$ involves proving its logical equivalent, $\neg q \to \neg p$ . You assume $\neg q$ is true and use a direct proof to show $\neg p$ must be true.
Choosing the right strategy often depends on which hypothesis (p or $\neg q$ ) provides a better starting point for algebraic or logical manipulation.

In our next lesson, we will formalize the language used in statements like "for every integer n" or "there exists a number x". We'll dive into predicate logic and explore the universal ( $\forall$ ) and existential ( $\exists$ ) quantifiers. This will allow us to analyze and construct more complex and powerful mathematical statements.

Recommended resources

The Anatomy of a Proof

Direct Proof: The Straightforward Path

Proof by Contrapositive: The Indirect Route

Conclusion