[Haskell-cafe] Re: Induction (help!)
Brandon S. Allbery KF8NH
allbery at ece.cmu.edu
Tue May 6 10:28:23 EDT 2008
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
More information about the Haskell-Cafe
mailing list