गणितीय प्रेरण: Difference between revisions

From Vigyanwiki
m (9 revisions imported from alpha:गणितीय_प्रेरण)
(No difference)

Revision as of 12:05, 10 August 2023

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

गणितीय आगमन गणितीय प्रमाण के लिए विधि है कि कथन प्रत्येक प्राकृतिक संख्या के लिए सत्य है , अर्थात्, अपरिमित रूप से बहुत से मामले सब पकड़। अनौपचारिक रूपक इस तकनीक को समझाने में मदद करते हैं, जैसे डोमिनोज़ गिरना या सीढ़ी चढ़ना:

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

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

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

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

यद्यपि इसका नाम अन्यथा सुझाव दे सकता है, गणितीय आगमन को आगमनात्मक तर्क के साथ भ्रमित नहीं होना चाहिए जैसा कि दर्शनशास्त्र में प्रयोग किया जाता है (प्रेरण की समस्या देखें)। गणितीय पद्धति सामान्य कथन को सिद्ध करने के लिए असीम रूप से कुशल स्थितियों की जांच करती है, किन्तु ऐसा चर (गणित) को सम्मिलित करने वाली निगमनात्मक तर्क की परिमित श्रृंखला द्वारा करती है। , जो अपरिमित रूप से कुशल मान ले सकता है।[4]

इतिहास

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

गणितीय आगमन द्वारा सबसे पहला अंतर्निहित प्रमाण गेराज द्वारा 1000 ईस्वी के आसपास लिखे गए अल-फखरी में है, जिन्होंने पास्कल के त्रिकोण के द्विपद प्रमेय और गुणों को सिद्ध करने के लिए इसे अंकगणितीय प्रगति पर प्रयुक्त किया।[7][8]

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

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

भारत में, भास्कर द्वितीय की चक्रवला विधि में गणितीय आगमन द्वारा प्रारंभिक अंतर्निहित प्रमाण दिखाई देते हैं।[10]

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

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

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

विवरण

गणितीय आगमन का सबसे सरल और सबसे सामान्य रूप अनुमान लगाता है कि कथन जिसमें प्राकृतिक संख्या सम्मिलित है 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) कथन है हम n पर आगमन द्वारा उपपत्ति देते हैं।

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

P (0) स्पष्ट रूप से सच है:

प्रेरण चरण: दिखाएँ कि प्रत्येक k ≥ 0 के लिए, यदि P(k) धारण करता है, तब P(k + 1) भी धारण करता है।

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

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

बीजगणितय रूप से, दाहिने हाथ की ओर सरल करता है:

चरम बाएँ और दाएँ पक्ष की सामान्तरी करते हुए, हम यह निष्कर्ष निकालते हैं:

अर्थात्, कथन P(k + 1) भी सत्य है, जो प्रेरण चरण की स्थापना करता है।

निष्कर्ष: चूँकि बेस केस और गणितीय आगमन दोनों ही सही सिद्ध हुए हैं, गणितीय आगमन द्वारा स्टेटमेंट P(n) हर प्राकृतिक संख्या n के लिए है। क्यू.ई.डी.।∎

त्रिकोणमितीय असमानता

गणितीय आगमन का उपयोग प्रायः असमानता (गणित) को सिद्ध करने के लिए किया जाता है। उदाहरण के रूप में, हम यह सिद्ध करते हैं किसी भी वास्तविक संख्या के लिए और प्राकृतिक संख्या .

पहली नज़र में, ऐसा प्रतीत हो सकता है कि अधिक सामान्य संस्करण, किसी भी वास्तविक संख्या के लिए , प्रेरण के बिना सिद्ध किया जा सकता है; किन्तु स्थिति दिखाता है कि के गैर-पूर्णांक मानों के लिए यह असत्य हो सकता है . इससे पता चलता है कि हम विशेष रूप से के प्राकृतिक मूल्यों के लिए कथन की जांच करते हैं , और प्रेरण सबसे आसान उपकरण है।

प्रस्ताव। किसी के लिए भी और , .

प्रमाण। मनमाना वास्तविक संख्या तय करें , और जाने कथन हो . हम सम्मिलित करते हैं .

आधार स्थिति: गणना पुष्टि करता है .

प्रेरण कदम: हम निहितार्थ (तर्क) दिखाते हैं किसी भी प्राकृतिक संख्या के लिए . प्रेरण परिकल्पना मानें: किसी दिए गए मान के लिए , एकल स्थिति क्या सच है। त्रिकोणमितीय सर्वसमिकाओं की सूची और निरपेक्ष मान#वास्तविक संख्याओं का उपयोग करके, हम यह निष्कर्ष निकालते हैं:

चरम बाएँ और दाएँ हाथ की मात्राओं के मध्य असमानता यह दर्शाती है सत्य है, जो प्रेरण चरण को पूरा करता है।

