गणितीय प्रेरण

Not to be confused with inductive reasoning.

डोमिनोज़ प्रभाव के अनुक्रमिक प्रभाव के संदर्भ में गणितीय प्रेरण को अनौपचारिक रूप से चित्रित किया जा सकता है।

गणितीय आगमन गणितीय प्रमाण के लिए एक विधि है कि एक कथन $P(n)$ प्रत्येक प्राकृतिक संख्या के लिए सत्य है $n$, अर्थात्, अपरिमित रूप से बहुत से मामले $P(0),P(1),P(2),P(3),\dots$सब पकड़। अनौपचारिक रूपक इस तकनीक को समझाने में मदद करते हैं, जैसे डोमिनोज़ गिरना या सीढ़ी चढ़ना:

Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step).

— Concrete Mathematics, page 3 margins.

प्रेरण द्वारा सबूत में दो मामले होते हैं। पहला, आधार मामला, के लिए कथन को सिद्ध करता है $n=0$ अन्य मामलों के ज्ञान के बिना। दूसरा मामला, प्रेरण चरण, यह साबित करता है कि यदि कथन किसी दिए गए मामले के लिए मान्य है $n=k$, तो इसे अगले मामले के लिए भी लागू होना चाहिए $n=k+1$. ये दो चरण स्थापित करते हैं कि कथन प्रत्येक प्राकृतिक संख्या के लिए लागू होता है $n$. आधार मामला आवश्यक रूप से शुरू नहीं होता है $n=0$, लेकिन अक्सर साथ $n=1$, और संभवतः किसी निश्चित प्राकृतिक संख्या के साथ $n=N$, सभी प्राकृतिक संख्याओं के लिए कथन की सत्यता स्थापित करना $n\geq N$.

अधिक सामान्य अच्छी तरह से स्थापित संरचनाओं, जैसे वृक्ष (सेट सिद्धांत); यह सामान्यीकरण, जिसे संरचनात्मक प्रेरण के रूप में जाना जाता है, का उपयोग गणितीय तर्क और कंप्यूटर विज्ञान में किया जाता है। इस विस्तारित अर्थ में गणितीय आगमन पुनरावर्तन से निकटता से संबंधित है। गणितीय आगमन अनुमान नियम है जिसका उपयोग औपचारिक प्रमाणों में किया जाता है, और यह कंप्यूटर प्रोग्रामों के लिए अधिकांश शुद्धता (कंप्यूटर विज्ञान) प्रमाणों का आधार है। यद्यपि इसका नाम अन्यथा सुझाव दे सकता है, गणितीय आगमन को आगमनात्मक तर्क के साथ भ्रमित नहीं होना चाहिए जैसा कि दर्शनशास्त्र में प्रयोग किया जाता है (प्रेरण की समस्या देखें)। गणितीय पद्धति सामान्य कथन को सिद्ध करने के लिए असीम रूप से कई मामलों की जांच करती है, लेकिन ऐसा वेरिएबल (गणित) को शामिल करने वाली निगमनात्मक तर्क की परिमित श्रृंखला द्वारा करती है। $n$, जो अपरिमित रूप से अनेक मान ले सकता है।

इतिहास

370 ई.पू. में, प्लेटो के परमेनाइड्स (संवाद) में निहित आगमनात्मक प्रमाण के प्रारंभिक उदाहरण के निशान शामिल हो सकते हैं। विपरीत पुनरावृत्त तकनीक, ऊपर की बजाय नीचे की ओर गिनना, सॉराइट्स विरोधाभास में पाया जाता है, जहां यह तर्क दिया गया था कि यदि रेत के 1,000,000 दाने ढेर बनाते हैं, और ढेर से दाने को हटाने से यह ढेर बन जाता है, तो रेत का दाना (या कोई दाना भी नहीं) ढेर बनाता है। गणितीय आगमन द्वारा सबसे पहला अंतर्निहित प्रमाण गेराज द्वारा 1000 ईस्वी के आसपास लिखे गए अल-फखरी में है, जिन्होंने पास्कल के त्रिकोण के द्विपद प्रमेय और गुणों को साबित करने के लिए इसे अंकगणितीय प्रगति पर लागू किया।

जैसा कि काट्ज़ कहते हैं

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³) 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 the sum formula for integral cubes.

भारत में, भास्कर द्वितीय की चक्रवला विधि में गणितीय आगमन द्वारा प्रारंभिक अंतर्निहित प्रमाण दिखाई देते हैं। हालांकि, इन प्राचीन गणितज्ञों में से किसी ने भी आगमन परिकल्पना को स्पष्ट रूप से नहीं बताया। इसी तरह का और मामला (वैका ने जो लिखा है, उसके विपरीत, जैसा कि फ्रायडेंथल ने ध्यान से दिखाया है) फ्रांसिस मौरोलिको की अपनी अरिथमेटिकोरम लिब्री डुओ (1575) में थी, जिसने यह साबित करने के लिए तकनीक का इस्तेमाल किया था कि पहले n समता (गणित) पूर्णांकों का योग n है^{2</उप>।}

