[Haskell-cafe] Induction (help!)
Brent Yorgey
byorgey at gmail.com
Tue May 6 10:38:41 EDT 2008
On Tue, May 6, 2008 at 5:34 AM, PR Stanley <prstanley at ntlworld.com> 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
>
For a more intuitive view, mathematical induction (at least, induction over
the integers) is like knocking over a chain of dominoes. To knock over the
whole (possibly infinite!) chain, you need two things:
1. You need to make sure that each domino is close enough to knock over the
next.
2. You need to actually knock over the first domino.
Relating this to proving a proposition P for all nonnegative integers, step
1 is like proving that P(k) implies P(k+1) -- IF the kth domino gets knocked
over (i.e. if P(k) is true), then it will also knock over the next one (P(k)
implies P(k+1)). Step 2 is like proving the base case -- P(0) is true.
Hopefully this helps you get a more intuitive view of what induction is all
about; you can use some of the other responses to fill in more details.
-Brent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080506/2eaf5009/attachment.htm
More information about the Haskell-Cafe
mailing list