הוכחה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

דוגמה להוכחה בגאומטריה אלגברית. סיום ההוכחה מסומן בהלמוש.


מאפיינים של הוכחות[עריכת קוד מקור | עריכה]

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

להוכחה משמשות טכניקות אחדות:

ניתן להבדיל בין שני סוגים של הוכחות:

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

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

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

נהוג לחתום הוכחות על ידי סימון מוסכם: בעברית: מש"ל (=מה שהיה להוכיח), באנגלית: .Q.E.D (מלטינית: quod erat demonstrandum, במובן שזהה מילולית אל זה של הביטוי העברי הנ"ל). לחלופין, נוהגים לעתים בימינו לסמן את סוף ההוכחה על ידי ציור של ריבוע ריק או מלא ( ) הנקרא הלמוש. חכמי התלמוד הבבלי, נהגו לחתום הוכחות בסימן ש"מ (מארמית: "שמע מינה"; מילולית: תשמע מזה [את מה שהיה להוכיח]).

השערה[עריכת קוד מקור | עריכה]

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

  • מרכוס דה סוטוי, חובת ההוכחה, באתר ynet‏, 15 בנובמבר 2006 (תיקוני טעויות מופיעים בטוקבק)