הצגת המקור של הדף "נסיגה אינסופית"

ב[[מתמטיקה]], '''נסיגה אינסופית''' היא שיטה ל[[הוכחה|הוכחת]] [[משפט (מתמטיקה)|משפט]]ים על [[סדר טוב|קבוצות סדורות היטב]], כגון קבוצת [[המספרים הטבעיים]]. נסיגה אינסופית היא [[הוכחה על דרך השלילה]] שבה מניחים שטענה מסוימת נכונה לאיבר כלשהו ומראים שזה גורר בהכרח שהיא נכונה גם לאיבר קטן יותר. כעת נניח שקבוצת האיברים שהטענה נכונה עבורם אינה ריקה. מחד, יש לה איבר מינימלי משום שהמערכת סדורה היטב. מאידך, לכל איבר בקבוצה הזו יש איבר קטן יותר, וזו סתירה. מכאן שהטענה אינה נכונה לאף איבר.

שימוש בנסיגה אינסופית ניתן לראות עוד בהוכחת [[אוקלידס]] לכך ש[[השורש הריבועי של 2]] הוא [[מספר אי-רציונלי]]. בהוכחת אוקלידס מראים שאם שורש 2 היה רציונלי, אז היה ניתן להציגו כ[[שבר (מתמטיקה)|שבר]] שניתן לצמצמו ב-2 עד אינסוף, ולכן שורש 2 אינו רציונלי. [[פייר דה פרמה|פרמה]] נחשב למי שמיסד את השימוש השיטתי בשיטה כשהשתמש בה כדי להוכיח טענות על [[משוואה דיופנטית|משוואות דיופנטיות]]. המפורסמת שבהן היא הטענה שלמשוואה <math>\ x^4+y^4=z^4</math> אין פתרונות במספרים טבעיים (זהו [[מקרה פרטי]] של [[המשפט האחרון של פרמה]]). הוכחת נסיגה מפורסמת נוספת של פרמה היא [[סכום של שני ריבועים#הוכחה באמצעות נסיגה|הוכחת הטענה]] שכל מספר [[ראשוני]] השקול ל-1 [[מודולו]] 4 הוא סכום של שני [[ריבוע (חזקה)|ריבועים]].

==דוגמאות==

* נוכיח בעזרת נסיגה אינסופית שאין פתרונות בטבעיים למשוואה <math>a^2 + b^2 = 3(c^2 + d^2)</math>:

נניח בשלילה שיש פתרון. אז מתקיים ש- <math>a^2+b^2</math> מתחלק ללא שארית ב-3. כיוון שמספר ריבועי חייב לתת בחלוקה ב-3 שארית 1 או 0, אנחנו מקבלים ששני המספרים חייבים להתחלק ב-3. יהיו <math>a', b'</math> מספרים המקיימים <math>a = 3a', b = 3b'</math>. נציב במשוואה המקורית ונקבל <math>(3a')^2 + (3b')^2 = 3(c^2 + d^2)</math>, או <math>3(a'^2 + b'^2) = c^2 + d^2</math>. אבל <math>a', b'</math> קטנים יותר מ- <math>a, b</math> בהתאמה, לכן לכל רביעית מספרים טבעיים קיימת רביעייה כך ששניים מהם קטנים יותר שעדיין מקיימת את המשוואה. אם נמשיך בכך עד אינסוף נגיע לסתירה. משום כך אין ל[[משוואה דיופנטית]] זו אף פתרון בטבעיים.

* נוכיח כי <math>\sqrt{2}</math> אי רציונלי:

נניח בשלילה כי קיימים <math>a,b \in \mathbb{Z} </math> כך ש: <math>\sqrt{2} =  \frac{a}{b}</math> כלומר <math>2 = \frac{a^2}{b^2}</math> לכן :<math>2b^2 = a^2</math> ע״פ [[המשפט היסודי של האריתמטיקה]]:

<math>\exists k \in \mathbb{Z} . 2k = a</math> לכן: <math>2b^2 = 4k^2</math> כלומר <math>b^2 = 2k^2</math> לכן <math>\exists p \in \mathbb{Z} . 2p = b</math>.

זה אומר שלכל זוג a,b קיים זוג k,p קטן יותר המקיים את התנאי ובגלל שקיימים a,b שסכומם מינימלי נוצרת סתירה.

* נוכיח את המשפט האחרון של פרמה למקרה n=4:

נסתמך על המשפט:

a, b, c הם מספרים שלמים.  <math>a^2 + b^2 = c^2</math> [[אם ורק אם]] קיימים k, s, t שלמים כך ש־ <math>a = 2kst , b = k(s^2-t^2),c = k(s^2+t^2)</math> זהו משפט מוכר הנותן ״לייצר״ שלשות פיתגוראיות.

קל לראות שאם אין פתרונות למשוואה: <math>a^4 + b^4 = c^2</math> אז אין גם למשוואה המקורית.

נניח בשלילה שקיימת שלשה a,b,c המקיימת את המשוואה כאשר c מינימלי.

נובע מכך ש - <math>\gcd(a,b,c) = 1</math> כי אם לא אפשר לצמצם את המשווה וc לא יהיה מינימלי.

כלומר <math>a^2, b^2,c</math> שלשה פיתגוראית פרמיטיבית.

לכן קיימים  s, t כך ש<math>a^2 = 2st , b^2 = (s^2-t^2),c = (s^2+t^2)</math>.

מהמשוואה <math>b^2 = s^2 - t^2</math> נובע שקיימים u,v שלמים כך ש־ <math>t = 2uv , b = u^2-v^2,s=u^2+v^2</math> .

ע״פ המשפט היסודי של האריתמטיקה קיימים x,y המקיימים <math>s = y^2, t = 2x^2</math>.

לכן u,v ריבועיים, כלומר קיימים n,m המקיימים: <math>u = m^2, v = n^2</math>.

לכן m,n,y שלישייה קטנה יותר המקיימת <math>m^4 + n^4 = y^2</math>.

סתירה!!! כי קיבלנו שלישייה קטנה יותר בניגוד להנחה.

==ראו גם==
*[[אינדוקציה מתמטית]]

==קישורים חיצוניים==
<DIV dir=ltr>
* [http://taharut.org/imo/I5773/descent_method.pdf שיטת הירידה] באתר תחרות הערים 
* {{JSTOR|W. H. Bussey|Fermat's Method of Infinite Descent|2974148|American Mathematical Monthly}} 
</DIV>

{{קצרמר|מתמטיקה}}
[[קטגוריה:מושגים במתמטיקה]]
[[קטגוריה:שיטות הוכחה]]