الاستقراء الرياضي

الاستقراء الرياضي هو أسلوب لإثبات صحة عبارة ما $P(n)$ ينطبق هذا على كل عدد طبيعي $n$ أي أن الحالات التي لا حصر لها $P(0),P(1),P(2),P(3),\dots$ جميعها صحيحة. يتم ذلك بإثبات حالة بسيطة أولاً، ثم إظهار أنه إذا افترضنا صحة الادعاء في حالة معينة، فإن الحالة التالية تكون صحيحة أيضاً. تساعد الاستعارات غير الرسمية في شرح هذه التقنية، مثل أحجار الدومينو المتساقطة أو تسلق السلم.

يثبت الاستقراء الرياضي أنه يمكننا الصعود إلى أعلى ما نريد على السلم، من خلال إثبات أنه يمكننا الصعود إلى الدرجة السفلية ( الأساس ) وأنه من كل درجة يمكننا الصعود إلى الدرجة التالية (الخطوة ) .

— الرياضيات الملموسة ، هوامش الصفحة 3.

يتكون البرهان بالاستقراء من حالتين. الأولى، وهي الحالة الأساسية ، تثبت العبارة لـ $n=0$ دون افتراض أي معرفة بحالات أخرى. الحالة الثانية، وهي خطوة الاستقراء ، تثبت أنه إذا كانت العبارة صحيحة لأي حالة معينة $n=k$ إذاً ، يجب أن ينطبق ذلك أيضاً على الحالة التالية. $n=k+1$ تثبت هاتان الخطوتان أن العبارة صحيحة لكل عدد طبيعي $n$ لا تبدأ الحالة الأساسية بالضرورة بـ $n=0$ ولكن غالباً مع $n=1$ وربما مع أي عدد طبيعي ثابت $n=N$ ، مما يثبت صحة العبارة لجميع الأعداد الطبيعية $n\geq N$ .

يمكن توسيع نطاق هذه الطريقة لإثبات عبارات تتعلق ببنى أكثر عمومية ذات أساس متين ، مثل الأشجار ؛ هذا التعميم، المعروف بالاستقراء البنيوي ، يُستخدم في المنطق الرياضي وعلوم الحاسوب . يرتبط الاستقراء الرياضي بهذا المعنى الموسع ارتباطًا وثيقًا بالاستدعاء الذاتي . يُعد الاستقراء الرياضي قاعدة استدلال تُستخدم في البراهين الرسمية ، وهو أساس معظم براهين صحة برامج الحاسوب. ^{[ 3 ]}

على الرغم من اسمها، يختلف الاستقراء الرياضي اختلافًا جوهريًا عن الاستدلال الاستقرائي المستخدم في الفلسفة ، حيث يؤدي فحص العديد من الحالات إلى استنتاج محتمل. يفحص المنهج الرياضي عددًا لا نهائيًا من الحالات لإثبات عبارة عامة، ولكنه يفعل ذلك من خلال سلسلة محدودة من الاستدلال الاستنتاجي تتضمن المتغير. $n$ والتي يمكن أن تأخذ قيمًا لا نهائية. والنتيجة هي برهان دقيق للعبارة، وليس تأكيدًا على احتماليتها. ^{[ 4 ]}

تاريخ

بحسب ديفيد إي. جويس ، لا يوجد دليل على استخدام مبدأ الاستقراء الرياضي في كتابات إقليدس . ^{[ 5 ]} ويجادل فابيو أسيربي في عام 2000 بأن محاورة بارمنيدس لأفلاطون (حوالي 370 قبل الميلاد) تحتوي على آثار برهان استقرائي ضمني مبكر. ^{[ 6 ]} وقد طعن نيغريبونتيس وفارماكي في هذا التفسير عام 2021، حيث ذكرا كذلك أن لا أفلاطون ولا أي من الفيثاغوريين الآخرين استخدموا مبدأ الاستقراء الرياضي. ^{[ 7 ]}

أُلف أقدم برهان ضمني بالاستقراء الرياضي على يد الكرجي حوالي عام ١٠٠٠ ميلادي، حيث طبقه على المتتابعات الحسابية لإثبات نظرية ذات الحدين وخصائص مثلث باسكال . ورغم ضياع العمل الأصلي، فقد أشار إليه السامول المغربي لاحقًا في رسالته "الباهر في الجبر" حوالي عام ١١٥٠ ميلادي. ^{[ ٨ ]}^{[ ٩ ]}^{[ ١٠ ]}

يقول كاتز في تاريخه للرياضيات

من الأفكار المهمة الأخرى التي طرحها الكرجي، وتابعها السماول وآخرون، فكرة الاستدلال الاستقرائي للتعامل مع بعض المتتابعات الحسابية. وهكذا، استخدم الكرجي هذا الاستدلال لإثبات نتيجة مجاميع المكعبات الصحيحة التي كان أريابهاتا يعرفها مسبقًا. [...] مع ذلك، لم يذكر الكرجي نتيجة عامة لأي عدد صحيح n ، بل ذكر نظريته للعدد الصحيح 10 تحديدًا. [...] ومع ذلك، فقد صُمم برهانه بوضوح ليكون قابلًا للتعميم على أي عدد صحيح آخر. [...] يتضمن استدلال الكرجي في جوهره المكونين الأساسيين للاستدلال الاستقرائي الحديث، وهما صحة العبارة عندما n = 1 (1 = ^1/3 )، واستنتاج صحتها عندما n = k من صحتها عندما n = k - 1. بالطبع، هذا المكون الثاني ليس صريحًا، لأن استدلال الكرجي، بمعنى ما، معكوس؛ أي أنه يبدأ من n = 10 وينزل إلى 1 بدلًا من الصعود. ومع ذلك، فإن حجته في الفخري هي أقدم برهان موجود لصيغة المجموع للمكعبات الصحيحة . ^{[ 11 ]}

في الهند، ظهرت البراهين الضمنية المبكرة عن طريق الاستقراء الرياضي في " الطريقة الدورية " لبهاسكارا . ^[¹²^]

مع ذلك، لم يذكر أي من هؤلاء الرياضيين القدماء فرضية الاستقراء صراحةً. وثمة حالة أخرى مشابهة (على عكس ما كتبه فاكا، كما أوضح فرويدنتال بدقة) ^{[ 13 ]} وهي حالة فرانشيسكو ماوروليكو في كتابه "Arithmeticorum libri duo " (1575)، الذي استخدم هذه التقنية لإثبات أن مجموع أول $n$ عدد فردي هو $n²$ $.$

كان جيرسونيدس (1288-1344) أول من استخدم الاستقراء استخدامًا دقيقًا . ^[¹⁴^]^[¹⁵^] وقدّم باسكال أول صياغة صريحة لمبدأ الاستقراء في كتابه "رسالة في المثلث الحسابي" (1665). كما استخدم عالم فرنسي آخر، هو فيرما ، مبدأً مشابهًا على نطاق واسع: البرهان غير المباشر بالتسلسل اللانهائي .

استخدم السويسري جاكوب برنولي فرضية الاستقراء ، ومنذ ذلك الحين أصبحت معروفة على نطاق واسع. ولم يظهر المعالجة الرسمية الحديثة لهذا المبدأ إلا في القرن التاسع عشر، على يد جورج بول ، ^{[ 16 ]} وأوغسطس دي مورغان ، وتشارلز ساندرز بيرس ، ^{[ 17 ]}^{[ 18 ]} وجوزيبي بيانو ، وريتشارد ديديكيند . ^{[ 12 ]}

وصف

أبسط أشكال الاستقراء الرياضي وأكثرها شيوعًا هو الاستدلال على أن العبارة التي تتضمن عددًا طبيعيًا $n$ (أي عدد صحيح $n \geq 0$ أو 1) صحيحة لجميع قيم $n$ . ويتكون البرهان من خطوتين:

