Deduction, contradiction and counterexamples
Introduzido| English | Significado |
|---|---|
| counterexample/ˈkaʊntəreɡzæmpl/ | Contraexemplo |
Primes that never run out, about 300 BC
- In Book IX of the Elements, written about 300 BC, Euclid proved that there are more primes than any finite list. Suppose the list $p_1, p_2, \dots, p_k$ is complete. Then $p_1p_2\cdots p_k + 1$ leaves remainder 1 when divided by each of them, so it has a prime factor not on the list. The argument is over 2,300 years old and still exact. Checking examples can never do this: only a proof covers every case.
- A-level proof uses three methods: deduction, contradiction and disproof by counterexample 反例.
Proof by deduction
- Start from definitions and known facts, and reach the result in logical steps.
- Odd numbers are $2a + 1$ and $2b + 1$; their sum is $2(a + b + 1)$, which is even for all integers $a, b$.
Which expression shows that the product of two odd numbers is odd?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
It has the form $2k + 1$ for every $a, b$.
Proof by contradiction
- Assume the statement is false, then show this leads to something impossible.
- So the assumption was wrong, and the statement is true.
Deduction, contradiction and counterexamples
A deductive proof starts from stated definitions or assumptions
Distinguish a proof for all integers from one counterexample.
To prove "there is no largest even number" by contradiction, what do you assume?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Assume the opposite of the statement.
Worked example: $\sqrt{2}$ is irrational
Prove by contradiction that $\sqrt{2}$ is irrational.
- Assume: $\sqrt{2} = \dfrac{a}{b}$ with integers $a, b$ having no common factor. Then $a^2 = 2b^2$, so $a^2$ is even, so $a$ is even: $a = 2c$.
- Continue: $4c^2 = 2b^2$, so $b^2 = 2c^2$, so $b$ is even too.
- Contradiction: $a$ and $b$ share the factor 2, against the assumption. Hence $\sqrt{2}$ is irrational.
In the proof that $\sqrt{2}$ is irrational, "$a^2$ is even, so $a$ is even" is a valid step.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
If $a$ were odd, $a^2$ would be odd.
Disproof by counterexample
- One example where a statement fails is enough to show it is false.
- "$2^n - 1$ is prime for every prime $n$": $n = 11$ gives $2047 = 23 \times 89$, so the claim is false.
Claim: $n^2 + n + 1$ is prime for every positive integer $n$. Give the smallest $n$ that is a counterexample.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
$n = 4$ gives $21 = 3 \times 7$.
Writing a proof
- Define your letters ("let $n$ be an integer"), give a reason for every step, and end with a concluding sentence.
- For an "if and only if" statement, prove both directions.
Put the steps of a proof by contradiction in order.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Assume, deduce, contradict, conclude.
Examples are not a proof. $n^2 - n + 11$ is prime for $n = 1, 2, \dots, 10$, but $n = 11$ gives $121 = 11^2$. However many cases work, a general statement needs a general argument.
A claim about all integers is proved once it has been checked for the first 1000 integers.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
A later integer could fail.
Deduction builds from definitions to the result; contradiction assumes the opposite and reaches an impossibility; one counterexample disproves a claim. Name your variables, justify each step, and conclude in words — never rely on checking examples.
Prove by contradiction that if $n^2$ is even, then $n$ is even.
The step used inside the $\sqrt{2}$ proof.