Chapter 5: Reading a Proof
Introduction (high school to first-year university)
5.1 The basic structure of a proof
A proof basically has the following structure:
Symbols for the end of a proof
- □ (open square): the end-of-proof symbol
- ■ (filled square): same as above
- Q.E.D.: abbreviation of the Latin "Quod Erat Demonstrandum" (what was to be demonstrated has been demonstrated)
5.2 Example 1: sum of even numbers
Theorem
The sum of two even numbers is even.
Before reading the proof
First, let us organize the statement:
- Hypothesis: $a$ and $b$ are even.
- Conclusion: $a + b$ is even.
Proof
Let $a$ and $b$ be even.
Step 1: By the definition of even, there exist integers $m, n$ such that
$$a = 2m, \quad b = 2n.$$Step 2: Computing $a + b$,
\begin{align} a + b &= 2m + 2n \\ &= 2(m + n). \end{align}Step 3: Since $m + n$ is an integer, setting $k = m + n$ gives
$$a + b = 2k,$$which means $a + b$ is even. $\square$
Walkthrough of the proof
5.3 Example 2: product of odd numbers
Theorem
The product of two odd numbers is odd.
Organizing the statement
- Hypothesis: $a$ and $b$ are odd.
- Conclusion: $a \times b$ is odd.
Definition of odd
An integer $n$ is odd if there exists an integer $k$ such that $n = 2k + 1$.
Proof
Let $a$ and $b$ be odd.
Step 1: By the definition of odd, there exist integers $m, n$ such that
$$a = 2m + 1, \quad b = 2n + 1.$$Step 2: Compute $a \times b$.
\begin{align} a \times b &= (2m + 1)(2n + 1) \\ &= 4mn + 2m + 2n + 1 \quad \text{(expand)}\\ &= 2(2mn + m + n) + 1 \quad \text{(factor out 2)} \end{align}Step 3: Since $2mn + m + n$ is an integer, setting $k = 2mn + m + n$ gives
$$a \times b = 2k + 1,$$which means $a \times b$ is odd. $\square$
What each step is doing
| Step | What it does |
|---|---|
| Step 1 | Express the hypothesis as a formula via the definition |
| Step 2 | Transform the expression toward the target form |
| Step 3 | Confirm the conclusion matches the definition |
5.4 Example 3: an inequality
Theorem
If $a > 0$ and $b > 0$, then $a + b > 0$.
Proof
Assume $a > 0$ and $b > 0$.
Step 1: Adding $b$ to both sides of $a > 0$ (adding the same number to both sides preserves the inequality),
$$a + b > 0 + b = b.$$Step 2: Since $b > 0$,
$$a + b > b > 0.$$Step 3: Therefore
$$a + b > 0$$holds. $\square$
Transitivity of inequalities
This proof used transitivity:
$$x > y \text{ and } y > z \Rightarrow x > z.$$5.5 Tips for reading a proof
Tip 1: First grasp the big picture
- What is being assumed?
- What is being shown?
- By what strategy is it proved?
Tip 2: Check the justification of each step
- "Why is this transformation allowed?"
- "Which definition or theorem is being used?"
Tip 3: Confirm with concrete examples
- Trace an abstract proof with concrete numbers.
- Example: follow the sum-of-evens proof with $a = 4, b = 6$.
Confirming with an example: sum of evens
With $a = 4 = 2 \times 2$ and $b = 6 = 2 \times 3$,
$a + b = 4 + 6 = 10 = 2 \times 5$.
Indeed $m = 2, n = 3, k = m + n = 5$, just as the proof says!
Tip 4: Mark the parts you do not understand
Do not try to understand everything at once; clearly mark what you do not understand and look it up later.
5.6 Chapter summary
| Point | Content |
|---|---|
| Structure of a proof | Hypothesis → inference → conclusion |
| Using definitions | Express a definition as a formula and use it in computation |
| Tips for reading | Grasp the big picture, check justifications, use examples |
Coming next
The next chapter works through the exercises of the Introduction. Let us review what we have covered so far.
Frequently asked questions
Q1: What is the basic mindset for reading a mathematical proof?
A: When reading a proof, proceed while checking "why does each step hold?". Verify for yourself even the parts marked "clearly" or "easily shown," and always keep the hypothesis and the conclusion in mind.
Q2: How do you choose between direct and indirect proof (contradiction / contrapositive)?
A: A direct proof derives the conclusion from the hypothesis and is the basic method. Proof by contradiction assumes the conclusion is false and derives a contradiction, suited to showing "does not exist" or "there are infinitely many." The contrapositive method shows $\neg Q \Rightarrow \neg P$ instead of $P \Rightarrow Q$.
Q3: What is the pattern for proving a necessary and sufficient condition?
A: To show $P \Leftrightarrow Q$, prove $P \Rightarrow Q$ (sufficiency) and $Q \Rightarrow P$ (necessity) separately. The standard form is "(⇒) Assuming $P$, … we obtain $Q$. (⇐) Assuming $Q$, …".