אי אפשר להוכיח מתוך המתמטיקה שאין סתירות במתמטיקה
המקטע הזה יהיה טכני למדי.
אני אצרף דוגמאות, כדי שהוא יהיה יותר קריא, אבל זה יהפוך אותו ליותר ארוך.
טענות וגרירות בלוגיקה
טענה היא דבר שיכול להיות אמת או שקר.
בלוגיקה מסמנים טענות באותיות.
דוגמאות לטענות:
- שמונה גדול משבעים (שקר)
- קיים מספר המתחלק גם בשבע וגם בתשע (אמת)
- כל מספר המתחלק בשמונה - מתחלק גם בשש (שקר)
- לכל מספר X קיים מספר Y כך ש- Y גדול מ- X בריבוע (אמת).
יש גם יחסים בין טענות
- טענה יכולה להיות אמיתית או שקרית במודל.
- לכל טענה יש גם טענה נגדית.
- יש יחסי גרירה בין טענות.
ערכי אמת
לטענה במודל יש "ערך אמת", כלומר - אמת או שקר.
הטענה "שמונה מחלק את תשע" היא שקר במספרים שלמים. במספרים רציונאליים היא אמת (המנה היא תשע שמיניות - מספר רציונאלי ולא שלם).
הטענה הנגדית
אם נסמן את הטענה "x הוא מספר גדול מעשר" אז הטענה "לא x" היא הטענה "x אינו גדול מעשר" (וזה שקול לטענה "x קטן מעשר או שווה לו").
באופן דומה, אם נסמן את הטענה "יש אינסוף מספרים ראשוניים שמשאירים שארית שלוש בחלוקה לארבע" באות y, אז "לא y" היא הטענה "יש רק מספר סופי של מספרים ראשוניים אשר משאירים שארית שלוש בחלוקה לארבע".
יחסי גרירה בין טענות
גרירה מטענה בודדת*: הטענה "x זוגי וגם y זוגי" גוררת את הטענה "y זוגי". באופן דומה, הטענה "x זוגי" גוררת את הטענה "או ש- x זוגי, או ש- y זוגי"
גרירה מזוג טענות*: זוג הטענות "x גדול מ- y" ו- "y גדול מ- z" גוררת את הטענה "x גדול מ- z". דוגמא נוספת: זוג הטענות השקריות "בכל יום חמישי לא יורד גשם" ו- "היום יום חמישי" גורר את הטענה (הנכונה במקרה) - "היום לא יורד גשם". כאשר אחת מהטענות הגוררות אינה נכונה, אז המסקנה יכולה להיות נכונה או שקרית. כאשר שתיהן נכונות - המסקנה חייבת להיות נכונה (אמיתית).
על גרירה ועל אפשרות להוכיח
הטבע הלא אינטואיטיבי של גרירה בלוגיקה
גרירה בלוגיקה אינה מה שנהוג לחשוב.
אומרים שהטענה "A גורר B" היא אמת בשלושה מתוך ארבעה מצבים, ושקר רק ברביעי.
היא אמת בכל אחד מאלה:
- אם A נכון וגם B נכון.
- אם A לא נכון וגם B לא נכון.
- אם A לא נכון וגם B נכון.
הטענה היא שקר רק אם A נכון (אמיתי) ואילו B אינו נכון (שקרי).
כך, למשל, האמירה "אם אחד גדול משבע אז יש פילים ורודים על הירח" היא אמת: גם הרישא (הטענה שלפני הגרירה) וגם הסיפא (הטענה שאחרי הגרירה) הן שקריות - אחד לא גדול משבע, ואין פילים ורודים על הירח.
לא אינטואיטיבי, אבל ככה זה עובד.
כל טענה גוררת כל טענה הניתנת להוכחה
זו נקודה קצת קשה, אבל הכרחית:
כל טענה גוררת שאחד קטן משתים.
למה?
כאשר אומרים "טענה A גוררת את טענה B", המשמעות של זה היא למעשה: "אם מניחים את כל מערכת האקסיומות שלנו בצרוף טענה A, אז אפשר להוכיח את טענה B".
עכשיו, נניח שטענה B היא נכונה ממילא (וגם ניתנת להוכחה), בלי קשר לטענה A. המשמעות של זה היא שאפשר להוכיח את B מתוך האקסיומות בלבד. במקרה כזה ברור שאפשר להוכיח את B מתוך האקסיומות בצירוף A (פשוט לא נשתמש ב- A - A לא תפריע ולא תעזור". לכן מתקיימת הדרישה הצורנית: "אפשר להוכיח את B מתוך מערכת האקסיומות בצירוף A", שמשמעה "A גורר את B".
כך, קצת בניגוד לאינטואיציה, זה נכון ש:
- שמונה גדול משבעים גורר שאחד קטן משתים.
- שמונה קטן משבעים גורר שאחד גדול משתים.
- היום השלושים וחמישה במאי גורר ששבע הוא מספר ראשוני.
- "אם אין לחם - אין תורה" גורר שבשבוע יש שבעה ימים.
המבנה הלוגי הסטדנרטי וקיצורי דרך
במבנה הלוגי הסטנדרטי, טענה מובילה לטענה, ולבסוף להוכחה. אבל זה לא הכל - יש גם קיצורי דרך להוכחות.
כל קיצורי הדרך מסתמכים על המבנה הלוגי הסטנדרטי, אבל הם מפשטים בהרבה את העבודה. זה אומר שאם משתמשים בקיצורי הדרך, אפשר לפרוס את ההוכחה עם קיצורי דרך להוכחה בלי קיצורי דרך, במבנה הלוגי הסטנדרטי. ההוכחה החדשה תהיה נכונה וחוקית לחלוטין, אבל ארוכה, מיגעת, וקשה להבנה.
הוכחה בדרך השלילה
אחד מקיצורי הדרך החשובים ביותר הוא הוכחה בדרך השלילה.
קיצור הדרך הזה אומר כך:
כדי להוכיח טענה A מספיק לעשות שני דברים:
- להראות את שטענה מסויימת אחרת, B, היא ניתנת להוכחה (ולכן נחשבת גם לנכונה).
- להראות שאם לא A אז לא B.
דוגמא: אין מספר ראשוני המסתיים בספרה 6.
הטענה A (שאנחנו רוצים להוכיח): אין מספר ראשוני המסתיים בספרה 6.
הטענה הנגדית, "לא A": קיים מספר ראשוני המסתיים בספרה 6.
הטענה B, שיודעים שהיא ניתנת להוכחה: מספר המסתיים בספרה שש - מתחלק בשתים.
ההוכחה: נניח בשלילה (כך אומרים) ש- A אינה נכונה. כלומר, קיים
אם X הוא מספר ראשוני אז המחלקים היחידים שלו הוא X עצמו ואחד. כיוון שהוא מסתיים בשש,הרי שהוא שונה משתים, ולכן הוא לא מתחלק בשתים. כלומר, לא B.
זו כמובן סתירה לכך שאנחנו יודעים שאפשר להוכיח את B (הווה אומר: ש- X מתחלק בשתים).
בזאת הושלמה ההוכחה לפי דרך השלילה (או, כמו שנהוג לכתוב במתמטיקה: מש"ל. פעם זה היה ראשי תיבות של "מה שכתבתי למעלה" (הטענה שצריך היה להוכיח), והיום זה נחשב ראשי תיבות של "מה שצריך להוכיח". בלועזית נהוג לכתוב QED, שזה ראשי תיבות לטיניים).
עכשיו, אחרי שהנחנו את כל היסודות - קדימה להוכחה:
לֶמָה (טענת עזר): אם יש סתירה במתמטיקה, אז אפשר להוכיח כל דבר.
נקודה לשים לב: אם אפשר להוכיח כל דבר, אז אפשר להוכיח כל משפט, וגם את היפוכו.
מה זה שיש סתירה במתמטיקה? זה אומר שקיימת טענה, אפילו טענה אחת ויחידה, אשר אפשר להוכיח אותה וגם את היפוכה.
זו סתירה, כי לא יכול להיות שגם טענה וגם היפוכה יהיו נכונים.
נניח שיש סתירה במתמטיקה. נניח שהטענה אשר אפשר להוכיח אותה ואת שלילתה היא A. כלומר, אפשר להוכיח את A, ואפשר גם להוכיח את הטענה "לא A".
אמרנו שאפשר עכשיו להוכיח כל דבר - אז נבחר את הטענה שאנחנו רוצים להוכיח. נקרא לה B. נטפל בטענה הנגדית - "לא B".
כיוון שאפשר להוכיח את לא A (מהאקסיומות), וכיוון שכל טענה גוררת טענה שאפשר להוכיח מהאקסיומות, הרי שנכונה הטענה "לא B גורר לא A".
מאידך, כיוון שאפשר להוכיח את A, הרי שמתקיים הזוג הנדרש להוכחה בדרך השלילה:
- לא B גורר לא A.
- אפשר להוכיח ש- A.
לכן, מהוכחה בדרך השלילה נובע ש- B נכון.
ההוכחה הזו תופסת לכל טענה.
מסקנת ביניים:
אם במתמטיקה יש סתירה (כלומר, שוב, טענה אשר אפשר להוכיח אותה ואת היפוכה), אזי כל מה שאפשר לרשום כטענה - אפשר גם להוכיח.
עכשיו, אם אפשר להוכיח מתוך המתמטיקה שבתמטיקה אין סתירה, אז בפרט אפשר לרשום באופן מתמטי את הטענה "במתמטיקה אין סתירה".
נזכור שאם במתמטיקה יש סתירה, אז אפשר להוכיח כל טענה (כלומר, כל טענה שאפשר לרשום באופן מתמטי), ובפרט את הטענה שבתמטיקה אין סתירה.
כלומר, אם בכלל אפשר לרשום במתמטיקה את הטענה "אין סתירה במתמטיקה" (ונדמה לי שאפשר), ואם יש לה הוכחה, אז ההוכחה שלה יכולה לנבוע מכך שזו אמת, אבל יכולה גם לנבוע מכך שיש סתירה במתמטיקה, והסתירה הזו מאפשרת להוכיח כך דבר.
הערה לסיום: בגלל הקושי הזה היו מתמטיקאים אשר לא קיבלו את ההנחות שבבסיס הנחה בדרך השלילה. זה ויכוח ששייך יותר לפילוסופיה של המתמטיקה. אני מתייחס לזה כאל קוריוז - המתמטיקה בימינו מסתמכת הרבה מאד על הוכחה בדרך השלילה, ולא קל לכונן אותה בלי הוכחה בדרך השלילה.