Mathematics | Proof

Welcome to Unit P4: Mastering Mathematical Proof!

Hello future mathematicians! Proof might seem like a scary word, but it is the absolute backbone of mathematics. In Pure Mathematics 4 (P4), we move beyond just using formulas; we learn how to definitively show why they are true.

This chapter will equip you with one of the most powerful and sophisticated proof techniques: Proof by Contradiction. Don't worry if this seems tricky at first—we will break it down into simple, manageable steps. By the end of this unit, you'll be able to tackle complex statements and prove them with certainty!

1. Review: Essential Proof Techniques

Before diving into the P4 specialisation, let's quickly review the proof methods you should already be familiar with, as they often form parts of more complex P4 proofs.

1.1 Proof by Deduction (The Standard Method)

This is the most common method. You start with known facts (axioms, definitions, or proven theorems) and use logical, sequential steps to arrive at the desired conclusion.

• Goal: Show Statement A leads to Statement B.
• Example: Prove that the sum of any two consecutive odd numbers is a multiple of 4.

  Step 1: Define the numbers. Let \(2k+1\) be the first odd number. The next consecutive odd number is \((2k+1) + 2 = 2k+3\).

  Step 2: Add them: \((2k+1) + (2k+3) = 4k + 4\).

  Step 3: Factorise: \(4k + 4 = 4(k+1)\).

  Step 4: Conclusion: Since the result can be written as 4 multiplied by an integer \((k+1)\), the sum is a multiple of 4.

1.2 Disproof by Counterexample

You cannot prove a statement is true by showing examples. However, you can prove a statement is false by finding just one single case that contradicts the claim. This is called a counterexample.

• The Claim: "For all integers \(n\), \(n^2 + n + 11\) is a prime number."
• The Disproof: Let \(n = 10\). Then \(n^2 + n + 11 = 100 + 10 + 11 = 121\). Since \(121 = 11 \times 11\), it is not a prime number.
• Key Takeaway: One counterexample is all you need to destroy a universal conjecture.

2. The P4 Specialisation: Proof by Contradiction

Proof by Contradiction (sometimes called Reductio ad Absurdum, meaning "reduction to absurdity") is a cornerstone of advanced mathematics and is often heavily tested in P4.

2.1 What is Proof by Contradiction?

The idea is simple yet brilliant: to prove a statement is TRUE, you temporarily assume that it is FALSE. You then follow the logical consequences of this false assumption until you reach a conclusion that is utterly impossible or contradicts a known fact (an absurdity). Since the logic was sound, the starting assumption (that the statement was false) must have been incorrect, meaning the original statement must be TRUE.

Analogy: Imagine you are trying to prove a friend, Sarah, is innocent. Instead, you assume she is guilty. If following the evidence based on her guilt leads to the conclusion that she was in two different countries at the exact same moment (an absurdity), then your initial assumption—that she was guilty—must be wrong. Therefore, she is innocent.

2.2 The Step-by-Step Process

Follow these four crucial steps every time you attempt a proof by contradiction:

1. State the Assumption (The Negation): Clearly state the opposite of what you are trying to prove. Use phrasing like: "Assume, for the sake of contradiction, that..."
2. Develop the Logical Argument: Use mathematical definitions, known theorems, and deduction to logically work through the consequences of your assumption.
3. Reach the Contradiction: Show that your logical argument leads to a result that is impossible (e.g., \(0=1\), or that an integer must be a fraction, or that a number is simultaneously even and odd).
4. Conclude and Affirm: State clearly that because a contradiction has been reached, the initial assumption must be false. Therefore, the original statement must be true.

2.3 Classic Example: Proving the Irrationality of \(\sqrt{2}\)

This is the most famous proof by contradiction and a high-stakes exam question. You must know how to structure this proof perfectly.

Statement to Prove: \(\sqrt{2}\) is an irrational number.

Step 1: State the Assumption (The Negation)

