משפט השלמות של גדל

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

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

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

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

הוכחת שקילות הניסוחים

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

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

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