الالحالة الأساسية (أوالحالة الأولية): أثبت أن العبارة صحيحة بالنسبة لـ 0 أو 1.
الخطوة الاستقراء (أوخطوة الاستقراء، أوحالة الخطوة): أثبت أنه لكل $n$ ، إذا كانت العبارة صحيحة لـ $n$ ، فإنها صحيحة لـ $n + 1.$ بعبارة أخرى، افترض أن العبارة صحيحة لعدد طبيعي $n$ ، وأثبت أن العبارة صحيحة لـ $n + 1$ .

تُسمى الفرضية في خطوة الاستقراء، والتي تنص على صحة العبارة لقيمة معينة لـ $n$ ، بفرضية الاستقراء . ولإثبات صحة هذه الفرضية، يُفترض صحة فرضية الاستقراء لـ $n$ ، ثم يُستخدم هذا الافتراض لإثبات صحة العبارة لـ $n$ $+$ $1$ .

المؤلفون الذين يفضلون تعريف الأعداد الطبيعية بحيث تبدأ من 0 يستخدمون تلك القيمة في الحالة الأساسية؛ أما أولئك الذين يعرفون الأعداد الطبيعية بحيث تبدأ من 1 فيستخدمون تلك القيمة.

أمثلة

مجموع الأعداد الطبيعية المتتالية

يمكن استخدام الاستقراء الرياضي لإثبات العبارة التالية لجميع الأعداد الطبيعية $n\geq 0$ : $P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.$

هذا يوضح صيغة عامة لمجموع الأعداد الطبيعية الأقل من أو تساوي عددًا معينًا؛ في الواقع، سلسلة لا نهائية من العبارات: $0={\tfrac {(0)(0+1)}{2}}$ ، $0+1={\tfrac {(1)(1+1)}{2}}$ ، $0+1+2={\tfrac {(2)(2+1)}{2}}$ ، إلخ.

اقتراح. لكل $n\in \mathbb {N}$ لدينا ذلك $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$

برهان. دع $P(n)$ كن البيان $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$ نقدم برهانًا بالاستقراء على $n$ .

الحالة الأساسية: أثبت أن العبارة صحيحة لأصغر عدد طبيعي $n = 0$ .

$P(0)$ هذا صحيح بشكل واضح: $0={\tfrac {0(0+1)}{2}}\,.$

خطوة الاستقراء: أثبت أنه لكل $k\geq 0$ ، لو $P(k)$ ثم يمسك $P(k+1)$ ينطبق أيضاً.

افترض فرضية الاستقراء التي تنص على أنه بالنسبة لـ $k$ الحالة الوحيدة $n=k$ يحمل، بمعنى $P(k)$ صحيح: $0+1+\cdots +k={\frac {k(k+1)}{2}}.$ وبناءً على ذلك: $(0+1+2+\cdots +k)+(k+1)={\frac {k(k+1)}{2}}+(k+1).$

جبريًا ، يتبسط الطرف الأيمن على النحو التالي: ${\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}.\end{aligned}}$

وبمساواة الجانبين الأيسر والأيمن، نستنتج ما يلي: $0+1+2+\cdots +k+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.$ أي البيان $P(k+1)$ وينطبق هذا أيضاً، مما يؤكد خطوة الاستقراء.

الخلاصة: بما أن كلاً من الحالة الأساسية وخطوة الاستقراء قد ثبتت صحتهما، فإن العبارة تُثبت بالاستقراء الرياضي $P(n)$ ينطبق هذا على كل عدد طبيعي $n\geq 0$ . QED

متباينة مثلثية

يُستخدم الاستقراء غالبًا لإثبات المتباينات . على سبيل المثال، نُثبت أن $\left|\sin nx\right|\leq n\left|\sin x\right|$ لأي عدد حقيقي $x$ والعدد الطبيعي $n$ .

للوهلة الأولى، قد يبدو أن هناك نسخة أكثر عمومية، $\left|\sin nx\right|\leq n\left|\sin x\right|$ لأي أعداد حقيقية $n,x$ يمكن إثبات ذلك دون استخدام الاستقراء؛ ولكن في هذه الحالة ${\textstyle n={\frac {1}{2}},\,x=\pi }$ يُظهر ذلك أنه قد يكون خاطئًا بالنسبة للقيم غير الصحيحة لـ $n$ وهذا يشير إلى أننا يجب أن نفحص البيان تحديداً بحثاً عن القيم الطبيعية لـ $n$ والحث هو الأداة الأنسب.

اقتراح. لأي $x\in \mathbb {R}$ و $n\in \mathbb {N}$ ، $\left|\sin nx\right|\leq n\left|\sin x\right|$ .

البرهان. لنفترض عددًا حقيقيًا عشوائيًا $x$ ودع $P(n)$ كن البيان $\left|\sin nx\right|\leq n\left|\sin x\right|$ . نقوم بالتعريف على $n$ .

الحالة الأساسية: الحساب $\left|\sin 0x\right|=0\leq 0=0\left|\sin x\right|$ التحقق $P(0)$ .

خطوة الاستقراء: نبين الاستلزام $P(k)\implies P(k+1)$ لأي عدد طبيعي $k$ لنفترض فرضية الاستقراء: لقيمة معينة $n=k\geq 0$ الحالة الوحيدة $P(k)$ صحيح. باستخدام صيغة جمع الزوايا ومتباينة المثلث ، نستنتج ما يلي: ${\begin{aligned}\left|\sin(k+1)x\right|&=\left|\sin kx\cos x+\sin x\cos kx\right|&&{\text{(angle addition)}}\\&\leq \left|\sin kx\cos x\right|+\left|\sin x\,\cos kx\right|&&{\text{(triangle inequality)}}\\&=\left|\sin kx\right|\left|\cos x\right|+\left|\sin x\right|\left|\cos kx\right|\\&\leq \left|\sin kx\right|+\left|\sin x\right|&&(\left|\cos t\right|\leq 1)\\&\leq k\left|\sin x\right|+\left|\sin x\right|&&{\text{(induction hypothesis}})\\&=(k+1)\left|\sin x\right|.\end{aligned}}$

يُظهر التفاوت بين الكميتين القصوى في الطرف الأيسر والطرف الأيمن أن $P(k+1)$ وهذا صحيح، مما يكمل خطوة الاستقراء.

الخلاصة: الاقتراح $P(n)$ ينطبق هذا على جميع الأعداد الطبيعية $n.$ QED

المتغيرات

عمليًا، غالبًا ما تُصاغ البراهين بالاستقراء بشكل مختلف، اعتمادًا على الطبيعة الدقيقة للخاصية المراد إثباتها. جميع أنواع الاستقراء هي حالات خاصة من الاستقراء المتسامي ؛ انظر أدناه .

الحالة الأساسية بخلاف 0 أو 1

إذا رغب المرء في إثبات عبارة، ليس لجميع الأعداد الطبيعية، ولكن فقط لجميع الأعداد $n$ الأكبر من أو تساوي عددًا معينًا $b$ ، فإن البرهان بالاستقراء يتكون مما يلي:

إثبات أن العبارة صحيحة عندما $n = b$ .
بإثبات أنه إذا كانت العبارة صحيحة لأي عدد $n \geq b$ ، فإن العبارة نفسها تنطبق أيضًا على $n + 1$ .

يمكن استخدام هذا، على سبيل المثال، لإظهار أن $2 ن \geq ن + 5$ لـ $ن \geq 3$ .

بهذه الطريقة، يمكن إثبات صحة العبارة $P (n)$ لجميع $قيم n \geq 1$ ، أو حتى لجميع $قيم n \geq -5$ . يُعد هذا الشكل من الاستقراء الرياضي حالة خاصة من الشكل السابق، لأنه إذا كانت العبارة المراد إثباتها هي $P (n)،$ فإن إثباتها باستخدام هاتين القاعدتين يُكافئ إثبات $P (n + b)$ لجميع الأعداد الطبيعية $n$ مع حالة أساسية للاستقراء تساوي $صفرًا$ . ^{[ 19 ]}

