גם אני לא מאמין באינדוקציה (כי לאמונה אין קשר לזה)

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

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

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

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

ובכן, כן – למה אינדוקציה היא לא מה שמתואר כאן? מה זו בכלל אינדוקציה?

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

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

עד כה דיברתי מאוד באוויר ולכן בואו נעבור לדוגמאות שעוסקות בקבוצת האובייקטים ה"קלאסית" שעליה מדברים כשמדברים על אינדוקציה מתמטית – המספרים הטבעיים, $latex 1,2,3,\dots$. בניסוח עבור מספרים טבעיים, אינדוקציה מתמטית אומרת את הדבר הבא: "אם תכונה כלשהי מתקיימת עבור המספר 1, ואם קיום התכונה עבור המספר $latex n$ גורר את הקיום שלה עבור המספר $latex n+1$, אז התכונה נכונה לכל המספרים הטבעיים". הניסוח הזה כה חשוב עד כי במערכת האקסיומות הסטנדרטית למספרים הטבעיים הוא נכלל כאחת מהאקסיומות ("אקסיומת האינדוקציה"). אין זה אומר שאנו מניחים שאינדוקציה היא משהו שנכונותו אינה דורשת הצדקה; אחרי שאציג דוגמה פשוטה נעבור לדיון בשאלה למה בכלל נכון להניח שאינדוקציה מתמטית "עובדת".

דוגמה קלאסית להוכחה באינדוקציה היא ההוכחה לנוסחת הסכום של כל המספרים הטבעיים מ-1 ועד $latex n$: $latex 1+2+3+\dots+n=\frac{n\left(n+1\right)}{2}$. אי אפשר להביא את הנוסחה הזו מבלי לספר את הסיפור שנלווה אליה למרות שאין לו שום קשר לאינדוקציה מתמטית: מספרים שהמורה של גאוס הקטן (שהיה בן 6? 7? משהו בסגנון…) התעצל יום אחד וכדי שיהיה לו שקט מהתלמידים נתן להם לסכם את כל המספרים מ-1 ועד 100 (כלומר, במקרה הזה $latex n=100$). התלמידים מן הסתם לא הכירו את הנוסחה. והנה אחרי דקה או שתיים בא גאוס אל המורה ונתן לו את הפתרון – 5050. למורה ההמום הוא הסביר את ההגיון שלו – אם סוכמים את האיבר הראשון והאחרון, שהם $latex 1$ ו-$latex n$, מקבלים $latex n+1$; ואם סוכמים את האיבר השני והלפני אחרון, שהם $latex 2$ ו-$latex n-1$, מקבלים גם $latex n+1$, וכן הלאה. כמה זוגות כאלו יש בסך הכל? בדיוק חצי ממספר האיברים, כלומר $latex \frac{n}{2}$. לכן סכום כל האיברים הוא $latex \frac{n}{2}\left(n+1\right)$. אני לא יודע אם גאוס אכן גילה כך את הנוסחה או שזה סתם צ'יזבט, אבל לטעמי זו הוכחה נפלאה ממש.

חזרה לאינדוקציה מתמטית. ההוכחה באינדוקציה של נכונות הנוסחה היא הרבה יותר משעממת לצערי, אבל זכרו שמדובר על דוגמה שמנסה להיות פשוטה ואולי גם תפיס את דעתם של אלו שלא נחה עליהם דעתם מההוכחה של גאוס במקרה שבו $latex n$ הוא אי זוגי – למרות שאפשר לנסח אותה בצורה שתטפל גם בה. צריך להתחיל מהוכחה שהטענה נכונה עבור $latex n=1$, אבל זה פשוט עניין של הצבה בנוסחה ובדיקה: אם מציבים $latex n=1$ מקבלים $latex \frac{1\cdot\left(1+1\right)}{2}=1$. השיעמום הזה עשוי ליצור את הרושם שהוכחת הבסיס היא תמיד טריוויאלית, ולא כן – לפעמים הוכחת הבסיס היא החלק המאתגר יותר בהוכחה באינדוקציה.

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