इंडक्शन का सबसे पहला कठोर #गणितीय_प्रमाण उपयोग गर्सोनाइडेस (1288-1344) द्वारा किया गया था। इंडक्शन के सिद्धांत का पहला स्पष्ट सूत्रीकरण ब्लेस पास्कल ने अपने ट्रेटे डु त्रिकोण अंकगणित (1665) में दिया था। अन्य फ्रांसीसी, पियरे डी फर्मेट ने संबंधित सिद्धांत का पर्याप्त उपयोग किया: अनंत वंश द्वारा अप्रत्यक्ष प्रमाण।

प्रेरण परिकल्पना को स्विस जैकब बर्नौली द्वारा भी नियोजित किया गया था, और तभी से यह अच्छी तरह से जाना जाने लगा। सिद्धांत का आधुनिक औपचारिक उपचार केवल 19वीं शताब्दी में जॉर्ज बूले के साथ आया, ऑगस्टस डी मॉर्गन, चार्ल्स सैंडर्स पियर्स, जोसेफ पीनो, और रिचर्ड डेडेकिंड।

विवरण

गणितीय आगमन का सबसे सरल और सबसे सामान्य रूप अनुमान लगाता है कि कथन जिसमें प्राकृतिक संख्या शामिल है n (यानी पूर्णांक n ≥ 0 या 1) के सभी मूल्यों के लिए धारण करता है n. प्रमाण में दो चरण होते हैं:

1. आधार मामला (या प्रारंभिक मामला): सिद्ध करें कि कथन 0 या 1 के लिए है।
2. प्रेरण कदम (या आगमनात्मक कदम, या कदम का मामला): साबित करें कि हर के लिए n, यदि कथन के लिए है n, तो यह धारण करता है n + 1. दूसरे शब्दों में, मान लें कि बयान कुछ मनमानी प्राकृतिक संख्या के लिए है n, और साबित करें कि कथन के लिए है n + 1.

प्रेरण चरण में परिकल्पना, कि कथन किसी विशेष के लिए धारण करता है n, प्रेरण परिकल्पना या आगमनात्मक परिकल्पना कहलाती है। इंडक्शन स्टेप को साबित करने के लिए, इंडक्शन परिकल्पना को मान लिया जाता है n और फिर इस धारणा का उपयोग यह साबित करने के लिए करता है कि कथन के लिए है n + 1.

लेखक जो प्राकृतिक संख्याओं को 0 से शुरू करने के लिए परिभाषित करना पसंद करते हैं, आधार मामले में उस मान का उपयोग करते हैं; जो 1 से शुरू होने वाली प्राकृत संख्याओं को परिभाषित करते हैं वे उस मान का उपयोग करते हैं।

उदाहरण

क्रमागत प्राकृत संख्याओं का योग

सभी प्राकृतिक संख्याओं n के लिए निम्नलिखित कथन P(n) को सिद्ध करने के लिए गणितीय आगमन का उपयोग किया जा सकता है।

$P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.$

यह दी गई संख्या से कम या उसके बराबर प्राकृतिक संख्याओं के योग के लिए सामान्य सूत्र बताता है; वास्तव में बयानों का अनंत क्रम: $0={\tfrac {(0)(0+1)}{2}}$, $0+1={\tfrac {(1)(1+1)}{2}}$, $0+1+2={\tfrac {(2)(2+1)}{2}}$, आदि।

प्रस्ताव। प्रत्येक के लिए $n\in \mathbb {N}$, $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$ सबूत। मान लीजिए P(n) कथन है $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$ हम n पर आगमन द्वारा उपपत्ति देते हैं।

आधार मामला: दिखाएँ कि कथन सबसे छोटी प्राकृतिक संख्या n = 0 के लिए है।

पी (0) स्पष्ट रूप से सच है: $0={\tfrac {0(0+1)}{2}}\,.$ प्रेरण चरण: दिखाएँ कि प्रत्येक k ≥ 0 के लिए, यदि P(k) धारण करता है, तो P(k + 1) भी धारण करता है।

प्रेरण परिकल्पना मान लें कि किसी विशेष k के लिए, एकल मामला n = k धारण करता है, जिसका अर्थ है P(k) सत्य है:

$0+1+\cdots +k={\frac {k(k+1)}{2}}.$

यह इस प्रकार है: