Deduction, contradiction and induction
Introducido| English | Significado |
|---|---|
| proof by exhaustion/pruːf baɪ eɡˈzɔːstʃn/ | A proof that splits a statement into a finite set of cases covering every possibility and proves each one. |
| counterexample/ˈkaʊntəreɡzæmpl/ | contrajemplo |
A theorem proved by checking every case, 1976
- In 1976, Kenneth Appel and Wolfgang Haken at the University of Illinois proved that any map can be coloured with four colours so that no two neighbouring regions share a colour. They reduced every possible map to 1,936 configurations and used a computer to check each one — over 1,000 hours of computing. It was the first major theorem proved by checking all the cases.
- Proof by exhaustion 穷举证明 splits a statement into a finite set of cases that together cover everything, then proves each case.
Proof by deduction
- Start from definitions and reach the result by logical steps: odd numbers are $2a + 1$ and $2b + 1$, and their sum is $2(a + b + 1)$, which is even.
- A deduction covers every case at once, because $a$ and $b$ stand for any integers.
Which line proves that the product of two consecutive integers is even?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
A deduction that works for every integer $n$.
Proof by exhaustion
- Split into cases that cover everything: even or odd ($2k$, $2k + 1$), or remainders mod 3 ($3k$, $3k + 1$, $3k + 2$).
- Prove each case algebraically — one number per case is not enough — and conclude that the result holds for all.
Deduction, contradiction and induction
A deductive proof starts from stated definitions or assumptions
Distinguish a proof for all integers from one counterexample.
Which set of cases covers every integer?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Every remainder on division by 4.
Verificar $n = 1$, $n = 2$ y $n = 3$ proves that $n^3 - n$ is always even.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Use $2k$ y $2k + 1$ algebraically.
Worked example: squares and multiples of 3
Prove that the square of any integer is either a multiple of 3 or one more than a multiple of 3.
- Case $n = 3k$: $n^2 = 9k^2 = 3(3k^2)$ — a multiple of 3.
- Case $n = 3k + 1$: $n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$.
- Case $n = 3k + 2$: $n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1$. All three cases give remainder 0 or 1. ∎
A favor $n = 3k + 2$, what is $n^2$ in the form $3m + r$?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
$9k^2 + 12k + 4$.
Disproof by counterexample
- In 1772, Leonhard Euler noted that $n^2 + n + 41$ is prime for $n = 0, 1, \dots, 39$.
- At $n = 40$: $1600 + 40 + 41 = 1681 = 41^2$. One counterexample shows "always prime" is false.
Buscar $n^2 + n + 41$ when $n = 41$, and note it is $41 \times 43$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$1681 + 41 + 41$.
Which is a counterexample to "if $a > b$ then $a^2 > b^2$"?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
$1 > -3$ pero $1 < 9$.
Small finite sets
- A claim about a short list can be proved by trying every member: "every prime between 30 and 40 is 1 more than a multiple of 6" — 31 and 37 both are.
- This is exhaustion too, because the list is complete.
Testing 0, 1 and 2 is not the same as testing $3k$, $3k + 1$ and $3k + 2$. Three numbers are only three examples; the algebraic cases include every integer.
For proof by exhaustion, split into cases that cover every possibility (even/odd, remainders mod 3), prove each one algebraically, and conclude that the result holds for all. One counterexample is enough to disprove a general claim.
Prove by exhaustion that $n^3 - n$ is a multiple of 3 for every integer $n$.
Factorise, then cases.