Proof

Welcome to the Chapter on Proof!

Hello future mathematician! Proof is arguably the most crucial chapter in Pure Mathematics. It’s not just about getting the right answer; it’s about establishing absolute certainty.
In Pure Maths 1 (P1), you learned the basics: proof by deduction, proof by exhaustion, and disproving with a counterexample. In Unit P2, we introduce a powerful and elegant new technique: Proof by Contradiction.

Don't worry if proof seems tricky at first. It uses rigorous logic, which is like exercising a new part of your brain! We will break down every technique into simple, manageable steps.

A Quick Review of P1 Proof Techniques

Before diving into the new material, let's briefly recap the methods you should already be comfortable with. These are the tools you use inside a contradiction proof!

1. Proof by Deduction

This is the most common method. You start with known facts (definitions, axioms, or given premises) and use a logical sequence of steps to arrive at the desired conclusion.
Example: Prove that the difference between the squares of two consecutive integers is always an odd number.

• Let the two consecutive integers be \(n\) and \(n+1\), where \(n\) is an integer.
• The difference between their squares is \( (n+1)^2 - n^2 \).
• Expanding: \( (n^2 + 2n + 1) - n^2 \).
• Simplifying: \( 2n + 1 \).
• Since \(n\) is an integer, \(2n\) is an even number, and \(2n+1\) is always an odd number. Q.E.D. (Latin for Quod Erat Demonstrandum — "which was to be demonstrated").

2. Proof by Exhaustion (or Proof by Cases)

This method involves splitting the problem into a finite number of cases and proving the statement holds true for every single one. This is only feasible when the set of possibilities is small.
Memory Aid: Think of "Exhausting" all the options available.

3. Disproof by Counterexample

To show a statement is false, you only need to find one instance (a counterexample) where the statement fails.

• Common Mistake to Avoid: Proving a statement is true for two or three examples is not a proof! You must prove it works for ALL cases (Deduction/Contradiction) or for all possible finite cases (Exhaustion).

---

The Core of P2 Proof: Proof by Contradiction

This technique is intellectually elegant and often used when a direct deduction seems impossible or overly complicated.

What is Proof by Contradiction?

Also known as Reductio ad Absurdum (reduction to absurdity), this method works like a detective solving a mystery. If you want to prove Statement P is true, you temporarily assume the exact opposite of P is true.
If this assumption (the opposite of P) leads you to a result that is logically impossible or contradicts a known mathematical fact, then the assumption must have been wrong.
If the assumption is wrong, the original statement P must be right!

Analogy: Imagine your friend claims the lights are off (Statement P is "Lights are off"). If you want to prove P is true using contradiction, you assume the opposite: "Lights are on". If assuming they are on leads you to the absurd conclusion that the room is both bright and completely dark, then the initial assumption ("Lights are on") must be false. Therefore, the lights are off.

The Step-by-Step Process for Proof by Contradiction

Follow these steps rigorously every time you use this method:

Step 1: State the Assumption (Negation)

Assume that the statement you want to prove is false. This is the negation of the original proposition.

Step 2: Use Logical Deduction

Use this assumption as your starting point and apply known mathematical rules and logical deductions (like P1 Proof by Deduction) to manipulate the equations or expressions.

Step 3: Reach a Contradiction

Continue the deduction until you arrive at a statement that is mathematically impossible (e.g., \( 0 = 1 \), or \( 2n+1 \) is even, or a number is simultaneously rational and irrational).

Step 4: Conclude

Because your assumption led to an impossibility (a contradiction), the assumption must be false. Therefore, the original statement must be true.

Key Takeaway: The entire goal is to show that assuming the opposite creates mathematical chaos.

---

The Essential Example: Proving \(\sqrt{2}\) is Irrational

This proof is a canonical example of Proof by Contradiction and is a required piece of knowledge for the P2 curriculum.

The Proposition (P):

The number \(\sqrt{2}\) is irrational.

Step 1: State the Assumption (The Negation)

We assume the opposite: that \(\sqrt{2}\) is rational.

Definition Reminder: A rational number can be written as a fraction \( \frac{p}{q} \), where \(p\) and \(q\) are integers (\(q \neq 0\)). Crucially, we assume that \(p\) and \(q\) have no common factors (the fraction is in its simplest, reduced form).

Therefore, we assume: $$ \sqrt{2} = \frac{p}{q} $$ where \(p, q \in \mathbb{Z}\) and the fraction \(\frac{p}{q}\) is irreducible.

Step 2: Use Logical Deduction

1. Square both sides: $$ 2 = \frac{p^2}{q^2} $$ 2. Rearrange: $$ p^2 = 2q^2 $$

3. Analyze this result: Since \(p^2\) equals 2 times some integer (\(q^2\)), \(p^2\) must be an even number.