مثال: تكوين مبالغ الدولار باستخدام العملات المعدنية

لنفترض وجود كمية غير محدودة من العملات المعدنية من فئتي 4 و5 دولارات. يمكن استخدام الاستقراء الرياضي لإثبات أن أي مبلغ صحيح من الدولارات أكبر من أو يساوي $12$ دولارًا يمكن تكوينه من خلال مجموعة من هذه العملات. لنرمز بـ $S (k)$ إلى العبارة " يمكن تكوين $k$ دولارًا من خلال مجموعة من العملات المعدنية من فئتي 4 و5 دولارات". يمكن إثبات صحة $S (k)$ لجميع $قيم k \geq 12$ بالاستقراء الرياضي على $k$ كما يلي:

الحالة الأساسية: إثبات أن $S (k)$ صحيح لـ $k = 12$ أمر بسيط: خذ ثلاث عملات معدنية من فئة 4 دولارات.

خطوة الاستقراء: بافتراض صحة $S (k)$ لقيمة معينة لـ $k \geq 12$ ( فرضية الاستقراء )، أثبت صحة $S (k + 1)$ أيضًا. لنفترض أن $S (k)$ صحيحة لقيمة معينة $لـ k \geq 12.$ إذا وُجد حل لـ $k$ دولارًا يتضمن على الأقل عملة واحدة من فئة 4 دولارات، استبدلها بعملة من فئة 5 دولارات لتحصل على $k + 1$ دولارًا. وإلا، إذا استُخدمت عملات من فئة 5 دولارات فقط، فيجب أن يكون $k$ من مضاعفات 5، أي 15 على الأقل؛ ولكن حينها يمكننا استبدال ثلاث عملات من فئة 5 دولارات بأربع عملات من فئة 4 دولارات لتحصل على $k + 1$ دولارًا. في كلتا الحالتين، تكون $S (k + 1)$ صحيحة.

لذلك، وبموجب مبدأ الاستقراء، فإن $S (k)$ ينطبق على جميع $k \geq 12$ ، وبذلك يكتمل البرهان.

في هذا المثال، على الرغم من أن $S (k)$ ينطبق أيضًا على ${\textstyle k\in \{4,5,8,9,10\}}$ لا يمكن تعديل البرهان أعلاه لاستبدال الحد الأدنى البالغ $12$ دولارًا بأي قيمة أقل $m$ . فعندما تكون $m = 11$ ، تكون الحالة الأساسية خاطئة؛ وعندما تكون $m = 10$ ، لن تنجح الحالة الثانية في خطوة الاستقراء (استبدال ثلاث عملات معدنية من فئة 5 دولارات بأربع عملات معدنية من فئة 4 دولارات)؛ ناهيك عن قيم $m$ الأقل .

الحث على أكثر من طاولة

قد يكون من المستحسن أحيانًا إثبات عبارة تتضمن عددين طبيعيين، $ن$ و $م$ ، بتكرار عملية الاستقراء. أي، يتم إثبات حالة أساسية وخطوة استقراء للعدد $ن$ ، وفي كل حالة من هاتين الحالتين يتم إثبات حالة أساسية وخطوة استقراء للعدد $م$ . انظر، على سبيل المثال، برهان التبديلية المصاحب لجمع الأعداد الطبيعية . كما يمكن استخدام حجج أكثر تعقيدًا تتضمن ثلاثة عدادات أو أكثر.

هبوط لا نهائي

طريقة التناقص اللانهائي هي شكل من أشكال الاستقراء الرياضي استخدمها بيير دي فيرما . تُستخدم هذه الطريقة لإثبات أن عبارة $Q (n)$ خاطئة لجميع الأعداد الطبيعية $n$ . وتتمثل صيغتها التقليدية في إثبات أنه إذا كانت $Q (n)$ صحيحة لعدد طبيعي $n$ ، فإنها صحيحة أيضًا لعدد طبيعي أصغر منها $m$ . ولأنه لا توجد متتابعات تناقصية لانهائية من الأعداد الطبيعية، فإن هذا الوضع مستحيل، مما يُثبت ( بالتناقض ) أن $Q (n)$ لا يمكن أن تكون صحيحة لأي قيمة لـ $n$ .

يمكن التحقق من صحة هذه الطريقة من خلال مبدأ الاستقراء الرياضي المعتاد. باستخدام الاستقراء الرياضي على العبارة $P (n)$ المعرفة على أنها " $Q (m)$ خاطئة لجميع الأعداد الطبيعية $m$ الأقل من أو تساوي $n$ "، يتبين أن $P (n)$ صحيحة لجميع $قيم n$ ، مما يعني أن $Q (n)$ خاطئة لكل عدد طبيعي $n$ .

الاستقراء الرياضي المحدود

إذا أراد المرء إثبات أن الخاصية $P$ تنطبق على جميع الأعداد الطبيعية الأقل من أو تساوي $N$ ثابتة ، فإن إثبات أن $P$ تحقق الشروط التالية يكفي: ^{[ 20 ]}

$ينطبق الشرط P$ على الصفر،
لأي عدد طبيعي $x$ أقل من $N$ ، إذا تحققت $P$ لـ $x$ ، فإن $P$ تتحقق لـ $x + 1$

الاستقراء بالبادئة

يتطلب الشكل الأكثر شيوعًا للإثبات بالاستقراء الرياضي إثبات في خطوة الاستقراء أن $\forall k\,(P(k)\to P(k+1))$

وبناءً على ذلك، فإن مبدأ الاستقراء "يُسهّل" $تطبيق$ هذه الخطوة في الانتقال من $P (0)$ إلى $P (n)$ . ويمكن تسمية هذا "استقراء السلف" لأن كل خطوة تثبت شيئًا ما عن عدد ما انطلاقًا من شيء ما عن سلفه.

أحد المتغيرات المهمة في مجال التعقيد الحسابي هو "الاستقراء البادئ"، حيث يتم إثبات العبارة التالية في خطوة الاستقراء: $\forall k\,(P(k)\to P(2k)\land P(2k+1))$ أو ما يعادل ذلك $\forall k\,\left(P\!\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)$

ثم يقوم مبدأ الاستقراء بأتمتة عدد من تطبيقات هذا الاستدلال يبلغ لوغاريتم ₂ ن، وذلك للانتقال من $P$ $(0)$ إلى $P$ $($ $n$ $)$ . في الواقع، يُطلق عليه اسم "استقراء البادئة" لأن كل خطوة تثبت شيئًا ما عن عدد ما انطلاقًا من شيء ما عن "بادئة" ذلك العدد - والتي تتشكل عن طريق اقتطاع البت الأدنى من تمثيله الثنائي . ويمكن أيضًا اعتباره تطبيقًا للاستقراء التقليدي على طول ذلك التمثيل الثنائي.

إذا فُسِّر الاستقراء التقليدي القائم على السلف حسابيًا على أنه حلقة $من n$ خطوة، فإن الاستقراء القائم على البادئة يُقابل حلقة من log $-n$ خطوة. ولهذا السبب، فإن البراهين التي تستخدم الاستقراء القائم على البادئة "أكثر جدوى من الناحية البنائية" من البراهين التي تستخدم الاستقراء القائم على السلف.

يمكن لتقنية الاستقراء السابق محاكاة الاستقراء السابق بشكل بديهي على نفس العبارة. ويمكن للاستقراء السابق محاكاة الاستقراء السابق، ولكن على حساب زيادة تعقيد العبارة نحويًا (بإضافة مُكمِّم شامل محدود )، لذا فإن النتائج المهمة التي تربط الاستقراء السابق بالحسابات متعددة الحدود تعتمد على استبعاد المُكمِّمات غير المحدودة تمامًا، والحد من التناوب المسموح به بين المُكمِّمات الشاملة والوجودية المحدودة في العبارة. ^[²¹^]

