נסיגה אינסופית

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

שימוש בנסיגה אינסופית ניתן לראות עוד בהוכחת אוקלידס לכך שהשורש הריבועי של 2 הוא מספר אי-רציונלי. בהוכחת אוקלידס מראים שאם שורש 2 היה רציונלי, אז היה ניתן להציגו כשבר שניתן לצמצמו ב-2 עד אינסוף, ולכן שורש 2 אינו רציונלי. פרמה נחשב למי שמיסד את השימוש השיטתי בשיטה כשהשתמש בה כדי להוכיח טענות על משוואות דיופנטיות. המפורסמת שבהן היא הטענה שלמשוואה $\ x^{4}+y^{4}=z^{4}$ אין פתרונות במספרים טבעיים (זהו מקרה פרטי של המשפט האחרון של פרמה). הוכחת נסיגה מפורסמת נוספת של פרמה היא הוכחת הטענה שכל מספר ראשוני השקול ל-1 מודולו 4 הוא סכום של שני ריבועים.

דוגמאות

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

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

נוכיח כי ${\sqrt {2}}$ אי רציונלי:

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

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

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

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

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

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