Lesson 4 of 8 · 15 min

Examples and counterexamples

Disprove a "for all" statement with a single counterexample, prove a "there exists" statement with a single example, and see why examples alone never prove a general result.

What you will be able to do

  • Explain why checking examples cannot prove a statement about infinitely many numbers.
  • Disprove a ∀\forall statement or an implication with one counterexample, showing it meets the hypothesis and fails the conclusion.
  • Prove a ∃\exists statement with one example.

In 1772, Leonhard Euler observed the prime-producing pattern now written as n2+n+41n^2 + n + 41: it is prime for n=0,1,…,39n = 0, 1, \ldots, 39. Try it yourself: n=1n = 1 gives 43, n=2n = 2 gives 47, n=3n = 3 gives 53. The pattern holds all the way to n=39n = 39.

Values of n2+n+41n^2 + n + 41. Thirty-nine successes in a row, then a failure.
nnn2+n+41n^2 + n + 41Prime?
143yes
247yes
353yes
461yes
571yes
……yes, every time
381523yes
391601yes
401681no: 1681=4121681 = 41^2

At n=40n = 40, n2+n+41=402+40+41=40(40+1)+41=41×41n^2 + n + 41 = 40^2 + 40 + 41 = 40(40 + 1) + 41 = 41 \times 41. So the statement "∀n∈Z+\forall n \in \mathbb{Z}^+, n2+n+41n^2 + n + 41 is prime" is false, and n=40n = 40 is a counterexample. Thirty-nine examples did not prove it; one counterexample disproved it.

Key idea

Counterexamples and examples

  • A counterexample to "∀x, P(x)⇒Q(x)\forall x,\ P(x) \Rightarrow Q(x)" is one value of xx for which P(x)P(x) is true and Q(x)Q(x) is false. One is enough to show the statement is false.
  • An example is enough to prove "∃x, P(x)\exists x,\ P(x)": show one xx that works.
  • Examples can never prove a ∀\forall statement about infinitely many numbers, however many you check.
Interactive

Is 2n>n22^n > n^2 for every positive integer?

Trace both curves at x=1,2,3,4,5x = 1, 2, 3, 4, 5. Where is 2x2^x not above x2x^2? Any positive integer there is a counterexample to "∀n∈Z+, 2n>n2\forall n \in \mathbb{Z}^+,\ 2^n > n^2".

Find the smallest positive integer nn that is a counterexample to the statement "∀n∈Z+, 2n>n2\forall n \in \mathbb{Z}^+,\ 2^n > n^2".

Worked example

Disproving a statement about squares

  • Simple familiar
  • Technology free

Prove or disprove: for all a,b∈Ra, b \in \mathbb{R}, if a2>b2a^2 > b^2 then a>ba > b.

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Test cases, especially negatives, zero and fractions.

  2. Pick one value that makes the hypothesis true and the conclusion false.

  3. Show both calculations and state the conclusion.

Watch out for

  • Choosing a=1a = 1, b=−3b = -3: then a2<b2a^2 < b^2, so the hypothesis fails and it is not a counterexample.

Common mistake

A counterexample must satisfy the hypothesis

To disprove "if nn is prime, then 2n+12n + 1 is prime", the value n=4n = 4 is no use: 44 is not prime, so the statement makes no claim about it. You need a prime nn with 2n+12n + 1 composite, such as n=7n = 7: 2(7)+1=15=3×52(7) + 1 = 15 = 3 \times 5.

Statement: "For all x∈Rx \in \mathbb{R}, if x≠0x \ne 0 then x+1x≥2x + \frac{1}{x} \ge 2." Select every value of xx that is a counterexample.

Select all that apply.

Examples do prove "there exists". "There exists an even prime" is proved by 22. "∃x∈Q′, x2∈Z\exists x \in \mathbb{Q}',\ x^2 \in \mathbb{Z}" is proved by x=3x = \sqrt{3}, because (3)2=3(\sqrt{3})^2 = 3. And when a set is finite, you can prove a "for all" statement by checking every element. That is called proof by exhaustion: for example, every integer from 1 to 10 has a square with last digit 0, 1, 4, 5, 6 or 9, which you can check one by one.

Worked example

Sums of irrational numbers

  • Simple familiar
  • Technology free

(a) Disprove the statement "the sum of any two irrational numbers is irrational".

(b) Hence decide whether "∃a,b∈Q′\exists a, b \in \mathbb{Q}' such that a+b∈Qa + b \in \mathbb{Q}" is true.

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Look for irrationals whose irrational parts cancel, such as 2\sqrt{2} and 3−23 - \sqrt{2}.

  2. Show each chosen number really is irrational, and that the result is rational.

Watch out for

  • Using 4\sqrt{4} as an irrational number: 4=2\sqrt{4} = 2.

Exam tip

How to write a counterexample

State the value, show the calculation, and say why it is a counterexample: "Let a=−3a = -3 and b=1b = 1. Then a2=9>1=b2a^2 = 9 > 1 = b^2, but a<ba < b. So the hypothesis holds and the conclusion fails, and the statement is false." A bare "a=−3a = -3" may not earn the mark.

Summary

  • One counterexample disproves a ∀\forall statement; one example proves an ∃\exists statement.

  • No number of examples proves a ∀\forall statement about infinitely many numbers (but checking every case of a finite set is a proof).

  • A counterexample to P⇒QP \Rightarrow Q must make PP true and QQ false.

  • Show the working for a counterexample and say clearly which part holds and which fails.

Finished the lesson?

Try the 2 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 4 of 80% read

Save your progress with a free account