Course contentsShow
← Mathematics
Lesson 2495 of 3,12150. Discrete Math — Logic and ProofFree lesson

Proof by Contrapositive: Method and Strategy

When and how to prove a statement by proving its contrapositive instead of using direct proof.

Proof by Contrapositive: Method and Strategy

You'll learn when and how to prove a statement by proving its contrapositive instead of using direct proof.

The Core Idea

Sometimes proving "If P, then Q" directly is difficult—perhaps you don't know how to start from P, or the path forward seems blocked. Here's where contrapositive proof shines: instead of proving P → Q directly, you prove its logically equivalent contrapositive: ¬Q → ¬P (if not Q, then not P).

Since you already know these statements are logically equivalent, proving the contrapositive is proving the original statement. The beauty? The contrapositive often gives you something concrete to work with.

When to Use This Strategy

Choose contrapositive proof when:

  • The original statement's hypothesis is vague or hard to manipulate
  • The conclusion is easier to negate and work backward from
  • You see phrases like "if n² is even..." where working with the negation (odd) is cleaner
  • Direct proof seems to lead nowhere after several attempts

The Method

  1. Identify the statement structure: P → Q
  2. Form the contrapositive: ¬Q → ¬P
  3. Assume ¬Q (the negation of the conclusion)
  4. Use direct proof techniques to show ¬P must follow
  5. Conclude that P → Q is proven

Example Setup

To prove: "If n² is even, then n is even."

Contrapositive approach: Prove "If n is not even (odd), then n² is not even (odd)."

Now you assume n is odd (n = 2k+1 for some integer k) and can directly compute n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. Done!

Key takeaway: Use contrapositive proof when negating the conclusion gives you a clearer starting point than assuming the hypothesis directly.