אינדוקציה מוזרה ומשמעותה (טור 784)

בס"ד

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

מהי אינדוקציה מדעית

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

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

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

מהי אינדוקציה מתמטית

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

ידוע במתמטיקה שסכום המספרים הטבעיים עד n הוא:

n(n+1)/2

לדוגמה, סכום כל המספרים עד 10 הוא: 1+2+3+4+5+6+7+8+9+10 = 10*11/2 = 55. איך מוכיחים חוק כללי כזה? מספרים שהמתמטיקאי הידוע קרל פרידריך גאוס (מגדולי המתמטיקאים בכל הזמנים) עשה את זה בגיל בית ספר יסודי. המורה ביקש מהתלמידים לחשב את סכום המספרים מ-1 עד 100. גאוס חישב[1] והסביר זאת כך (אני מדגים על הסכום עד 10): טלו את המספר הראשון והאחרון בספרה, סכומם הוא 1+10=11. כך גם סכומם של השני והלפני אחרון (2+9=11) וכך כל שאר הזוגות. כמה זוגות ישנם בסדרה הזאת? 5. לכן הסכום הוא מספר הזוגות (חצי ממספר האיברים שאנחנו מסכמים) כפול הסכום של כל זוג. זהו בדיוק הביטוי שרשום למעלה.[2]

דרך אחרת להוכיח זאת היא באמצעות אינדוקציה מתמטית. זה הולך בערך כך:

• בודקים אם זה נכון עבור המקרה של סדרה בת מספר אחד. זוהי הסדרה שכוללת רק את 1. הסכום הוא כמובן 1. הביטוי שלמעלה גם הוא נותן 1.
• בבית הספר מלמדים לבדוק זאת גם עבור סדרה עם שני מספרים 1+2. התוצאה יוצאת 3 וגם שם זה עובד. זה סתם הרגל נחמד (ובהקשר של אינדוקציה מדעית הוא בהחלט חשוב, כי דוגמה אחת לבד לא מספיקה ליצור הכללה טובה), אבל כאן הוא לא באמת נחוץ.
• כעת מניחים שהוא נכון לכל סדרה של מספרים באורך k: 1+2+3+…+k =k(k+1)/2
• בשלב הבא, שמכונה "צעד האינדוקציה" (ההכללה), מוכיחים שאם זה נכון עבור n=k זה בהכרח נכון גם עבור n=k+1.

מה שצריך להוכיח הוא שאם לוקחים את הסכום מהסעיף הקודם ומוסיפים לו את האיבר הבא בסדרה (כלומר מוסיפים לו את המספר k+1), מקבלים בדיוק את אותו ביטוי מלמעלה כשבמקום k כותבים k+1 (כי כעת הסדרה היא באורך n=k+1). אם זה מתקיים, הוכחנו את צעד האינדוקציה. לא אעשה את זה כאן, אבל כל מי שלמד כיתה ט יכול לראות בקלות שזה אכן מתקיים.

מהי המשמעות של ההוכחה הזאת? בעצם ראינו שהנוסחה של סכום המספרים הללו נכונה עבור n=1. צעד האינדוקציה אומר שאם זה נכון עבור סדרה כלשהי של מספרים זה נכון גם עבור סדרה שכוללת עוד מספר. כעת ברור לכולנו שבעצם הוכחנו את נכונות הנוסחה לסדרה בכל אורך שהוא. אם זה נכון עבור n=1 אז צעד האינדוקציה מוכיח שזה נכון גם עבור n=2, וכעת עוד צעד אינדוקציה מוכיח שזה נכון גם עבור n=3 וכן הלאה לכל סדרה בכל אורך n שהוא. מכאן תוכלו גם להבין מדוע הבדיקה עבור n=2 מיותרת באינדוקציה מתמטית. הלוגיקה פועלת לגמרי גם בלי זה.

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

חשוב להבין שלהנחת האינדוקציה כשלעצמה אין שום משמעות. אנחנו לא באמת מניחים שזה נכון עבור n=k. זוהי רק הנחה היפותטית שעליה נבנה צעד האינדוקציה. הדבר היחיד שהוכחנו הוא שאם (!) זה נכון עבור n=k (למרות שייתכן שזה כשלעצמו לא נכון) אז גם עבור n=k+1 זה נכון. בהמשך אשוב לנקודה הזאת.

