गणितीय आगमन का सिद्धांत
गणितीय आगमन (mathematical induction) गणित में उपपत्ति की एक बहुत प्रचलित विधि है। इसका प्रयोग सबसे अधिक तब होता है, जब हम प्राकृत संख्याओं या किसी अन्य अनुक्रम के साथ काम करते हैं।
सिद्धांत
गणितीय आगमन के सिद्धांत का आधार यह है कि दिए गए कथन को हम किसी पहले अवयव के लिए सिद्ध करते हैं। प्राकृत संख्याओं में यह प्रायः n = 1 होता है। यह हम केवल मान रखकर सिद्ध करते हैं (आधार चरण)। अगले, आगमन चरण में हम सप्रतिबंध कथन “यदि कथन n = a के लिए सत्य है, तो वह n = a + 1 के लिए भी सत्य है” सिद्ध करते हैं।
इन दो चरणों से हम निष्कर्ष निकाल सकते हैं कि दिया गया कथन सभी n के लिए सत्य है (उस समुच्चय के, जिसके साथ हम काम कर रहे हैं)। ऐसा क्यों है? शुरुआत में हम सिद्ध करते हैं कि कथन n = 1 के लिए सत्य है। साथ ही हम जानते हैं कि यदि कथन n = a के लिए सत्य है, तो वह n = a + 1 के लिए भी सत्य है। अतः हम a = 1 चुनते हैं। हम जानते हैं कि कथन a = 1 के लिए सत्य है, और यह भी जानते हैं कि यह a + 1 = 2 के लिए सत्य है। अब हम जानते हैं कि कथन a = 2 के लिए सत्य है। पर चूँकि यह a + 1 के लिए भी सत्य है, इसलिए यह 2 + 1 = 3 के लिए भी सत्य होना चाहिए। और इसी तरह आगे।
पहला उदाहरण
पहला उदाहरण तुच्छ होगा। हम सिद्ध करेंगे कि यदि किसी भी सम संख्या में दो जोड़ें, तो फिर से सम संख्या मिलती है। हम प्राकृत संख्याओं में काम कर रहे हैं, इसलिए व्यापक सम संख्या को 2n लिखते हैं, जहाँ n एक प्राकृत संख्या है। यदि n के स्थान पर कोई भी प्राकृत संख्या रखें, तो परिणाम में सम संख्या मिलती है, यह पहली नज़र में दिखता है। विभाज्यता को खड़ी रेखा से इस प्रकार लिखते हैं:
इस लेखन का अर्थ है कि दो, व्यंजक 2n को बिना शेष के विभाजित करता है। जब हम विभाज्यता लिखना जानते हैं, तो वह भी लिख सकते हैं, जो हमें गणितीय आगमन से सिद्ध करना है।
पहले उदाहरण में हमें यही सिद्ध करना है: कि दो, व्यंजक 2n + 2 को विभाजित करता है – यह दिए गए शाब्दिक कथन “यदि किसी भी सम संख्या में दो जोड़ें, तो फिर से सम संख्या मिलती है” के बिल्कुल संगत है।
आधार चरण में हम इसे पहले अवयव, अर्थात् एक, के लिए सिद्ध करते हैं। व्यंजक में n = 1 रखते हैं:
दो, चार को बिना शेष के विभाजित करता है, इसलिए पहले अवयव के लिए यह सत्य है। इसके बाद आगमन चरण आता है, जिसमें हमें सिद्ध करना है कि यदि यह a-वें अवयव के लिए सत्य है, तो (a + 1)-वें अवयव के लिए भी सत्य है। शुरुआत में हम मान लेते हैं कि हमारी मान्यता, अर्थात् n = a के लिए कथन, सत्य है (आगमन परिकल्पना):
इस व्यंजक को हम सत्य मानते हैं – उपपत्ति बनाने में हम इसका उपयोग करेंगे। अब हम सिद्ध करना चाहते हैं कि
हमने क्या किया? a के स्थान पर हमने (a + 1) लिखा। कोष्ठक महत्वपूर्ण हैं, यह व्यंजक ग़लत होता: 2a + 1 + 2। हम पूरे व्यंजक में एक नहीं जोड़ रहे, बल्कि सचमुच a से एक बड़ा व्यंजक, अर्थात् (a + 1), बना रहे हैं। कोष्ठक खोलकर व्यंजक को सरल करते हैं।
अब विभाज्यता पर एक छोटी-सी बात। यदि हमारे पास दो संख्याएँ हैं, मान लीजिए p और q, जो किसी संख्या, जैसे r, से विभाज्य हैं, तो उनका योग भी संख्या r से विभाज्य होता है। अतः:
उदाहरण के लिए, हम यहाँ संख्याएँ p = 8, q = 20 और r = 4 रख सकते हैं। हम देखते हैं कि चार, आठ और बीस दोनों को विभाजित करता है। और यह उनके योग 8 + 20 = 28 को भी विभाजित करता है।
हम अपने उदाहरण में इसका उपयोग कैसे करेंगे? दाएँ पक्ष को हम संख्याओं p और q में इस प्रकार बाँटते हैं:
संख्या q, अर्थात् दो, स्पष्ट रूप से दो से विभाज्य है। और व्यंजक p भी दो से विभाज्य है, क्योंकि आगमन परिकल्पना हमें यही बताती है। व्यंजक p बिल्कुल हमारी परिकल्पना के संगत है, जिसे हम सत्य मान रहे हैं। और यदि p दो से विभाज्य है और साथ ही q दो से विभाज्य है, तो उनका योग भी दो से विभाज्य है।
परिकल्पना के बारे में एक बार फिर। शुरुआत में हमने कहा था कि हम मानते हैं कि
इसीलिए जब उपपत्ति बनाते समय हमें व्यंजक 2a + 2 मिला, तो हम उसके बारे में कह सके कि वह दो से विभाज्य है। कारण यही है कि यह हमारी परिकल्पना है। सामान्यतः गणितीय आगमन का यही सबसे कठिन चरण होता है – यह समझना कि आगमन परिकल्पना का उपयोग कब और क्यों किया जा सकता है।
इसी के साथ आगमन पूरा होता है, उपपत्ति सफलतापूर्वक हो गई, प्रमेय सत्य है।
यदि आप चाहें, तो इसे दूसरी तरह भी बाँट सकते थे और परिकल्पना का उपयोग करने की ज़रूरत नहीं पड़ती: p = 2n और q = 2 + 2। संख्या q = 4 स्पष्ट रूप से दो से विभाज्य है और इसी तरह p = 2n भी, क्योंकि दो से भाग देने पर हमें संख्या n मिलती है, जो प्राकृत, अर्थात् पूर्णांक है। फिर से हमें दो ऐसे व्यंजक मिले, जो दोनों दो से विभाज्य हैं, इसलिए उनका योग भी दो से विभाज्य है।
पर दोनों ही स्थितियों में हमने सिद्ध किया कि
- दिया गया व्यंजक n = 1 के लिए सत्य है,
- यदि व्यंजक n के लिए सत्य है, तो वह n + 1 के लिए भी सत्य है।
यहाँ से हम निष्कर्ष निकाल सकते हैं:
- हम जानते हैं कि व्यंजक n = 1 के लिए सत्य है।
- यदि यह n के लिए सत्य है, तो n + 1 के लिए भी सत्य होना चाहिए, अर्थात् 1 + 1 के लिए भी, अर्थात् व्यंजक n = 2 के लिए भी सत्य है।
- यदि यह n के लिए सत्य है, तो n + 1 के लिए भी सत्य होना चाहिए, अर्थात् 2 + 1 के लिए भी, अर्थात् व्यंजक n = 3 के लिए भी सत्य है।
- यदि यह n के लिए सत्य है, तो n + 1 के लिए भी सत्य होना चाहिए, अर्थात् 3 + 1 के लिए भी, अर्थात् व्यंजक n = 4 के लिए भी सत्य है।
- यदि यह n के लिए सत्य है, तो n + 1 के लिए भी सत्य होना चाहिए, अर्थात् 4 + 1 के लिए भी, अर्थात् व्यंजक n = 5 के लिए भी सत्य है।
- …
दूसरा उदाहरण
अब हम गणितीय आगमन से एक सरल कथन सिद्ध करेंगे:
पहले आधार चरण: हम जाँचते हैं कि कथन n = 1 के लिए सत्य है या नहीं, क्योंकि यह उन प्राकृत संख्याओं का पहला अवयव है, जिनसे हम n चुनते हैं।
यह स्पष्ट रूप से सत्य है। अब हम आगमन चरण पर आते हैं, जिसमें हमें जाँचना है कि यदि कथन n = a के लिए सत्य है, तो क्या वह n = a + 1 के लिए भी सत्य है। अतः हमारी परिकल्पना यह है कि
और हम सिद्ध करना चाहते हैं:
पहले बाएँ पक्ष को हम घातों के नियमों से तोड़ते हैं और दाएँ पक्ष में बस कोष्ठक खोलते हैं।
बाएँ पक्ष में गुणा के स्थान पर हम योग लिखते हैं, दाएँ पक्ष को बिना बदले छोड़ देते हैं।
अब हम परिकल्पना का उपयोग करते हैं। परिकल्पना वह कथन है, जिसे हम सत्य मानते हैं। असमिका के दोनों पक्षों में दो-दो पद हैं, जो जोड़े गए हैं। साथ ही हम जानते हैं कि
पहली पंक्ति हमें परिकल्पना बताती है और दूसरा कथन स्पष्ट है (2a का सबसे छोटा मान a = 1 पर होता है और वह दो के बराबर है)। अतः हम जानते हैं कि बाएँ पक्ष के दोनों पद दाएँ पक्ष के दोनों पदों से बड़े या उनके बराबर हैं। इस प्रकार हमने आगमन से सिद्ध कर दिया कि यदि व्यंजक a के लिए सत्य है, तो (a + 1) के लिए भी सत्य है। और चूँकि व्यंजक एक के लिए भी सत्य है, इसलिए दिया गया व्यंजक सत्य है।
तीसरा उदाहरण
आइए, यह कथन सिद्ध करें:
शब्दों में: यदि n तीन से विभाज्य है, तो n2 भी तीन से विभाज्य है। यदि n तीन से विभाज्य नहीं है, तो व्यंजक अपने आप सत्य है (सप्रतिबंध कथन की परिभाषा से)। इसलिए हम केवल उन स्थितियों पर विचार करेंगे, जिनमें n तीन से विभाज्य है। इससे हमें प्राकृत संख्याओं का अनुक्रम ai=3, 6, 9, 12, 15… मिलता है। अब से हम इसी अनुक्रम ai में काम करेंगे।
आगमन द्वारा उपपत्ति हम आधार चरण से शुरू करते हैं, अर्थात् यह जाँचते हैं कि कथन पहले अवयव के लिए सत्य है या नहीं। याद रखिए कि हम अनुक्रम ai में काम कर रहे हैं, इसलिए हम इस अनुक्रम का पहला अवयव, अर्थात् अवयव a1, लेते हैं, जो तीन है। तीन के लिए व्यंजक सत्य है:
अब हम आगमन चरण पर आते हैं। हम देखते हैं कि अनुक्रम ai को 3n के रूप में लिखा जा सकता है, जहाँ n एक प्राकृत संख्या है। अर्थात् दूसरा अवयव पिछले से तीन अधिक है, आदि। अब मान लीजिए कि व्यंजक n के लिए सत्य है, और हमें सुनिश्चित करना है कि वह (n + 3) के लिए भी सत्य हो, क्योंकि यही वह नियम है, जो उस अनुक्रम का अगला अवयव देता है, जिसमें हम काम कर रहे हैं। पहले हम परिकल्पना लिखते हैं:
और फिर वह, जो हम सिद्ध करना चाहते हैं:
दूसरी ओर के कोष्ठक को सूत्र से खोलते हैं:
और हम लगभग लक्ष्य तक पहुँच गए। बाईं ओर ऐसा व्यंजक है, जो निश्चित रूप से तीन से विभाज्य है, क्योंकि परिकल्पना के अनुसार n तीन से विभाज्य है (हम केवल अनुक्रम ai की संख्याओं में काम कर रहे हैं) और तीन भी तीन से विभाज्य है। दाईं ओर पहले n2 है, जो परिकल्पना के अनुसार तीन से विभाज्य है। हम जानते हैं कि n तीन से विभाज्य है, और परिकल्पना कहती है कि यदि n तीन से विभाज्य है, तो n2 भी तीन से विभाज्य है:
इसके बाद व्यंजक 6n आता है, जो स्पष्ट रूप से तीन से विभाज्य है। इसे आप भिन्न को सरल करने की तरह सोच सकते हैं:
चर n कोई प्राकृत संख्या है, इसलिए गुणनफल 2n भी प्राकृत संख्या होगा। अर्थात् तीन से भाग देने पर हमें प्राकृत संख्या मिली, इसलिए व्यंजक 6n तीन से विभाज्य होना चाहिए। और अंत में नौ भी तीन से विभाज्य है। व्यंजक पहले अवयव के लिए भी सत्य है और आगमन चरण में भी, अतः वह सत्य है।
व्यंजक में कोष्ठकों की संख्या
अंतिम उदाहरण थोड़ा असामान्य होगा। हम यह कथन सिद्ध करने का प्रयास करेंगे कि किसी सरल व्यंजक में कोष्ठकों की संख्या हमेशा सम होती है। इससे आप देखेंगे कि गणितीय आगमन का प्रयोग केवल प्राकृत संख्याओं में ही नहीं, बल्कि बिल्कुल अलग संदर्भ में भी किया जा सकता है। शुरुआत में हमें परिभाषित करना होगा कि सरल व्यंजक क्या है। सरल व्यंजक है:
- कोई प्राकृत संख्या,
- यदि p एक सरल व्यंजक है, तो (p2) भी एक सरल व्यंजक है,
- यदि p और q सरल व्यंजक हैं, तो (p + q) भी एक सरल व्यंजक है।
अतः ये सरल व्यंजक हैं: 12, 54, (5 + 6), (12 + 7), (62), ((5 + 6)2)। और इसके विपरीत, ये सरल व्यंजक नहीं हैं:
- 1 + 2 → बाहरी कोष्ठक नहीं हैं,
- (1 + 2 → दायाँ कोष्ठक नहीं है,
- 132 → बाहरी कोष्ठक नहीं हैं,
- (1 + 2 + 3) → कोष्ठक कम हैं, सही लेखन (1 + (2 + 3)) होना चाहिए
कोई सरल व्यंजक, उदाहरण के लिए, इस तरह बन सकता है। शुरुआत में हम सरल व्यंजक (a + b) चुनते हैं। अब a के स्थान पर सरल व्यंजक a = (c + d) रखते हैं, जिससे हमें ((c + d) + b) मिलता है, और b के स्थान पर तीन रखते हैं: ((c + d) + 3)। c के स्थान पर दस रखते हैं: ((10 + d) + 3) और अंत में d के स्थान पर (52) रखते हैं: ((10 + (52)) + 3)। कोष्ठकों का ध्यान रखना महत्वपूर्ण है, वरना यह काम नहीं करेगा।
अब हम सिद्ध करेंगे कि सरल व्यंजक में कोष्ठकों की संख्या सम होती है (शून्य भी सम संख्या है)।
आधार चरण में हम कोई पहला अवयव चुनते हैं। इस स्थिति में पहला अवयव सबसे सरल व्यंजक होगा, जो कोई भी प्राकृत संख्या है। अतः हम रखते हैं
व्यंजक j में कोष्ठकों की संख्या शून्य है, अतः पहला अवयव शर्त पूरी करता है। आगमन चरण में हम मानेंगे कि हमारे पास दो सरल व्यंजक p और q हैं और दोनों में कोष्ठकों की संख्या सम है। तब हमें सिद्ध करना है कि सरल व्यंजकों (p + q) और (p2) में भी कोष्ठकों की संख्या सम है।
पहले योग। आइए, एक फलन z(q) भी परिभाषित करें, जो व्यंजक q में कोष्ठकों की संख्या देता है। तब व्यंजक (p + q) में z(p) + z(q) + 2 कोष्ठक हैं। अर्थात् इसमें व्यंजकों p और q के कोष्ठकों के योग से दो कोष्ठक अधिक हैं। परिकल्पना के अनुसार z(p) और z(q) दोनों सम हैं, अतः यदि हम तीन सम संख्याओं को जोड़ें, तो फिर से सम संख्या मिलती है। इस स्थिति के लिए कथन सत्य है।
अब घात। फिर से परिकल्पना है कि सरल व्यंजक p में कोष्ठकों की संख्या सम है। तब व्यंजक (p2) में z(p) + 2 कोष्ठक हैं, अर्थात् फिर से व्यंजक p से दो कोष्ठक अधिक। इस स्थिति में भी हम सम संख्याएँ जोड़ रहे हैं, इसलिए परिणाम सम है।
कथन पहले अवयव के लिए सत्य है और आगमन चरण में भी सत्य है, इसलिए कथन सत्य है।
विषय-सूची: उपपत्ति क्या है, विरोधाभास द्वारा उपपत्ति, गणितीय आगमन का सिद्धांत