אינדוקציה שלמה ואינדוקציה רגילה

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

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

את התיאור המאוד כללי ומנופנף ידיים הזה לרוב דוחסים לתוך המסגרת המאוד פשוטה של המספרים הטבעיים - המספרים \( 1,2,3,4,\dots \) (נעזוב את 0 להפעם). הרעיון הוא שיש לנו סדרה של טענות, כשכל טענה מתאימה למספר טבעי אחר. למשל, השווין \( 1+2+3+\dots+n=\frac{n\left(n+1\right)}{2} \) הוא בעצם דרך כללית לתאר את הסדרה הבאה של טענות:

טענה מס’ 1: \( 1=\frac{1\left(1+1\right)}{2} \)

טענה מס’ 2: \( 1+2=\frac{2\left(2+1\right)}{2} \)

טענה מס’ 3: \( 1+2+3=\frac{3\left(3+1\right)}{2} \)

וכך זה נמשך ונמשך.

אינדוקציה “רגילה” אומרת את הדבר הבא: נניח שאנחנו יודעים להוכיח את הטענה במפורש עבור \( n=1 \) (הבסיס) ונניח גם שאם נתון לנו שהטענה נכונה עבור \( n \) כלשהו אז אנחנו יודעים להוכיח שהטענה נכונה עבור \( n+1 \) (הצעד) אז הטענה נכונה לכל \( n \). האינטואיציה היא שכדי להוכיח את טענה 3, למשל, אנחנו מבצעים שרשרת של טענות מהצורה “אוקיי, קודם כל טענה 1 נכונה כי הנה הוכחה מפורשת. עכשיו, אני יודע להוכיח שאם טענה 1 נכונה אז גם טענה 2 נכונה, וכבר ראיתי שטענה 1 נכונה אז המסקנה היא שטענה 2 נכונה. עכשיו, אני יודע להוכיח שאם טענה 2 נכונה אז גם טענה 3 נכונה, וכבר ראינו ש-2 נכונה ולכן גם 3 נכונה”. עבור טענה 1,000,000 אותו עיקרון בדיוק יעבוד, אם כי השרשרת שתיווצר תהיה מפלצתית באורכה (אבל האורך הזה יהיה סופי, שזו הנקודה החשובה פה כי הוכחות אמורות להיות תמיד סופיות).

אינדוקציה “שלמה” אומרת את הדבר הבא: נניח שאם נתון לנו שהטענה נכונה לכל מספר טבעי מ-1 ועד \( n \), אז אנחנו יודעים להוכיח את הטענה עבור \( n+1 \), אז מכאן נובע שהטענה נכונה לכל \( n \). כאן אין הבדלה בין הבסיס ובין הצעד, כי הבסיס הוא הסיטואציה שבה \( n=0 \), ואז ה”צעד” אומר את הדבר הבא: אנחנו יודעים להוכיח שהטענה נכונה עבור 1 אם נתון לנו שהיא נכונה לכל מספר טבעי שגדול או שווה ל-1 אבל קטן או שווה ל-0, כלומר במקרה הזה לא נתון לנו כלום, וזו בדיוק הסיטואציה של להוכיח את המקרה \( n=1 \) בלי כלום.

מה ההבדל בין אינדוקציה רגילה ושלמה? באינדוקציה שלמה יש יותר על מה להתבסס כשבאים להוכיח שהטענה נכונה עבור \( n+1 \). באינדוקציה רגילה כל מה שיש לנו הוא את נכונות הטענה עבור \( n \), וזהו; אבל אולי המקרה עבור \( n \) לא רלוונטי עבור \( n+1 \) ודווקא קל להוכיח את המקרה \( n+1 \) אם נתונה לנו הטענה עבור \( n-1 \)? לכן אינדוקציה שלמה באה להגיד לנו - קחו איזה מקרה שתרצו מבין אלו ש”כבר עברתם”. אם נחשוב על זה לרגע, כשאני מוכיח את המקרה \( n=5 \) באינדוקציה רגילה, מה שאני עושה הוא קודם כל לייצר הוכחות עבור המקרים \( 1,2,3,4 \) ואז להשתמש רק במקרה 4 כדי להוכיח את 5. אין סיבה עקרוני למה לא להשתמש גם ב”תוצרי הלוואי” שהוכחתי בדרך - 1,2,3.

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

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

