🚀 go-pugleaf

mab@wdl39.wdl.loral.com (Mark A Biggar) writes:
: I have seen two different definitions of induction:
: 
: method 1
:       prove p(0)
:       prove (p(0) & p(1) & ... & p(n)) -> p(n+1)
:       therefore p(x) holds for all positive integers
: 
: method 2
:       prove p(0)
:       prove p(n) -> p(n+1)
:       therefore p(X) holds etc.
: 
: Are these of equal strength, in other words can I prove some things with 1
: that I can't prove with just 2?

They're equivalent.  Obviously anything you can prove with 2 can also
be proved with 1.  The other way around, define the predicate
    q(n) = p(0) & p(1) & ... & p(n)
Take your proof using 1, and where you prove
    (p(0) & p(1) & ... & p(n)) -> p(n+1)
replace it instead by the following:
    Assume q(n).
    Hence, p(0) & p(1) & ... & p(n) holds.
    <include old proof of (p(0) & p(1) & ... & p(n)) -> p(n+1)>
    By modus ponens, conclude p(n+1).
    Hence, (p(0) & p(1) & ... & p(n)) & p(n+1) = q(n+1) holds.
    By deduction theorem, 
    q(n) -> q(n+1)
    By method 2, q(x) holds for all positive integers x.
Since q(x) -> p(x), conclude that p(x) holds for all positive integers x.
--
==================================================
| Michael Fischer <fischer-michael@cs.yale.edu>  |
==================================================