רעיון בסיסי - אינדוקציה על הטבעיים
בשביל להוכיח שטענה מסוימת נכונה עבור כל מספר טבעי
(למשל
) מספיק להוכיח את הבאים:
- (בסיס האינדוקציה) הטענה מתקיימת עבור
כלומר
מתקיים
- (צעד האינדוקציה)אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר
.
למה זה מספיק?
בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור כלומר
מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור
(שזה אכן כך) אז הטענה נכונה גם עבור
כלומר
. אה! אז עכשיו זה נכון עבור
אז לפי אותה טענה זה נכון גם עבור
! ומה עכשיו? אם זה נכון עבור
זה נכון עבור
. וכן על זה הדרך. אפשר להשתכנע שבסופו של דבר
נכון לכל
דוגמא:
נוכיח באינדוקציה כי הטענה
נכונה לכל
טבעי
הוכחה:
עבור אכן מתקיים כי
כעת נראה שאם הטענה נכונה עבור כלשהוא, כלומר אם מתקיים
אזי הטענה נכונה עבור
, כלומר
. כלומר נוכיח ש:
נוכיח:
לפי הנחת האינדוקציה אפשר להמשיך הלאה
וסיימנו
דוגמא נוספת:
הוכח כי לכל מספר טבעי מתקיים כי
פתרון:
עבור אכן מתקיים
כעת נניח שהטענה נכונה עבור ונוכיח את הטענה עבור
לפי הנחת האינדוקציה ניתן להמשיך
שזה הטענה עבור וסיימנו.
סדר טוב
הגדרה: יהי יחס סדר חלקי על קבוצה
.
יקרא סדר טוב אם לכל
קיים איבר מינימום/הכי קטן/ראשון ב
.
מינוח: נאמר כי סדורה היטב.
דוגמא: הקס"ח היא סדורה היטב - תתי הקבוצות הלא ריקות שלה הן
והאיבר הראשון בכל תת קבוצה הוא בהתאמה
.
עקרון הסדר הטוב
נסתכל על - קבוצת הטבעיים עם יחס הסדר "קטן שווה" הסטנדרטי.
אינטואיטיבית, אכן מתקיים כי לכל קבוצה לא ריקה של טבעיים קיים איבר ראשון - "אם 1 שם, הוא הקטן ביותר; אם 2 שם, הוא הקטן ביותר; ממשיכים כך עד שמגיעים לאיבר כלשהו (כי הקבוצה לא ריקה), והוא הקטן ביותר".
פורמלית, טענה זו, הנקראת עקרון הסדר הטוב, והיא שקולה לטענת (/אקסיומת) האינדוקציה.
דוגמא נוספת: ניתן להגדיר אל יחס סדר חלקי לפי התמונה הבא (כאשר מזהים כל שבר עם זוג סדור ומבטלים את החזרות המיותרות)
התבוננו והשתכנעו שזה גם סדר טוב.
הערה: זה בניגוד לסדר "קטן שווה" הרגיל על השברים שאינו סדר טוב כי לקבוצה
אין איבר מינימום.
משפט הסדר הטוב
משפט הסדר הטוב קובע שלכל קבוצה קיים סדר טוב.
תרגיל:
תהא קבוצה בת מנייה. הוכח כי ניתן לסדר אותה היטב (בהינתן עקרון הסדר הטוב).
פתרון:
לפי הנתון קיימת פונקציה חח"ע ועל .
נגדיר את היחס הבא על
כך:
. זהו יחס סדר (השתכנעו!).
בנוסף,
סדורה היטב על ידו: תהא
תת קבוצה לא ריקה. אזי
תת קבוצה לא ריקה ולכן קיים בה איבר מינימום נסמנו
. בדקו כי
איבר מינימום.
הכללות
הכללה פשוטה 1
הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה ש:
- הטענה מתקיימת עבור
מסוים כלומר
מתקיים
- אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר
.
אז באופן דומה הטענה נכונה נכונה עבור
כלומר - במקום להוכיח עבור ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור
ואז הטענה מתקיים החל מ-k
דוגמא:
הוכח כי לכל מתקיים
לכל
פתרון:
עבור נקבל
כי
כעת נניח כי הטענה נכונה עבור כלשהוא, כלומר מתקיים
נוכיח עבור מהנחת האינדוקציה נקבל כי
וסיימנו
הכללה פשוטה 2
אם נוכיח עבור טענה ש:
- הטענה מתקיימת עבור
מסוים כלומר
מתקיים
- אם הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים
(כלומר מתקיים
עבור
) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר
מתקיים).
אז באופן דומה הטענה נכונה נכונה עבור
כלומר - אפשר להחליף את ההנחה שמתקיים עבור ולהוכיח עבור
בהנחה שמתקיים עבור כל מי שקטן שווה
ולהוכיח עבור
דוגמא:
כל מספר טבעי ניתן להציגו כמכפלה של מספרים ראשוניים
הוכחה:
עבור זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.
כעת נניח שהטענה נכונה לכל ונוכיח עבור
אם ראשוני - סיימנו כי אז הוא הפירוק של עצמו.
אחרת מתפרק למכפלה
כאשר
לפי הנחת האינדוקציה
מתפרקים למכפלה של מספרים ראשוניים
כאשר
ראשוניים
ואז
וסיימנו
הכללה מעמיקה
תהא קבוצה סדורה היטב (נסמן את היחס שלה ב
) בת מניה אז ניתן להוכיח שטענה
מתקיימת לכל
ע"י הוכחת הטענה הבא:
- אם הטענה
נכונה עבור
אז הטענה נכונה עבור
.
למה זה עובד?
נניח בשלילה כי הטענה לא מתקיימת לכל
אזי נגדיר
- קבוצת כל האיברים ב
שעבורם הטענה אינה נכונה. מהנחת השלילה
.
כיוון ש סדורה היטב אזי קיים ב
מינימום, נסמנו
. לפי הגדרת מינימום והגדרת
נובע כי לכל
הטענה נכונה (אם היה
שהטענה לא נכונה לגביו אזי הוא היה בקבוצה
ואז זה היה סתירה לכך ש
מינימום של קבוצה זאת).
אבל אם זה כך אז לפי הטענה שמוכיחים זה גורר כי כן מתקיים. סתירה. ולכן הטענה נכונה לכל
הערה: אפשר לעשות אינדוקציה הנקראת אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)
תרגילים יותר מעניינים
תרגיל:
יהיו קבוצות אזי
הוכחה:
עבור זה נכון כי הפרש סימטרי של 2 קבוצות זה כל ה
- ים שנמצאים או בראשונה בלבד או בשניה בלבד.
נניח כי הטענה נכונה עבור קבוצות. נוכיח עבור
קבוצות:
כאשר
לפי הנחת האינדוקציה מתקיים ולכן ניתן להמשיך כך
לכן, הטענה נכונה גם עבור וסיימנו
תרגיל:
הוכיחו בעזרת אינדוקציה כי כל מצולע קמור (כלומר הצלע בין כל שני קודקודים נמצאת בפנים המצולע) בן צלעות ניתן לשילוש (כלומר ניתן לחלק אותו למשולשים)
ושיש בשילוש עיבוד הנוסחה נכשל (שגיאת לקסינג): n − 3
אלכסונים.
פתרון:
עבור : מצולע קמור בן 3 צלעות חייב להיות משולש (ייתכן בעיוות כלשהוא) ולכן הוא ניתן לשילוש ע"י
אלכסונים.
כעת נניח שהטענה נכונה עבור כל מצולע קמור בן ונוכיח את הטענה עבור מצלוע קמור בן
צלעות (כלומר שכל מצולע קמור בן
ניתן לשילוש עם
אלכסונים). יהא מצולע קמור
בן
צלעות. נמתח קו בין שני קודקודים שלו. כעת המצולע שהתחלנו איתו התחלק לשני מצולעים קמורים, נסמנם
. נסמן את מספר הצלעות של
ב
(כלומר יש לו
צלעות משותפות עם
+ הצלע שהוספנו. מספר הצלעות של
הוא
ולכן מספר הצלעות המשותפות בין
ל
הוא
ולכן מספר הצלעות של
הוא
.
כיוון ש
ניתן להפעיל את הנחת האינדוקציה על
ולהסיק כי
ניתן לשילוש ע"י
אלכסונים.
צירוף השילושים של
יתן שילוש של
עם
אלכסונים כנדרש.
תרגיל:
יהיו מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחא
הוכחה (באינדוקציה על מספר המטריצות):
עבור זה ההגדרה של כפל בין 2 מטריצות
כעת, נניח שהטענה נכונה עבור כל שהוא. נוכיח נכונות עבור
לפי הנחת האינדוקציה נמשיך:
וסיימנו.
אזהרה
אינדוקציה היא כלי חזק אך יש לשים לב כי משתמשים בו נכונה.
דוגמא מפורסמת להוכחת שגויה באינדוקציה היא הדוגמא הבא:
טענה: כל קבוצה של סוסים לא ריקה מכילה סוסים מצבע יחיד.
"הוכחה": נוכיח בעזרת אינדוקציה על מספר האיברים בקבוצת הסוסים.
עבור אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד
כעת נניח כל קבוצה עם סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל
תהא קבוצה עם
סוסים אזי לפי הנחת האינדוקציה
ו
הן קבוצות שמכילות סוסים מצבע יחיד (כי אלו קבוצות סוסים מגודל
)
ולכן כל הסוסים ב
ג"כ בעלי צבע יחיד (כי יש חפיפה בין
ובין
.
חישבו איפה השגיאה (רמז: במעבר מ ל
)