הוכחה משתמשת בכללים להסקת מסקנות, אך יש בה גם שימוש נרחב בשפה טבעית, ולכן עלולה להיות בה עמימות הנובעת מעמימותה של השפה. כדי להימנע מעמימות זו ניתן להשתמש בהוכחה פורמלית.
להוכחה משמשות טכניקות אחדות:
ניתן להבדיל בין שני סוגים של הוכחות:
משפט ארבעת הצבעים, שהוכח בשנת 1976, היה המשפט הראשון שלהוכחתו נדרשה הסתייעות מהותית במחשב. עובדה זו עוררה פולמוס בין המתמטיקאים סביב השאלה האם הוכחה כזו, שאדם אינו יכול לבדוק אותה בכוחות עצמו, יכולה להיחשב כהוכחה מתמטית תקפה.
פעמים רבות ניתן להוכיח טענה מסוימת בדרכים שונות, ולעיתים אף דרכים רבות למדי. משפט פיתגורס נודע במאות הוכחות שניתנו לו. למשפט הקובע שהמספרים הרציונליים הם קבוצה בת מניה מופיעות בוויקיפדיה העברית שלוש הוכחות שונות, בערכים: קבוצה בת מנייה, מספר רציונלי ועוצמה.
נהוג לחתום הוכחות על ידי סימון מוסכם: בעברית: מש"ל (=מה שהיה להוכיח), באנגלית: .Q.E.D (מלטינית: quod erat demonstrandum, במובן שזהה מילולית אל זה של הביטוי העברי הנ"ל). לחלופין, נוהגים לעיתים בימינו לסמן את סוף ההוכחה על ידי ציור של ריבוע ריק או מלא () הנקרא הלמוש. חכמי התלמוד הבבלי, נהגו לחתום הוכחות בסימן ש"מ (מארמית: "שמע מינה"; מילולית: תשמע מזה [את מה שהיה להוכיח]).
השערה.
טענות לא מעטות דרשו מאות רבות של שנים עד להוכחתן או להפרכתן. דוגמאות לכך הן המשפט האחרון של פרמה שזכה להוכחה כשלוש מאות וחמישים שנה לאחר שהועלה, ושלוש הבעיות של ימי קדם, שהוכחו כבלתי ניתנות לפתרון כאלפיים שנה לאחר שהוצגו. בעיות פתוחות (כאלה שטרם זכו להוכחה או להפרכה) רבות ממשיכות ללוות את המתמטיקה, ובין המפורסמות שבהן ניתן למנות את השערת גולדבך והשערת רימן.
האם כל השערה ניתנת להוכחה או להפרכה? שאלה זו תלויה קודם כל במערכת האקסיומות בה אנחנו משתמשים. כיוון שכל הוכחה בנויה משימוש חוזר ונשנה באקסיומות ובכללי ההיסק קביעת אוסף שונה של אקסיומות תתן אוסף שונה של משפטים שניתן להוכיח. לא ניתן לבחור את האקסיומות בצורה שרירותית לחלוטין: אם קיימת סתירה באוסף האקסיומות שלנו אז ניתן להוכיח מתוכו כל משפט (כלומר ניתן להוכיח גם טענה וגם את שלילתה), ולכן אוסף זה אינו מעניין.
אוסף אקסיומות שלא מכיל סתירה נקרא עקבי. לאוסף כזה של אקסיומות יש מודלים שמממשים אותן, ומשפט השלמות של גדל טוען שאוסף המשפטים שניתן להוכיח מתוך האקסיומות הוא בדיוק אוסף המשפטים שמתקיימים בכל המודלים שמממשים את האקסיומות. לכן, אם לא ניתן להוכיח או להפריך טענה מסוימת מתוך מערכת אקסיומות נתונה, ניתן להוסיף אותה או את שלילתה לאוסף האקסיומות ולקבל אוסף עקבי חדש של אקסיומות.
מצד שני, ניתן לשאול האם קיים אוסף אקסיומות שהוא מצד אחד עקבי ומצד שני מספיק רחב כדי שיהיה אפשר להוכיח מתוכו או להפריך מתוכו כל טענה? משפט אי השלמות הראשון של גדל נותן תשובה שלילית לשאלה הזו עבור מקרים מעניינים רבים. מערכות אקסיומות שניתן לנסח בהן חלק מספיק משמעותי מהאריתמטיקה, לא יכולות להיות מצד אחד גדולות מספיק כדי שיהיה ניתן להוכיח או להפריך מתוכן כל טענה ומצד שני פשוטות לתיאור. באופן פורמלי: בתורה עקבית - שהאקסיומות שלה ניתנות לזיהוי מכני [="אפקטיבי"] - ושניתן לפתח בה את האריתמטיקה (של החיבור ושל הכפל), תמיד תהיינה השערות אשר מחד גיסא ניתנות לניסוח (בשפתה של התורה), ואשר מאידך גיסא אינן ניתנות להוכחה ואף לא להפרכה (במסגרת אותה תורה).
לעומת זאת, תחשיב פסוקים - המהווה את הבסיס של הלוגיקה המתמטית - הוא שלם, ולכן לא יהיו בו מקרים כאלו. קיימים ענפים נוספים - כוללניים יותר - שהם שלמים (במובן זה), למשל תחשיב הכמתים (ללא סימני פונקציות/יחסים ואף ללא סימן השויון) מסדר ראשון, ואפילו האריתמטיקה של החיבור (ללא הכפל).
ארץ הקודש
הבעיות הגאומטריות של ימי קדם
הבעיות הגאומטריות של ימי קדם הן בעיות בנייה שנוסחו על ידי היוונים הקדמונים, והעסיקו מתמטיקאים במשך מאות שנים. הבעיות הן:
את כל הבניות יש לבצע במסגרת כללי המשחק של הגאומטריה, כלומר באמצעות בנייה בסרגל ובמחוגה בלבד (הסרגל ללא שנתות ואינו יכול למדוד אורך).
רק במאה התשע-עשרה הושם קץ לניסיונות לפתור בעיות בנייה אלה, כאשר הוכח בעזרת תורת גלואה שהן לא פתירות, כלומר אין דרך לבצע את הבניות הנדרשות. עד למועד זה תרמו הניסיונות לפתרון בעיות אלה להתפתחותה של הגאומטריה.
כמוצא זמני מחוסר היכולת לפתור בעיות אלה בכלים המצומצמים של הבנייה הגאומטרית (סרגל ומחוגה), המציאו היוונים כלים משוכללים המאפשרים את ביצוע הבנייה הנדרשת.
בעיה נודעת נוספת, בעלת אופי שונה והשפעה מרחיקת לכת על הגאומטריה העתיקה והמודרנית, היא הבעיה של הוכחת אקסיומת המקבילים, האקסיומה החמישית של אוקלידס, מתוך האקסיומות האחרות.
הכפלת נפחה של קובייה.
על פי האגדה, בשנת 430 לפנה"ס השתוללה באתונה מגפת דבר קשה. כאשר נשאל האורקל שבמקדש אפולו שבעיר דלפי כיצד לעצור את המגפה, ענה: הכפילו את נפח המזבח לאפולו. מזבח זה היה בצורת קובייה. האתונאים בנו מזבח חדש שאורך צלעו כפול מזה של המזבח הקיים. משלא נפסקה המגפה הבינו האתונאים את טעותם: נפח המזבח החדש היה גדול פי שמונה (שתיים בחזקת שלוש) מנפח המזבח המקורי. כך נולדה הבעיה הראשונה: כיצד לבנות קובייה שנפחה כפול מזה של קובייה נתונה. ליתר דיוק: כאשר נתונה צלע של קובייה, לבנות צלע של קובייה שנפחה כפול.
היפוקרטס מחיוס ניסח מחדש את הבעיה, כך שנדרשת מציאת שני ממוצעים גאומטריים עוקבים המשתלבים בין קטע נתון ובין קטע כפול באורכו. הוא ומנכמוס הראו שאפשר לפתור בעיה זו על ידי חיתוך פרבולה והיפרבולה, או שתי פרבולות כמו formula_1 ו- formula_2.
במאה השנייה לפני הספירה הראה דיוקלס כיצד להכפיל את הקוביה באמצעות הציסואידה. ניוטון השתמש לצורך כך בעקום החלזון של פסקל, ה-limacon.
הכפלת הקוביה דורשת בנייה של קטע שאורכו formula_3, והיום ידוע שמספר זה אינו ניתן לבנייה בסרגל ומחוגה. לכן לא ניתן להכפיל את הקובייה בעזרת סרגל ומחוגה בלבד.
תרבוע העיגול.
בעיית תַּרְבּוּעַ העיגול (או ריבוע העיגול) דורשת לבנות ריבוע השווה בשטחו לעיגול נתון. לבעיה זו הוצעו כל כך הרבה פתרונות שגויים, עד שבשנת 1775 החליטה האקדמיה הצרפתית למדעים שלא לבדוק יותר פתרונות לבעיה זו.
שטחו של מעגל שווה ל-πR2, כלומר רדיוסו בחזקה שנייה כפול פאי, ושטחו של ריבוע הוא formula_4, כלומר צלעו בחזקה שנייה. מכך מתקבל שעלינו לבנות קטע שאורכו הוא הרדיוס כפול שורש פאי. מתכונותיו של שדה המספרים הניתנים לבנייה נגזר שאם ניתן לבנות קטע באורך formula_5 ניתן גם לבנות קטע באורך formula_6, ולהפך.
בשנת 1882 הוכיח פרדיננד לינדמן את משפט לינדמן שקובע שעבור כל α אלגברי שאינו 0, formula_7 הוא מספר טרנסצנדנטי. מכאן ניתן להוכיח בשלילה שפאי טרנסצנדנטי. נניח שפאי הוא מספר אלגברי. מכיוון ש-i (השורש הריבועי של 1-) אלגברי, גם המכפלה של i ופאי אלגברית. זהות אוילר קובעת כי :formula_8
, ולכן 1- הוא טרנצנדנטי, מה שבבירור לא נכון. מכאן נובע ש־formula_5 הוא מספר טרנסצנדנטי. מהוכחה זו נובע שלא ניתן לבנות ריבוע השווה בשטחו לעיגול נתון, משום שבבנייה באמצעות סרגל ומחוגה בלבד לא ניתן לבנות יחס טרנסצנדנטי.
חלוקה לשלוש (טריסקציה) של זווית.
בעיה זו דורשת לחלק זווית נתונה לשלושה חלקים שווים. מתברר שאפילו את הזווית של שישים מעלות לא ניתן לחלק לשלושה, כלומר, לא ניתן לבנות במחוגה וסרגל זווית של עשרים מעלות. הראשון שהוכיח תוצאה זו היה Pierre Laurent Wantzel, (1814--1869), ב-1837.
עם זאת, תחת ההיתר לסמן על הסרגל סימן אחד, הבעיה פתירה.
בנית מצולע משוכלל בן שבע צלעות.
ראו בנייה בסרגל ובמחוגה לדיון כללי בבנייה של מצולעים משוכללים.
קבוצה (מתמטיקה)
קבוצה היא מושג יסודי במתמטיקה. בגישה הנאיבית לתורת הקבוצות, קבוצה היא אוסף כלשהו של איברים (ללא חשיבות לסדר). בתורת הקבוצות האקסיומטית מושג הקבוצה אינו מוגדר, ותכונותיו מתקבלות מרשימת האקסיומות.
נהוג להציג קבוצה באמצעות סוגריים מסולסלים, שבתוכם מפורטים כל איברי הקבוצה (למשל {כלב, חתול, צרצר} ), או מופיע כלל לפיו נוצרים כל איברי הקבוצה (למשל {x :x אזרח סין} ). לעיתים מוצגת הקבוצה באמצעות רשימה של חלק מאיבריה שבסופם '...' (שלוש נקודות), מתוך הנחה שהקורא יסיק מהחלק הנתון את יתר איברי הקבוצה.
עצמים הנמצאים בקבוצה הם איברי הקבוצה. בין האיברים לא חייב להיות קשר כלשהו מעבר לכך. כאשר עצם כלשהו הוא איבר בקבוצה נאמר שהוא שייך לקבוצה, על כל עצם אחר נאמר שהוא לא שייך לקבוצה זו. אפשר שגם עצם השייך לקבוצה הוא קבוצה בעצמו.
הגדרה.
בתיאור נאיבי קבוצה היא אוסף של עצמים. כל עצם בעולם, או שהוא שייך לקבוצה (ואז הוא נקרא איבר של הקבוצה) או שאינו שייך לה. לא ניתן להיות איבר של קבוצה יותר מפעם אחת. שתי קבוצות הן שוות כאשר יש להן בדיוק אותם האיברים.
כאשר רוצים לבסס את תורת הקבוצות באופן ריגורוזי נחוצה הגדרה קשוחה יותר שאינה מסתמכת על תאורים עמומים. ההגדרה המקובלת ביותר לקבוצה היא באמצעות אקסיומות ZF הכתובות בשפה מסדר ראשון. האקסיומות מגדירות יקום שלאיבריו אנו קוראים קבוצות ומוגדר עליהן יחס של שייכות. ביקום יש רק קבוצות ולכן איבריה של קבוצה הם תמיד קבוצות בעצמם. האקסיומות מטילות מספר מגבלות על מה ראוי להיקרא קבוצה (למשל קבוצה לא יכולה להיות שייכת לעצמה) כדי למנוע סתירות דוגמת הפרדוקס של ראסל.
כמעט כל עצם במתמטיקה ניתן להגדיר כקבוצה, ולכן ניתן לומר שהיקום שנוצר על ידי אקסיומות ZF הוא זירת המשחקים לכמעט כל המתמטיקה.