Assume, for contradiction, that \(\sqrt{2}\) is a rational number.
If \(\sqrt{2}\) is rational, it can be written as a fraction in its simplest form:
$$\sqrt{2} = \frac{a}{b}$$

where \(a\) and \(b\) are integers, \(b \neq 0\), and \(a\) and \(b\) have no common factors (i.e., the fraction is fully simplified).

Step 2: Develop the Logical Argument

Square both sides: $$\left(\sqrt{2}\right)^2 = \left(\frac{a}{b}\right)^2$$ $$2 = \frac{a^2}{b^2}$$

Rearrange to make \(a^2\) the subject:

$$a^2 = 2b^2 \quad (*)$$

Since \(a^2\) equals 2 multiplied by an integer (\(b^2\)), \(a^2\) must be an even number.

If \(a^2\) is even, then \(a\) itself must also be even. (If \(a\) were odd, \(a^2\) would be odd).
Since \(a\) is even, we can write \(a\) as \(2k\), where \(k\) is an integer.

Now, substitute \(a = 2k\) back into equation \((*)\):

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

Divide both sides by 2:

$$2k^2 = b^2$$

Since \(b^2\) equals 2 multiplied by an integer (\(k^2\)), \(b^2\) must be an even number.
If \(b^2\) is even, then \(b\) itself must also be even.

Step 3: Reach the Contradiction

From our working, we found:

• \(a\) is even.
• \(b\) is even.

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

This contradicts our initial assumption (Step 1) that the fraction \(\frac{a}{b}\) was in its simplest form (i.e., that \(a\) and \(b\) had no common factors).

Step 4: Conclude and Affirm

Since the initial assumption that \(\sqrt{2}\) is rational leads to a contradiction, the assumption must be false.
Therefore, \(\sqrt{2}\) must be an irrational number. (Q.E.D. - Quod Erat Demonstrandum, "which was to be shown").

3. Common Contradiction Scenarios and Pitfalls

3.1 Proofs Involving Number Theory

Contradiction is often used to prove statements about primes, limits, or the non-existence of something.

Example Scenario: Prove that there is no greatest odd integer.

• Assumption: Assume there IS a greatest odd integer, call it \(N\).
• Argument: Consider the number \(N+2\). Since \(N\) is odd, \(N+2\) is also odd.
• Contradiction: \(N+2 > N\). This contradicts the assumption that \(N\) was the greatest odd integer.
• Conclusion: There is no greatest odd integer.

3.2 Common Mistakes to Avoid

When writing a proof by contradiction, struggling students often make two critical errors:

Mistake 1: Assuming the Wrong Negation

• If the statement is "All integers are even," the negation is "There exists at least one integer that is NOT even (i.e., is odd)."
• AVOID: Confusing "not all" with "none." The negation of "A is true for all X" is "A is false for at least one X."

Mistake 2: Failing to State the Simplest Form Assumption (Crucial for irrationality proofs)

• When dealing with rational numbers \(\frac{a}{b}\), you must explicitly state that \(a\) and \(b\) are co-prime (have no common factors). If you skip this, you cannot logically generate the final contradiction.

Mistake 3: Jumping to the Conclusion

• You must explicitly state where the contradiction occurs and how it relates to the initial assumption. Do not just stop after finding \(a\) and \(b\) are even; you must say: "This contradicts the assumption that \(\frac{a}{b}\) was in its simplest form."

3.3 Proofs in P4 Contexts (Brief Connection)

While the method (contradiction) remains the same, in P4 you might be asked to apply it to concepts like infinite sequences, convergence, or advanced inequalities that involve bounds or limits. The technique of assuming the opposite holds and showing it breaks a fundamental mathematical rule is universally applicable.

Key Takeaway from the Proof Chapter

Proof by Contradiction is your mathematical superpower when direct deduction fails. It allows you to prove impossibility, irrationality, and non-existence with absolute certainty. Remember the structure: assume the opposite, follow the logic rigorously, and expose the absurdity!

Keep practising the \(\sqrt{2}\) proof—it is the best training ground for this crucial P4 skill!