निष्कर्ष: प्रस्ताव सभी प्राकृतिक संख्याओं के लिए धारण करता है . ∎

वेरिएंट

व्यवहार में, गणितीय आगमन द्वारा प्रूफ को प्रायः अलग प्रकार से संरचित किया जाता है, जो कि सिद्ध की जाने वाली संपत्ति की सटीक प्रकृति पर निर्भर करता है।

गणितीय आगमन के सभी प्रकार ट्रांसफिनिट गणितीय आगमन के विशेष स्थितियों हैं; #ट्रांसफिनिट गणितीय आगमन देखें गए हैं ।

=== 0 या 1 === के अतिरिक्त बेस केस

यदि कोई कथन सिद्ध करना चाहता है, तब सभी प्राकृतिक संख्याओं के लिए नहीं, किंतु केवल सभी संख्याओं के लिए n किसी निश्चित संख्या से अधिक या उसके सामान्तर b, तब प्रेरण द्वारा प्रमाण में निम्नलिखित सम्मिलित हैं:

  1. दिखा रहा है कि कथन कब धारण करता है n = b.
  2. दिखा रहा है कि यदि कथन मनमाना संख्या के लिए है nb, तब वही कथन भी मान्य है n + 1.

इसका उपयोग, उदाहरण के लिए, यह दिखाने के लिए किया जा सकता है 2nn + 5 के लिए n ≥ 3.

इस प्रकार, कोई उस कथन को सिद्ध कर सकता है P(n) सभी के लिए रखता है n ≥ 1, या सभी के लिए भी n ≥ −5. गणितीय आगमन का यह रूप वास्तव में पिछले रूप का विशेष स्थिति है, क्योंकि यदि कथन को सिद्ध किया जाना है P(n) तब इन दो नियमों के साथ इसे सिद्ध करना सिद्ध करने के सामान्तर है P(n + b) सभी प्राकृतिक संख्याओं के लिए n गणितीय आगमन बेस केस के साथ 0.[17] होता है।

उदाहरण: सिक्कों द्वारा डॉलर की राशि बनाना

4- और 5-डॉलर के सिक्कों की अनंत आपूर्ति मान लें। गणितीय आगमन का उपयोग यह सिद्ध करने के लिए किया जा सकता है कि डॉलर की कोई भी पूरी राशि इससे अधिक या सामान्तर है 12 ऐसे सिक्कों के संयोजन से बनाया जा सकता है। होने देना S(k) कथन को निरूपित करेंk डॉलर को 4- और 5-डॉलर के सिक्कों के संयोजन से बनाया जा सकता है। इसका प्रमाण S(k) सभी के लिए सत्य है k ≥ 12 फिर प्रेरण द्वारा प्राप्त किया जा सकता है k निम्नलिखित नुसार:

आधार स्थिति: दिखा रहा है S(k) के लिए रखता है k = 12 सरल है: तीन 4-डॉलर के सिक्के लें सकते हैं।

प्रेरण चरण: यह देखते हुए S(k) के कुछ मूल्य के लिए रखता है k ≥ 12 (प्रेरण परिकल्पना), सिद्ध करें S(k + 1) भी रखता है। मान लीजिए S(k) कुछ मनमानी के लिए सच है k ≥ 12. यदि इसका कोई उपाय है k डॉलर जिसमें कम से कम 4-डॉलर का सिक्का सम्मिलित है, इसे बनाने के लिए 5-डॉलर के सिक्के से बदलें k + 1 डॉलर। अन्यथा, यदि केवल 5-डॉलर के सिक्कों का उपयोग किया जाता है, k 5 का गुणक होना चाहिए और इसलिए कम से कम 15 होना चाहिए; किन्तु फिर हम बनाने के लिए तीन 5-डॉलर के सिक्कों को चार 4-डॉलर के सिक्कों से बदल सकते हैं k + 1 डॉलर। हर स्थितियों में, S(k + 1) क्या सच है।

इसलिए, प्रेरण के सिद्धांत द्वारा, S(k) सभी के लिए रखता है k ≥ 12, और प्रमाण पूरा हो गया है।

चूंकि इस उदाहरण में S(k) के लिए भी रखता है , उपरोक्त प्रमाण की न्यूनतम राशि को बदलने के लिए संशोधित नहीं किया जा सकता है 12 डॉलर किसी भी कम मूल्य के लिए m. के लिए m = 11, आधार स्थिति वास्तव में झूठा है; के लिए m = 10, प्रेरण चरण में दूसरा स्थिति (तीन 5- को चार 4-डॉलर के सिक्कों से बदलना) काम नहीं करेगा; और भी कम के लिए अकेले रहने दो m.

से अधिक काउंटरों पर गणितीय आगमन

