Proof

Chapter 1 – Proof

General Introduction
Mathematics is often described as the art of true statements. What makes a mathematical statement true, though, is not the consensus of mathematicians, nor the weight of experimental evidence, but a proof — a logical argument that starts from accepted facts (axioms, definitions or previously-proved results), and compels every rational reader to agree with the conclusion.

Why begin the A-Level course with proof?

• Cross-disciplinary glue. Whether you later study calculus, statistics, physics or computer science, rigourous reasoning underpins every topic.

• Life skill. Clear argumentation is prized in law, engineering, finance — even many decision-making.

• Gateway to creativity. Once you can justify new ideas, you are free to invent boldly.

• Historical note. Euclid’s Elements (≈ 300 BC) collected known geometry in 465 theorems, each proved rigorously. Twenty-three centuries later the structure of those proofs still guides textbooks (including this one!).

---

Section – Foundations of Proof

In this opening section we explore two complementary viewpoints:

Mastery here will let you tackle every later proof you meet, from trigonometric identities to induction or series.

---

Lesson 1.1 — Structures of Proof

Objectives

By the end you should be able to

1. Recognise the assumptions → conclusion layout of a proof.

2. Employ correct logical notation (⇒, ⇔, ∴, ∀, ∃ ).

3. Distinguish direct proof, proof by contrapositive, and proof by contradiction, choosing the most efficient route.

---

1. Key Concepts & Definitions

Notation refresher

• ∀ “for all”, ∃ “there exists”, ⇔ “therefore”, ⇒ “implies”.

• Use words and ∧, ∨, not rather than “/” or “x” which can be ambiguous.

---

2. Illustrative Examples

Example 1 — Direct proof Claim. The sum of two even integers is even.
Proof. Let the integers be \(2k\) and \(2m\)  (\(k, m \in \mathbb{Z}\)).
\(2k + 2m = 2(k + m)\). Since \(k + m\) is an integer, the sum is 2 × integer ⇒ even. ∴ proved.

Example 2 — Contrapositive
Claim. If \(n^2\) is even, then \(n\) is even. Contrapositive. If  \(n\) is odd, then \(n^2\) is odd. Proof of contrapositive.
Let n = 2k + 1. Then \(n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\) ⇒ odd. Therefore contrapositive true ⇒ original claim true.

Example 3 — Contradiction Claim. \(\sqrt{2}\) is irrational.
Assume opposite: \(\sqrt{2} = \frac{a}{b}\) in lowest terms. ⇒ \(2 = \frac{a^2}{b^2}\) ⇒ \(a^2 = 2b^2\) ⇒ \(a\) even ⇒ write \(a = 2k\) ⇒ \(a^2 = 4k^2 ⇒ 2b^2 = 4k^2 ⇒ b^2 = 2k^2 ⇒ b\) even ⇒ \(a\) and \(b\) share factor 2 though assumed coprime.
Hence assumption false; \(\sqrt{2}\) is irrational.

---

3. Points of Caution

• Forgetting the domain. Always state “for all \(n \in \mathbb{Z}\)” or similar.

• Arrow abuse. = is ≠ ⇒; avoid strings like “2 = 4 ⇒ n = 0”.

• Contradiction fallacy. You must actually reach an impossible statement (e.g. 0 = 1), not merely an unpleasant one!

Lesson 1.2 — Disproof & Counter-example

Objectives

You will learn to

1. Disprove universal claims with a single counter-example.

2. Prove conditional statements false by finding where hypothesis true but conclusion false.

3. Apply exhaustion logically (finite cases only).

4. Detect and critique faulty reasoning in others’ proofs.

---

1. Constructing Counter-examples

A statement of the form “For all x, P(x)” is falsified by one x with ¬P(x). Analogy: To show “Every swan is white” false, one black swan in Perth suffices.

Example 4. “All primes are odd.” Counter-example: 2.
Example 5. “If x² = x then x = 1.” Counter-example: x = 0 (since \(0^2 = 0\) but \(0 \neq 1\)).

Checklist

1. Understand the claim precisely.

2. Identify minimal conditions to break it.

3. Exhibit the object and verify it really violates P(x).

---

2. Proof by Exhaustion

Sometimes only a finite set of possibilities exists; you may verify each.

Example 6. Show that a quadratic \(ax^2 + bx + c\), (\(a, b, c \in \mathbb{Z}\),  \(|a|=|b|=|c|=1\)) has at least one real root.
There are 8 sign choices; compute discriminant in each. (Students will practise this in Exercise 8.)

Pitfall: “Checking a few examples” ≠ exhaustion unless you justify that you have checked ALL possibilities.

---

3. Critiquing Incorrect Reasoning

Flawed proof (popular on the internet). Take a = b ≠ 0. Multiply both sides by a: \(a^2 = ab\). Subtract: \(a^2 – b^2 = ab – b^2\).
Factor: \((a + b)(a – b) = b(a – b)\). Divide by (a − b):
\(a + b = b\). Since \(a = b\), this gives \(2b = b.\) Let’s assume \(a = b = 1 \Rightarrow 2 = 1\).
Error? Division by \((a – b) = 0\) (since \(a = b\)).
Division by zero is undefined ⇒ argument collapses.

Learning to spot such hidden assumptions is just as important as crafting your own proofs.

---

Practice Exercises

How to use

1. Attempt without notes.

2. Check the hint only if stuck.

3. Compare with Answer Keys.

4. Log any errors and revisit the relevant lesson section.

---

A. Easy

1. Prove directly: The sum of three consecutive integers is divisible by 3.