כדי לפשט טיפה את הדיון מבלי לפגוע במהות שלו, בואו נציג ניסוח קצת יותר נקי של מהי אינדוקציה. במקום לדבר על “תכונות” נדבר על קבוצות. אינדוקציה רגילה אומרת את הדבר הבא: תהא \( S \) קבוצה כלשהי של מספרים טבעיים. אם \( 1\in S \) וגם ידוע שלכל \( n \) טבעי, אם \( n\in S \) אז \( n+1\in S \), אז המסקנה היא ש-\( S=\mathbb{N} \), דהיינו \( S \) כוללת את כל הטבעיים. בואו ננסח את זה בצורה יותר פורמלית, כדי למנוע ככל הניתן כפלי משמעות שהשפה מכניסה:

\( \forall S\left[\left(1\in S\wedge\left(\forall n\left(n\in S\to n+1\in S\right)\right)\right)\to S=\mathbb{N}\right] \)

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

\( \forall S\left[\left(\forall n\left(\forall k\left(k<n\to k\in S\right)\to n\in S\right)\right)\to S=\mathbb{N}\right] \)

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

\( \left(\forall n\left(\forall k\left(k<n\to k\in S\right)\to n\in S\right)\right)\to S=\mathbb{N} \)

זו טענה מהמבנה הכללי \( A\to B \). טענות כאלו הן נכונות תמיד, למעט במקרה שבו \( A \) הוא “אמת” ואילו \( B \) הוא “שקר”. כלומר, היעד שלנו הוא להראות שהמקרה הזה לא מתאפשר. מכיוון שבמקרה הזה \( A \) הוא “אמת” אני יכול להוסיף את \( A \) להנחות שלי, ומכיוון שאני רוצה להראות שגם \( B \) הוא אמת, אני רוצה להוכיח את \( B \). במילים אחרות, אם אני מתחזק לעצמי שתי רשימות - רשימה של “ההנחות שלי” ורשימה של “הדברים שעלי להוכיח”, ורשימת “הדברים שעלי להוכיח” כללה את \( A\to B \), אז אני מוציא את \( A\to B \) מהרשימה הזו, מוסיף לה את \( B \) ומוסיף את \( A \) לרשימת ההנחות שלי.

על כן, ה”צריך להוכיח” שלי כולל דבר יחיד: \( S=\mathbb{N} \). ההנחות שלי כוללות את הרישא של נוסחת האינדוקציה השלמה, ואת כל נוסחת האינדוקציה הרגילה. כלומר, יש לי שתי הנחות:

1. \( \forall n\left(\forall k\left(k<n\to k\in S\right)\to n\in S\right) \)
2. \( \left(1\in S\wedge\left(\forall n\left(n\in S\to n+1\in S\right)\right)\right)\to S=\mathbb{N} \)

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

\( 1\in S\wedge\left(\forall n\left(n\in S\to n+1\in S\right)\right) \)

אלו בעצם שני “צריך להוכיח” שונים שכתובים יחד. רשימת ה”צריך להוכיח” שלי, אם כן, היא כעת:

1. \( 1\in S \)
2. \( \forall n\left(n\in S\to n+1\in S\right) \)

וההנחה שבאמצעותה אני אמור להוכיח את שני אלו היא זו: \( \forall n\left(\forall k\left(k<n\to k\in S\right)\to n\in S\right) \). בואו נראה איך זה מוכיח את 1: ההנחה מתקיימת לכל \( n \), ולכן בפרט עבור הבחירה \( n=1 \). כשמציבים את הבחירה הזו בהנחה, מקבלים

\( \left(\forall k\left(k<1\to k\in S\right)\to1\in S\right) \). כמו קודם, אנחנו יכולים להחליף את ה”צריך להוכיח” הנוכחי שלנו, \( 1\in S \), ברישא של הפסוק הזה, \( \forall k\left(k<1\to k\in S\right) \). אצלנו הטבעיים לא כוללים את 0, ולכן \( k<1 \) הוא משהו שלא מתקיים לאף טבעי. לכן הנוסחה \( \forall k\left(k<1\to k\in S\right) \) היא נכונה תמיד (אם הרישא היא “שקר” לא אכפת לנו אם הסיפא היא אמת או שקר). זה מסיים את זה.

עד עכשיו הכל עבד כל כך חלק, אז איפה הבעיה בעצם? בדיוק בשלב הבא: נשאר לי להוכיח ש-

\( \forall n\left(n\in S\to n+1\in S\right) \)