يمكن للمرء أن يذهب بالفكرة خطوة أبعد: يجب على المرء أن يثبت $\forall k\,\left(P\!\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)$ وبناءً على ذلك، فإن مبدأ الاستقراء "يُؤتمت" تطبيقات هذا الاستدلال من $لوغاريتم لوغاريتم ن في الانتقال من$ $P (0)$ إلى $P (n)$ . وقد استُخدم هذا الشكل من الاستقراء، على نحو مماثل، لدراسة الحوسبة المتوازية ذات الزمن اللوغاريتمي.

تحريض كامل (قوي)

هناك نوع آخر يُسمى الاستقراء الكامل ، أو استقراء مسار القيم ، أو الاستقراء القوي (على عكس الشكل الأساسي للاستقراء الذي يُعرف أحيانًا بالاستقراء الضعيف )، وهو يجعل خطوة الاستقراء أسهل في الإثبات باستخدام فرضية أقوى: حيث يتم إثبات العبارة $P(m+1)$ بافتراض أن $P(n)$ ينطبق هذا على جميع الأعداد الطبيعية $n$ أقل من $m+1$ على النقيض من ذلك، فإن الشكل الأساسي لا يفترض إلا $P(m)$ إن اسم "الاستقراء القوي" لا يعني أن هذه الطريقة يمكنها إثبات أكثر مما يمكن إثباته "الاستقراء الضعيف"، ولكنه يشير فقط إلى الفرضية الأقوى المستخدمة في خطوة الاستقراء.

في الواقع، يمكن إثبات أن الطريقتين متكافئتان، كما هو موضح أدناه. في هذا النوع من الاستقراء الكامل، لا يزال يتعين إثبات الحالة الأساسية. $P(0)$ بل وقد يكون من الضروري إثبات حالات إضافية مثل $P(1)$ قبل تطبيق الحجة العامة، كما في المثال أدناه لعدد فيبوناتشي $F_{n}$ .

على الرغم من أن الصيغة الموصوفة للتو تتطلب إثبات الحالة الأساسية، إلا أن هذا غير ضروري إذا كان بإمكان المرء إثبات $P(m)$ (بافتراض $P(n)$ لجميع المستويات الأدنى $n$ ) للجميع $m\geq 0$ هذه حالة خاصة من الاستقراء المتسامي كما هو موضح أدناه، على الرغم من أنها لم تعد مكافئة للاستقراء العادي. في هذه الصيغة، تندرج الحالة الأساسية ضمن الحالة $m=0$ ، أين $P(0)$ وقد ثبت ذلك دون غيره $P(n)$ مفترض؛ قد تحتاج هذه الحالة إلى معالجة منفصلة، ولكن في بعض الأحيان ينطبق نفس المنطق على $m=0$ و $m>0$ مما يجعل البرهان أبسط وأكثر أناقة. ومع ذلك، في هذه الطريقة، من الضروري التأكد من أن برهان $P(m)$ لا يفترض ضمنيًا أن $m>0$ على سبيل المثال، بقول "اختر عشوائيًا" $n<m$ أو بافتراض أن مجموعة من $m$ عنصرًا تحتوي على عنصر.

التكافؤ مع الاستقراء العادي

الاستقراء الكامل مكافئ للاستقراء الرياضي العادي كما هو موضح أعلاه، بمعنى أنه يمكن تحويل برهان باستخدام إحدى الطريقتين إلى برهان باستخدام الأخرى. لنفترض وجود برهان لـ $P(n)$ بالاستقراء الكامل. بعد ذلك، يمكن تحويل هذا البرهان إلى برهان استقراء عادي بافتراض فرضية استقرائية أقوى. ليكن $Q(n)$ كن البيان " $P(m)$ ينطبق على الجميع $m$ بحيث $0\leq m\leq n$ "—يصبح هذا الفرض الاستقرائي للاستقراء العادي. يمكننا حينها أن نُبين $Q(0)$ و $Q(n+1)$ ل $n\in \mathbb {N}$ بافتراض فقط $Q(n)$ وأظهر ذلك $Q(n)$ يشير إلى $P(n)$ [ ²²^]

أما إذا، من ناحية أخرى، $P(n)$ إذا تم إثبات ذلك بالاستقراء العادي، فإن الإثبات سيكون في الواقع إثباتاً بالاستقراء الكامل: $P(0)$ وقد تم إثبات ذلك في الحالة الأساسية، دون استخدام أي افتراضات، و $P(n+1)$ يتم إثبات ذلك في خطوة الاستقراء، حيث يمكن للمرء أن يفترض جميع الحالات السابقة ولكنه يحتاج فقط إلى استخدام الحالة $P(n)$ .

مثال: أعداد فيبوناتشي

يُعد الاستقراء الكامل مفيدًا للغاية عندما يتطلب الأمر عدة أمثلة على فرضية الاستقراء لكل خطوة من خطوات الاستقراء. على سبيل المثال، يمكن استخدام الاستقراء الكامل لإثبات أن $F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}$ أين $F_{n}$ هو العدد $النوني$ في متتالية فيبوناتشي ، و ${\textstyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}$ ( النسبة الذهبية ) و ${\textstyle \psi ={\frac {1}{2}}(1-{\sqrt {5}})}$ هي جذور متعددة الحدود $x^{2}-x-1$ باستخدام حقيقة أن $F_{n+2}=F_{n+1}+F_{n}$ لكل $n\in \mathbb {N}$ يمكن التحقق من الهوية المذكورة أعلاه عن طريق الحساب المباشر لـ ${\textstyle F_{n+2}}$ إذا افترضنا أن هذا ينطبق بالفعل على كليهما ${\textstyle F_{n+1}}$ و ${\textstyle F_{n}}$ لإكمال البرهان، يجب التحقق من الهوية في الحالتين الأساسيتين: $n=0$ و ${\textstyle n=1}$ .

مثال: التحليل إلى العوامل الأولية

يستخدم برهان آخر بالاستقراء الكامل فرضية أن العبارة صحيحة لجميع القيم الأصغر $n$ بمزيد من التفصيل، لننظر في العبارة التي تنص على أن "كل عدد طبيعي أكبر من 1 هو حاصل ضرب عدد أولي واحد أو أكثر "، وهو ما يمثل " الوجود " في النظرية الأساسية للحساب . ولإثبات خطوة الاستقراء، فإن فرضية الاستقراء هي أنه بالنسبة لعدد معطى $m>1$ ينطبق هذا البيان على جميع الأحجام الأصغر $n>1$ . لو $m$ إذا كان عدداً أولياً فهو بالتأكيد ناتج ضرب أعداد أولية، وإذا لم يكن كذلك فهو، بحكم التعريف، ناتج ضرب: $m=n_{1}n_{2}$ حيث لا يساوي أي من العاملين 1؛ وبالتالي لا يساوي أي منهما 1. $m$ وبالتالي، كلاهما أكبر من 1 وأصغر من $m$ تنطبق فرضية الاستقراء الآن على $n_{1}$ و $n_{2}$ إذن، كل واحد منها هو ناتج ضرب أعداد أولية. $m$ هو ناتج ضرب الأعداد الأولية، وبالتالي فهو بالتبعية ناتج ضرب الأعداد الأولية نفسه.

مثال: إعادة النظر في المبالغ الدولارية

سنحاول إثبات المثال نفسه المذكور أعلاه ، ولكن هذه المرة باستخدام الاستقراء القوي . وتبقى العبارة كما هي: $S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b$

