Home All Subjects Progress Videos Graphics

Progress

241 / 241 subjects

Phases

29-01 — Direct Proof and Proof by Contrapositive

Phase: 29 — Proof Techniques Subject: 29-01 Prerequisites: 03-08 (Mathematical Induction), basic logic (AND, OR, NOT, IMPLIES) Next subject: 29-02 — Proof by Contradiction

Learning Objectives

By the end of this subject, you will be able to:

  1. Structure a direct proof with clear hypotheses, logical steps, and conclusion
  2. Identify the hypothesis and conclusion in an "if-then" statement
  3. Prove statements of the form "for all x, P(x) implies Q(x)"
  4. Formulate and prove the contrapositive of a statement
  5. Know when contrapositive proof is easier than direct proof

Core Content

1. What Is a Proof?

A proof is a logical argument that establishes the truth of a mathematical statement beyond all doubt. Unlike scientific experiments (which provide evidence), proofs provide certainty.

Structure of a proof: 1. Statement: What you're proving (theorem, proposition, lemma) 2. Hypotheses: The assumptions (given conditions) 3. Logical steps: Each step follows from previous steps by rules of logic or previously proven results 4. Conclusion: The statement being proven

2. Direct Proof

A direct proof of "If P, then Q" assumes P is true and uses logical steps to deduce Q.

Template:

Assume P is true.
[Use definitions, theorems, algebra, etc.]
Therefore Q is true.
Since we assumed P and deduced Q, "if P then Q" is proven. ∎

Example structure: - Theorem: If $n$ is even, then $n^2$ is even. - Proof: Assume $n$ is even. Then $n = 2k$ for some integer $k$. $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$. Since $2k^2$ is an integer, $n^2$ is even. ∎

3. Proving "For All" Statements

"For all x in S, P(x)" requires showing that no matter which $x$ you pick from $S$, $P(x)$ holds.

Template:

Let x be an arbitrary element of S.
[Prove P(x) using only properties of x that hold for ALL elements of S]
Since x was arbitrary, P(x) holds for all x in S. ∎

Critical: You must not use any special properties of a particular $x$. The proof must work for every possible $x$.

4. Proof by Contrapositive

The contrapositive of "If P, then Q" is "If not Q, then not P."

Key fact: A statement and its contrapositive are logically equivalent. Proving the contrapositive proves the original statement.

When to use contrapositive: - When assuming "not Q" gives you more information than assuming "P" - When Q is a "negative" statement (e.g., "is not divisible", "is irrational") - When direct proof gets stuck

Template:

We prove the contrapositive: if not Q, then not P.
Assume not Q.
[Use this stronger assumption]
Therefore not P.
Since the contrapositive is true, the original statement is true. ∎

Example: - Theorem: If $n^2$ is even, then $n$ is even. - Contrapositive: If $n$ is odd, then $n^2$ is odd. - Proof: Assume $n$ is odd. Then $n = 2k + 1$. $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. ∎

5. Common Proof Patterns

Divisibility proofs: Use definitions ($a \mid b$ means $b = ak$ for some integer $k$).

Inequality proofs: Often use algebraic manipulation or known inequalities (AM-GM, Cauchy-Schwarz).

Set proofs: Use element arguments (show $x \in A \implies x \in B$) or algebraic manipulation of set definitions.

Worked Examples

Example 1: Direct Proof — Sum of Two Odds

Problem: Prove that the sum of two odd integers is even.

Solution (direct proof):

Let $m$ and $n$ be arbitrary odd integers. By definition of odd: $m = 2k + 1$ and $n = 2j + 1$ for some integers $k, j$.

$$m + n = (2k + 1) + (2j + 1) = 2k + 2j + 2 = 2(k + j + 1)$$

Since $k + j + 1$ is an integer, $m + n$ is of the form $2 \cdot \text{(integer)}$, which means $m + n$ is even.

Answer: Proven. The sum of any two odd integers is even. ∎

Example 2: Contrapositive — Rational Square Root

Problem: Prove that if $\sqrt{n}$ is rational, then $n$ is a perfect square.

Solution (contrapositive):

Contrapositive: If $n$ is NOT a perfect square, then $\sqrt{n}$ is irrational.

Assume $n$ is not a perfect square. Suppose for contradiction that $\sqrt{n}$ is rational. Then $\sqrt{n} = a/b$ in lowest terms ($\gcd(a, b) = 1$).

Squaring: $n = a^2/b^2$, so $a^2 = nb^2$.

This means $b^2 \mid a^2$. Since $\gcd(a, b) = 1$, we must have $b = 1$. So $\sqrt{n} = a$, meaning $n = a^2$ — a perfect square. Contradiction.

Therefore $\sqrt{n}$ is irrational when $n$ is not a perfect square.

