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