[Haskell-cafe] Re: Induction (help!)

[Brandon S. Allbery KF8NH]

On 2008 May 6, at 8:37, PR Stanley wrote:

>> Thus, in traditional logic, if you induce "all apples are red",  
>> simple
>> observation of a single non-red apple quickly reduces your result to
>> "at least one apple is not red on one side, all others may be red",
>> i.e, you can't deduce "all apples are red" with your samples anymore.
>
>        Paul: surely, you wouldn't come up with an incorrect premise  
> like "all apples are red" in the first place.

You could come up with it as a hypothesis, if you've never seen a  
green or golden apple.  This is all that's needed; induction starts  
with "*if* P".

However, the real world is a really lousy way to understand inductive  
logic:  you can come up with hypotheses (base cases), but figuring out  
*what* the inductive step is is difficult at best --- never mind the  
impossibility of *proving* such.  Here's what we're trying to assert:

   IF... you have a red apple
   AND YOU CAN PROVE... that another related apple is also red
   THE YOU CAN CONCLUDE... that all such related apples are red

 From a mathematical perspective this is impossible; we haven't  
defined "apple", much less "related apple".  In other words, we can't  
assert either a hypothesis or an inductive case!  So much for the real  
world.

This only provides a way to construct if-thens, btw; it's easy to  
construct such that are false.  In mathematics you can sometimes  
resolve this by constructing a new set for which the hypothesis does  
hold:  for example, if you start with a proposition `P(n) : n is a  
natural number' and use the inductive case `P(n-1) : n-1 is a natural  
number', you run into trouble with n=0.  If you add the concept of  
negative numbers, you come up with a new proposition:  `P(n): n is an  
integer'.  This is more or less how the mathematical notion of integer  
came about, as naturals came from whole numbers (add 0) and complex  
numbers came from reals (add sqrt(-1)).

-- 
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery at kf8nh.com
system administrator [openafs,heimdal,too many hats] allbery at ece.cmu.edu
electrical and computer engineering, carnegie mellon university    KF8NH