4. Crucial Sub-Step: If \(p^2\) is even, then \(p\) itself must also be an even number. (Think: if \(p\) were odd, \(p^2\) would be odd).

5. Since \(p\) is even, we can write \(p\) as \(2k\) for some integer \(k\).

6. Substitute \(p=2k\) back into the equation \( p^2 = 2q^2 \): $$ (2k)^2 = 2q^2 $$ $$ 4k^2 = 2q^2 $$

7. Divide both sides by 2: $$ 2k^2 = q^2 $$

Step 3: Reach a Contradiction

Look at the result \( q^2 = 2k^2 \).

• Since \(q^2\) equals 2 times some integer (\(k^2\)), \(q^2\) must be an even number.
• If \(q^2\) is even, then \(q\) itself must also be an even number.

What have we found?
From Step 2, we deduced that \(p\) is even.
From Step 3, we deduced that \(q\) is even.

If both \(p\) and \(q\) are even, they both share a factor of 2.

This contradicts our initial assumption (from Step 1) that \(p\) and \(q\) had no common factors (i.e., that the fraction \(\frac{p}{q}\) was fully reduced).

Step 4: Conclude

Since the assumption that \(\sqrt{2}\) is rational leads to a logical contradiction, the assumption must be false.
Therefore, the original statement is true: \(\sqrt{2}\) is irrational. Q.E.D.

---

Proof by Contradiction with Specific Number Sets

Contradiction can also be used to prove properties about integers, often involving parity (even/odd).

Example 2: Proving there are infinitely many prime numbers

(This is a famous proof by Euclid, demonstrating the power of contradiction.)

Proposition (P): There are infinitely many prime numbers.

Step 1: State the Assumption

Assume the opposite: There are a finite number of prime numbers.

Step 2: Use Deduction

1. If the number of primes is finite, we can list them all: \(P_1, P_2, P_3, \dots, P_n\), where \(P_n\) is the largest prime number.
2. Consider a new number \(N\), which is the product of all these finite primes plus 1: $$ N = (P_1 \times P_2 \times P_3 \times \dots \times P_n) + 1 $$ 3. Now, try to divide \(N\) by any prime number in our list (\(P_i\)). 4. If we divide \(N\) by \(P_i\), the term \((P_1 \times \dots \times P_n)\) divides perfectly, leaving a remainder of 1.

Step 3: Reach a Contradiction

Since \(N\) has a remainder of 1 when divided by every single prime number in our complete list:

Case A: \(N\) must be a new prime number, not included in our original finite list (\(P_1\) to \(P_n\)).
Case B: \(N\) must be composite (not prime), meaning it is divisible by some smaller prime factor \(X\). But \(X\) cannot be any of the primes \(P_1\) to \(P_n\) (because we saw they all leave a remainder of 1). Therefore, \(X\) must be a new prime, outside our original finite list.

In either case (A or B), we have found a prime number that was not in our supposed "complete list" of all primes.
This contradicts our initial assumption that our list \(P_1\) to \(P_n\) was exhaustive.

Step 4: Conclude

The number of primes cannot be finite. Therefore, there are infinitely many prime numbers.

---

Accessibility Features & Practice Tips

Common Mistakes When Using Contradiction

• Weak Negation: The assumption must be the perfect opposite. If the statement is "All numbers are even," the negation is NOT "All numbers are odd." The correct negation is "At least one number is not even (i.e., is odd)."
• Assuming the Conclusion: You cannot use the truth of the original statement during your deduction steps. Your deduction must flow purely from the false assumption.
• Forgetting Irreducibility: In proofs involving rational numbers (like \(\sqrt{2}\)), always state upfront that \(p\) and \(q\) have no common factors. If you miss this key part, you have nothing to contradict later.

Understanding Mathematical Jargon

Understanding these terms is critical for setting up your assumption (Step 1):

Statement Type	Negation (Assumption)
\(x\) is rational	\(x\) is irrational
\(x\) is a multiple of 3	\(x\) is not a multiple of 3
For all \(n\), P is true	There exists at least one \(n\) where P is false
The set is finite	The set is infinite

Did You Know?

Proof by Contradiction is often considered a non-constructive proof. A constructive proof shows you exactly how to find the answer. A non-constructive proof, like Contradiction, simply guarantees that an answer (or state) must exist because its opposite leads to nonsense.

Key Takeaway Summary

You now have a complete toolkit for proof: Deduction, Exhaustion, Counterexample, and the powerful Contradiction method. Contradiction requires you to systematically assume the opposite and follow the resulting logic until it crashes against a known mathematical fact. Master the \(\sqrt{2}\) example, and you master the technique!

Keep practicing these structured steps, and soon you'll find the logic flows naturally! Good luck!