$latex \frac{n\left(n+1\right)}{2}+\left(n+1\right)=\frac{n\left(n+1\right)+2\left(n+1\right)}{2}=\frac{\left(n+1\right)\left(n+2\right)}{2}$

למי שהמעבר האחרון לא ברור לו – הוצאתי את הגורם המשותף $latex \left(n+1\right)$ משני המחוברים.

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

במקרה הפרטי של הטענה שלנו זה הולך כך. ראינו שסכום כל האיברים עד 1 הוא 1; לכן סכום כל האיברים עד 2 הוא סכום כל האיברים עד 1 (שהוא 1) ועוד 2, כלומר 3; ולכן סכום כל האיברים עד 3 הוא סכום של האיברים עד 2 (שראינו לפני שניה שהוא 3) ועוד 3, כלומר 6; ולכן סכום כל האיברים עד 4 הוא סכום כל האיברים עד 3 (שראינו לפני רגע שהוא 6) ועוד 4, כלומר 10, ו-10 הוא בדיוק $latex \frac{4\left(4+1\right)}{2}$, כמו שרצינו. לכן הטענה נכונה גם עבור 4.

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

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

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

בואו נעבור לדבר הרבה יותר מטריד – האם אינדוקציה היא לא כלי חלש מדי? הרי כל מה שאני יכול לעשות הוא להוכיח איתה טענות על מספרים טבעיים! ובכן, לשאלה הזו יש שתי תשובות: לא, ולא. ה"לא" הראשון הוא שגם טענות על טבעיים יכולות בעצם להחביא בתוכן טענות על דברים שונים לחלוטין. הבה וניזכר בטענה שהוכחתי בפוסט הקודם – הוכחתי שם שכל לוח משבצות בגודל $latex 2^{n}\times2^{n}$ שהוסרה ממנו בדיוק משבצת אחת ניתן לריצוף בידי צורות "ר". כלומר, טענתי טענה על לוחות של משבצות, לא על מספרים טבעיים; ועם זאת, ההוכחה הייתה באינדוקציה. הכיצד? כי הטענה שלי, אם מנסחים אותה פורמלית עד הסוף, הייתה "לכל מספר טבעי $latex n$ מתקיימת התכונה שלוח שגודלו $latex 2^{n}\times2^{n}$ והוסרה ממנו משבצת אחת ניתן לריצוף".

למעשה, מה שקרה כאן הוא שהוכחתי טענה על האובייקט "לוח" תוך ניצול העובדה שהמבנה של הלוחות שעניינו אותי הוא פשוט יחסית וניתן לתיאור באמצעות פרמטר שהוא מספר טבעי, ושאני יכול להוכיח את הטענה על לוח שמאופיין על ידי הפרמטר $latex n+1$ באמצעות הסתמכות על נכונות הטענה עבור לוחות שמאופיינים על ידי הפרמטר $latex n$. פעמים רבות במתמטיקה השלב הראשון בדרך להוכחה באינדוקציה הוא בדיוק זיהוי המבנה של האובייקטים שעליהם רוצים להוכיח דבר מה כדי שיהיה ברור מי מהם מתאים למספר 1, מי מתאים ל-2 וכן הלאה.

אך למעשה, זה לא נגמר כאן. אין שום הכרח להסתפק באינדוקציות על מספרים טבעיים בלבד. הרחבה מיידית אחת של האינדוקציה היא לכל קבוצה סדורה היטב. קבוצה סדורה היטב היא קבוצה שאפשר להשוות בין כל שניים מאיבריה ולהגיד מי מהם קטן יותר, ובנוסף לכך מקיימת עוד תכונה (תכונת הסדר הטוב) והיא שלכל תת-קבוצה של איברים מתוכה יש איבר מינימלי. דוגמה לקבוצה שאינה סדורה היטב היא השלמים, $latex \mathbb{Z}$ – לה עצמה אין איבר מינימלי (למה?). לעומת זאת קבוצת הטבעיים $latex \mathbb{N}$ היא הדוגמה הקלאסית ביותר לקבוצה סדורה היטב.

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

