[Haskell-cafe] Induction (help!)

[Brent Yorgey]

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