מבוא למתמטיקה אוניברסיטאית/הוכחה בשלילה

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

אופן השימוש

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

דוגמא – קיום אינסוף מספרים הראשונים

אחד השימושים הראשונים המתועדים לשימוש בהוכחה בשלילה נעשה ע"י המתמטיקאי היווני אוקלידס בהוכחתו כי קיימים אינסוף מספרים ראשוניים.

מהלך ההוכחה:
רוצים להוכיח כי קיימים אינסוף מספרים ראשוניים.

נניח בשלילה את ההפך, כלומר כי קיימים רק מספר סופי של מספרים ראשוניים, אותם נסמן $a_{1},\ldots ,a_{n}$ .

כעת, נביט במספר b השווה ל- $a_{1}\times \cdots \times a_{n}+1$ . המספר הזה מתחלק עם שארית אחד בכל המספרים הראשוניים הקיימים, כלומר הוא לא מתחלק בהם. מכאן שהמספר b הוא אחד מן השניים: או ראשוני והגענו לסתירה פנימית, או מתחלק לראשוני נוסף הגדול מכל הראשוניים הנתונים, בכל מקרה מצאנו ראשוני נוסף - דבר הנתון בסתירה להנחה שקיימים רק הראשוניים הנתונים בתחילה.

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

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

הפרק הקודם: אינדוקציה

הוכחה בשלילה

-