प्रेरण प्रक्रिया को पुनरावृत्त करके, कभी-कभी दो प्राकृतिक संख्याओं, एन और एम से जुड़े कथन को सिद्ध करना वांछनीय होता है। यही है, आधार स्थितियों और एन के लिए प्रेरण कदम सिद्ध होता है, और उनमें से प्रत्येक में आधार स्थिति और एम के लिए प्रेरण कदम सिद्ध होता है। उदाहरण के लिए, प्राकृतिक संख्याओं के योग के साथ प्राकृतिक संख्याओं के योग को सम्मिलित करने वाले प्रमाण देखें। तीन या अधिक काउंटरों से जुड़े अधिक जटिल तर्क भी संभव हैं।

अनंत वंश

अनंत वंश की विधि गणितीय प्रेरण का रूपांतर है जिसका उपयोग पियरे डी फर्मेट द्वारा किया गया था। इसका प्रयोग यह दर्शाने के लिए किया जाता है कि कुछ कथन Q(n) सभी प्राकृतिक संख्याओं n के लिए असत्य है। इसके पारंपरिक रूप में यह दिखाया गया है कि यदि क्यू (एन) कुछ प्राकृतिक संख्या एन के लिए सत्य है, तब यह कुछ सख्ती से छोटी प्राकृतिक संख्या एम के लिए भी प्रयुक्त होता है। क्योंकि प्राकृतिक संख्याओं का कोई अनंत घटता हुआ क्रम नहीं है, यह स्थिति असंभव होगी, जिससे (विरोधाभास द्वारा प्रमाण) दिखाया जाएगा कि Q(n) किसी भी n के लिए सत्य नहीं हो सकता है।

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

उपसर्ग प्रेरण

गणितीय आगमन द्वारा प्रमाण के सबसे सामान्य रूप में प्रेरण चरण में सिद्ध करने की आवश्यकता होती है कि

जहां प्रेरण सिद्धांत पी (0) से पी (एन) तक पहुंचने में इस चरण के एन अनुप्रयोगों को स्वचालित करता है। इसे पूर्ववर्ती प्रेरण कहा जा सकता है क्योंकि प्रत्येक चरण उस संख्या के पूर्ववर्ती के बारे में कुछ से किसी संख्या के बारे में कुछ सिद्ध करता है।

कम्प्यूटेशनल जटिलता में रुचि का प्रकार उपसर्ग प्रेरण है, जिसमें कोई प्रेरण चरण में निम्नलिखित कथन को सिद्ध करता है:

या समकक्ष

प्रेरण सिद्धांत तब द्विआधारी लघुगणक लॉग2 को स्वचालित करता है पी (0) से पी (एन) तक प्राप्त करने में इस अनुमान के आवेदन। वास्तव में, इसे उपसर्ग प्रेरण कहा जाता है क्योंकि प्रत्येक चरण उस संख्या के उपसर्ग के बारे में कुछ से संख्या के बारे में कुछ सिद्ध करता है - जैसा कि इसके बाइनरी प्रतिनिधित्व के निम्न बिट को काटकर बनाया गया है। इसे बाइनरी प्रतिनिधित्व की लंबाई पर पारंपरिक प्रेरण के आवेदन के रूप में भी देखा जा सकता है।

यदि पारंपरिक पूर्ववर्ती गणितीय आगमन को कम्प्यूटेशनल रूप से एन-स्टेप लूप के रूप में व्याख्यायित किया जाता है, तब प्रीफिक्स गणितीय आगमन लॉग-एन-स्टेप लूप के अनुरूप होगा। इसके कारण, पूर्ववर्ती प्रेरण का उपयोग करने वाले प्रमाणों की तुलना में उपसर्ग प्रेरण का उपयोग करने वाले प्रमाण अधिक रचनात्मक रूप से रचनात्मक हैं।

पूर्ववर्ती प्रेरण ही कथन पर उपसर्ग प्रेरण को तुच्छ रूप से अनुकरण कर सकता है। उपसर्ग गणितीय आगमन पूर्ववर्ती गणितीय आगमन का अनुकरण कर सकता है, किन्तु केवल स्टेटमेंट को सिंटैक्टिकली कॉम्प्लेक्स ( परिबद्ध क्वांटिफायर यूनिवर्सल क्वांटिफायर जोड़कर) बनाने की मूल्य पर, इसलिए प्रीफिक्स गणितीय आगमन से बहुपदी समय फलन कम्प्यूटेशन से संबंधित दिलचस्प परिणाम अनबाउंड क्वांटिफायर को पूरी प्रकार से बाहर करने और सीमित करने पर निर्भर करते हैं। कथन में अनुमत बाउंडेड यूनिवर्सल और अस्तित्वगत परिमाणक क्वांटिफायर्स का प्रत्यावर्तन।[18] कोई इस विचार को कदम आगे ले जा सकता है: उसे सिद्ध करना होगा.

