Ultimate Guide to Methods of Proof: Contradiction and Counterexamples

Introduction

With the language of formal logic mastered, we can finally begin proving theorems. While direct proof (starting with known facts and algebraically arriving at the conclusion) is common, it often falls short for complex problems. In this guide, Methods of Proof, we explore alternative strategies: destroying false claims with a single counterexample, and proving true claims by assuming the impossible (Proof by Contradiction). We will also apply these techniques to integer arithmetic.

Executive Summary

This guide covers three crucial proof techniques:

• Disproof by Counterexample: Proving a universal statement ($\forall$) is false by providing a single specific example where it fails.
• Proof by Contradiction: Proving a statement $P$ is true by assuming its negation $\sim P$ is true, and showing this leads to a logical absurdity.
• Integer Proofs: Using definitions of even ($2k$) and odd ($2k+1$) integers to prove properties of numbers.

What is this about?

If someone claims, "All prime numbers are odd," how do you disprove them? You don't need a massive algebraic argument. You simply say, "The number 2 is prime, and it is even." Boom. The claim is shattered. This is a counterexample.

But what if someone asks you to prove that $\sqrt{2}$ is irrational? You cannot test every single fraction in the universe. Instead, you use Proof by Contradiction: you assume $\sqrt{2}$ is a fraction, and then use algebra to prove that this assumption breaks the laws of mathematics. Since the assumption leads to a contradiction, the original statement must be true!

Main Content

1. Disproof by Counterexample

To disprove a statement that claims something is true "for all" cases ($\forall$), you only need to find one case where it is false.

Steps for Disproof:

1. State the original claim clearly.
2. Provide specific numbers (the counterexample).
3. Show that these numbers satisfy the premise but fail the conclusion.
4. Conclude that the universal statement is false.

Example: Disprove the statement "For all real numbers $x$, $x^2 \ge x$". Counterexample: Let $x = 0.5$. Then $x^2 = 0.25$. Since $0.25$ is NOT greater than or equal to $0.5$, the statement is false.

2. Proof by Contradiction

Proof by contradiction (also known as reductio ad absurdum) is arguably the most elegant tool in mathematics.

Steps for Proof by Contradiction:

1. The Assumption: Assume that the statement you are trying to prove is FALSE (i.e., assume its negation).
2. The Logic: Use valid mathematical steps and algebra based on that false assumption.
3. The Contradiction: Arrive at a conclusion that is obviously impossible or contradicts a known mathematical fact (e.g., $1 = 0$, or an integer being both even and odd).
4. The Conclusion: State that because the assumption led to a contradiction, the assumption must be false. Therefore, the original statement must be true.

3. Integer Proofs

Many proofs in the HSC involve the set of integers ($\mathbb{Z}$). You must memorize the formal algebraic definitions of integer types:

• Even Integer: Can be written as $n = 2k$, where $k$ is an integer.
• Odd Integer: Can be written as $n = 2k + 1$, where $k$ is an integer.
• Multiple of 3: Can be written as $n = 3k$, where $k$ is an integer.
• Rational Number: Can be written as $\frac{a}{b}$, where $a$ and $b$ are integers with no common factors (coprime), and $b \neq 0$.

When proving properties about integers, you substitute these definitions into the algebraic expressions and factorize to show the result fits the required definition.

Simple Worked Example

Question: Use proof by contradiction to prove that there are no positive integers $x$ and $y$ such that $x^2 - y^2 = 1$.

Solution: Step 1: The Assumption Assume to the contrary that there do exist positive integers $x$ and $y$ such that $x^2 - y^2 = 1$.

Step 2: The Logic Factorize the difference of two squares: $(x - y)(x + y) = 1$ Since $x$ and $y$ are positive integers, both $(x - y)$ and $(x + y)$ must be integers. The only way two integers can multiply to give $1$ is if they are both $1$ or both $-1$. Since $x$ and $y$ are positive, $(x + y)$ must be positive. Thus, they must both equal $1$:

1. $x + y = 1$
2. $x - y = 1$

Add the two equations together: $2x = 2 \implies x = 1$ Substitute $x=1$ into equation (1): $1 + y = 1 \implies y = 0$

Step 3: The Contradiction We have found that $y = 0$. However, our initial premise stated that $y$ must be a positive integer. Since $0$ is not positive, this is a contradiction.

Step 4: The Conclusion Because our assumption led to a contradiction, the assumption is false. Therefore, there are no positive integers $x$ and $y$ such that $x^2 - y^2 = 1$.

mini-FAQ page

Q: When should I use proof by contradiction instead of a direct proof? A: Contradiction is highly effective when proving negative statements (e.g., "prove $x$ is NOT rational", "prove there are NO solutions", "prove a set is infinite"). It is also useful when the direct path seems algebraically impossible.

Q: What is a "coprime" integer? A: Two integers are coprime if their greatest common divisor is 1 (they share no common factors). This is crucial when proving irrationality (like $\sqrt{2}$). We assume it equals $\frac{a}{b}$ where $a,b$ are coprime, and then contradict that by proving they are both even.

Common mistakes to avoid

• Failing to state the assumption clearly: The marker needs to know exactly what you are assuming. Start your proof with the exact phrase: "Assume to the contrary that..."
• Assuming the wrong negation: If you are trying to prove "If $P$ then $Q$" by contradiction, your assumption must be the exact negation: "$P$ AND not $Q$".

Practice on Vu's Maths Hub

Proof by contradiction is a guaranteed exam topic. You must be fluent in the classic proofs.

• Master the proofs for the irrationality of $\sqrt{2}$ and $\sqrt{3}$ in the HSC Proof Booklet.
• Try solving challenging integer parity (even/odd) proofs in the HSC Last Resorts Booklet.

Further Readings

• Ready for the next challenge? Learn how to prove algebraic inequalities in our next guide: Proof of Inequalities (Part 1).
• Explore more HSC math resources and full worked solutions at Vu's Maths Hub.

Connect with me

Want to master Mathematical Proof and guarantee top marks in HSC Mathematics Extension 2? Visit Vu's Maths Hub for in-depth booklets, rigorous worked solutions, and expert advice to help you ace your exams!