ومع ذلك، ستكون هناك اختلافات طفيفة في بنية وافتراضات البرهان، بدءًا من الحالة الأساسية الموسعة.

دليل.

الحالة الأساسية: أثبت أن $S(k)$ يحمل لـ $k=12,13,14,15$ . ${\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}$

الحالة الأساسية صحيحة.

خطوة الاستقراء: بالنظر إلى بعض $j>15$ ، يفترض $S(m)$ ينطبق على الجميع $m$ مع $12\leq m<j$ أثبت ذلك $S(j)$ يحجز.

اختيار $m=j-4$ وملاحظة ذلك $15<j\implies 12\leq j-4<j$ يُظهر ذلك أن $S(j-4)$ يثبت ذلك، وفقًا لفرضية الاستقراء. أي أن المجموع $j-4$ يمكن تشكيلها من خلال مزيج من $4$ و $5$ عملات الدولار. ثم، ببساطة إضافة $4$ إضافة عملة الدولار إلى هذا المزيج ينتج عنه المجموع $j$ . إنه، $S(j)$ يثبت. ^{[ 23 ]} وهو المطلوب إثباته

الاستقراء الأمامي والخلفي

أحيانًا، يكون من الأنسب الاستدلال العكسي، مما يثبت صحة العبارة لـ $n-1$ ، بالنظر إلى صلاحيتها لـ $n$ مع ذلك، لا يكفي إثبات صحة العبارة لعدد واحد لتحديد الحالة الأساسية؛ بل يلزم إثباتها لمجموعة جزئية لانهائية من الأعداد الطبيعية. على سبيل المثال، استخدم أوغستين لويس كوشي الاستقراء الأمامي (المنتظم) أولًا لإثبات متباينة الوسطين الحسابي والهندسي لجميع قوى العدد 2 ، ثم استخدم الاستقراء العكسي لإثباتها لجميع الأعداد الطبيعية. ^{[ 24 ]}^{[ 25 ]}

مثال على خطأ في خطوة الاستقراء

يجب إثبات خطوة الاستقراء لجميع قيم $n$ . ولتوضيح ذلك، اقترح جويل إي. كوهين الحجة التالية، والتي تزعم إثبات أن جميع الخيول من نفس اللون عن طريق الاستقراء الرياضي : ^{[ 26 ]}

الحالة الأساسية: في مجموعة تتكون من حصان واحد فقط ، يوجد لون واحد فقط.

خطوة الاستقراء: افترض كفرضية استقراء أنه ضمن أي مجموعة من $n$ الخيول، لا يوجد سوى لون واحد. انظر الآن إلى أي مجموعة من $n+1$ الخيول. رتبها حسب العدد التالي: $1,2,3,\dotsc ,n,n+1$ ضع في اعتبارك المجموعات ${\textstyle \left\{1,2,3,\dotsc ,n\right\}}$ و ${\textstyle \left\{2,3,4,\dotsc ,n+1\right\}}$ كل منها عبارة عن مجموعة من فقط $n$ لذا، يوجد لون واحد فقط ضمن كل مجموعة من الخيول. لكن المجموعتين تتداخلان، لذا يجب أن يكون هناك لون واحد فقط بين جميعها. $n+1$ خيل.

الحالة الأساسية $n=1$ الأمر بديهي، وخطوة الاستقراء صحيحة في جميع الحالات $n>1$ ومع ذلك، فإن الحجة المستخدمة في خطوة الاستقراء غير صحيحة بالنسبة لـ $n+1=2$ لأن العبارة القائلة بأن "المجموعتين تتداخلان" خاطئة بالنسبة لـ ${\textstyle \left\{1\right\}}$ و ${\textstyle \left\{2\right\}}$ .

الإضفاء الطابع الرسمي

في منطق الرتبة الثانية ، يمكن كتابة " بديهية الاستقراء" على النحو التالي: $\forall P\,{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n\,{\bigl (}P(n){\bigr )}{\Bigr )},$ حيث $P (\cdot)$ هو متغير للمسندات التي تتضمن عددًا طبيعيًا واحدًا و $k$ و $n$ هما متغيرات للأعداد الطبيعية .

بمعنى آخر، فإن الحالة الأساسية $P (0)$ وخطوة الاستقراء (أي أن فرضية الاستقراء $P (k)$ تستلزم $P (k + 1)$ ) تستلزمان معًا أن $P (n)$ صحيحة لأي عدد طبيعي $n$ . وتؤكد بديهية الاستقراء صحة استنتاج أن $P (n)$ صحيحة لأي عدد طبيعي $n$ من الحالة الأساسية وخطوة الاستقراء.

يُغطي المُكمِّم الأول في البديهية المسندات بدلاً من الأعداد الفردية. هذا مُكمِّم من الدرجة الثانية، مما يعني أن هذه البديهية مُصاغة في منطق الدرجة الثانية . يتطلب وضع بديهيات الاستقراء الحسابي في منطق الدرجة الأولى مخطط بديهيات يحتوي على بديهية منفصلة لكل مسند مُحتمل. تتضمن مقالة بديهيات بيانو مزيدًا من النقاش حول هذه المسألة.

صاغ بيانو أول بديهية الاستقراء البنيوي للأعداد الطبيعية، واستخدمها لتحديد الأعداد الطبيعية إلى جانب البديهيات الأربع الأخرى التالية:

الصفر عدد طبيعي.
الدالة اللاحقة $s$ لكل عدد طبيعي تعطي عددًا طبيعيًا $(s (x) = x + 1)$ .
الدالة اللاحقة أحادية .
0 ليس ضمن نطاق s $.$

في نظرية المجموعات ZFC من الدرجة الأولى ، لا يُسمح بالتكميم على المسندات، ولكن لا يزال بإمكان المرء التعبير عن الاستقراء عن طريق التكميم على المجموعات: $\forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}$ $يمكن قراءة A$ على أنها مجموعة تمثل قضية، وتحتوي على أعداد طبيعية، تتحقق عندها تلك القضية. هذه ليست بديهية، بل نظرية، نظرًا لأن الأعداد الطبيعية تُعرَّف في لغة نظرية مجموعات ZFC بواسطة بديهيات، على غرار بديهيات بيانو. انظر بناء الأعداد الطبيعية باستخدام بديهية اللانهاية ومخطط بديهيات التحديد .

الاستقراء المتسامي

يمكن تعميم أحد أشكال مبدأ الاستقراء الكامل ليشمل العبارات المتعلقة بعناصر أي مجموعة مؤسسة ، أي مجموعة ذات علاقة غير انعكاسية < لا تحتوي على سلاسل تنازلية لانهائية . كل مجموعة تمثل عددًا ترتيبيًا هي مجموعة مؤسسة، ومجموعة الأعداد الطبيعية إحداها.

عند تطبيق الاستقراء المتسامي على مجموعة ذات أساس متين، يمكن صياغته كخطوة واحدة. لإثبات صحة العبارة $P (n)$ لكل عدد ترتيبي:

أثبت، لكل عدد ترتيبي $n$ ، أنه إذا تحققت $P (m)$ لجميع $m < n$ ، فإن $P (n)$ تتحقق أيضًا.

يُطلق على هذا النوع من الاستقراء، عند تطبيقه على مجموعة من الأعداد الترتيبية (التي تُشكّل فئة مُرتبة ترتيبًا جيدًا وبالتالي ذات أساس متين )، اسم الاستقراء المتسامي . وهو أسلوب إثبات مهم في نظرية المجموعات والطوبولوجيا وغيرها من المجالات.

تُميّز البراهين بالاستقراء المتسامي عادةً ثلاث حالات:

عندما يكون $n$ عنصرًا أصغر، أي لا يوجد عنصر أصغر من $n$ ؛
عندما يكون لـ $n$ سلف مباشر، أي أن مجموعة العناصر الأصغر من $n$ تحتوي على أكبر عنصر؛
عندما لا يكون لـ $n سلف مباشر، أي أن$ $n$ هو ما يسمى بالعدد الترتيبي الحدي .