"לכל $latex x\in A$, אם טענה כלשהי מתקיימת לכל $latex y<x$ שנמצא ב-$latex A$ אז היא מתקיימת עבור $latex x$".

שימו לב שכאן בכלל לא דיברתי על בסיס האינדוקציה אבל זה לא אומר שהוא לא שם – אם אני מוכיח את צעד האינדוקציה אני חייב תוך כדי כך גם להוכיח את בסיס האינדוקציה. מדוע? ובכן, עבור $latex x\in A$ שהוא האיבר המינימלי של $latex A$ כולה ($latex A$ היא סדורה היטב אז הוא קיים) פשוט לא קיימים איברים $latex y<x$, ולכן האמירה "הטענה מתקיימת לכל $latex y<x$" היא בודאות נכונה בלי קשר לכלום (מה שנקרא במתמטיקה "באופן ריק") ולכן כדי להוכיח את צעד האינדוקציה אני חייב להוכיח שהטענה מתקיימת עבור $latex x$ המינימלי מבלי שיהיה לי שום דבר להסתמך עליו.

זו דוגמה נחמדה לאופן שבו ברגע שבו מבצעים אבסטרקציה כלשהי לנושא הדיון שלנו ועוברים לדבר על מקרה כללי הרבה יותר, הניסוחים דווקא הופכים לפשוטים ואלגנטיים יותר (בהינתן, כמובן, שבכלל מצליחים להבין מה הולך כאן – וזה לא קל לעיכול בהתחלה). גם ההוכחה שהעקרון הזה "עובד" היא פשוטה: נניח שהוכחתי את צעד האינדוקציה, ועדיין יש איברים ב-$latex A$ שאינם מקיימים את התכונה. הבה ונתבונן בתת-הקבוצה של $latex A$ שכוללת בדיוק את כל האיברים שאינם מקיימים את התכונה. מכיוון ש-$latex A$ היא קבוצה סדורה היטב, קיים איבר מינימלי $latex x$ לאותה תת קבוצה. מכיוון שהוא האיבר המינימלי מבין כל האיברים שאינם מקיימים את התכונה, הרי שלכל $latex y\in A$ שמקיים $latex y<x$ כן מתקיימת התכונה – אבל אז, מצעד האינדוקציה, נובע שהיא מתקיימת גם עבור $latex x$ – סתירה.

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

אפשר להכליל את מושג האינדוקציה גם באופן נוסף לפעמים יש לנו אובייקטים שנוצרים באופן אינדוקטיבי: מתחילים מקבוצה פשוטה של איברי בסיס, ואז בכל שלב בונים איבר חדש מתוך חלק מהאיברים הקיימים. דוגמה קלאסית לכך היא נוסחאות מתמטיות פורמליות; אובייקט הבסיס הוא מספר טבעי כלשהו, ואילו אם $latex \alpha,\beta$ הן שתי נוסחאות אז גם $latex \left(\alpha+\beta\right)$ ו-$latex \left(\alpha\times\beta\right)$ הן נוסחאות, למשל. בעזרת כללי הבניה הללו אנו רואים ש-$latex \left(5+3\right)\times7$ היא נוסחה בעוד ש-$latex \left(5+3\right)\times2+9$ דווקא אינה נוסחה "חוקית" (איפה הסוגריים סביב 9?). אם יש לנו קבוצת אובייקטים שכזו, אז כדי להוכיח עליה טענה מספיק להוכיח שהטענה מתקיימת עבור איברי הבסיס, ושאם מפעילים כלל בניה על אובייקטים שמקיימים את הטענה, אז גם התוצר מקיים את הטענה. שימו לב שזה זהה לאינדוקציה "רגילה" במספרים טבעיים עם "כלל הבניה" שלוקח מספר $latex a$ ומייצר ממנו את המספר $latex a+1$. בלוגיקה מתמטית ובתחומים קרובים במדעי המחשב הוכחות כאלו הן נפוצות להחריד, עד שבדיחה ידועה אומרת שההבדל בין מדען מחשב ומתמטיקאי הוא שהמתמטיקאי יודע גם להוכיח דברים שלא באינדוקציה.

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

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

