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

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

שימוש בנסיגה אינסופית ניתן לראות עוד בהוכחת אוקלידס לכך שהשורש הריבועי של 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$ בהתאמה, לכן לכל רביעית מספרים טבעיים קיימת רביעייה כך ששניים מהם קטנים יותר שעדיין מקיימת את המשוואה. אם נמשיך בכך עד אינסוף נגיע לסתירה. משום כך אין למשוואה דיופנטית זו אף פתרון בטבעיים.