जहां प्रेरण सिद्धांत पी (0) से पी (एन) तक प्राप्त करने में इस अनुमान के लॉग लॉग एन अनुप्रयोगों को स्वचालित करता है। लॉग-टाइम समानांतर संगणना का अध्ययन करने के लिए, प्रेरण के इस रूप का उपयोग किया गया है।

पूर्ण (शक्तिशाली ) प्रेरण

अन्य प्रकार, जिसे पूर्ण प्रेरण कहा जाता है, मूल्य प्रेरण या शक्तिशाली प्रेरण का कोर्स (इसके विपरीत प्रेरण का मूल रूप कभी-कभी कमजोर प्रेरण के रूप में जाना जाता है), शक्तिशाली परिकल्पना का उपयोग करके प्रेरण चरण को सिद्ध करना आसान बनाता है: कथन को सिद्ध करता है इस धारणा के अनुसार सभी प्राकृतिक संख्याओं के लिए धारण करता है से कम ; इसके विपरीत, मूल रूप केवल ग्रहण करता है . शक्तिशाली गणितीय आगमन नाम का कारण यह नहीं है कि यह विधि कमजोर गणितीय आगमन से अधिक सिद्ध हो सकती है, किन्तु केवल गणितीय आगमन चरण में उपयोग की जाने वाली शक्तिशाली परिकल्पना को संदर्भित करती है।

वास्तव में, यह दिखाया जा सकता है कि दो विधियाँ वास्तव में समतुल्य हैं, जैसा कि नीचे बताया गया है। पूर्ण आगमन के इस रूप में, व्यक्ति को अभी भी आधार स्थिति को सिद्ध करना होता है, , और अतिरिक्त-आधार स्थितियों को सिद्ध करना भी आवश्यक हो सकता है जैसे कि सामान्य तर्क प्रयुक्त होने से पहले, जैसा कि फिबोनाची संख्या के नीचे दिए गए उदाहरण में है .

चूंकि अभी बताए गए फॉर्म में आधार स्थितियों को सिद्ध करने की आवश्यकता है, यदि कोई सिद्ध कर सकता है तब यह अनावश्यक है (मान लिया सभी के लिए कम ) सबके लिए . यह नीचे वर्णित के रूप में #ट्रांसफिनिट गणितीय आगमन का विशेष स्थिति है, चूंकि यह अब सामान्य गणितीय आगमन के सामान्तर नहीं है। इस रूप में आधार को केस द्वारा सम्‍मिलित किया जाता है , कहाँ किसी अन्य के साथ सिद्ध नहीं होता है मान लिया गया हैं;

इस स्थितियों को अलग से संभालने की आवश्यकता हो सकती है, किन्तु कभी-कभी वही तर्क प्रयुक्त होता है और , जिससे प्रूफ़ सरल और अधिक सुरुचिपूर्ण हो जाता है।

चूंकि , इस पद्धति में, यह सुनिश्चित करना महत्वपूर्ण है कि इसका प्रमाण परोक्ष रूप से यह नहीं मानता , उदा. कहकर मनमाना चुनें , या यह मानकर कि m तत्वों के समुच्चय में तत्व है।

पूर्ण आगमन सामान्य गणितीय आगमन के समान है, जैसा कि ऊपर वर्णित है, इस अर्थ में कि विधि द्वारा प्रमाण को दूसरे द्वारा प्रमाण में परिवर्तित किया जा सकता है। मान लीजिए इसका प्रमाण है पूर्ण प्रेरण द्वारा। होने देना कथन हो सभी के लिए रखता है ऐसा है कि . तब सभी के लिए रखता है यदि और केवल यदि सभी के लिए रखता है , और हमारे प्रमाण के प्रमाण में आसानी से परिवर्तित हो जाता है (साधारण) प्रेरण द्वारा। यदि, दूसरी ओर, सामान्य प्रेरण द्वारा सिद्ध किया गया था, प्रमाण पहले से ही पूर्ण प्रेरण द्वारा प्रभावी रूप से होगा: बिना किसी पूर्वधारणा के आधार स्थितियों में सिद्ध होता है, और गणितीय आगमन स्टेप में सिद्ध होता है, जिसमें कोई पहले के सभी स्थितियों को मान सकता है किन्तु केवल केस का उपयोग करने की आवश्यकता होती है .

उदाहरण: फाइबोनैचि संख्याएं

पूर्ण प्रेरण सबसे उपयोगी होता है जब प्रत्येक प्रेरण चरण के लिए आगमनात्मक परिकल्पना के कुशल उदाहरण आवश्यक होते हैं। उदाहरण के लिए, यह दिखाने के लिए पूर्ण प्रेरण का उपयोग किया जा सकता है

