Chapter 7 Disproving a conjecture

We’ve discussed truth values a lot already, and we’ve agreed that mathematical statements must be either true or they are false. Once we’ve decided that we’re interested in finding out the truth value of a mathematical statement, we rename it a conjecture and get to work…

To prove a conjecture means to show that its truth value is “true.” To disprove a conjecture means to show that its truth value is “false.”

In this chapter we’ll discuss disproving conjectures. There’s two ways to show a conjecture is false.

7.1 Finding a counterexample

Disproving false conjectures is generally easier than proving true conjectures. This is because all false conjectures have counterexamples.

Take a look at the following two conjectures:

Example 7.1 No Chinese citizen has green eyes.

Example 7.2 All Irish citizens have a vowel in their surname.

How you would prove, or disprove, these conjectures?

• To prove this first one, we would need to check the eye colour of all Chinese citizens. That’s because this is a conjecture about all Chinese citizens. How long is that going to take!?! Is it even possible?!? But to disprove this conjecture, we just need to find one Chinese citizen with green eyes. Much easier! This single green-eyed Chinese citizen would be our counterexample.

• To prove the second conjecture, we would need to consult a database of the surnames of all Irish citizens. We would then set up a computer to check that each of them contain a vowel (a, e, i, o or u). To disprove the conjecture, we would just need to identify just one Irish citizen whose surname did not contain a vowel. This could be done using the database approach as well, or maybe we know of a famous Irish person whose surname is vowel-less. This one person would be our counterexample.

Just one counterexample is needed to disprove a false conjecture. Of course, we might find lots of counterexamples, i.e. many Chinese citizens who have green eyes, or many Irish citizens without vowels in their surname. This would be great - it would probably make our job of finding a counterexample easier! But even if there is only one Chinese citizen with green eyes, or one Irish citizen with a surname devoid of vowels, that is enough to show the conjecture is false.

Exercise 7.1 The following conjectures are all false. Find a single counterexample which shows this.

1. All prime numbers are odd.
2. \((a + b)^2 = a^2 + b^2\) for any numbers \(a\) and \(b\).
3. All sheep in South Africa are white. (Good luck Googling!)
4. The national flags of all UN members are rectangular.
5. All numbers are either positive or negative.
6. \(a^2 > a\), where \(a\) is a whole number.
7. If \(a\) is a whole number and \(a^2\) is divisible by \(4\), then \(a\) is divisible by 4.

Exercise 7.2 In the last exercise, you found counterexamples which disproved the conjectures.

1. Which of the conjectures above have just one counterexample?
2. Which of the conjectures above have a few counterexamples?
3. Which of the conjectures above have an infinite number of counterexamples?

7.2 Finding a disproof

Finding a counterexample is the most common and popular way of disproving a conjecture. It’s also possible to disprove a conjecture without finding a counterexample. This is called finding a disproof, and often happens when you set out looking for a proof and it goes wrong! We’ll look at this a bit later.