Direct Proof

Disproof by Counterexample

Recall (or visit my logic page) that a conditional statement says that a certain property is true for every member of a certain set. If we can find one member of the specified set for which the example of a member of the set for which the specified properties do not hold is called a counterexample of the statement. Stating a counterexample of a conditional statement will thus disprove the statement. Note that here by "disprove it" I mean "prove it to be false."

Now, we show how to disprove a statement of the form:

∀ x ∈ D, if P(x), then Q(x)

We know that to show this statement is false is equivalent to show that its negation is true. The negation of the statement is:

∃ x ∈ D such that P(x) and ~Q(x)

Hence, the method of disproof by counterexample is as follows:

To disprove a Statement of the form:

∀ x ∈ D, if P(x), then Q(x)

Find a value of x in the domain D for which antecedent P(x) is true and consequent Q(x) is false. Such an x is called a counterexample.

The use of a counterexample to disprove a statement is simple and easy, if counterexample can be found, but this is not always possible. Goldbach (1690 - 1764) developed the conjecture that "every even number except two could be represented as the sum of two primes." No one has yet proved or disproved this statement. Note that inductive reasoning (in contrast to deductive reasoning) leads only to tentative or probable conclusions called conjectures.

As an example, disprove the following statement by finding a counterexample:

∀ real numbers a and b, if a² = b², then a = b.

To disprove this universal statement, we need to find real numbers a and b so that antecedent a² = b² is true and consequent a = b is false. In other words, we need to find real numbers such that a² = b² and a ≠ b.

Let us suppose that a = 1 and b = -1.

Then (a² = b²) is 1 = 1 and (a ≠ b) is 1 ≠ -1.

Example 2: Disprove the following universal statement:

For all positive integers n, if n is prime, then n is odd

[Recall, to show the given statement is false, all we needed to do is to show its negation is true.]

And the negation of the above statement is:

∃ an integer n such that n is prime and n is not odd

or equivalently,

∃ an integer n such that n is prime and n is even

Now keeping the this in mind, let n = 2. Then n is prime and n is even. Hence, ∃ an integer n such that n is prime and n is even [is a true statement], and so the given statement is false.

Example 3: Disprove the following statement by counterexample:

If a sum of two integers is even, then one of the summands is even.

[Note that in the expression, a + b = c, a and b are summands and c is the sum.]

Our counterexample would be:

                                        Let m = 1 and n = 3.

                                        Then, we have

                                                        m + n = 1 + 3

                                                                  = 4

That is, (m + n) is even number, but neither summand m nor n is even.