ובכן, היכן הרמאות? הבסיס דווקא תקין לחלוטין (אף שהאינטואיציה אומרת שהוא בעייתי). הרמאות היא בצעד האינדוקציה, והיא עדינה יחסית – היא מתבססת על כך שאינטואיטיבית, אנחנו חושבים שבצעד האינדוקציה אנחנו מוכיחים את הטענה עבור $latex n$ "גדול", למרות שזה ממש לא זה. אנחנו מוכיחים את הטענה עבור $latex n$ כללי, וזה שונה מהותית. זה אומר שלהוכחה שלנו אסור להסתמך על הנחה סמויה כלשהי על הגודל של $latex n$, למרות שזה בדיוק מה שאנחנו עושים כרגע. למה? כי את תעלול ריקון הקבוצה שלנו אפשר להפעיל באופן מוצלח רק אם $latex n$ הוא לפחות 3. אם $latex n=2$ אז יש בקבוצה רק שני סוסים – נקרא להם אליס ובוב. אם נוציא את אליס מהקבוצה יישאר בה רק בוב, וברור שבקבוצה שמכילה רק את בוב, לכל הסוסים יש את הצבע של בוב. ואז נכניס את אליס לקבוצה ונוציא ממנה את בוב, ושוב, לכל הסוסים בקבוצה יש את אותו צבע – הצבע של אליס – אבל זה לא אומר כלום על הצבע של בוב… ההנחה הסמויה היא שבקבוצת הסוסים שלנו יש גם "סוס מתווך" כלשהו שתמיד נשאר בקבוצה, ולכן הצבע שלו זהה גם לצבע של אליס וגם לצבע של בוב ולכן הצבעים של אליס ובוב זהים, אבל בקבוצה בגודל 2 לא קיים סוס מתווך כזה ולכן צעד האינדוקציה כושל פה.

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

