اصل استقراء ریاضی
طبق این اصل داریم:
اگر S مجموعه ای ناتهی باشد آنگاه با دو شرط زیر با مجموعه اعداد طبیعی(N) برابر خواهد بود:
1)یک عضو این مجموعه باشد
2)به ازای تمام اعداد طبیعی n واقع بر مجموعه S ، n+1 نیز عضو آن مجموعه باشد.
از این اصل برای اثبات برخی از فرمولی های ریاضیات در زمینه اعداد گسسته و طبیعی استفاده می شود.
لازم به توضیح است این اصل با پذیرش اصل خوشترتیبی قابل اثبات است.
برهان: برای اثبات از برهان خلف کمک می گیریم. به برهان خلف فرض می کنیم با مفروضات فوق مجموعه S برابر مجموعه اعداد طبیعی نباشد. پس مجموعه ای چون T وجود دارد که S=N-T. حال داریم: مجموعه T زیر مجموعه اعداد طبیعی است و ناتهی است(چرا؟) پس بنا بر اصل خوشترتیبی T دارا عضو مینیمم است چون
واضح است که
و چون
پس داریم:
و چون
برابر مینیمم مجموعه T است پس
و لذا از شرط دوم مجموعه S داریم:
که این تناقض است چون
پس فرض خلف باطل و حکم(اصل اسقرا) برقرار است.
اصل استقرای ریاضی به سه اصل تقسیم می شود:
اصل استقرای معمولی یا ضعیف:
مطابق این اصل اگر (P(n حکمی برای مجموعه ای از اعداد طبیعی باشد، و P برای n=1 درست باشد و از درستی (P(k (فرض استقراء) بتوانیم به درستی (P(k+1 برسیم. در این صورت به این نتیجه می رسیم که که حکم (P(n برای تمام اعدا طبیعی درست است.
اصل استقرای قوی ریاضی:
این اصل بیان میکند اگر S زیر مجموعه ای از اعداد طبیعی باشد به گونه ای که:
1)
2) اگر اعداد طبیعی کوچکتر از n عضو S باشند انگاه بتوان نتیجه گرفت n هم عضوی از S است
می توان گفت مجموعه S همان مجموعه اعداد طبیعی است.
اصل استقرای تعمیم یافته:
پیوست مربوطه:
