إجراء الاستقراء على الأعداد الطبيعية
بعد إنهاء هذا القسم، ستكون قادرًا على إثبات عبارة «صحيحة لكل عدد طبيعي 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، ويمكن استخدام ihih هو «إذا كان صحيحًا لـ k» الوارد في البند 2. إنه فرضية، ومضمونها هو استبدال 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.- فرع
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 فهما اسمان اخترتهما أنت.
القسم التالي
الاستقراء لا يُستخدم على الأعداد فقط. القسم التالي يطبّق الاستقراء على القوائم، وستواجه فيه لأول مرة حالة "تعذّر إكمال البرهان، ويحتاج أولًا إلى برهان مساعد".