कहाँ nवां फाइबोनैचि संख्या है, और (सुनहरा अनुपात) और बहुपद के बहुपद की जड़ हैं . इस तथ्य का उपयोग करके कि प्रत्येक के लिए , उपरोक्त पहचान के लिए प्रत्यक्ष गणना द्वारा सत्यापित किया जा सकता है यदि कोई मानता है कि यह पहले से ही दोनों के लिए है और . प्रमाण को पूरा करने के लिए, पहचान को दो आधार स्थितियों में सत्यापित किया जाना चाहिए: और .

उदाहरण: प्रधान गुणनखंड

पूर्ण प्रेरण द्वारा अन्य प्रमाण उस परिकल्पना का उपयोग करता है जो कथन सभी छोटे लोगों के लिए रखता है अधिक अच्छी प्रकार। इस कथन पर विचार करें कि 1 से अधिक प्रत्येक प्राकृतिक संख्या ( या अधिक) अभाज्य संख्याओं का गुणनफल है, जो कि अंकगणित का मौलिक प्रमेय है # अंकगणित के मौलिक प्रमेय का अस्तित्व भाग है। गणितीय आगमन स्टेप को सिद्ध करने के लिए, गणितीय आगमन परिकल्पना यह है कि किसी दिए गए के लिए कथन सभी छोटे के लिए है . यदि प्राइम है तब यह निश्चित रूप से प्राइम्स का उत्पाद है, और यदि नहीं, तब परिभाषा के अनुसार यह उत्पाद है: , जहां कोई भी कारक 1 के सामान्तर नहीं है; इसलिए कोई भी सामान्तर नहीं है , और इसलिए दोनों 1 से बड़े और उससे छोटे हैं . प्रेरण परिकल्पना अब प्रयुक्त होती है और , इसलिए प्रत्येक अभाज्य संख्या का गुणनफल है। इस प्रकार प्राइम्स के उत्पादों का उत्पाद है, और इसलिए विस्तार से खुद प्राइम्स का उत्पाद है।

उदाहरण: डॉलर राशियों पर दोबारा गौर किया गया

हम उसी उदाहरण को #उदाहरण के रूप में सिद्ध करने की कोशिश करेंगे: सिक्कों द्वारा डॉलर की राशि बनाना, इस बार शक्तिशाली प्रेरण के साथ। कथन वही रहता है:

चूंकि , विस्तारित आधार स्थितियों से प्रारंभ होने वाले प्रमाण की संरचना और मान्यताओं में थोड़ा अंतर होगा।

प्रमाण।

बेस केस: वो दिखाओ के लिए रखता है .

आधार स्थिति रखता है।

प्रेरण कदम: कुछ दिया , मान लीजिए सभी के लिए रखता है साथ . सिद्ध करें कि रखती है।

का चयन , और वह देख रहा है पता चलता है कि आगमनात्मक परिकल्पना द्वारा धारण करता है। अर्थात् योग के कुछ संयोजन द्वारा बनाया जा सकता है और डॉलर के सिक्के। फिर, बस जोड़ना डॉलर का सिक्का उस संयोजन का योग देता है . वह है, रखती है। ∎

फॉरवर्ड-बैकवर्ड गणितीय आगमन

कभी-कभी, कथन को सिद्ध करते हुए, पीछे की ओर घटाना अधिक सुविधाजनक होता है , के लिए इसकी वैधता दी . चूंकि , आधार स्थितियों को स्थापित करने के लिए किसी संख्या के लिए कथन की वैधता सिद्ध करना पर्याप्त नहीं है; इसके अतिरिक्त , किसी को प्राकृतिक संख्याओं के अनंत उपसमुच्चय के लिए कथन को सिद्ध करने की आवश्यकता है। उदाहरण के लिए, ऑगस्टिन लुइस कॉची ने पहली बार आगे (नियमित) गणितीय आगमन को सिद्ध करने के लिए उपयोग किया जाता हैं।

अंकगणित और ज्यामितीय साधनों की असमानता # कॉची द्वारा 2 की सभी शक्तियों के लिए आगे-पीछे प्रेरण का उपयोग करके प्रमाण, और फिर इसे सभी प्राकृतिक संख्याओं के लिए दिखाने के लिए पीछे की ओर प्रेरण का उपयोग किया जाता है।[19][20]

प्रेरण चरण में त्रुटि का उदाहरण

एन के सभी मूल्यों के लिए प्रेरण चरण सिद्ध होना चाहिए। इसका वर्णन करने के लिए, जोएल ई. कोहेन ने निम्नलिखित तर्क का प्रस्ताव रखा, जो गणितीय आगमन द्वारा यह सिद्ध करने के लिए है कि सभी घोड़े ही रंग के होते हैं:[21]

बेस केस: केवल घोड़े के समुच्चय में, केवल ही रंग होता है।