بالمعنى الدقيق، ليس من الضروري في الاستقراء المتسامي إثبات حالة أساسية، لأنها حالة خاصة فارغة من القضية القائلة بأنه إذا كانت $P$ صحيحة لجميع $قيم n < m$ ، فإن $P$ صحيحة لـ $m$ . وهي صحيحة بشكل فارغ تحديدًا لعدم وجود قيم $n < m$ يمكن أن تُستخدم كأمثلة مضادة. لذا، فإن الحالات الخاصة هي حالات خاصة من الحالة العامة.

العلاقة بمبدأ الترتيب الجيد

يُصاغ مبدأ الاستقراء الرياضي عادةً كمسلمة من مسلمات الأعداد الطبيعية؛ انظر مسلمات بيانو . وهو أقوى بكثير من مبدأ الترتيب الجيد في سياق مسلمات بيانو الأخرى. لنفترض ما يلي:

بديهية التثليث : لأي عددين طبيعيين $n$ و $m$ ، يكون $n$ أصغر من أو يساوي $m$ إذا وفقط إذا كان $m$ ليس أصغر من $n$ .
لأي عدد طبيعي $n$ ، يكون $n + 1$ أكبر من n .
بالنسبة لأي عدد طبيعي $n$ ، لا يوجد عدد طبيعي بين n و $n + 1$ .
لا يوجد عدد طبيعي أقل من الصفر.

يمكن إثبات أن الاستقراء، في ضوء البديهيات المذكورة أعلاه، يستلزم مبدأ الترتيب الجيد. ويستخدم البرهان التالي الاستقراء الكامل والبديهيتين الأولى والرابعة.

البرهان. لنفترض وجود مجموعة غير فارغة ، $S$ ، من الأعداد الطبيعية ليس لها أصغر عنصر. ولتكن $P (n)$ هي العبارة التي تنص على أن $n$ ليس في $S.$ إذن $P (0)$ صحيحة، لأنه لو كانت خاطئة لكان 0 أصغر عنصر في $S.$ علاوة على ذلك، ليكن $n$ عددًا طبيعيًا، ولنفترض أن $P (m)$ صحيحة لجميع الأعداد الطبيعية $m$ الأقل من $n + 1.$ إذن إذا كانت $P (n + 1)$ خاطئة، فإن $n + 1$ ينتمي إلى $S$ ، وبالتالي فهو أصغر عنصر في $S$ ، وهذا تناقض. إذن $P (n + 1)$ صحيحة. لذلك، وفقًا لمبدأ الاستقراء الكامل، فإن $P (n)$ صحيحة لجميع الأعداد الطبيعية $n$ ؛ وبالتالي فإن $S$ فارغة، وهذا تناقض. انتهى البرهان.

" خط الأعداد " للمجموعة

{(0, n): n \in N} \cup {(1, n): n \in N}

. تشير الأرقام إلى المكون الثاني للأزواج؛ ويمكن الحصول على المكون الأول من اللون أو الموقع.

من ناحية أخرى، المجموعة $\{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}$ كما هو موضح في الصورة، فإنّ الترتيب المعجمي [27]: 35lf مُرتب ترتيبًا جيدًا . علاوة ^{على ذلك ،}^{باستثناء بديهية} الاستقراء، فإنه يُحقق جميع بديهيات بيانو، حيث يُفسَّر ثابت بيانو 0 على أنه الزوج (0، 0)، وتُعرَّف دالة بيانو اللاحقة على الأزواج بواسطة $succ($ $x$ $,$ $n$ $) = ($ $x$ $,$ $n$ $+$ $1)$ لجميع $x\in \{0,1\}$ و $n\in \mathbb {N}$ كمثال على انتهاك بديهية الاستقراء، عرّف المسند $P (x, n)$ على أنه $(x, n) = (0, 0)$ أو $(x, n) = succ(y, m)$ لبعض $y\in \{0,1\}$ و $m\in \mathbb {N}$ إذن، تكون الحالة الأساسية $P (0, 0)$ صحيحة بشكل بديهي، وكذلك خطوة الاستقراء: إذا كانت $P (x, n)$ ، فإن $P (succ(x, n))$ . مع ذلك، فإن $P$ ليست صحيحة لجميع الأزواج في المجموعة، لأن $P (1, 0)$ خاطئة.

تُقدّم بديهيات بيانو، مع مبدأ الاستقراء، نموذجًا فريدًا للأعداد الطبيعية. ويُتيح استبدال مبدأ الاستقراء بمبدأ الترتيب الجيد نماذج أكثر تعقيدًا تُحقق جميع البديهيات. ^{[ 27 ]}

ورد خطأً في العديد من الكتب ^{[ 27 ]} والمصادر أن مبدأ الترتيب الجيد يُكافئ بديهية الاستقراء. في سياق بديهيات بيانو الأخرى، لا ينطبق هذا، ولكنهما متكافئان في سياق بديهيات أخرى؛ ^{[ 27 ]} تحديدًا، يستلزم مبدأ الترتيب الجيد بديهية الاستقراء في سياق البديهيتين الأوليين المذكورتين أعلاه.

كل عدد طبيعي إما أن يكون 0 أو $n + 1$ لعدد طبيعي $ما n$ .

من الأخطاء الشائعة في العديد من البراهين الخاطئة افتراض أن $n - 1$ هو عدد طبيعي فريد ومحدد جيدًا، وهي خاصية لا تستلزمها بديهيات بيانو الأخرى. ^{[ 27 ]}

انظر أيضاً

ملحوظات

