I Proved all Odds are Prime - with Inductive Reasoning

Posted by shonk at 04:33 AM in Geek Talk | TrackBack

Just so nobody forgets what a geek I really am, let's talk about induction. Now, what I want to do is to try to explain the differences between "mathematical induction" and "philosophical induction", otherwise known as inductive reasoning. Just allow me to apologize in advance for the irregularities in my explanation.

Just to start things out concretely, here are the relevant dictionary definitions of the two terms:

3. Logic.

a. The process of deriving general principles from particular facts or instances.

b. A conclusion reached by this process.

4. Mathematics. A two-part method of proving a theorem involving an integral parameter. First the theorem is verified for the smallest admissible value of the integer. Then it is proven that if the theorem is true for any value of the integer, it is true for the next greater value. The final proof contains the two parts.

Now, the concept of inductive reasoning is pretty straightforward, as it is basically a natural extension of how we view the world. Basically, when you're reasoning inductively, you're observing that a lot of things in a certain class of things have a particular characteristic and then concluding that all things in that class must have that characteristic. For example, if I notice that every swan I've ever seen is white and, based on that information, conclude that all swans are white, I'm reasoning inductively. This is, in large measure, the way in which the natural sciences work. The natural scientist observes that everything he drops falls at the same rate and then concludes that all objects fall at that rate, even the ones he's never dropped himself. This sort of reasoning seems to derive from Aristotle, who arrived at First Principles by generalizing from experience.

Now, this sort of reasoning has its merits, but it is also limited. The problem is that the inductively reasoned generalization may be true, but it is not necessarily true. There's always the possibility that there is some example that would falsify it, if only one had observed it. For example, if I am the first one at a meeting and notice that each of the next eight people to come into the room are men, it would be tempting to conclude, by inductive reasoning, that the next person to enter the room will also be male. However, this does not mean that the ninth person will necessarily be male; it may be that the chair of the meeting is a woman. Similarly, although a child in Utah may only have Mormon friends, it would be folly for him to conclude that all people are Mormons. It is because most of its conclusions are based on this sort of inductive reasoning that physics is constantly being revised; as better methods of observation are made possible by technological advances, physicists are able to observe phenomena that were inaccessible to their predecessors and therefore are not covered in the old theories.

This uncertainty would prove fatal to mathematics, were it to attempt to use an un-modified form of inductive reasoning. In fact, mathematicians are known to rather derisively refer to this sort of argument as "proof by example", which is really no proof at all. However, by it's nature, the principle of induction can make problems easier to solve, so mathematics has developed a modified form of inductive reasoning called mathematical induction. There is some dispute over who first invented the technique: some argue that the first proof to use it was Francesco Maurolico's proof that the sum of the first n odd integers is n² from 1575; others that DeMorgan invented the term and made it precise in 1838; still others that Dedekind was the first to formalize the principle in the modern sense. Probably all of these are right in large measure, since use differs from definition differs from formalization; one could argue that the idea stretches all the way back to Euclid.

So, aside from all this history, what the hell is mathematical induction anyway? Basically, the notion is that if you're dealing with the natural numbers (0, 1, 2 and so on; the non-negative integers), then if you have some proposition that holds for 0 (usually denoted by P(0)) and if, for every non-negative integer n, it is true that if you assume the proposition holds for n - P(n) - then it holds for n+1, then the proposition holds for every non-negative integer.

That's a bit technical, so let's see if I can make it a little clearer. Basically, the idea is this: I want to show that some property holds for all non-negative integers (in practice, the argument could be for all positive integers, or all integers greater than 50, or whatever, but let's stick to the simplest case). First, I demonstrate that it holds for the smallest non-negative integer, 0. The natural inclination might be to then show it holds for the next smallest integer (1), and then for the next-smallest (2), and so on. But it's clear that if I attack the problem in this way, I'll spend a very long time not getting very far, because no matter how big I get, there will always be bigger integers where my property might fail. Even if I am really dedicated and spend many years carefully showing, one-by-one, that my property holds for each integer up to 5,000,000, there is no guarantee that it will hold for 5,000,001, just as there was no guarantee that the next person to walk in the door of my meeting was a man. So, instead of going one-by-one, I say to myself "What if my property holds for some integer? Does that imply that it holds for the next biggest integer?" If I think of the integers as lying on the number line in the usual way, this question basically asks "What if I randomly put my finger on some number on the line and assume the property holds for that number? Is there some way to show that this assumption implies that the property must necessarily hold for the number directly to the right of my finger?" If I could show this, then I will have a proof for the following reason: I already know the property holds for 0, so (since I could have randomly picked 0 when I stuck my finger on the line) I know the property must hold for 1. Then, since I know the property holds for 1, it must hold for 2, since I proved that if it holds for any integer then it holds for the next-smallest interger.

It is precisely in this way that we can think of our "induction engine" running along all the numbers and proving our proposition. The Wikipedia makes a nice analogy with dominoes:

if you have a long row of dominos standing on end and you can be sure that

1. The first domino will fall.

2. Whenever a domino falls, its next neighbor will also fall.

then you can conclude that all dominos will fall.

The reason is this: you know that if a domino falls, it will knock over its next door neighbor, and you know the first domino will fall, so you know the first domino will knock over the second domino, which will knock over the third, which will knock over the fourth, and so on, until all the dominoes have fallen down. It doesn't matter how many dominos we have, they're all going to fall down. We could even have infinitely many dominoes and still be sure that they all will fall.

This isn't the most obvious concept in the world, but it is an extremely elegant one. The beauty of mathematical induction is that it allows you to prove that a number has some property even if you really don't know anything about the number itself. No matter how nasty the number, if you know that it's predecessor will "knock it over" if struck in just the right way, then you can be sure that the number will be "knocked over" simply by pushing the some really small number, like 0 or 1, and then letting the chain reaction take place.

In point of fact, though this is beyond what I want to try to explain, the principle of mathematical induction works not just on non-negative integers, but on any set that more-or-less looks like the non-negative integers. So it really is a powerful tool.

Unfortunately, philosophic induction (inductive reasoning) and mathematical induction use the same word to describe similar, but by no means identical, ideas. For this reason, I usually call philosophic induction "extrapolation", since it extrapolates known results into unknown territory. But I'm well aware that philosophers don't like people like me using different terminology, so I imagine we'll be stuck with this discrepancy until we stop listening to philosophers. Not that most of us do, anyway (yeah, taking cheapshots both at Aaron and my brother with that one).