गणितीय आगमन स्टेप: गणितीय आगमन परिकल्पना के रूप में मान लें कि किसी भी समुच्चय के अंदर घोड़ों का ही रंग होता है। अब इसके किसी भी समुच्चय को देखें घोड़े। उन्हें नंबर दें: . समुच्चय्स पर विचार करें और . प्रत्येक केवल का समुच्चय है घोड़े, इसलिए प्रत्येक के अंदर केवल रंग होता है। किन्तु दो समुच्चय ओवरलैप करते हैं, इसलिए सभी के मध्य केवल ही रंग होना चाहिए घोड़े।

आधार स्थिति तुच्छ है, और प्रेरण कदम सभी स्थितियों में सही है . चूँकि, गणितीय आगमन स्टेप में उपयोग किया गया तर्क गलत है , क्योंकि कथन है कि दो समुच्चय ओवरलैप के लिए गलत है और .

औपचारिकता

दूसरे क्रम के तर्क में, आगमन के स्वयंसिद्ध को निम्नानुसार लिखा जा सकता है:

,

जहाँ P(.) प्राकृतिक संख्या वाले विधेय के लिए चर है और प्राकृतिक संख्याओं के लिए k और n चर हैं।

शब्दों में, आधार स्थिति P(0) और गणितीय आगमन स्टेप (अर्थात्, गणितीय आगमन परिकल्पना P(k) तात्पर्य P(k + 1)) साथ इसका कारण है P(n) किसी भी प्राकृतिक संख्या के लिए n. प्रेरण का स्वयंसिद्ध अनुमान लगाने की वैधता पर जोर देता है P(n) किसी भी प्राकृतिक संख्या के लिए धारण करता है n बेस केस और गणितीय आगमन स्टेप से होता है।

स्वयंसिद्ध में पहला क्वांटिफायर अलग-अलग संख्याओं के अतिरिक्त विधेय पर आधारित है। यह दूसरे क्रम का क्वांटिफायर है, जिसका अर्थ है कि यह स्वयं सिद्ध दूसरे क्रम के तर्क में कहा गया है। प्रथम-क्रम तर्क में अंकगणितीय प्रेरण को स्वयं सिद्ध करने के लिए स्वयंसिद्ध स्कीमा की आवश्यकता होती है जिसमें प्रत्येक संभावित विधेय के लिए अलग स्वयंसिद्ध हो। लेख पियानो सिद्धांत में इस मुद्दे पर आगे की चर्चा सम्मिलित है।

प्राकृतिक संख्याओं के लिए संरचनात्मक प्रेरण का सिद्धांत सबसे पहले पीनो द्वारा तैयार किया गया था, जिन्होंने इसका उपयोग निम्नलिखित चार अन्य स्वयंसिद्धों के साथ प्राकृतिक संख्याओं को निर्दिष्ट करने के लिए किया था:

  1. 0 प्राकृतिक संख्या है।
  2. उत्तराधिकारी समारोह s प्रत्येक प्राकृतिक संख्या का प्राकृतिक संख्या प्राप्त होती है (s(x) = x + 1).
  3. उत्तराधिकारी कार्य इंजेक्शन है।
  4. 0 के समारोह की सीमा में नहीं है s.

प्रथम-क्रम तर्क में । प्रथम-क्रम ZFC समुच्चय सिद्धांत, विधेय पर परिमाणीकरण की अनुमति नहीं है, किन्तु कोई भी समुच्चय पर परिमाणीकरण द्वारा प्रेरण व्यक्त कर सकता है:

A प्रस्ताव का प्रतिनिधित्व करने वाले समुच्चय के रूप में पढ़ा जा सकता है, और इसमें प्राकृतिक संख्याएँ होती हैं, जिसके लिए प्रस्ताव रखता है। यह स्वयंसिद्ध नहीं है, किंतु प्रमेय है, यह देखते हुए कि पीनो के अनुरूप, स्वयंसिद्धों द्वारा ZFC समुच्चय सिद्धांत की भाषा में प्राकृतिक संख्याओं को परिभाषित किया गया है।

ट्रांसफिनिट गणितीय आगमन

पूर्ण प्रेरण के सिद्धांत की भिन्नता किसी भी अच्छी प्रकार से स्थापित समुच्चय के तत्वों के बारे में कथनों के लिए सामान्यीकृत की जा सकती है, अर्थात, प्रतिवर्त संबंध वाला समुच्चय < जिसमें कोई अनंत अवरोही श्रृंखला नहीं है। क्रमिक संख्या का प्रतिनिधित्व करने वाला प्रत्येक समुच्चय अच्छी प्रकार से स्थापित है, प्राकृतिक संख्याओं का समुच्चय उनमें से है।