↑ مات ديفوس، الاستقراء الرياضي ، جامعة سيمون فريزر
↑ جيراردو كون دياز، الاستقراء الرياضي، مؤرشف في 2 مايو 2013 على موقع Wayback Machine ، جامعة هارفارد
↑ أندرسون، روبرت ب. (1979). إثبات صحة البرامج . نيويورك: جون وايلي وأولاده. ص 1. ISBN 978-0471033950.
↑ سوبر، بيتر. "الاستقراء الرياضي" . كلية إيرلهام. مؤرشف من الأصل في 24 مايو 2011. تم الاطلاع عليه في 26 مارس 2011 .
↑ "أصول إقليدس، الكتاب السابع، التعريفان 1 و2" . webspace.ship.edu . تم الاطلاع عليه بتاريخ 23 مايو 2026 .
↑ أسيربي، فابيو (1 يناير 2000). "أفلاطون: بارمنيدس 149أ7-ج3. برهان بالاستقراء الكامل؟" . أرشيف تاريخ العلوم الدقيقة 55 (2000)، 57-76 .
↑ سريامان، بهارات، محرر (2024)، دليل تاريخ وفلسفة الممارسة الرياضية. المجلد 4، مرجع سبرينغر الطبيعي، تشام: سبرينغر، ص 985، ISBN 978-3-031-40845-8، بقراءة المصادر بدقة، لدينا بعض الحجج الجديدة التي تُظهر أن الفيثاغوريين كان لديهم بالفعل برهان استقرائي، ولكن بدون مبدأ الاستقراء الرياضي.
↑ راشد 1994 ، ص 62-84.
↑ المعرفة الرياضية والتفاعل بين الممارسات "أُعطي أقدم برهان ضمني عن طريق الاستقراء الرياضي حوالي عام 1000 في عمل للرياضي الفارسي الكرجي"
↑ «نظرية ذات الحدين» . mathcenter.oxford.emory.edu . تاريخ الاطلاع: 2 ديسمبر 2024. مع ذلك، لم يكن أول من درسها. يُنسب الفضل حاليًا في اكتشافها إلى عالم الرياضيات والمهندس الفارسي الكرجي، الذي عاش بين عامي 935 و1029. ( معلومة جانبية مثيرة للاهتمام: قدم الكرجي أيضًا فكرة الاستدلال بالاستقراء الرياضي ) .
↑ كاتز (1998)، ص 255
1 2 كاجوري (1918) ، ص 197: «إن عملية الاستدلال المسماة "الاستقراء الرياضي" لها عدة أصول مستقلة. وقد تم تتبعها إلى السويسري جاكوب (جيمس) برنولي، والفرنسيين بيير باسكال وبولس فيرما، والإيطالي فريدريك ماوروليكوس. [...] من خلال قراءة ما بين السطور، يمكن للمرء أن يجد آثارًا للاستقراء الرياضي في وقت أبكر، في كتابات الهنود واليونانيين، كما هو الحال، على سبيل المثال، في "الطريقة الدورية" لبهاسكارا، وفي برهان إقليدس على أن عدد الأعداد الأولية لا نهائي.»
↑ راشد 1994 ، ص 62.
↑ سيمونسون 2000 .
↑ رابينوفيتش 1970 .
↑ «قد يُطلب أحيانًا إثبات نظرية تكون صحيحة كلما كانت الكمية n التي تتضمنها عددًا صحيحًا، وعادةً ما تكون طريقة الإثبات على النحو التالي: أولًا، يُثبت صحة النظرية عندما n = 1. ثانيًا، يُثبت أنه إذا كانت النظرية صحيحة عندما يكون n عددًا صحيحًا مُعطى ، فستكون صحيحة إذا كان n هو العددالصحيح الأكبر منه. ومن ثم، فإن النظرية صحيحة بشكل عام. ... يمكن تسمية هذا النوع من الحجج بالاستدلال المستمر » (بول، حوالي 1849، رسالة تمهيدية في المنطق، غير رياضي ، ص 40-41، أعيد طبعه في: غراتان-غينيس، إيفور وبورنيه، جيرار (1997)، جورج بول: مخطوطات مختارة في المنطق وفلسفته ، دار بيركهاوزر للنشر، برلين، ISBN). 3-7643-5456-9)
↑ بيرس 1881 .
↑ شيلدز 1997 .
↑ تيد سوندستروم، الاستدلال الرياضي ، ص 190، بيرسون، 2006، رقم ISBN 978-0131877184
↑ سموليان، ريموند (2014). دليل المبتدئين في المنطق الرياضي . دوفر. ص 41. ISBN 978-0486492377.
↑ بوس، صموئيل (1986). الحساب المحدود . نابولي: بيبليوبوليس.
↑ "برهان: الاستقراء القوي مكافئ للاستقراء الضعيف" . جامعة كورنيل . تم الاطلاع عليه بتاريخ 4 مايو 2023 .
↑ شفيعي، نيلوفر. "الاستقراء القوي والترتيب الجيد" (ملف PDF) . جامعة يورك . تم الاطلاع عليه بتاريخ 28 مايو 2023 .
↑ "الاستقراء الأمامي والخلفي | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 23 أكتوبر 2019 .
↑ كوشي، أوغسطين لويس (1821). دروس التحليل في المدرسة الملكية للفنون التطبيقية، الجزء الأول، التحليل الجبري، مؤرشف في 14 أكتوبر 2017 في أرشيف الإنترنت في باريس. يمكن الاطلاع على برهان متباينة الوسطين الحسابي والهندسي في الصفحات 457 وما بعدها.
↑ كوهين، جويل إي. (1961). "حول طبيعة البرهان الرياضي". أوبوس .. أعيد طبعه في كتاب "A Random Walk in Science " (تحرير آر إل ويبر)، دار نشر كرين، روساك وشركاه، 1973.
1 2 3 4 5 أومان، لارس-دانيال (6 مايو 2019). "هل الاستقراء والترتيب الجيد متكافئان؟" . مجلة الرياضيات الذكية . 41 (3): 33-40 . doi : 10.1007/s00283-019-09898-4 .

مراجع

مقدمة

فرانكلين، ج .؛ داود، أ. (2011). البرهان في الرياضيات: مقدمة . سيدني: كيو بوكس. ISBN 978-0-646-54509-7.(الفصل 8.)
"الاستقراء الرياضي" . موسوعة الرياضيات . دار نشر EMS . 2001 [1994].
هيرمس، هانز (1973). مقدمة في المنطق الرياضي . هوخشولتكست. لندن: سبرينغر. ISBN 978-3540058199ISSN 1431-4657 . MR 0345788 .
كنوت، دونالد إي. (1997). فن برمجة الحاسوب، المجلد 1: الخوارزميات الأساسية ( الطبعة الثالثة). أديسون-ويسلي. ISBN 978-0-201-89683-1.(القسم 1.2.1: الاستقراء الرياضي، الصفحات 11-21.)
كولموغوروف، أندريه ن .؛ فومين، سيرجي ف. (1975). مدخل إلى التحليل الحقيقي . ترجمة وتحرير: سيلفرمان، ر. أ. نيويورك: دوفر. ISBN 978-0-486-61226-3.(القسم 3.8: الاستقراء المتغاير، الصفحات 28-29.)

تاريخ

أتشيربي، فابيو (أغسطس 2000). " أفلاطون: بارمنيدس 149أ7-ج3. برهان بالاستقراء الكامل؟" . أرشيف تاريخ العلوم الدقيقة . 55 (1): 57-76 . doi : 10.1007/s004070000020 . JSTOR 41134098. S2CID 123045154 .
بوسّي، دبليو إتش (1917). "أصل الاستقراء الرياضي". المجلة الرياضية الأمريكية الشهرية . 24 (5): 199-207 . doi : 10.2307/2974308 . JSTOR 2974308 .
كاجوري، فلوريان (1918). "أصل تسمية "الاستقراء الرياضي"". المجلة الرياضية الأمريكية الشهرية . 25 (5): 197–201 . doi : 10.2307/2972638 . JSTOR 2972638 .
فاولر، د. (1994). "هل استخدم الإغريق الاستقراء الرياضي؟ وهل استخدموه فعلاً؟". فيزيس . 31 : 253-265 .
فرويدينثال، هانز (1953). "Zur Geschichte der vollständigen Induction". المحفوظات الدولية لتاريخ العلوم . 6 : 17 - 37.
كاتز، فيكتور ج. (1998). تاريخ الرياضيات: مقدمة . أديسون-ويسلي . ISBN 0-321-01618-1.
بيرس، تشارلز ساندرز (1881). " في منطق الأعداد" . المجلة الأمريكية للرياضيات . 4 ( 1-4 ): 85-95 . doi : 10.2307/2369151 . JSTOR 2369151. MR 1507856 . أُعيد طبعه (CP 3.252–288)، (W 4:299–309)
رابينوفيتش، ناحوم ل. ( 1970). "الحاخام ليفي بن غيرشون وأصول الاستقراء الرياضي". أرشيف تاريخ العلوم الدقيقة . 6 (3): 237-248 . doi : 10.1007/BF00327237 . MR 1554128. S2CID 119948133 .
راشد، رشدي (1972). "الاستقراء الرياضي: الكرجي، السماول". أرشيف تاريخ العلوم الدقيقة ( بالفرنسية). 9 (1): 1-21 . doi : 10.1007/BF00348537 . MR 1554160. S2CID 124040444 .
راشد، ر. (1994). "الاستقراء الرياضي: الكرجي والسموال". تطور الرياضيات العربية: بين الحساب والجبر . دراسات بوسطن في فلسفة العلوم. المجلد 156. سبرينغر للعلوم والأعمال. ISBN 9780792325659.
شيلدز، بول (1997). "مسلمات بيرس في الحساب". في: هاوزر، ناثان؛ روبرتس، دون د.؛ إيفرا، جيمس فان (محررون). دراسات في منطق تشارلز س. بيرس . مطبعة جامعة إنديانا. ص 43-52 . ISBN 0-253-33020-3MR 1720827 .
سيمونسون، تشارلز ج. (شتاء 2000). "رياضيات ليفي بن غيرشون، الرالباغ" (ملف PDF) . بيكهول دراخيكا ديهو . 10. مطبعة جامعة بار إيلان: 5-21 . مؤرشف من الأصل (ملف PDF) في 11 أكتوبر 2017. تم الاطلاع عليه في 29 ديسمبر 2019 .
أونغورو، س. (1991). "الرياضيات اليونانية والاستقراء الرياضي". فيزيس . 28 : 273-289 .
أونغورو، س. (1994). “الصيد بعد الحث”. الفيزياء . 31 : 267 – 272.
فاكا، ج. (1909). "موروليكوس، أول من اكتشف مبدأ الاستقراء الرياضي" . نشرة الجمعية الرياضية الأمريكية . 16 (2): 70-73 . doi : 10.1090/S0002-9904-1909-01860-9 . MR 1558845 .
يادغاري، محمد (1978) . "استخدام الاستقراء الرياضي عند أبي كامل شجاع بن أسلم (850-930)". إيزيس . 69 (2): 259-262 . doi : 10.1086/352009 . JSTOR 230435. S2CID 144112534 .

