Re: [Haskell-cafe] Re: Induction (help!)
Hi I don't know what it is that I'm not getting where mathematical induction is concerned. This is relevant to Haskell so I wonder if any of you gents could explain in unambiguous terms the concept please. The wikipedia article offers perhaps the least obfuscated definition I've found so far but I would still like more clarity. The idea is to move onto inductive proof in Haskell. First, however, I need to understand the general mathematical concept. Top marks for clarity and explanation of technical terms. Thanks Paul Induction - from the small picture, extrapolate the big Deduction - from the big picture, extrapolate the small 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. Sorry, still none the wiser Cheers, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Induction (help!)
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] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Induction (help!)
On Tue, May 6, 2008 at 4:53 AM, Achim Schneider [EMAIL PROTECTED] wrote: PR Stanley [EMAIL PROTECTED] wrote: Hi I don't know what it is that I'm not getting where mathematical induction is concerned. This is relevant to Haskell so I wonder if any of you gents could explain in unambiguous terms the concept please. The wikipedia article offers perhaps the least obfuscated definition I've found so far but I would still like more clarity. The idea is to move onto inductive proof in Haskell. First, however, I need to understand the general mathematical concept. Top marks for clarity and explanation of technical terms. Thanks Paul Induction - from the small picture, extrapolate the big Deduction - from the big picture, extrapolate the small Induction has two meanings in mathematics, and I don't believe this is the type of induction the OP was asking about. See Daniel Fischer's response for the type you are asking about, and try not to be confused by the irrelevant discussion about inductive logic. Luke 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. As used in mathematical induction, deductionaly sound: 1) Let apple be defined as being of continuous colour. 2) All apples are of the same colour 3) One observed apple is red Ergo: All apples are red Q.E.D. The question that is left is what the heck an apple is, and how it differs from these things you see at a supermarket. It could, from the above proof, be a symbol for red rubberband. The samples are defined by the logic. Proposition 2 should be of course inferable from looking at one single apple, or you're going to look quite silly. It only works in mathematics, where you can have exact, either complete or part-wise, copies of something. If you can think of a real-world example where this works, please speak up. That's it. Aristotlean logic sucks. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
