home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2881 < prev    next >
Encoding:
Text File  |  1992-08-12  |  1.8 KB  |  49 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!cs.yale.edu!ginkgo.theory.cs.yale.edu!fischer
  3. From: fischer@ginkgo.theory.cs.yale.edu (Michael Fischer)
  4. Subject: Re: Math Induction (was Re: tabulation of primes)
  5. Message-ID: <1992Aug12.220058.15036@cs.yale.edu>
  6. Sender: news@cs.yale.edu (Usenet News)
  7. Nntp-Posting-Host: ginkgo.theory.cs.yale.edu
  8. Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
  9. X-Newsreader: Tin 1.1az (for az) PL4
  10. References: <1992Aug12.213221.8240@wdl.loral.com>
  11. Date: Wed, 12 Aug 1992 22:00:58 GMT
  12. Lines: 35
  13.  
  14. mab@wdl39.wdl.loral.com (Mark A Biggar) writes:
  15. : I have seen two different definitions of induction:
  16. : 
  17. : method 1
  18. :       prove p(0)
  19. :       prove (p(0) & p(1) & ... & p(n)) -> p(n+1)
  20. :       therefore p(x) holds for all positive integers
  21. : 
  22. : method 2
  23. :       prove p(0)
  24. :       prove p(n) -> p(n+1)
  25. :       therefore p(X) holds etc.
  26. : 
  27. : Are these of equal strength, in other words can I prove some things with 1
  28. : that I can't prove with just 2?
  29.  
  30. They're equivalent.  Obviously anything you can prove with 2 can also
  31. be proved with 1.  The other way around, define the predicate
  32.     q(n) = p(0) & p(1) & ... & p(n)
  33. Take your proof using 1, and where you prove
  34.     (p(0) & p(1) & ... & p(n)) -> p(n+1)
  35. replace it instead by the following:
  36.     Assume q(n).
  37.     Hence, p(0) & p(1) & ... & p(n) holds.
  38.     <include old proof of (p(0) & p(1) & ... & p(n)) -> p(n+1)>
  39.     By modus ponens, conclude p(n+1).
  40.     Hence, (p(0) & p(1) & ... & p(n)) & p(n+1) = q(n+1) holds.
  41.     By deduction theorem, 
  42.     q(n) -> q(n+1)
  43.     By method 2, q(x) holds for all positive integers x.
  44. Since q(x) -> p(x), conclude that p(x) holds for all positive integers x.
  45. --
  46. ==================================================
  47. | Michael Fischer <fischer-michael@cs.yale.edu>  |
  48. ==================================================
  49.