प्राकृतिक संख्याओं पर इंडक्शन
यह खंड पूरा करने के बाद, आप "सभी प्राकृतिक संख्याओं n के लिए सत्य" वाले प्रस्ताव सिद्ध कर सकेंगे। पहले खंड में वह sumTo_formula जो समझ नहीं आया था, इस खंड के अंत तक आप खुद पढ़कर समझ जाएँगे।
सीखने के बाद आप क्या कर सकेंगे
- इंडक्शन प्रमाण के दो भागों को बताना
- इंडक्शन परिकल्पना
ihक्या है और कहाँ उपयोग हो सकती है, इसे पढ़कर समझना induction n withसे पूरा इंडक्शन प्रमाण लिखना
इंडक्शन की ज़रूरत क्यों है
पिछले खंड का decide केवल ठोस संख्याएँ ही निकाल सकता है। "सभी n के लिए" के अनंत केस होते हैं, जिन्हें पूरा नहीं किया जा सकता।
इंडक्शन का तरीका केवल दो बातें सिद्ध करना है:
- n 0 होने पर सत्य है।
- अगर k के लिए सत्य है, तो k + 1 के लिए भी सत्य है।
इन दो बातों से, 0 सत्य होता है, तो 1 सत्य होता है, तो 2 सत्य होता है, और ऐसे चलता रहता है, हर प्राकृतिक संख्या की बारी आती है। जैसे डोमिनो की एक कतार गिराना: पहली टिक गिरती है, और हर टिक अगली को गिरा सकती है।
Lean में, ये दो बातें दो शाखाओं से मेल खाती हैं:
induction n with
| zero => n 0 होने का केस सिद्ध करें
| succ k ih => n, k + 1 होने का केस सिद्ध करें, ih का उपयोग किया जा सकता हैih ही दूसरी बात 2 वाला "अगर k के लिए सत्य है" है। यह एक परिकल्पना है, जिसका अर्थ है प्रस्ताव में n की जगह k रख देना।
हाथ लगाकर: 0 + n = n
यह प्रस्ताव सिद्ध करने की ज़रूरत नहीं लगती। लेकिन Lean का जोड़ दूसरी संख्या पर परत दर परत परिभाषित है, n + 0 से n सीधे निकल आता है, 0 + n से नहीं। आज़माकर देखें तो पता चलेगा:
example (n : Nat) : 0 + n = n := by
rflis not definitionally equal to the right-hand sideइसलिए इंडक्शन लगाना होगा। आप एक बार करके देखें, दूसरी शाखा में ih कैसा दिखता है इस पर ध्यान दें:
theorem zero_add' (n : Nat) : 0 + n = n := by
induction n with
| zero =>
rfl
| succ k ih =>
rw [Nat.add_succ]
rw [ih]
कोड में लिखें तो:
theorem zero_add' (n : Nat) : 0 + n = n := by
induction n with
| zero =>
rfl
| succ k ih =>
rw [Nat.add_succ]
rw [ih]इसमें एक तैयार प्रमेय का उपयोग हुआ है, देखें यह क्या कहता है:
#check @Nat.add_succNat.add_succ : ∀ (n m : Nat), n + m.succ = (n + m).succm.succ यानी m + 1। यह प्रमेय कहता है: n + (m + 1) बराबर है (n + m) + 1। इससे रीराइट करने पर, लक्ष्य में 0 + k आ जाता है, जो ठीक ih का बायाँ पक्ष है, इसलिए ih से एक बार और रीराइट किया जा सकता है।
इंडक्शन प्रमाण का तरीका यही है: k + 1 वाले केस को ऐसे रूप में लाना जिसमें k वाला केस दिखे, और फिर इंडक्शन परिकल्पना का उपयोग करना।
- मैंने अभ्यास में
zero_add'का प्रमाण पूरा किया - मैं बता सकता हूँ कि इस प्रमाण में
ihका अर्थ क्या है:0 + k = k
जोड़ के सूत्र पर लौटें
पहले अनुभाग के फलन और प्रमेय:
def sumTo : Nat → Nat
| 0 => 0
| n + 1 => sumTo n + (n + 1)
theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1) := by
induction n with
| zero =>
rfl
| succ k ih =>
simp [sumTo]
rw [Nat.mul_add, ih]
simp [Nat.mul_add, Nat.add_mul]
omegaअब पढ़ सकते हैं:
induction n with: n पर आगमन (induction)।zeroशाखा: n यह है 0, दोनों ओर से गणना करने पर 0 आता है,rfl।succ k ihशाखा:ihयह है2 * sumTo k = k * (k + 1)।simp [sumTo]: परिभाषा के अनुसारsumTo (k + 1)कोsumTo k + (k + 1)में विस्तारित करें।rw [Nat.mul_add, ih]: 2 को कोष्ठकों में गुणा करें,2 * sumTo kप्रकट होता है, इसेihसे बदलें।- अंतिम दो पंक्तियाँ: बचा हुआ भाग शुद्ध अंकगणित है, गुणा विस्तारित करें और
omegaको सौंप दें।
तरीका वही है: परिभाषा विस्तारित करें, k वाला मामला सामने आने दें, ih का उपयोग करें, बाकी स्वचालित रणनीति को सौंप दें।
- मैं
sumTo_formulaमें बता सकता हूँ कि किस चरण में आगमन परिकल्पना का उपयोग हुआ
आपकी परीक्षाsucc k ih ब्रांच में, इंडक्शन परिकल्पना ih क्या कहती है?
जाँच बिंदु
- मैं आगमन प्रमाण के दो भाग बता सकता हूँ: 0 का मामला, k से k + 1 तक
- मैं
induction n with | zero => … | succ k ih => …की संरचना लिख सकता हूँ - मुझे पता है कि
ihएक धारणा है, लक्ष्य नहीं - मैं समझ गया हूँ कि
sumTo_formulaकी हर पंक्ति क्या कर रही है
सफल नहीं हुए?
succ शाखा में पता नहीं कि अगला कदम क्या है। देखें कि लक्ष्य में ih का बायाँ पक्ष दिखता है या नहीं। नहीं दिखे, तो पहले परिभाषा विस्तारित करें या पुनर्लेखन करें, जब तक कि वह दिखे।
शाखा का नाम गलत लिखा। प्राकृतिक संख्याओं की दो शाखाओं के नाम निश्चित रूप से zero और succ हैं।k और ih आपके दिए हुए नाम हैं।
अगला अनुभाग
आगमन केवल संख्याओं पर नहीं लागू होता।अगला अनुभाग सूचियों पर आगमन करता है, और पहली बार ऐसी स्थिति आती है जब "प्रमाण आगे नहीं बढ़ता, पहले एक सहायक प्रमेय सिद्ध करना होगा"।