מבט נוסף על ההבדל בין שני סוגי האינדוקציה

בטור 537, תיארתי את האינדוקציה המדעית, והראיתי שהיא עלולה לתעתע בנו. אם יש תכונה שמתקיימת עבור כל מספר טבעי שאנחנו בודקים ופתאום נפגוש מספר טבעי שבו היא לא מתקיימת, זה מאד יפתיע אותנו. חשבו למשל אם הנוסחה שנתתי למעלה לסכום של מספרים טבעיים הייתה מתקיימת לכל מספר טבעי n=1,2,3… 734, אבל פתאום ב-735 זה היה מפסיק. שם הנוסחה הייתה נותנת תוצאה שגויה. הייתם ודאי נדהמים כמוני. זה נובע מהנטייה שלנו לעשות הכללות. הנטייה הזאת מבוססת על העיקרון שתופעה סדירה כנראה אינה מקרית. בדיוק על כך מבוססות ההכללות המדעיות שלנו (וגם חזקות שלוש פעמים בהלכה. ראו בטורים 729 ו-308). אם ראינו עצם אחד שנופל לקרקע, ועוד אחד ועוד אחד, ובפרט אם מדובר בעצמים מסוגים שונים, סביר מאד שכל העצמים (בעלי המסה) ייפלו לקרקע. בטור הנ"ל הבאתי תוצאה מתמטית כזאת בדיוק: היא מתקיימת עבור כל המספרים הטבעיים, עד מספר גדול כלשהו (אפשר אפילו לכוונן אותו).

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

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

אינדוקציה על צבעם של סוסים

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

• נבדוק זאת עבור n=1, כלומר עבור קבוצה שמכילה סוס אחד. שם זה כמובן מתקיים. יש לו צבע מסוים.
• ראינו שבאינדוקציה מתמטית, הבדיקה עבור n=2 מיותרת, אז כאן נדלג עליה.
• כעת נניח שזה מתקיים עבור כל קבוצה של n=k סוסים, כלומר שכל קבוצה של k סוסים מכילה סוסים מאותו צבע (שימו לב, בינתיים זוהי רק הנחה לצורך צעד האינדוקציה. אנחנו לא באמת מניחים את נכונותה של העובדה הזאת).
• צעד האינדוקציה: נוכיח שאם זה נכון לקבוצה בת k סוסים זה בהכרח נכון גם לקבוצה של k+1 סוסים.

איך הולכת ההוכחה? פשוט מאד:

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

כמובן שהדוגמה של 9 ו-10 סוסים אינה אלא הדגמה להוכחה. זה נכון לכל מספר של k+1 סוסים, כשמוציאים מהם שתי קבוצות שונות של k סוסים.

פרדוקס

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

הפגם בהוכחה

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

מה משמעות הדבר? שההוכחה שהצגתי עבור הדוגמה של 10 ו-9 סוסים, לא באמת מייצגת את כל גדלי הקבוצות. עבור קבוצה שבה k+1=2 זה לא מתקיים. כלומר צעד האינדוקציה שאם זה נכון עבור n=k זה נכון גם עבור n=k+1, אינו מתקיים כאשר k=1. טוב, עדיין לכאורה מתבקש להסיק שהמשפט הזה נכון לכל קבוצות הסוסים בכל גודל למעט קבוצה של שני סוסים. איך זה עוזר לנו ליישב את הממצא האמפירי (שיש סוסים עם צבעים שונים) עם המשפט שהוכחנו?

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

לקח לחיים

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

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

[1] למעשה, גאוס הוכיח נוסחה כללית יותר, שעוסקת בסכום של כל טור חשבוני, כלומר טור שההפרש בין כל שני איברים עוקבים שלו הוא קבוע (כמו למשל 1+12+23+34…).

[2] אני מתעלם כרגע מהמקרה של מספר אי זוגי של מחוברים. זה יוצא אותו דבר.