כלומר, עבור \( a \) שרירותי כלשהו, אנחנו רוצים להוכיח ש-\( a\in S\to a+1\in S \) (בכוונה החלפתי את האות). במילים אחרות, אנחנו רוצים להוכיח את \( a+1\in S \) עם ההנחה \( a\in S \) והנחה נוספת: ההנחה החזקה-לכאורה של אינדוקציה שלמה, שאומרת ש- \( \forall n\left(\forall k\left(k<n\to k\in S\right)\to n\in S\right) \). אם אני אציב \( n=a+1 \), הסיפא של ההנחה שלי תהיה בדיוק מה שאני חותר אליו, ויישאר לי רק להראות את \( \forall k\left(k<a+1\to k\in S\right) \). וכאן אני נתקע.

למה אני נתקע? כי לא נתון לי ש-\( k\in S \) לכל \( k<a+1 \); זה נתון רק עבור \( k \) ספציפי - \( k=a \). ההנחה הרחבה של האינדוקציה השלמה היא חסרון במקרה הנוכחי, כי בניגוד לסיטואציות הרגילות שבהן אני משתמש באינדוקציה שלמה, ואז זה מקל על החיים, כאן אני מנסה להוכיח את עקרון האינדוקציה השלמה עצמו, ולצורך כך אני צריך לקושש יותר נתונים מאשר בדרך כלל. לכאורה נתקעתי.

הפתרון הוא פתרון סטנדרטי כאשר משתמשים באינדוקציה ונתקעים - לחזק את הנחת האינדוקציה. כשמוכיחים את צעד האינדוקציה מוכיחים \( n\in S\to n+1\in S \). כאן אנחנו נעזרים בהנחה \( n\in S \) כדי להוכיח את הצעד \( n+1\in S \). אם ההנחה \( n\in S \) לא מספיק טובה לנו, אנחנו מחליפים את \( S \) כולה ב-\( S^{\prime} \) שהיא חיזוק של \( S \) - כלומר, היא תכונה שכל מי שמקיים אותה מקיים גם את \( S \), אבל כוללת יותר אינפורמציה שאפשר לנצל. בצורה הזו אנחנו מקבלים את ההנחה החזקה יותר \( n\in S^{\prime} \) ואם בחרנו את \( S^{\prime} \) בחוכמה, נוכל להוכיח את הצעד החזק יותר (ולכן הקשה יותר להוכחה) \( n+1\in S^{\prime} \) יותר בקלות.

במקרה שלנו החיזוק הוא די ברור: \( S^{\prime}=\left\{ n\in S\ |\ \forall k<n\left(k\in S\right)\right\} \). כלומר, התכונה שלנו עכשיו היא “אני מקיים את \( S \) וכך גם כל מי שקטן ממני”. בבירור \( S^{\prime}\subseteq S \) ולכן אם אוכיח \( S^{\prime}=\mathbb{N} \) ינבע מכך \( S=\mathbb{N} \). בשביל להוכיח ש-ּ\( S^{\prime}=\mathbb{N} \) צריך להוכיח את שתי הטענות שהצגתי קודם:

1. \( 1\in S^{\prime} \)
2. \( \forall n\left(n\in S^{\prime}\to n+1\in S^{\prime}\right) \)

מבין שתיהן, הטענה הראשונה כבר טופלה - כבר ראינו ש-\( 1\in S \) ומכיוון שלא קיים \( k<1 \) אז השייכות \( 1\in S^{\prime} \) נובעת מיידית. נשאר רק להוכיח את צעד האינדוקציה ה”מחוזק”, כלומר ש-\( a\in S^{\prime}\to a+1\in S^{\prime} \). כעת, אם \( a\in S^{\prime} \) אז מהגדרת \( S^{\prime} \) נקבל ש-\( k\in S \) לכל \( k<a+1 \). זה אומר שכדי להראות ש-\( a+1\in S^{\prime} \) צריך אך ורק להראות ש-\( a+1\in S \). עכשיו מצבנו השתפר! אנחנו צריכים להוכיח את הטענה

\( a+1\in S \)

שגם קודם הסתבכנו איתה, אבל עכשיו יש לנו הנחה חזקה יותר:

\( a\in S^{\prime} \)

וההנחה הזו נותנת לנו את מה שהיה חסר לנו קודם: \( k\in S \) לכל \( k<a+1 \). עם ההנחה הזו אפשר להשתמש בהנחה הנוספת שקיבלנו מעקרון האינדוקציה השלמה ולקבל \( a+1\in S \) כפי שרצינו, מה שמסיים את ההוכחה.

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