अच्छी प्रकार से स्थापित समुच्चय के लिए प्रयुक्त, ट्रांसफिनिट गणितीय आगमन को कदम के रूप में तैयार किया जा सकता है। यह सिद्ध करने के लिए कि कथन P(n) प्रत्येक क्रमिक संख्या के लिए है:

  1. दिखाएँ, प्रत्येक क्रम संख्या n के लिए, कि यदि P(m) सभी के लिए प्रयुक्त होता है m < n, तब P(n) भी धारण करता है।

गणितीय आगमन का यह रूप, जब क्रमिक संख्याओं के समुच्चय पर प्रयुक्त होता है (जो सुव्यवस्थित और इसलिए अच्छी प्रकार से स्थापित वर्ग (समुच्चय सिद्धान्त) बनाता है), को ट्रांसफिनिट गणितीय आगमन कहा जाता है। यह समुच्चय थ्योरी, टोपोलॉजी और अन्य क्षेत्रों में महत्वपूर्ण प्रूफ विधि है।

ट्रांसफिनिट गणितीय आगमन द्वारा प्रमाण सामान्यतः पर तीन स्थितियों में अंतर करते हैं:

  1. जब n न्यूनतम तत्व है, अर्थात n से छोटा कोई तत्व नहीं है;
  2. जब n का प्रत्यक्ष पूर्ववर्ती होता है, अर्थात तत्वों का समूह जो n से छोटा होता है, उसमें सबसे बड़ा तत्व होता है;
  3. जब n का कोई प्रत्यक्ष पूर्ववर्ती नहीं है, अर्थात n तथाकथित सीमा क्रमसूचक है।

कड़ाई से बोलते हुए, आधार स्थितियों को सिद्ध करने के लिए ट्रांसफ़िनिटी गणितीय आगमन में यह आवश्यक नहीं है, क्योंकि यह प्रस्ताव का विशेष स्थिति है कि यदि P सभी के लिए सत्य है n < m, तब P, m के लिए सत्य है। यह रिक्त रूप से सत्य है क्योंकि इसका कोई मान नहीं है n < m यह प्रति उदाहरण के रूप में काम कर सकता है। तब विशेष स्थितियों सामान्य स्थितियों के विशेष स्थितियों हैं।

सुव्यवस्थित सिद्धांत से संबंध

गणितीय आगमन के सिद्धांत को सामान्यतः प्राकृतिक संख्याओं के स्वयंसिद्ध के रूप में कहा जाता है; पीआनो स्वयं सिद्ध देखें। यह अन्य पीआनो अभिगृहीतबं के संदर्भ में सुव्यवस्थित सिद्धांत से सख्त रूप से शक्तिशाली है। निम्नलिखित मान लीजिए:

  • ट्राइकोटॉमी (गणित) स्वयंसिद्ध: किसी भी प्राकृतिक संख्या n और m के लिए, n, m से कम या उसके सामान्तर है यदि और केवल यदि m, n से कम नहीं है।
  •  प्रत्येक प्राकृतिक संख्या n के लिए ,कोई भी प्राकृतिक संख्या और n + 1के बीच नहीं है।
  •  प्रत्येक प्राकृतिक संख्या n के लिए ,कोई भी प्राकृतिक संख्या और n + 1के बीच नहीं है।.
  • कोई प्राकृतिक संख्या शून्य से कम नहीं होती।

इसके पश्चात् यह सिद्ध किया जा सकता है कि उपरोक्त सूचीबद्ध सूक्तियों को देखते हुए प्रेरण, अच्छी प्रकार से आदेश देने वाले सिद्धांत का तात्पर्य है। निम्नलिखित प्रमाण पूर्ण आगमन और पहले और चौथे स्वयंसिद्धों का उपयोग करता है।

प्रमाण। मान लीजिए कि प्राकृतिक संख्याओं का खाली समुच्चय उपस्तिथ है। बता दें P(n) यह प्रामाणित है कि n S में नहीं है। तब P(0) सत्य है, क्योंकि यदि यह असत्य था तब 0 S का सबसे छोटा अवयव है। इसके अतिरिक्त, मान लें कि n प्राकृतिक संख्या है, और मान लीजिए कि P(m) सभी प्राकृतिक संख्याओं के लिए सत्य है, m से कम n + 1. तब यदि P(n + 1) गलत है n + 1 एस में है, इस प्रकार एस में न्यूनतम तत्व है, विरोधाभास है। इस प्रकार P(n + 1) क्या सच है। इसलिए, पूर्ण आगमन सिद्धांत द्वारा, P(n) सभी प्राकृत संख्याओं n पर प्रयुक्त होता है; तब एस खाली विरोधाभास होता है। ∎

समुच्चय के लिए संख्या रेखा {(0, n): n}{(1, n): n}. संख्याएं जोड़े के दूसरे घटक को संदर्भित करती हैं; पहले रंग या स्थान से प्राप्त किया जा सकता है।

दूसरी ओर, समुच्चय , चित्र में दिखाया गया है, सुव्यवस्थित है[22]: 35lf  लेक्सिकोग्राफिक ऑर्डर द्वारा।

