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

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

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

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

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

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

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

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

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

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

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.