गणितीय प्रेरण: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Form of mathematical proof}} {{Distinguish|inductive reasoning}} {{Use dmy dates|date=February 2021}} Image:Dominoeffect.png|thumb|right|डोमिन...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Form of mathematical proof}} | {{Short description|Form of mathematical proof}} | ||
{{Distinguish|inductive reasoning}} | {{Distinguish|inductive reasoning}} | ||
[[Image:Dominoeffect.png|thumb|right|डोमिनोज़ प्रभाव के अनुक्रमिक प्रभाव के संदर्भ में गणितीय प्रेरण को अनौपचारिक रूप से चित्रित किया जा सकता है।<ref>Matt DeVos, [https://www.sfu.ca/~mdevos/notes/graph/induction.pdf ''Mathematical Induction''], [[Simon Fraser University]]</ref><ref>Gerardo con Diaz, ''[http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf Mathematical Induction] {{Webarchive|url=https://web.archive.org/web/20130502163438/http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf |date=2 May 2013 }}'', [[Harvard University]]</ref>]]गणितीय आगमन [[गणितीय प्रमाण]] के लिए एक विधि है कि एक कथन <math>P(n)</math> प्रत्येक [[प्राकृतिक संख्या]] के लिए सत्य है <math>n</math>, अर्थात्, अपरिमित रूप से बहुत से मामले <math>P(0),P(1),P(2),P(3),\dots</math>सब पकड़। अनौपचारिक रूपक इस तकनीक को समझाने में मदद करते हैं, जैसे डोमिनोज़ गिरना या सीढ़ी चढ़ना: | [[Image:Dominoeffect.png|thumb|right|डोमिनोज़ प्रभाव के अनुक्रमिक प्रभाव के संदर्भ में गणितीय प्रेरण को अनौपचारिक रूप से चित्रित किया जा सकता है।<ref>Matt DeVos, [https://www.sfu.ca/~mdevos/notes/graph/induction.pdf ''Mathematical Induction''], [[Simon Fraser University]]</ref><ref>Gerardo con Diaz, ''[http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf Mathematical Induction] {{Webarchive|url=https://web.archive.org/web/20130502163438/http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf |date=2 May 2013 }}'', [[Harvard University]]</ref>]]गणितीय आगमन [[गणितीय प्रमाण]] के लिए एक विधि है कि एक कथन <math>P(n)</math> प्रत्येक [[प्राकृतिक संख्या]] के लिए सत्य है <math>n</math>, अर्थात्, अपरिमित रूप से बहुत से मामले <math>P(0),P(1),P(2),P(3),\dots</math>सब पकड़। अनौपचारिक रूपक इस तकनीक को समझाने में मदद करते हैं, जैसे डोमिनोज़ गिरना या सीढ़ी चढ़ना: | ||
{{quote | {{quote | ||
| Line 7: | Line 7: | ||
|source=''[[Concrete Mathematics]]'', page 3 margins. | |source=''[[Concrete Mathematics]]'', page 3 margins. | ||
}} | }} | ||
प्रेरण द्वारा | प्रेरण द्वारा सबूत में दो मामले होते हैं। पहला, आधार मामला, के लिए कथन को सिद्ध करता है <math>n=0</math> अन्य मामलों के ज्ञान के बिना। दूसरा मामला, प्रेरण चरण, यह साबित करता है कि ''यदि'' कथन किसी दिए गए मामले के लिए मान्य है <math>n=k</math>, तो इसे अगले मामले के लिए भी लागू होना चाहिए <math>n=k+1</math>. ये दो चरण स्थापित करते हैं कि कथन प्रत्येक प्राकृतिक संख्या के लिए लागू होता है <math>n</math>. आधार मामला आवश्यक रूप से शुरू नहीं होता है <math>n=0</math>, लेकिन अक्सर साथ <math>n=1</math>, और संभवतः किसी निश्चित प्राकृतिक संख्या के साथ <math>n=N</math>, सभी प्राकृतिक संख्याओं के लिए कथन की सत्यता स्थापित करना <math>n\geq N</math>. | ||
अधिक सामान्य अच्छी तरह से स्थापित संरचनाओं, जैसे वृक्ष (सेट सिद्धांत); यह सामान्यीकरण, जिसे [[संरचनात्मक प्रेरण]] के रूप में जाना जाता है, का उपयोग [[गणितीय तर्क]] और [[कंप्यूटर विज्ञान]] में किया जाता है। इस विस्तारित अर्थ में गणितीय आगमन पुनरावर्तन से निकटता से संबंधित है। गणितीय आगमन | अधिक सामान्य अच्छी तरह से स्थापित संरचनाओं, जैसे वृक्ष (सेट सिद्धांत); यह सामान्यीकरण, जिसे [[संरचनात्मक प्रेरण]] के रूप में जाना जाता है, का उपयोग [[गणितीय तर्क]] और [[कंप्यूटर विज्ञान]] में किया जाता है। इस विस्तारित अर्थ में गणितीय आगमन पुनरावर्तन से निकटता से संबंधित है। गणितीय आगमन [[अनुमान नियम]] है जिसका उपयोग [[औपचारिक प्रमाण]]ों में किया जाता है, और यह कंप्यूटर प्रोग्रामों के लिए अधिकांश [[शुद्धता (कंप्यूटर विज्ञान)]] प्रमाणों का आधार है।<ref> | ||
{{cite book | {{cite book | ||
| last = Anderson | | last = Anderson | ||
| Line 22: | Line 22: | ||
| isbn = 978-0471033950 | | isbn = 978-0471033950 | ||
}}</ref> | }}</ref> | ||
यद्यपि इसका नाम अन्यथा सुझाव दे सकता है, गणितीय आगमन को आगमनात्मक तर्क के साथ भ्रमित नहीं होना चाहिए जैसा कि [[दर्शन]]शास्त्र में प्रयोग किया जाता है ([[प्रेरण की समस्या]] देखें)। गणितीय पद्धति | यद्यपि इसका नाम अन्यथा सुझाव दे सकता है, गणितीय आगमन को आगमनात्मक तर्क के साथ भ्रमित नहीं होना चाहिए जैसा कि [[दर्शन]]शास्त्र में प्रयोग किया जाता है ([[प्रेरण की समस्या]] देखें)। गणितीय पद्धति सामान्य कथन को सिद्ध करने के लिए असीम रूप से कई मामलों की जांच करती है, लेकिन ऐसा वेरिएबल (गणित) को शामिल करने वाली [[निगमनात्मक तर्क]] की परिमित श्रृंखला द्वारा करती है। <math>n</math>, जो अपरिमित रूप से अनेक मान ले सकता है।<ref>{{cite web|url=http://www.earlham.edu/~peters/courses/logsys/math-ind.htm|title=Mathematical Induction|last=Suber|first=Peter|publisher=Earlham College|access-date=26 March 2011}}</ref> | ||
== इतिहास == | == इतिहास == | ||
370 ई.पू. में, [[प्लेटो]] के [[परमेनाइड्स (संवाद)]] में निहित आगमनात्मक प्रमाण के | 370 ई.पू. में, [[प्लेटो]] के [[परमेनाइड्स (संवाद)]] में निहित आगमनात्मक प्रमाण के प्रारंभिक उदाहरण के निशान शामिल हो सकते हैं।{{sfn|Acerbi|2000}} विपरीत पुनरावृत्त तकनीक, ऊपर की बजाय नीचे की ओर गिनना, सॉराइट्स विरोधाभास में पाया जाता है, जहां यह तर्क दिया गया था कि यदि रेत के 1,000,000 दाने ढेर बनाते हैं, और ढेर से दाने को हटाने से यह ढेर बन जाता है, तो रेत का दाना (या कोई दाना भी नहीं) ढेर बनाता है।{{sfn|Hyde|Raffman|2018}} | ||
गणितीय आगमन द्वारा सबसे पहला अंतर्निहित प्रमाण [[गेराज]] द्वारा 1000 ईस्वी के आसपास लिखे गए अल-फखरी में है, जिन्होंने पास्कल के त्रिकोण के [[द्विपद प्रमेय]] और गुणों को साबित करने के लिए इसे [[अंकगणितीय प्रगति]] पर लागू किया।{{sfn|Rashed|1994|pp=62–84}}<ref>[https://books.google.com/books?id=HGMXCgAAQBAJ&pg=PA193 Mathematical Knowledge and the Interplay of Practices] "The earliest implicit proof by mathematical induction was given around 1000 in a work by the Persian mathematician Al-Karaji"</ref> | गणितीय आगमन द्वारा सबसे पहला अंतर्निहित प्रमाण [[गेराज]] द्वारा 1000 ईस्वी के आसपास लिखे गए अल-फखरी में है, जिन्होंने पास्कल के त्रिकोण के [[द्विपद प्रमेय]] और गुणों को साबित करने के लिए इसे [[अंकगणितीय प्रगति]] पर लागू किया।{{sfn|Rashed|1994|pp=62–84}}<ref>[https://books.google.com/books?id=HGMXCgAAQBAJ&pg=PA193 Mathematical Knowledge and the Interplay of Practices] "The earliest implicit proof by mathematical induction was given around 1000 in a work by the Persian mathematician Al-Karaji"</ref> | ||
जैसा कि काट्ज़ कहते हैं {{quote|text=Another important idea introduced by al-Karaji and continued by al-Samaw'al and others was that of an inductive argument for dealing with certain arithmetic sequences. Thus al-Karaji used such an argument to prove the result on the sums of integral cubes already known to [[Aryabhata]] [...] Al-Karaji did not, however, state a general result for arbitrary ''n''. He stated his theorem for the particular integer 10 [...] His proof, nevertheless, was clearly designed to be extendable to any other integer. [...] Al-Karaji's argument includes in essence the two basic components of a modern argument by induction, namely the [[truth]] of the statement for ''n'' = 1 (1 = 1<sup>3</sup>) and the deriving of the truth for ''n'' = ''k'' from that of ''n'' = ''k'' - 1. Of course, this second component is not explicit since, in some sense, al-Karaji's argument is in reverse; this is, he starts from ''n'' = 10 and goes down to 1 rather than proceeding upward. Nevertheless, his argument in ''al-Fakhri'' is the earliest extant proof of [[Squared triangular number|the sum formula for integral cubes]].<ref>Katz (1998), p. 255</ref>}} | जैसा कि काट्ज़ कहते हैं {{quote|text=Another important idea introduced by al-Karaji and continued by al-Samaw'al and others was that of an inductive argument for dealing with certain arithmetic sequences. Thus al-Karaji used such an argument to prove the result on the sums of integral cubes already known to [[Aryabhata]] [...] Al-Karaji did not, however, state a general result for arbitrary ''n''. He stated his theorem for the particular integer 10 [...] His proof, nevertheless, was clearly designed to be extendable to any other integer. [...] Al-Karaji's argument includes in essence the two basic components of a modern argument by induction, namely the [[truth]] of the statement for ''n'' = 1 (1 = 1<sup>3</sup>) and the deriving of the truth for ''n'' = ''k'' from that of ''n'' = ''k'' - 1. Of course, this second component is not explicit since, in some sense, al-Karaji's argument is in reverse; this is, he starts from ''n'' = 10 and goes down to 1 rather than proceeding upward. Nevertheless, his argument in ''al-Fakhri'' is the earliest extant proof of [[Squared triangular number|the sum formula for integral cubes]].<ref>Katz (1998), p. 255</ref>}} | ||
भारत में, भास्कर द्वितीय की [[चक्रवला विधि]] में गणितीय आगमन द्वारा प्रारंभिक अंतर्निहित प्रमाण दिखाई देते हैं।<ref name="Induction Bussey">{{harvp|Cajori|1918|p=197|ps=: 'The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.'}}</ref> | भारत में, भास्कर द्वितीय की [[चक्रवला विधि]] में गणितीय आगमन द्वारा प्रारंभिक अंतर्निहित प्रमाण दिखाई देते हैं।<ref name="Induction Bussey">{{harvp|Cajori|1918|p=197|ps=: 'The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.'}}</ref> | ||
हालांकि, इन प्राचीन गणितज्ञों में से किसी ने भी आगमन परिकल्पना को स्पष्ट रूप से नहीं बताया। इसी तरह का | हालांकि, इन प्राचीन गणितज्ञों में से किसी ने भी आगमन परिकल्पना को स्पष्ट रूप से नहीं बताया। इसी तरह का और मामला (वैका ने जो लिखा है, उसके विपरीत, जैसा कि फ्रायडेंथल ने ध्यान से दिखाया है){{sfn|Rashed|1994|p=62}} [[फ्रांसिस मौरोलिको]] की अपनी अरिथमेटिकोरम लिब्री डुओ (1575) में थी, जिसने यह साबित करने के लिए तकनीक का इस्तेमाल किया था कि पहले n [[समता (गणित)]] [[पूर्णांक]]ों का योग n है<sup>2</उप>। | ||
इंडक्शन का सबसे पहला कठोर #गणितीय_प्रमाण उपयोग [[गर्सोनाइडेस]] (1288-1344) द्वारा किया गया था।{{sfn|Simonson|2000}}{{sfn|Rabinovitch|1970}} इंडक्शन के सिद्धांत का पहला स्पष्ट सूत्रीकरण [[ब्लेस पास्कल]] ने अपने ट्रेटे डु त्रिकोण अंकगणित (1665) में दिया था। | इंडक्शन का सबसे पहला कठोर #गणितीय_प्रमाण उपयोग [[गर्सोनाइडेस]] (1288-1344) द्वारा किया गया था।{{sfn|Simonson|2000}}{{sfn|Rabinovitch|1970}} इंडक्शन के सिद्धांत का पहला स्पष्ट सूत्रीकरण [[ब्लेस पास्कल]] ने अपने ट्रेटे डु त्रिकोण अंकगणित (1665) में दिया था। अन्य फ्रांसीसी, [[पियरे डी फर्मेट]] ने संबंधित सिद्धांत का पर्याप्त उपयोग किया: [[अनंत वंश]] द्वारा अप्रत्यक्ष प्रमाण। | ||
प्रेरण परिकल्पना को स्विस [[जैकब बर्नौली]] द्वारा भी नियोजित किया गया था, और तभी से यह अच्छी तरह से जाना जाने लगा। सिद्धांत का आधुनिक औपचारिक उपचार केवल 19वीं शताब्दी में [[जॉर्ज बूले]] के साथ आया,<ref>"It is sometimes required to prove a theorem which shall be true whenever a certain quantity ''n'' which it involves shall be an integer or whole number and the method of proof is usually of the following kind. ''1st''. The theorem is proved to be true when ''n'' = 1. ''2ndly''. It is proved that if the theorem is true when ''n'' is a given whole number, it will be true if ''n'' is the next greater integer. Hence the theorem is true universally. … This species of argument may be termed a continued ''[[Polysyllogism|sorites]]''" (Boole c. 1849 ''Elementary Treatise on Logic not mathematical'' pp. 40–41 reprinted in [[Ivor Grattan-Guinness|Grattan-Guinness, Ivor]] and Bornet, Gérard (1997), ''George Boole: Selected Manuscripts on Logic and its Philosophy'', Birkhäuser Verlag, Berlin, {{isbn|3-7643-5456-9}})</ref> [[ऑगस्टस डी मॉर्गन]], [[चार्ल्स सैंडर्स पियर्स]],{{sfn|Peirce|1881}}{{sfn|Shields|1997}} [[जोसेफ पीनो]], और [[रिचर्ड डेडेकिंड]]।<ref name="Induction Bussey"/> | प्रेरण परिकल्पना को स्विस [[जैकब बर्नौली]] द्वारा भी नियोजित किया गया था, और तभी से यह अच्छी तरह से जाना जाने लगा। सिद्धांत का आधुनिक औपचारिक उपचार केवल 19वीं शताब्दी में [[जॉर्ज बूले]] के साथ आया,<ref>"It is sometimes required to prove a theorem which shall be true whenever a certain quantity ''n'' which it involves shall be an integer or whole number and the method of proof is usually of the following kind. ''1st''. The theorem is proved to be true when ''n'' = 1. ''2ndly''. It is proved that if the theorem is true when ''n'' is a given whole number, it will be true if ''n'' is the next greater integer. Hence the theorem is true universally. … This species of argument may be termed a continued ''[[Polysyllogism|sorites]]''" (Boole c. 1849 ''Elementary Treatise on Logic not mathematical'' pp. 40–41 reprinted in [[Ivor Grattan-Guinness|Grattan-Guinness, Ivor]] and Bornet, Gérard (1997), ''George Boole: Selected Manuscripts on Logic and its Philosophy'', Birkhäuser Verlag, Berlin, {{isbn|3-7643-5456-9}})</ref> [[ऑगस्टस डी मॉर्गन]], [[चार्ल्स सैंडर्स पियर्स]],{{sfn|Peirce|1881}}{{sfn|Shields|1997}} [[जोसेफ पीनो]], और [[रिचर्ड डेडेकिंड]]।<ref name="Induction Bussey"/> | ||
== विवरण == | == विवरण == | ||
गणितीय आगमन का सबसे सरल और सबसे सामान्य रूप अनुमान लगाता है कि | गणितीय आगमन का सबसे सरल और सबसे सामान्य रूप अनुमान लगाता है कि कथन जिसमें प्राकृतिक संख्या शामिल है {{mvar|n}} (यानी पूर्णांक {{math|''n'' ≥ 0}} या 1) के सभी मूल्यों के लिए धारण करता है {{mvar|n}}. प्रमाण में दो चरण होते हैं: | ||
# | # आधार मामला (या प्रारंभिक मामला): सिद्ध करें कि कथन 0 या 1 के लिए है। | ||
# | # प्रेरण कदम (या आगमनात्मक कदम, या कदम का मामला): साबित करें कि हर के लिए {{mvar|n}}, यदि कथन के लिए है {{mvar|n}}, तो यह धारण करता है {{math|''n'' + 1}}. दूसरे शब्दों में, मान लें कि बयान कुछ मनमानी प्राकृतिक संख्या के लिए है {{mvar|n}}, और साबित करें कि कथन के लिए है {{math|''n'' + 1}}. | ||
प्रेरण चरण में परिकल्पना, कि कथन किसी विशेष के लिए धारण करता है {{mvar|n}}, प्रेरण परिकल्पना या आगमनात्मक परिकल्पना कहलाती है। इंडक्शन स्टेप को साबित करने के लिए, इंडक्शन परिकल्पना को मान लिया जाता है {{mvar|n}} और फिर इस धारणा का उपयोग यह साबित करने के लिए करता है कि कथन के लिए है {{math|''n'' + 1}}. | प्रेरण चरण में परिकल्पना, कि कथन किसी विशेष के लिए धारण करता है {{mvar|n}}, प्रेरण परिकल्पना या आगमनात्मक परिकल्पना कहलाती है। इंडक्शन स्टेप को साबित करने के लिए, इंडक्शन परिकल्पना को मान लिया जाता है {{mvar|n}} और फिर इस धारणा का उपयोग यह साबित करने के लिए करता है कि कथन के लिए है {{math|''n'' + 1}}. | ||
| Line 51: | Line 47: | ||
सभी प्राकृतिक संख्याओं n के लिए निम्नलिखित कथन P(n) को सिद्ध करने के लिए गणितीय आगमन का उपयोग किया जा सकता है। | सभी प्राकृतिक संख्याओं n के लिए निम्नलिखित कथन P(n) को सिद्ध करने के लिए गणितीय आगमन का उपयोग किया जा सकता है। | ||
: <math>P(n)\!:\ \ 0 + 1 + 2 + \cdots + n = \frac{n(n + 1)}{2}.</math> | : <math>P(n)\!:\ \ 0 + 1 + 2 + \cdots + n = \frac{n(n + 1)}{2}.</math> | ||
यह दी गई संख्या से कम या उसके बराबर प्राकृतिक संख्याओं के योग के लिए | यह दी गई संख्या से कम या उसके बराबर प्राकृतिक संख्याओं के योग के लिए सामान्य सूत्र बताता है; वास्तव में बयानों का अनंत क्रम: <math>0 = \tfrac{(0)(0+1)}2</math>, <math>0+1 = \tfrac{(1)(1+1)}2</math>, <math>0+1+2 = \tfrac{(2)(2+1)}2</math>, आदि। | ||
<u>प्रस्ताव।</u> प्रत्येक के लिए <math>n\in\mathbb{N}</math>, <math>0 + 1 + 2 + \cdots + n = \tfrac{n(n + 1)}{2}.</math> | <u>प्रस्ताव।</u> प्रत्येक के लिए <math>n\in\mathbb{N}</math>, <math>0 + 1 + 2 + \cdots + n = \tfrac{n(n + 1)}{2}.</math> | ||
| Line 73: | Line 69: | ||
निष्कर्ष: चूँकि बेस केस और इंडक्शन स्टेप दोनों ही सही साबित हुए हैं, गणितीय इंडक्शन द्वारा स्टेटमेंट P(n) हर प्राकृतिक संख्या n के लिए है। क्यू.ई.डी.|∎ | निष्कर्ष: चूँकि बेस केस और इंडक्शन स्टेप दोनों ही सही साबित हुए हैं, गणितीय इंडक्शन द्वारा स्टेटमेंट P(n) हर प्राकृतिक संख्या n के लिए है। क्यू.ई.डी.|∎ | ||
=== | === त्रिकोणमितीय असमानता === | ||
इंडक्शन का उपयोग अक्सर [[असमानता (गणित)]] को साबित करने के लिए किया जाता है। | इंडक्शन का उपयोग अक्सर [[असमानता (गणित)]] को साबित करने के लिए किया जाता है। उदाहरण के रूप में, हम यह साबित करते हैं <math>|\!\sin nx| \leq n\,|\!\sin x|</math> किसी भी [[वास्तविक संख्या]] के लिए <math>x</math> और प्राकृतिक संख्या <math>n</math>. | ||
पहली नज़र में, ऐसा प्रतीत हो सकता है कि | पहली नज़र में, ऐसा प्रतीत हो सकता है कि अधिक सामान्य संस्करण, <math>|\!\sin nx| \leq n\,|\!\sin x|</math> किसी भी वास्तविक संख्या के लिए <math>n,x</math>, प्रेरण के बिना सिद्ध किया जा सकता है; लेकिन मामला <math display="inline">n=\frac{1}{2},\, x=\pi</math> दिखाता है कि के गैर-पूर्णांक मानों के लिए यह असत्य हो सकता है <math>n</math>. इससे पता चलता है कि हम विशेष रूप से के प्राकृतिक मूल्यों के लिए बयान की जांच करते हैं <math>n</math>, और प्रेरण सबसे आसान उपकरण है। | ||
<u>प्रस्ताव।</u> किसी के लिए भी <math>x \in \mathbb{R}</math> और <math>n \in \mathbb{N}</math>, <math>|\!\sin nx|\leq n\,|\!\sin x|</math>. | <u>प्रस्ताव।</u> किसी के लिए भी <math>x \in \mathbb{R}</math> और <math>n \in \mathbb{N}</math>, <math>|\!\sin nx|\leq n\,|\!\sin x|</math>. | ||
सबूत। | सबूत। मनमाना वास्तविक संख्या तय करें <math>x</math>, और जाने <math>P(n)</math> बयान हो <math>|\!\sin nx|\leq n\,|\!\sin x|</math>. हम शामिल करते हैं <math>n</math>. | ||
आधार मामला: गणना <math>|\!\sin 0x| = 0 \leq 0 = 0\,|\!\sin x|</math> पुष्टि करता है <math>P(0)</math>. | आधार मामला: गणना <math>|\!\sin 0x| = 0 \leq 0 = 0\,|\!\sin x|</math> पुष्टि करता है <math>P(0)</math>. | ||
| Line 104: | Line 100: | ||
== वेरिएंट == | == वेरिएंट == | ||
व्यवहार में, इंडक्शन द्वारा प्रूफ को अक्सर अलग तरह से संरचित किया जाता है, जो कि सिद्ध की जाने वाली संपत्ति की सटीक प्रकृति पर निर्भर करता है। | व्यवहार में, इंडक्शन द्वारा प्रूफ को अक्सर अलग तरह से संरचित किया जाता है, जो कि सिद्ध की जाने वाली संपत्ति की सटीक प्रकृति पर निर्भर करता है। | ||
इंडक्शन के सभी प्रकार [[ट्रांसफिनिट इंडक्शन]] के विशेष मामले हैं; #ट्रांसफिनिट इंडक्शन देखें। | इंडक्शन के सभी प्रकार [[ट्रांसफिनिट इंडक्शन]] के विशेष मामले हैं; #ट्रांसफिनिट इंडक्शन देखें। | ||
| Line 114: | Line 109: | ||
इसका उपयोग, उदाहरण के लिए, यह दिखाने के लिए किया जा सकता है {{math|2<sup>''n''</sup> ≥ ''n'' + 5}} के लिए {{math|''n'' ≥ 3}}. | इसका उपयोग, उदाहरण के लिए, यह दिखाने के लिए किया जा सकता है {{math|2<sup>''n''</sup> ≥ ''n'' + 5}} के लिए {{math|''n'' ≥ 3}}. | ||
इस प्रकार, कोई उस कथन को सिद्ध कर सकता है {{math|''P''(''n'')}} सभी के लिए रखता है {{math|''n'' ≥ 1}}, या सभी के लिए भी {{math|''n'' ≥ −5}}. गणितीय आगमन का यह रूप वास्तव में पिछले रूप का | इस प्रकार, कोई उस कथन को सिद्ध कर सकता है {{math|''P''(''n'')}} सभी के लिए रखता है {{math|''n'' ≥ 1}}, या सभी के लिए भी {{math|''n'' ≥ −5}}. गणितीय आगमन का यह रूप वास्तव में पिछले रूप का विशेष मामला है, क्योंकि यदि कथन को सिद्ध किया जाना है {{math|''P''(''n'')}} तो इन दो नियमों के साथ इसे साबित करना साबित करने के बराबर है {{math|''P''(''n'' + ''b'')}} सभी प्राकृतिक संख्याओं के लिए {{mvar|n}} इंडक्शन बेस केस के साथ {{math|0}}.<ref>Ted Sundstrom, ''Mathematical Reasoning'', p. 190, Pearson, 2006, {{isbn|978-0131877184}}</ref> | ||
==== उदाहरण: सिक्कों द्वारा डॉलर की राशि बनाना ==== | ==== उदाहरण: सिक्कों द्वारा डॉलर की राशि बनाना ==== | ||
4- और 5-डॉलर के सिक्कों की अनंत आपूर्ति मान लें। इंडक्शन का उपयोग यह साबित करने के लिए किया जा सकता है कि डॉलर की कोई भी पूरी राशि इससे अधिक या बराबर है {{math|12}} ऐसे सिक्कों के संयोजन से बनाया जा सकता है। होने देना {{math|''S''(''k'')}} कथन को निरूपित करें{{mvar|k}} डॉलर को 4- और 5-डॉलर के सिक्कों के संयोजन से बनाया जा सकता है। इसका प्रमाण {{math|''S''(''k'')}} सभी के लिए सत्य है {{math|''k'' ≥ 12}} फिर प्रेरण द्वारा प्राप्त किया जा सकता है {{mvar|k}} निम्नलिखित नुसार: | 4- और 5-डॉलर के सिक्कों की अनंत आपूर्ति मान लें। इंडक्शन का उपयोग यह साबित करने के लिए किया जा सकता है कि डॉलर की कोई भी पूरी राशि इससे अधिक या बराबर है {{math|12}} ऐसे सिक्कों के संयोजन से बनाया जा सकता है। होने देना {{math|''S''(''k'')}} कथन को निरूपित करें{{mvar|k}} डॉलर को 4- और 5-डॉलर के सिक्कों के संयोजन से बनाया जा सकता है। इसका प्रमाण {{math|''S''(''k'')}} सभी के लिए सत्य है {{math|''k'' ≥ 12}} फिर प्रेरण द्वारा प्राप्त किया जा सकता है {{mvar|k}} निम्नलिखित नुसार: | ||
| Line 122: | Line 115: | ||
आधार मामला: दिखा रहा है {{math|''S''(''k'')}} के लिए रखता है {{math|1=''k'' = 12}} सरल है: तीन 4-डॉलर के सिक्के लें। | आधार मामला: दिखा रहा है {{math|''S''(''k'')}} के लिए रखता है {{math|1=''k'' = 12}} सरल है: तीन 4-डॉलर के सिक्के लें। | ||
प्रेरण चरण: यह देखते हुए {{math|''S''(''k'')}} के कुछ मूल्य के लिए रखता है {{math|''k'' ≥ 12}} (प्रेरण परिकल्पना), साबित करें {{math|''S''(''k'' + 1)}} भी रखता है। मान लीजिए {{math|''S''(''k'')}} कुछ मनमानी के लिए सच है {{math|''k'' ≥ 12}}. अगर इसका कोई उपाय है {{mvar|k}} डॉलर जिसमें कम से कम | प्रेरण चरण: यह देखते हुए {{math|''S''(''k'')}} के कुछ मूल्य के लिए रखता है {{math|''k'' ≥ 12}} (प्रेरण परिकल्पना), साबित करें {{math|''S''(''k'' + 1)}} भी रखता है। मान लीजिए {{math|''S''(''k'')}} कुछ मनमानी के लिए सच है {{math|''k'' ≥ 12}}. अगर इसका कोई उपाय है {{mvar|k}} डॉलर जिसमें कम से कम 4-डॉलर का सिक्का शामिल है, इसे बनाने के लिए 5-डॉलर के सिक्के से बदलें {{math|''k'' + 1}} डॉलर। अन्यथा, यदि केवल 5-डॉलर के सिक्कों का उपयोग किया जाता है, {{mvar|k}} 5 का गुणक होना चाहिए और इसलिए कम से कम 15 होना चाहिए; लेकिन फिर हम बनाने के लिए तीन 5-डॉलर के सिक्कों को चार 4-डॉलर के सिक्कों से बदल सकते हैं {{math|''k'' + 1}} डॉलर। हर मामले में, {{math|''S''(''k'' + 1)}} क्या सच है। | ||
इसलिए, प्रेरण के सिद्धांत द्वारा, {{math|''S''(''k'')}} सभी के लिए रखता है {{math|''k'' ≥ 12}}, और सबूत पूरा हो गया है। | इसलिए, प्रेरण के सिद्धांत द्वारा, {{math|''S''(''k'')}} सभी के लिए रखता है {{math|''k'' ≥ 12}}, और सबूत पूरा हो गया है। | ||
| Line 128: | Line 121: | ||
हालांकि इस उदाहरण में {{math|''S''(''k'')}} के लिए भी रखता है <math display="inline">k \in \{ 4, 5, 8, 9, 10 \}</math>, उपरोक्त प्रमाण की न्यूनतम राशि को बदलने के लिए संशोधित नहीं किया जा सकता है {{math|12}} डॉलर किसी भी कम मूल्य के लिए {{mvar|m}}. के लिए {{math|1=''m'' = 11}}, आधार मामला वास्तव में झूठा है; के लिए {{math|1=''m'' = 10}}, प्रेरण चरण में दूसरा मामला (तीन 5- को चार 4-डॉलर के सिक्कों से बदलना) काम नहीं करेगा; और भी कम के लिए अकेले रहने दो {{mvar|m}}. | हालांकि इस उदाहरण में {{math|''S''(''k'')}} के लिए भी रखता है <math display="inline">k \in \{ 4, 5, 8, 9, 10 \}</math>, उपरोक्त प्रमाण की न्यूनतम राशि को बदलने के लिए संशोधित नहीं किया जा सकता है {{math|12}} डॉलर किसी भी कम मूल्य के लिए {{mvar|m}}. के लिए {{math|1=''m'' = 11}}, आधार मामला वास्तव में झूठा है; के लिए {{math|1=''m'' = 10}}, प्रेरण चरण में दूसरा मामला (तीन 5- को चार 4-डॉलर के सिक्कों से बदलना) काम नहीं करेगा; और भी कम के लिए अकेले रहने दो {{mvar|m}}. | ||
=== | === से अधिक काउंटरों पर इंडक्शन === | ||
प्रेरण प्रक्रिया को पुनरावृत्त करके, कभी-कभी दो प्राकृतिक संख्याओं, एन और एम से जुड़े बयान को साबित करना वांछनीय होता है। यही है, | प्रेरण प्रक्रिया को पुनरावृत्त करके, कभी-कभी दो प्राकृतिक संख्याओं, एन और एम से जुड़े बयान को साबित करना वांछनीय होता है। यही है, आधार मामले और एन के लिए प्रेरण कदम साबित होता है, और उनमें से प्रत्येक में आधार मामला और एम के लिए प्रेरण कदम साबित होता है। उदाहरण के लिए, प्राकृतिक संख्याओं के योग के साथ प्राकृतिक संख्याओं के योग को शामिल करने वाले प्रमाण देखें। तीन या अधिक काउंटरों से जुड़े अधिक जटिल तर्क भी संभव हैं। | ||
=== अनंत वंश === | === अनंत वंश === | ||
{{main|Infinite descent}} | {{main|Infinite descent}} | ||
अनंत वंश की विधि गणितीय प्रेरण का | अनंत वंश की विधि गणितीय प्रेरण का रूपांतर है जिसका उपयोग पियरे डी फर्मेट द्वारा किया गया था। इसका प्रयोग यह दर्शाने के लिए किया जाता है कि कुछ कथन Q(n) सभी प्राकृतिक संख्याओं n के लिए असत्य है। इसके पारंपरिक रूप में यह दिखाया गया है कि यदि क्यू (एन) कुछ प्राकृतिक संख्या एन के लिए सत्य है, तो यह कुछ सख्ती से छोटी प्राकृतिक संख्या एम के लिए भी लागू होता है। क्योंकि प्राकृतिक संख्याओं का कोई अनंत घटता हुआ क्रम नहीं है, यह स्थिति असंभव होगी, जिससे ([[विरोधाभास द्वारा प्रमाण]]) दिखाया जाएगा कि Q(n) किसी भी n के लिए सत्य नहीं हो सकता है। | ||
इस पद्धति की वैधता को गणितीय आगमन के सामान्य सिद्धांत से सत्यापित किया जा सकता है। क्यू(एम) के रूप में परिभाषित बयान पी (एन) पर गणितीय आगमन का उपयोग सभी प्राकृतिक संख्याओं के लिए गलत है जो एन से कम या बराबर है, यह निम्नानुसार है कि पी (एन) सभी एन के लिए है, जिसका अर्थ है कि क्यू (एन) है हर प्राकृतिक संख्या n के लिए असत्य। | इस पद्धति की वैधता को गणितीय आगमन के सामान्य सिद्धांत से सत्यापित किया जा सकता है। क्यू(एम) के रूप में परिभाषित बयान पी (एन) पर गणितीय आगमन का उपयोग सभी प्राकृतिक संख्याओं के लिए गलत है जो एन से कम या बराबर है, यह निम्नानुसार है कि पी (एन) सभी एन के लिए है, जिसका अर्थ है कि क्यू (एन) है हर प्राकृतिक संख्या n के लिए असत्य। | ||
| Line 142: | Line 135: | ||
जहां प्रेरण सिद्धांत पी (0) से पी (एन) तक पहुंचने में इस चरण के एन अनुप्रयोगों को स्वचालित करता है। इसे पूर्ववर्ती प्रेरण कहा जा सकता है क्योंकि प्रत्येक चरण उस संख्या के पूर्ववर्ती के बारे में कुछ से किसी संख्या के बारे में कुछ साबित करता है। | जहां प्रेरण सिद्धांत पी (0) से पी (एन) तक पहुंचने में इस चरण के एन अनुप्रयोगों को स्वचालित करता है। इसे पूर्ववर्ती प्रेरण कहा जा सकता है क्योंकि प्रत्येक चरण उस संख्या के पूर्ववर्ती के बारे में कुछ से किसी संख्या के बारे में कुछ साबित करता है। | ||
कम्प्यूटेशनल जटिलता में रुचि का | कम्प्यूटेशनल जटिलता में रुचि का प्रकार उपसर्ग प्रेरण है, जिसमें कोई प्रेरण चरण में निम्नलिखित कथन को सिद्ध करता है: | ||
: <math>\forall k (P(k) \to P(2k) \land P(2k+1))</math> | : <math>\forall k (P(k) \to P(2k) \land P(2k+1))</math> | ||
या समकक्ष | या समकक्ष | ||
: <math>\forall k \left( P\!\left(\left\lfloor \frac{k}{2} \right\rfloor \right) \to P(k) \right)</math> | : <math>\forall k \left( P\!\left(\left\lfloor \frac{k}{2} \right\rfloor \right) \to P(k) \right)</math> | ||
प्रेरण सिद्धांत तब द्विआधारी लघुगणक | लॉग को स्वचालित करता है<sub>2</sub>पी (0) से पी (एन) तक प्राप्त करने में इस अनुमान के आवेदन। वास्तव में, इसे उपसर्ग प्रेरण कहा जाता है क्योंकि प्रत्येक चरण उस संख्या के उपसर्ग के बारे में कुछ से | प्रेरण सिद्धांत तब द्विआधारी लघुगणक | लॉग को स्वचालित करता है<sub>2</sub>पी (0) से पी (एन) तक प्राप्त करने में इस अनुमान के आवेदन। वास्तव में, इसे उपसर्ग प्रेरण कहा जाता है क्योंकि प्रत्येक चरण उस संख्या के उपसर्ग के बारे में कुछ से संख्या के बारे में कुछ साबित करता है - जैसा कि इसके बाइनरी प्रतिनिधित्व के निम्न बिट को काटकर बनाया गया है। इसे बाइनरी प्रतिनिधित्व की लंबाई पर पारंपरिक प्रेरण के आवेदन के रूप में भी देखा जा सकता है। | ||
यदि पारंपरिक पूर्ववर्ती इंडक्शन को कम्प्यूटेशनल रूप से एन-स्टेप लूप के रूप में व्याख्यायित किया जाता है, तो प्रीफिक्स इंडक्शन लॉग-एन-स्टेप लूप के अनुरूप होगा। इसके कारण, पूर्ववर्ती प्रेरण का उपयोग करने वाले प्रमाणों की तुलना में उपसर्ग प्रेरण का उपयोग करने वाले प्रमाण अधिक रचनात्मक रूप से रचनात्मक हैं। | यदि पारंपरिक पूर्ववर्ती इंडक्शन को कम्प्यूटेशनल रूप से एन-स्टेप लूप के रूप में व्याख्यायित किया जाता है, तो प्रीफिक्स इंडक्शन लॉग-एन-स्टेप लूप के अनुरूप होगा। इसके कारण, पूर्ववर्ती प्रेरण का उपयोग करने वाले प्रमाणों की तुलना में उपसर्ग प्रेरण का उपयोग करने वाले प्रमाण अधिक रचनात्मक रूप से रचनात्मक हैं। | ||
पूर्ववर्ती प्रेरण | पूर्ववर्ती प्रेरण ही कथन पर उपसर्ग प्रेरण को तुच्छ रूप से अनुकरण कर सकता है। उपसर्ग इंडक्शन पूर्ववर्ती इंडक्शन का अनुकरण कर सकता है, लेकिन केवल स्टेटमेंट को सिंटैक्टिकली कॉम्प्लेक्स ( [[परिबद्ध क्वांटिफायर]] [[यूनिवर्सल क्वांटिफायर]] जोड़कर) बनाने की कीमत पर, इसलिए प्रीफिक्स इंडक्शन से [[बहुपदी समय फलन]] कम्प्यूटेशन से संबंधित दिलचस्प परिणाम अनबाउंड क्वांटिफायर को पूरी तरह से बाहर करने और सीमित करने पर निर्भर करते हैं। बयान में अनुमत बाउंडेड यूनिवर्सल और [[अस्तित्वगत परिमाणक]] क्वांटिफायर्स का प्रत्यावर्तन।<ref name=Buss:BA>{{cite book|last=Buss|first=Samuel|title=Bounded Arithmetic|date=1986|publisher=Bibliopolis|location=Naples}}</ref> | ||
कोई इस विचार को | कोई इस विचार को कदम आगे ले जा सकता है: उसे सिद्ध करना होगा | ||
: <math>\forall k \left( P\!\left( \left\lfloor \sqrt{k} \right\rfloor \right) \to P(k) \right)</math> | : <math>\forall k \left( P\!\left( \left\lfloor \sqrt{k} \right\rfloor \right) \to P(k) \right)</math> | ||
जहां प्रेरण सिद्धांत पी (0) से पी (एन) तक प्राप्त करने में इस अनुमान के लॉग लॉग एन अनुप्रयोगों को स्वचालित करता है। लॉग-टाइम समानांतर संगणना का अध्ययन करने के लिए, प्रेरण के इस रूप का उपयोग किया गया है। | जहां प्रेरण सिद्धांत पी (0) से पी (एन) तक प्राप्त करने में इस अनुमान के लॉग लॉग एन अनुप्रयोगों को स्वचालित करता है। लॉग-टाइम समानांतर संगणना का अध्ययन करने के लिए, प्रेरण के इस रूप का उपयोग किया गया है। | ||
=== पूर्ण (मजबूत) प्रेरण === | |||
अन्य प्रकार, जिसे पूर्ण प्रेरण कहा जाता है, मूल्य प्रेरण या मजबूत प्रेरण का कोर्स (इसके विपरीत प्रेरण का मूल रूप कभी-कभी कमजोर प्रेरण के रूप में जाना जाता है), मजबूत परिकल्पना का उपयोग करके प्रेरण चरण को साबित करना आसान बनाता है: कथन को सिद्ध करता है <math>P(m+1)</math> इस धारणा के तहत <math>P(n)</math> सभी प्राकृतिक संख्याओं के लिए धारण करता है <math>n</math> से कम <math>m+1</math>; इसके विपरीत, मूल रूप केवल ग्रहण करता है <math>P(m)</math>. मजबूत इंडक्शन नाम का मतलब यह नहीं है कि यह विधि कमजोर इंडक्शन से अधिक साबित हो सकती है, लेकिन केवल इंडक्शन चरण में उपयोग की जाने वाली मजबूत परिकल्पना को संदर्भित करती है। | |||
=== | |||
वास्तव में, यह दिखाया जा सकता है कि दो विधियाँ वास्तव में समतुल्य हैं, जैसा कि नीचे बताया गया है। पूर्ण आगमन के इस रूप में, व्यक्ति को अभी भी आधार स्थिति को सिद्ध करना होता है, <math>P(0)</math>, और अतिरिक्त-आधार मामलों को साबित करना भी आवश्यक हो सकता है जैसे कि <math>P(1)</math> सामान्य तर्क लागू होने से पहले, जैसा कि फिबोनाची संख्या के नीचे दिए गए उदाहरण में है <math>F_{n}</math>. | वास्तव में, यह दिखाया जा सकता है कि दो विधियाँ वास्तव में समतुल्य हैं, जैसा कि नीचे बताया गया है। पूर्ण आगमन के इस रूप में, व्यक्ति को अभी भी आधार स्थिति को सिद्ध करना होता है, <math>P(0)</math>, और अतिरिक्त-आधार मामलों को साबित करना भी आवश्यक हो सकता है जैसे कि <math>P(1)</math> सामान्य तर्क लागू होने से पहले, जैसा कि फिबोनाची संख्या के नीचे दिए गए उदाहरण में है <math>F_{n}</math>. | ||