לכל מאן דבעי!

במסגרת לימודיי נתקלתי בשאלה שעלתה בראשי בעודי פותר תרגיל באינדוקציה.

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

אני אשמח אם מישהו יסביר לי איך אפשר ללמוד זאת ע"י איפוס ביטוי?

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