58 תגובות בנושא “גם אני לא מאמין באינדוקציה (כי לאמונה אין קשר לזה)”

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

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

    (דבילי אך משכנע)

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

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

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

  5. תלוי בהגדרה של המספרים הטבעיים.

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

  6. כן אבל אז מה שאמרתי נכון ואינדוקציה היא אקסיומה (ולכן אין שום טעם להתווכח עליה).
    מהדברים של "the man who wears shorts sometimes" השתמע שיש דרך אחרת להגדיר את הטבעיים שב אפשר להוכיח את קיום סדר טוב (ולכן גם את נכונות האינדוקציה).

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

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

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

  10. "אינדוקציה מתימטית" – בכל צורה שהיא, היא החלק העיקרי של הגדרת המספרים הטבעיים (בכל צורה שהיא: על ידי מערכת אקסיומות שהם מודל שלה, או בתור אובייקט בתוך מערכת אחרת).
    רוב הדברים המעניינים שאפשר להוכיח על מספרים טבעיים אינם נובעים משאר אקסיומות פאנו, כך שאין "דרך אחרת" להוכיח אותם ("ללא אינדוקציה"). כשמוכיחים ש n^3-25n מתחלק ב-24 עבור n אי-זוגי ב"דרך אחרת", שאני מניח שהיא לפרק לגורמים n(n+5)(n-5)‎ ואז לטעון שאחד מהגורמים מתחלק ב-3, ולפי אי-זוגיות n אחד משני הגורמים הזוגיים מתחלק ב-4, ולכן הכל מתחלק ב-2·3·4=24' מסתמכים על כמה וכמה משפטים שההוכחה שלהם כוללת כמה וכמה פעמים שימוש באינדוקציה (כמו למשל החלוקה עם שארית והפריקות היחידה לראשוניים). אז בעצם זאת אינה הוכחה "ללא אינדוקציה" אלא רק העברת ה"עבודה השחורה" של ההוכחה באינדוקציה למישהו אחר (זה שהוכיח את המשפטים. מן הסתם אוקלידס…).

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

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

    דבר אחרון:
    אחד הדברים המופלאים המוגדרים בעזרת אינדוקציהרקורסיה הם המספרים של Conway:
    למשל: מגדירים פעולה של חבורה על כל הסודרים על ידי כך שבכל משבצת בלוח הפעולה רושמים את הסודר הקטן ביותר שלא סותר את תכונות הפעולה עבור משבצות קודמות (כלומר הסודר הקטן ביותר שעדיין לא הופיע באותה שורהעמודה). מוכיחים (באינדוקציה כמובן) שהתקבלה פעולה של חבורה חילופית וכל איבר נגדי של עצמו. קוראים לפעולה "חיבור" ומגדירים פעולה נוספת שקוראים לה "כפל": ממלאים את הטבלה לפי הסדר כך שבכל שלב (בהנחת דיסטריבוטיביות) לא יווצר מחלק אפס (פורמלית: מגדירים את המכפלה AB להיות הסודר הקטן ביותר שאינו Ab+aB+ab כאשר a כל סודר שקטן מ-A ו-b כל סודר שקטן מ-B. ואז מוכיחים באינדוקציה שמה שהתקבל מקיים את כל אקסיומות השדה, ושלכל פולינום עם מקדמים ב"שדה" זה יש שורש ב"שדה" (כלומר זה "שדה" סגור אלגברית, כאשר הסיבה היחידה למרכאות היא שזאת לא קבוצה). הבנייה היותר חשובה של מספרי Conway מגדירה חיבור וכפל עם יחס סדר ומקבלת מבנה גדול שמכיל בתוכו שדה שמכיל גם את הממשיים, גם את כל הסודרים (וכמובן הופכיים לכל אחד מהם ועוד כל מיני דברים נחמדים).

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

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

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

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

  14. הדוגמה עם המדרגות נכונה לגמרי – קרא שוב את ההנחות שם. לב העניין הוא בכך שמתמטית אפשר להוכיח טענה בסגנון "אם כך וכך עבור n אז גם כך וכך עבור n+1". התרנגולת לא יכולה לעשות את זה.

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

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

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

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

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

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

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

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

  19. לטל:
    באקסיומות ZF של תורת הקבוצות קיימת אקסיומה הקובעת שיש מה שנקרא "קבוצה אינדוקטיבית". קבוצה אינדוקטיבית מוגדרת להיות קבוצה ש
    (1) הקבוצה הריקה שייכת אליה
    (2) אם קבוצה x שייכת אליה אז גם {x U {x שייכת אליה
    כעת מכך שאנחנו יודעים שיש לפחות קבוצה אחת כזאת אנחנו מקבלים לפי אקסיומת ההפרדה שיש קבוצה אינדוקטיבית קטנה ביותר (כזאת שמוכלת בכל קבוצה אינדוקטיבית). את הקבוצה הזאת מזהים עם קבוצת המספרים הטבעיים N, כש-0 מזוהה עם הקבוצה הריקה ו- n+1 עם {n U {n לכל n. ניתן לראות שעבור הקבוצה הזאת מתקיים עיקרון האינדוקציה:
    אם תכונה P מתקיימת עבור 0, ואם מכך ש-P מתקיימת עבור n נובע שהיא מתקיים עבור n+1 – אז היא מתקיימת עבור כל N.
    זה נובע פשוט מכך שלפי ההגדרה קבוצת כל האיברים ב-N שמקיימים את P היא קבוצה אינדוקטיבית, ולכן היא בפרט מכילה את N ומכאן שווה לה. כעת בעזרת העקרון הזה אפשר להראות ש-N סדורה היטב על ידי הכלה וכו'.

    אם אתה מתעניין בנושא יש פיתוח מפורט שלו (ושל עוד הרבה דברים מעניינים אחרים) ב- Introduction to Set Theory של Hrbacek ו- Jech.

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

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

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

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

  23. אם כבר אני הייתי פותח קבוצה בפייסבוק: "יעוגל ה-pi ל- 3 !" 🙂

    פוסט מעולה!

    נ.ב. יש דרך לדמיין פיזיקה של עולם בה באמת pi הוא 3, או שזה מן הנמנעות?

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

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

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

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

  27. השם "אינדוקציה" הוא בחירה מאוד אומללה, שכן אינדוקציה (במתמטיקה) היא "אינסוף" צעדים, שכל אחד מהם הוא דדוקטיבי.

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

    יתכן שלא הבנת נכון את הטענות בגנותה של האינדוקציה?

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

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

  29. אם כך אנחנו באותו ראש 🙂

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

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

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

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

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

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

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

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

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

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

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

  38. זאת אינה התנגדות לאינדוקציה. אבל ניתן לשאול אם כך ובהינתן חוקי חזקות מדוע 1^אינסוף (1 בחזקת אינסוף) הינו גודל בלתי מוגדר.

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

  40. אני ממש לא צריך להזכיר כאן שחזקות מוגדרות גם עבור חזקות ממשיות. הבעיה נוצרת בביטוי 1^1/4 (אחד בחזקת רבע). מציגים את רבע כחצי כפול חצי ואז נוצר צורך להגדיר סדר פעולות. דרך אחת תוביל לחזקה ממשית (1 בחזקת 1 חלקי שורש שתיים) דרך אחרת עשויה (עלולה; תלוי את מי שואלים) להוביל ל i. הסדר הטוב (שקיים בטבעיים) תלוי במוסכמות שלנו איך מרחיבים שדות/חוגים וכאן התוצאות שמתקבלות תהיינה שונות מבחינה מתימטית

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

    אני עדיין לא רואה איך אתה מציע להגדיר את אחד בחזקת אינסוף בעזרת אינדוקציה.

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

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

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

  45. יותם – נראה לי שהיא תלך כך:
    1. ידוע שסוסים מסתובבים בשלישיות או יותר מכך, לחלופין, אין דבר כזה סוסים שמסתובבים לבד או בזוג.
    [מין דרך מצחיקה להגדיר קבוצה A – מכילה את כל המספרים הטבעיים שגדולים ממש מ – 2, A סדורה היטב כי היא תת קבוצה של כל הטבעיים].
    2. יש לי באורווה 3 סייחים ששלושתם כחולים.
    [מקרה פרטי – נוכיח שהאיבר המינימלי (3) מקיים תכונה M].
    3. נניח ש n סוסים כחולים, n שייך ל A.
    4. נוכיח ש n+1 סוסים כחולים [באותו אופן בדיוק עם הסייח השחור].

    -מסקנה: כל הסוסים כחולים…

    לדעתי הכשל נעוץ **לא** בגלל שזה לא נכון עבור n=2,
    אלא בגלל ש: "3 סוסים" [או n סוסים אם תרצה] לא מייצגים איבר ב – A שהוא מספר טבעי, אלא הם מייצג תת קבוצה שמכילה 3 איברים……….

    רוצה לומר: 3 סוסים **לא שווה** ל – 3 סוסים, זה לא אותו איבר כי יכול להיות שמדובר בסוסים שונים. ההקבלה בשלב 2 היא שגויה ולכן לא ניתן להשתמש באינדוקציה מתמטית.

    אבל קח את מה שאני אומר בערבון מוגבל, אין לי הכשרה מתמטית..

  46. יותר פשוט וקצר – אתה מבצע אינדוקציה מתמטית על קבוצות לא סדורות (אין משמעות ליחס בין סוס a ליחס בין סוס b – הם סוסים, לא מספרים).

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

    זה משהו כזה: קבוצה 1 מכילה לוויתן כחול, קבוצה 2 מכילה נמלה, ובגלל ש 2 גדול מאחד נסיק שנמלה גדולה מלוויתן כחול.

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

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *