yeolyi.comSeongyeol's CS

Proof

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.

Propositions and counterexamples

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.

Press n to check it

 

  1. Press next about ten times.
  2. Press 39 and then 40.

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.

Proof by contradiction

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.

Assume these are the only primes

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.”

Wrapping up

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.

Challenge

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?