## Monday, 1 June 2015

### Deduction, induction and contradiction.

In order to think, we need the tools for thinking. And thinking can be slippery. Consider the following proof.

A normal dog has one more tail than no dog.
No dog has two tails
Therefore a normal dog has three tails.

The fallacy here is simple; the phrase "no dog" has two different meanings. But it illustrates how easy it can be to think fallaciously. And in particular, when dealing with concepts like "zero" and "nothing", you have to be especially watchful.

I'm used to three ways to prove things. The first is deduction.

Suppose 2x = 6, then what is x? Well, we divide both sides by 2 to get x=3. That's deduction.
Another deduction: All dogs have a tail. Rover is a dog. Therefore, Rover has a tail.

Induction is also good, but more subtle. Suppose we want to prove that for all integers, 1 + 2 + 3 + ... + n = n(n + 1)/2

First, is it true for n=1? A few momentw using your fingers will convence you that it is. A good start.

Now, suppose it's true for integer n. Is it true for n+1? Well, if it's true for n, and we add n+1 to both sides of the equation, then the right hand side becomes (n-squared+n)/2+n+1 = (n-squared+3n+2)/2 = ((n+1)(n+2)/2.

So for any n, it's also true for n+1. And it's true for 1. So it's true for all integers.

The third, and my favourite proof, is proof by contradiction. I will now prove that there's an infinite number of prime numbers.

Suppose there's a finite number of primes, N. Multiply them all together, and add one. This must be a prime, because if you divide it by any of the lower primes, you get a remainder of one. And clearly it's larger than the others. So there's one more prime than we thought. Contradiction! So there cannot be a finite number pf primes.