2. Use contrapositive: If \(3n\) is odd, then n is odd.

3. Disprove: “For all real \(x, x^2 < x\).”

4. Spot the mistake: \(\frac{1}{0} = 0\), therefore \(0 \times 0 = 1\). Explain why this is invalid.

5. Exhaustion: Show that any integer \(m\) with \(0 \leq m \leq 3\) satisfies \(m^4 \equiv m\) (mod 4).

---

B. Intermediate

6. Direct proof: For integers \(p, q\), if \(p\) is even and \(q\) is odd, then \(p^2 + q^2\) is odd.

7. Contradiction: There is no smallest positive rational number.

8. Exhaustion challenge: For signs \(a, b, c \in \{-1,1\}\), prove \(ax^2 + bx + c \geq 1\) has a real root (hint: discriminant table).

9. Construct counter-example to show: “If \(n\) is even then \(n^2\) is even” does hold, but the converse of “If \(n^2\) is even then \(n\) is even” might fail over rationals.

10. Critique: A student writes “Since \(n^2\) ends with 5, \(n\) ends with \(5 ⇒ n\) divisible by \(5 ⇒ n^2\) divisible by 25.” Identify assumption leaps.

C. Advanced

11. Prove by contradiction: There are infinitely many primes of the form \(4k + 3\). (Outline hints provided.)

12. Using contrapositive, prove: If \(a, b\) are integers and \(a^2\) divides \(b\), then \(a\) divides \(b\).

13. Show that no integer of the form \(10k + 6\) can be expressed as the sum of two squares of integers.

14. (Problem-solving) Suppose \(n \in \mathbb{N}\) and \(n(n + 1)\) is a perfect cube. Prove \(n = 0\).

---

Detailed Answer Keys

Work through the reasoning line by line; don’t just skim for the final sentence!

---

A. Easy Solutions

1. Let integers be \(k – 1, k, k + 1\). Sum = \(3k \Rightarrow\) divisible by 3.

2. Contrapositive: If n is even \(\Rightarrow 3n\) is even \(. \Rightarrow\) can’t be odd. Thus original statement true.

3. Counter-example: \(x = 0.5 \Rightarrow 0.25 < 0.5\).

4. \(\frac{1}{0}\) undefined; \(\infty\) symbol not a number; multiplication rules do not apply.

5. Check \(m = 0,1,2,3;\) residues \(0^4, 1^4, 2^4, 3^4 = 0, 1, 0, 1\) (mod 4).

---

B. Intermediate Solutions

6. \(p = 2k\) squared ⇒ \(4k^2\); \(q = 2k + 1\) squared ⇒ \(4k^2 + 4k + 1\). \( p^2 + q^2\)  ⇒ \(8k^2 + 4k + 1 = 4k(2k+1) + 1\);  \(4k\) is even, \(2k + 1\) is odd. multiplying an even number with an odd one always give an even number, son \(4k(2k+1)\) is even  \(\Rightarrow 4k(2k+1) + 1\) is odd

7. Assume smallest positive rational \(r = \frac{(\frac{a}{2})}{b}\) in lowest form. Then \((a – 1)/b\) is even smaller ⇒ a = 1. But 1/b not necessarily smaller?
   Use \((a – 1)/b\) if \(a > 1\), else \(\frac{(a)}{(2b)}\). Leads to contradiction.

8. Calculate \(b^2 – 4ac\) values; at least one row: positive.

9. Over \(\mathbb{Q}\): \(n = \sqrt{2}\) ⇒ \(n^2\) even but \(n\) not even. Show converse fails.

10. Missing link: “n ends with 5 ⇒ n divisible by 5” is correct, but leap to \(n^2\) divisible by 25 assumes multiplication by itself adds another factor 5.

C. Advanced Solutions

11. Assume finite list: \(p_1, …, p_k \equiv 3\) (mod 4). Consider \(N = 4(p_1 … p_k) – 1 \equiv 3\) (mod 4).
    Any prime divisor \(q\) of \(N\) cannot be \(\equiv 2\) nor \(\equiv 1\) (mod 4) (quadratic residues argument). Thus \(q \equiv 3\) (mod 4) but not in list ⇒ contradiction.

12. Contrapositive: If \(a ∤ b\) ⇒ ∃ prime \(p|a\) with \(p ∤ b\) ⇒ \(p^2 ∤ b\) ⇒ \(a^2 ∤ b\). 

13. Squares mod 4 are 0 or 1; sum of two squares mod 10 cannot include 6.

14. \(n(n+1)\) cube ⇒ consecutive integers form a cube; only possible at \(n = 0\) by bounding argument (use \(\gcd(n, n+1) = 1\)).

---

Practical Application & Further Exploration

1. Computer Science. Correctness proofs for algorithms (e.g. loop invariants) mirror direct proofs.

2. Physics. Dimensional analysis often disproves impossible formulae via counter-example substitution.

3. Engineering. Safety cases for aircraft rely on exception trees and identifying counter-scenarios.

4. Pure Maths preview. Proof styles you met reappear as mathematical induction (Chapter 2) and proof by construction in combinatorics.

---

Curiosity prompts

• Investigate Hilbert’s programme: Could all of mathematics be reduced to purely mechanical proof?

• Read about the first computer-verified proof of the Four-Colour Theorem (1976) — an early blend of exhaustion and algorithmic checking!

---

Summary Checklist

• I can state what a proof is and outline its structure.

• I can choose and execute direct, contrapositive or contradiction proofs.

• I can destroy a false universal claim with a single counter-example.

• I can scrutinise and detect flaws in a presented argument.