הוכחות בדרך השלילה

מאת: עודד לבנה

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

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

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

דוגמא ראשונה
שאלה: איך יודעים שיש אינסוף מספרים?

התשובה הרגילה היא: כי לכל מספר אפשר להוסיף 1.

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

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

אגב, ראשי התיבות מש"ל הם תרגום של QED- Quod Erat Demonstrandum.
אלי בר יהלום סיפר לי שבפעם הראשונה שהשתמשו בהם משמעם היה
"מה שכתבתי למעלה" (למעלה נכתב "טענה:...) ורק במרוצת
הזמן שינו את משמעותם ל- "מה שרצינו להוכיח;".


רקע

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

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

הגדרה רקורסיבית:
אפשר להגדיר את N עצרת כך:
0 עצרת זה 1.
עבור כל מספר N גדול מ-0, מגדירים את N עצרת כמכפלה של N ב-1-N עצרת.
לדוגמא:
2! = 2
3! = 6
  4! = 24
   5! = 120
ומכאן ברכת המתמטיקאים ליום הולדת 24:
מזל טוב ל-!4, שיהיה לך עד !5.


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

שאלה: איך יודעים שיש אינסוף מספרים ראשוניים?

תשובה בלי דרך השלילה:
(אין לי מושג. אתם מוזמנים לנסות. תשובות בהמשך המאמר לא אנסה יותר להציג
בלי דרך השלילה.)

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

נעיר שאין כאן טענה שלכל N ראשוני N!+1 הוא ראשוני.
(לדוגמא: ל-121, 5 אינו ראשוני, כי הוא 11 בריבוע).
הטענה היא שהמספר N!+1 אינו מתחלק לאף ראשוני הקטן מ-N או שווה לו.

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

הרקע הלוגי הוא שאם הטענה "לא quot;A& מביאה לסתירה, אז A נכונה.


חידות הנפתרות בדרך השלילה

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

עיקר הפתרון
נכנה את האנשים א, ב, ג, ד, ה, ו.
נניח בשלילה שאין אף שלישיה שלחצה ידיים ואף שלישיה שלא לחצה ידיים.
נביט באדם א.
נחלק את האנשים לאלה שלחצו איתו ידיים ואלה שלא לחצו איתו ידיים.
חילקנו חמישה אנשים לשתי קבוצות. לכן, לפי עיקרון השובך, יש לפחות קבוצה אחת
אשר יש בה לפחות שלושה אנשים.
(האמת, במקרה הפשוט הזה לא צריך שובך כדי להבין זאת).
נניח שזו הקבוצה של אנשים שלחצו ידיים עם א.
(אם אלו האנשים אשר לא לחצו ידיים עם א, אז ההוכחה דומה,
ויש להחליף בכל מקום את "לחצו" ב-&לא לחצו;" quot; )
נניח שהאנשים האלה הם ב, ג, ו- ד. (אלה רק שמות. אפשר להניח שאלו שמותיהם).
יש לנו האפשרויות הבאות:
1. אם ב לחץ עם ג- אז א-ב-ג זו שלישיה שלחצה ידיים.
;nbsp;   &לכן, שלחצה ידיים לפי הנחת השלילה (שאין שלישיה)- ב לא לחץ יד עם ג.
2. אם ב לחץ עם ד- אז א-ב-ד זו שלישיה שלחצה ידיים.
;nbsp;   &לכן, לפי הנחת השלילה, ב לא לחץ יד עם ד.
3. אם ג לחץ עם ד- אז א-ג-ד זו שלישיה שלחצה ידיים.
;nbsp;   &לכן, לפי הנחת השלילה, ד ג לא לחץ יד עם.

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


השורש של 2