If a program gives the right answer for the few inputs you tried, can you say it’s right for every input? Testing can find an input that fails, but it can’t show that no such input exists. The way to be sure something is true in every case is a mathematical proof.
A sentence that is clearly either true or false is called a proposition. “7 is odd” is a true proposition, while “this song is good” is not a proposition, since the answer differs from person to person.
Let’s take an example of a proposition. For that we need primes. A number greater than 1 that is divisible only by 1 and itself is called a prime number. 2, 3, 5, and 7 are primes, and 15 is not, since it is divisible by 3 and 5.
“Whatever integer n ≥ 0 is, n² + n + 41 is prime.” n = 0 gives 41, n = 1 gives 43, n = 2 gives 47. All prime.
A proposition that held 40 times in a row becomes false because of a single n = 40. Such a case is called a counterexample. One counterexample is enough to show something is false.
Showing something is true is harder. There are endlessly many n, so we can’t check them all; we need a way to show it’s true for every n without checking each one.
Let’s prove “there are infinitely many primes.” First we assume the opposite, “there are only finitely many primes,” is true. If starting from there we reach a conclusion that makes no sense, a contradiction, the assumption was wrong and the original proposition is true. This method of proof is called proof by contradiction.
Suppose 2, 3, and 5 are the only primes. Multiply them all and add 1, and you get 31.
Dividing 31 by any of 2, 3, and 5 leaves 1. No prime on the list divides 31.
But every number greater than 1 is divisible by some prime. A number that isn't prime splits into two smaller numbers multiplied together, and if those aren't prime you keep splitting until you reach primes. 31 is divisible only by 1 and 31, so 31 itself is such a prime.
Such a prime isn't on the list, which contradicts the assumption that 2, 3, and 5 are the only primes. The argument works whatever primes are on the list, so no list can hold every prime. There are infinitely many primes.
Pick primes to change the list. You can pick all six.
In computer science, proof by contradiction is also a common way to show that “no program can do that.”
A proposition claiming “true in every case” breaks with a single counterexample, and showing it’s true takes reasoning like proof by contradiction that doesn’t look at the cases one by one. The next post covers mathematical induction, which proves propositions where n grows one at a time, like falling dominoes.
The proof by contradiction multiplied every prime on the list and added 1. If the list holds every prime from the smallest up to p (2, 3, 5, …, p), which of the following is always true of that number?