इसके अतिरिक्त, आगमन अभिगृहीत को छोड़कर, यह सभी पीआनो अभिगृहीतबं को संतुष्ट करता है, जहां पीआनो के स्थिरांक 0 की व्याख्या जोड़ी (0, 0) के रूप में की जाती है, और पीआनो के उत्तराधिकारी फलन को जोड़े पर परिभाषित किया जाता है succ(x, n) = (x, n + 1) सभी के लिए और .

प्रेरण सिद्धांत के उल्लंघन के उदाहरण के रूप में, भविष्यवाणी को परिभाषित करें P(x, n) जैसा (x, n) = (0, 0) या (x, n) = succ(y, m) कुछ के लिए और . तब आधार स्थिति P(0, 0) तुच्छ रूप से सत्य है, और ऐसा ही प्रेरण चरण भी है: यदि P(x, n), तब P(succ(x, n)). चूँकि, समुच्चय में सभी जोड़ियों के लिए P सही नहीं है।

अधिष्ठापन सिद्धांत के साथ पियानो के अभिगृहीत विशिष्ट रूप से प्राकृतिक संख्याओं का प्रतिरूपण करते हैं। प्रेरण सिद्धांत को सुव्यवस्थित सिद्धांत के साथ बदलने से अधिक विदेशी मॉडल की अनुमति मिलती है जो सभी स्वयंसिद्धों को पूरा करते हैं।[22]

यह गलती से कुशल किताबों में छप गया है[22]और सूत्रों का कहना है कि सुव्यवस्थित सिद्धांत प्रेरण सिद्धांत के सामान्तर है। अन्य पियानो अभिगृहीतबं के संदर्भ में, यह स्थिति नहीं है, किन्तु अन्य अभिगृहीतबं के संदर्भ में, वह समतुल्य हैं;[22] विशेष रूप से, सुव्यवस्थित सिद्धांत का तात्पर्य पहले दो उपरोक्त सूचीबद्ध स्वयंसिद्धों के संदर्भ में आगमन अभिगृहीत से है और

  • प्रत्येक प्राकृत संख्या या तब 0 होती है या n + 1 कुछ प्राकृतिक संख्या के लिए n.

कुशल गलत प्रमाणों में सामान्य गलती यह मान लेना है n − 1 अनूठी और अच्छी प्रकार से परिभाषित प्राकृतिक संख्या है, संपत्ति जो अन्य पीआनो स्वयंसिद्धों द्वारा निहित नहीं है।[22]

यह भी देखें

टिप्पणियाँ

  1. Matt DeVos, Mathematical Induction, Simon Fraser University
  2. Gerardo con Diaz, Mathematical Induction Archived 2 May 2013 at the Wayback Machine, Harvard University
  3. Anderson, Robert B. (1979). Proving Programs Correct. New York: John Wiley & Sons. p. 1. ISBN 978-0471033950.
  4. Suber, Peter. "Mathematical Induction". Earlham College. Retrieved 26 March 2011.
  5. Acerbi 2000.
  6. Hyde & Raffman 2018.
  7. Rashed 1994, pp. 62–84.
  8. 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"
  9. काट्ज़ (1998), पृष्ठ। 255
  10. 10.0 10.1 Cajori (1918), p. 197: '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.'
  11. Rashed 1994, p. 62.
  12. Simonson 2000.
  13. Rabinovitch 1970.
  14. "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 sorites" (Boole c. 1849 Elementary Treatise on Logic not mathematical pp. 40–41 reprinted in 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)
  15. Peirce 1881.
  16. Shields 1997.
  17. Ted Sundstrom, Mathematical Reasoning, p. 190, Pearson, 2006, ISBN 978-0131877184
  18. Buss, Samuel (1986). Bounded Arithmetic. Naples: Bibliopolis.
  19. "Forward-Backward Induction | Brilliant Math & Science Wiki". brilliant.org (in English). Retrieved 2019-10-23.
  20. Cauchy, Augustin-Louis (1821). Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique, Archived 14 October 2017 at the Wayback Machine Paris. The proof of the inequality of arithmetic and geometric means can be found on pages 457ff.
  21. Cohen, Joel E. (1961). "On the nature of mathematical proof". Opus.. Reprinted in A Random Walk in Science (R. L. Weber, ed.), Crane, Russak & Co., 1973.
  22. 22.0 22.1 22.2 22.3 22.4 Öhman, Lars–Daniel (6 May 2019). "Are Induction and Well-Ordering Equivalent?". The Mathematical Intelligencer. 41 (3): 33–40. doi:10.1007/s00283-019-09898-4.


संदर्भ



परिचय

इतिहास

श्रेणी:गणितीय आगमन श्रेणी:साक्ष्य युक्त लेख