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

Not to be confused with विवेचनात्मक तार्किकता.

File:Dominoeffect.png

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

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

गणितीय प्रेरण यह साबित करता है कि हम सीढ़ी पर जितना चाहें उतना ऊपर चढ़ सकते हैं, यह साबित करके कि हम निचले पायदान (आधार) पर चढ़ सकते हैं और प्रत्येक पायदान से हम अगले पायदान पर चढ़ सकते हैं ( कदम)।

— ठोस गणित, पेज 3 मार्जिन।

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

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

इतिहास

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

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

अल-कराजी द्वारा पेश किया गया और अल-सामावल और अन्य लोगों द्वारा जारी रखा गया एक और महत्वपूर्ण विचार कुछ अंकगणितीय अनुक्रमों से निपटने के लिए एक आगमनात्मक तर्क था। इस प्रकार अल-कराजी ने आर्यभट्ट को पहले से ही ज्ञात अभिन्न घनों के योग पर परिणाम साबित करने के लिए इस तरह के तर्क का इस्तेमाल किया, हालांकि, अल-कराजी ने मनमाने ढंग से एन के लिए एक सामान्य परिणाम नहीं बताया। . उन्होंने विशेष पूर्णांक 10 के लिए अपना प्रमेय बताया [...] उनका प्रमाण, फिर भी, स्पष्ट रूप से किसी अन्य पूर्णांक तक विस्तार योग्य होने के लिए डिज़ाइन किया गया था। [...] अल-करजी के तर्क में संक्षेप में प्रेरण द्वारा आधुनिक तर्क के दो बुनियादी घटक शामिल हैं, अर्थात् n = 1 (1 = 1^{3<) के लिए कथन का सत्य /sup>) और n = k से n = k के लिए सत्य की व्युत्पत्ति - 1. बेशक, यह दूसरा घटक स्पष्ट नहीं है क्योंकि, कुछ अर्थों में, अल-काराजी का तर्क उलटा है; यानी, वह n = 10 से शुरू करता है और ऊपर की ओर बढ़ने के बजाय नीचे 1 तक जाता है। फिर भी, अल-फखरी में उनका तर्क पूर्णांक घनों का योग सूत्र का सबसे पुराना प्रमाण है।}

भारत में, भास्कर द्वितीय की चक्रवला विधि में गणितीय आगमन द्वारा प्रारंभिक अंतर्निहित प्रमाण दिखाई देते हैं। हालांकि, इन प्राचीन गणितज्ञों में से किसी ने भी आगमन परिकल्पना को स्पष्ट रूप से नहीं बताया। इसी तरह का और मामला (वैका ने जो लिखा है, उसके विपरीत, जैसा कि फ्रायडेंथल ने ध्यान से दिखाया है) फ्रांसिस मौरोलिको की अपनी अरिथमेटिकोरम लिब्री डुओ (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 <!--\; \cdots \; -->+k=\frac{k(}{}$