Answer: By contrapositive, if $\sqrt{n}$ is rational, then $n$ is a perfect square. ∎

Example 3: Direct Proof — Even Square

Problem: Prove that if $n$ is even, then $n^2$ is even.

Solution (direct proof):

Assume $n$ is even. By definition, $n = 2k$ for some integer $k$.

$$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$$

Since $2k^2$ is an integer, $n^2$ is of the form $2 \cdot \text{(integer)}$, so $n^2$ is even.

Answer: Proven directly. If $n$ is even, then $n^2$ is even. ∎

Practice Problems

Problem 1: Prove directly: If $n$ is odd, then $n^2$ is odd.

Problem 2: Prove by contrapositive: If $n^2$ is odd, then $n$ is odd.

Problem 3: Prove: The product of two even integers is divisible by 4.

Problem 4: Prove by contrapositive: If $a \nmid b$ (a does not divide b), then $a^2 \nmid b^2$.

Problem 5: Prove: For any integer $n$, $n^2 + n$ is always even.

Summary

  1. Direct proof assumes the hypothesis and logically deduces the conclusion
  2. "For all" statements require choosing an arbitrary element and proving the property for it
  3. Proof by contrapositive proves "if not Q then not P" instead of "if P then Q" — logically equivalent
  4. Contrapositive is useful when the negation gives stronger assumptions or when direct proof stalls
  5. Key definitions (even = $2k$, odd = $2k+1$, $a \mid b$ means $b = ak$) are the building blocks of elementary proofs

Key Terms

Pitfalls

Quiz

  1. Skipping the 'assume P' step. In a direct proof, you must explicitly assume P is true. Starting from 'let x be arbitrary' without linking to P produces a vacuous proof.
  2. Confusing contrapositive with contradiction. Contrapositive proves ¬Q → ¬P (a direct proof of the contrapositive). Contradiction assumes P ∧ ¬Q and derives a logical falsehood. They are related but distinct.
  3. Proving the converse by accident. 'If Q then P' is not the same as 'If P then Q'. Make sure you're proving the right direction.
  4. Vague quantifiers in proofs. 'For all x' and 'there exists x' require different proof strategies. Mixing them up is a common undergraduate error.
  5. Negating statements incorrectly. The negation of 'P and Q' is 'not P or not Q' (De Morgan). The negation of 'for all x, P(x)' is 'there exists x such that not P(x)'. These flip in contrapositive proofs.
  6. Forgetting to justify each step. A proof is an argument, not just a conclusion. Every claim needs a reason (definition, theorem, axiom, or prior result).

Q1: A direct proof of "If P, then Q" begins by:

A) Assuming Q is true and deducing P B) Assuming P is true and deducing Q C) Assuming both P and Q are false D) Not making any assumptions

Correct: B)

Q2: The contrapositive of "If $n$ is even, then $n^2$ is even" is:

A) If $n^2$ is even, then $n$ is even B) If $n$ is odd, then $n^2$ is odd C) If $n^2$ is odd, then $n$ is odd D) If $n$ is even, then $n$ is odd

Correct: C)

Q3: A statement and its contrapositive are:

A) Sometimes equivalent B) Always logically equivalent (both true or both false) C) Never equivalent D) Equivalent only for even numbers

Correct: B)

Q4: To prove "for all $x \in S$, $P(x)$" by direct proof, you should:

A) Test $P(x)$ for a few values of $x$ and generalise B) Let $x$ be an arbitrary element of $S$ and prove $P(x)$ C) Find a counterexample D) Assume $P(x)$ is false and derive a contradiction

Correct: B)

Q5: Proof by contrapositive is particularly useful when:

A) The hypothesis is easier to work with than the conclusion B) The NEGATION of the conclusion is easier to work with than the hypothesis C) You want to prove two statements at once D) The statement involves only numbers

Correct: B)

Q6: In a direct proof that "if $n$ is even, then $n^2$ is even," the first step is:

A) To state that $n^2$ is even B) To assume $n$ is even and write $n = 2k$ C) To compute $n^2$ D) To find a counterexample

Correct: B)

Q7: Which of the following is proved most naturally by contrapositive?

A) "If $x > 2$, then $x^2 > 4$" B) "If $x^2$ is irrational, then $x$ is irrational" C) "The sum of two even numbers is even" D) "There are infinitely many primes"

Correct: B)

Q8: The logical form of a direct proof of "If P, then Q" is:

A) Modus tollens B) Modus ponens C) Proof by cases D) Reductio ad absurdum

Correct: B)

Next Steps

Continue to 29-02 — Proof by Contradiction to learn one of the most powerful proof techniques — assuming the opposite of what you want to prove and deriving an impossibility.