[1] مات ديفوس، الاستقراء الرياضي ، جامعة سيمون فريزر

[2] جيراردو كون دياز، الاستقراء الرياضي، مؤرشف في 2 مايو 2013 على موقع Wayback Machine ، جامعة هارفارد

[3] أندرسون، روبرت ب. (1979). إثبات صحة البرامج . نيويورك: جون وايلي وأولاده. ص 1. ISBN 978-0471033950.

[4] سوبر، بيتر. "الاستقراء الرياضي" . كلية إيرلهام. مؤرشف من الأصل في 24 مايو 2011. تم الاطلاع عليه في 26 مارس 2011 .

[5] "أصول إقليدس، الكتاب السابع، التعريفان 1 و2" . webspace.ship.edu . تم الاطلاع عليه بتاريخ 23 مايو 2026 .

[6] أسيربي، فابيو (1 يناير 2000). "أفلاطون: بارمنيدس 149أ7-ج3. برهان بالاستقراء الكامل؟" . أرشيف تاريخ العلوم الدقيقة 55 (2000)، 57-76 .

[7] سريامان، بهارات، محرر (2024)، دليل تاريخ وفلسفة الممارسة الرياضية. المجلد 4، مرجع سبرينغر الطبيعي، تشام: سبرينغر، ص 985، ISBN 978-3-031-40845-8، بقراءة المصادر بدقة، لدينا بعض الحجج الجديدة التي تُظهر أن الفيثاغوريين كان لديهم بالفعل برهان استقرائي، ولكن بدون مبدأ الاستقراء الرياضي.

[FOOTNOTERashed199462–84-8] راشد 1994 ، ص 62-84.

[9] المعرفة الرياضية والتفاعل بين الممارسات "أُعطي أقدم برهان ضمني عن طريق الاستقراء الرياضي حوالي عام 1000 في عمل للرياضي الفارسي الكرجي"

[10] «نظرية ذات الحدين» . mathcenter.oxford.emory.edu . تاريخ الاطلاع: 2 ديسمبر 2024. مع ذلك، لم يكن أول من درسها. يُنسب الفضل حاليًا في اكتشافها إلى عالم الرياضيات والمهندس الفارسي الكرجي، الذي عاش بين عامي 935 و1029. ( معلومة جانبية مثيرة للاهتمام: قدم الكرجي أيضًا فكرة الاستدلال بالاستقراء الرياضي ) .

[11] كاتز (1998)، ص 255

[Induction_Bussey-12] 1 2 كاجوري (1918) ، ص 197: «إن عملية الاستدلال المسماة "الاستقراء الرياضي" لها عدة أصول مستقلة. وقد تم تتبعها إلى السويسري جاكوب (جيمس) برنولي، والفرنسيين بيير باسكال وبولس فيرما، والإيطالي فريدريك ماوروليكوس. [...] من خلال قراءة ما بين السطور، يمكن للمرء أن يجد آثارًا للاستقراء الرياضي في وقت أبكر، في كتابات الهنود واليونانيين، كما هو الحال، على سبيل المثال، في "الطريقة الدورية" لبهاسكارا، وفي برهان إقليدس على أن عدد الأعداد الأولية لا نهائي.»

[FOOTNOTERashed199462-13] راشد 1994 ، ص 62.

[FOOTNOTESimonson2000-14] سيمونسون 2000 .

[FOOTNOTERabinovitch1970-15] رابينوفيتش 1970 .

[16] «قد يُطلب أحيانًا إثبات نظرية تكون صحيحة كلما كانت الكمية n التي تتضمنها عددًا صحيحًا، وعادةً ما تكون طريقة الإثبات على النحو التالي: أولًا، يُثبت صحة النظرية عندما n = 1. ثانيًا، يُثبت أنه إذا كانت النظرية صحيحة عندما يكون n عددًا صحيحًا مُعطى ، فستكون صحيحة إذا كان n هو العددالصحيح الأكبر منه. ومن ثم، فإن النظرية صحيحة بشكل عام. ... يمكن تسمية هذا النوع من الحجج بالاستدلال المستمر » (بول، حوالي 1849، رسالة تمهيدية في المنطق، غير رياضي ، ص 40-41، أعيد طبعه في: غراتان-غينيس، إيفور وبورنيه، جيرار (1997)، جورج بول: مخطوطات مختارة في المنطق وفلسفته ، دار بيركهاوزر للنشر، برلين، ISBN). 3-7643-5456-9)

[FOOTNOTEPeirce1881-17] بيرس 1881 .

[FOOTNOTEShields1997-18] شيلدز 1997 .

[19] تيد سوندستروم، الاستدلال الرياضي ، ص 190، بيرسون، 2006، رقم ISBN 978-0131877184

[20] سموليان، ريموند (2014). دليل المبتدئين في المنطق الرياضي . دوفر. ص 41. ISBN 978-0486492377.

[Buss:BA-21] بوس، صموئيل (1986). الحساب المحدود . نابولي: بيبليوبوليس.

[22] "برهان: الاستقراء القوي مكافئ للاستقراء الضعيف" . جامعة كورنيل . تم الاطلاع عليه بتاريخ 4 مايو 2023 .

[yorku-23] شفيعي، نيلوفر. "الاستقراء القوي والترتيب الجيد" (ملف PDF) . جامعة يورك . تم الاطلاع عليه بتاريخ 28 مايو 2023 .

[24] "الاستقراء الأمامي والخلفي | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 23 أكتوبر 2019 .

[25] كوشي، أوغسطين لويس (1821). دروس التحليل في المدرسة الملكية للفنون التطبيقية، الجزء الأول، التحليل الجبري، مؤرشف في 14 أكتوبر 2017 في أرشيف الإنترنت في باريس. يمكن الاطلاع على برهان متباينة الوسطين الحسابي والهندسي في الصفحات 457 وما بعدها.

[26] كوهين، جويل إي. (1961). "حول طبيعة البرهان الرياضي". أوبوس .. أعيد طبعه في كتاب "A Random Walk in Science " (تحرير آر إل ويبر)، دار نشر كرين، روساك وشركاه، 1973.

[Ohman2019-27] 1 2 3 4 5 أومان، لارس-دانيال (6 مايو 2019). "هل الاستقراء والترتيب الجيد متكافئان؟" . مجلة الرياضيات الذكية . 41 (3): 33-40 . doi : 10.1007/s00283-019-09898-4 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ ٨ ]

[ ٩ ]

[ ١٠ ]

[ 11 ]

[

[ 13 ]

[

[

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

22

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

على ذلك ،

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