Skip to content

प्राकृतिक संख्याओं पर इंडक्शन ​

यह खंड पूरा करने के बाद, आप "सभी प्राकृतिक संख्याओं n के लिए सत्य" वाले प्रस्ताव सिद्ध कर सकेंगे। पहले खंड में वह sumTo_formula जो समझ नहीं आया था, इस खंड के अंत तक आप खुद पढ़कर समझ जाएँगे।

सीखने के बाद आप क्या कर सकेंगे ​

  • इंडक्शन प्रमाण के दो भागों को बताना
  • इंडक्शन परिकल्पना ih क्या है और कहाँ उपयोग हो सकती है, इसे पढ़कर समझना
  • induction n with से पूरा इंडक्शन प्रमाण लिखना

इंडक्शन की ज़रूरत क्यों है ​

पिछले खंड का decide केवल ठोस संख्याएँ ही निकाल सकता है। "सभी n के लिए" के अनंत केस होते हैं, जिन्हें पूरा नहीं किया जा सकता।

इंडक्शन का तरीका केवल दो बातें सिद्ध करना है:

  1. n 0 होने पर सत्य है।
  2. अगर k के लिए सत्य है, तो k + 1 के लिए भी सत्य है।

इन दो बातों से, 0 सत्य होता है, तो 1 सत्य होता है, तो 2 सत्य होता है, और ऐसे चलता रहता है, हर प्राकृतिक संख्या की बारी आती है। जैसे डोमिनो की एक कतार गिराना: पहली टिक गिरती है, और हर टिक अगली को गिरा सकती है।

Lean में, ये दो बातें दो शाखाओं से मेल खाती हैं:

text
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 से नहीं। आज़माकर देखें तो पता चलेगा:

lean
example (n : Nat) : 0 + n = n := by
  rfl
text
is not definitionally equal to the right-hand side

इसलिए इंडक्शन लगाना होगा। आप एक बार करके देखें, दूसरी शाखा में ih कैसा दिखता है इस पर ध्यान दें:

खुद प्रमाण लिखेंपहला इंडक्शन प्रमाण: 0 + n = nस्थिति और एरर Lean द्वारा 4.35.0 जनरेट
theorem zero_add' (n : Nat) : 0 + n = n := by
  induction n with
  | zero =>
    rfl
  | succ k ih =>
    rw [Nat.add_succ]
  rw [ih]

कोड में लिखें तो:

lean
theorem zero_add' (n : Nat) : 0 + n = n := by
  induction n with
  | zero =>
    rfl
  | succ k ih =>
    rw [Nat.add_succ]
    rw [ih]

इसमें एक तैयार प्रमेय का उपयोग हुआ है, देखें यह क्या कहता है:

lean
#check @Nat.add_succ
text
Nat.add_succ : ∀ (n m : Nat), n + m.succ = (n + m).succ

m.succ यानी m + 1। यह प्रमेय कहता है: n + (m + 1) बराबर है (n + m) + 1। इससे रीराइट करने पर, लक्ष्य में 0 + k आ जाता है, जो ठीक ih का बायाँ पक्ष है, इसलिए ih से एक बार और रीराइट किया जा सकता है।

इंडक्शन प्रमाण का तरीका यही है: k + 1 वाले केस को ऐसे रूप में लाना जिसमें k वाला केस दिखे, और फिर इंडक्शन परिकल्पना का उपयोग करना।

  • मैंने अभ्यास में zero_add' का प्रमाण पूरा किया
  • मैं बता सकता हूँ कि इस प्रमाण में ih का अर्थ क्या है: 0 + k = k

जोड़ के सूत्र पर लौटें ​

पहले अनुभाग के फलन और प्रमेय:

lean
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 आपके दिए हुए नाम हैं।

अगला अनुभाग ​

आगमन केवल संख्याओं पर नहीं लागू होता।अगला अनुभाग सूचियों पर आगमन करता है, और पहली बार ऐसी स्थिति आती है जब "प्रमाण आगे नहीं बढ़ता, पहले एक सहायक प्रमेय सिद्ध करना होगा"।

gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.