משפט השלמות של גדל, ההוכחה (חלק ב')

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

לפני שנזכיר מה זה בכלל עדים וניגש לחלק הזה בהוכחה, בואו נסיים עם ה”עקבית מקסימלית” שהוא פשוט יותר מכיוון שכבר עשינו את זה בדיוק בהוכחת משפט השלמות לתחשיב הפסוקים. נניח שיש לנו תורה עקבית \( \Phi \) ואנחנו רוצים להרחיב אותה לתורה עקבית מקסימלית \( \Phi^{\prime} \); פשוט נמספר את כל הפסוקים הקיימים, \( \varphi_{1},\varphi_{2},\varphi_{3},\dots \) ואז נגדיר אינדוקטיבית סדרה של תורות \( \Phi_{0},\Phi_{1},\Phi_{2},\dots \) באופן הבא: \( \Phi_{0}=\Phi \) ולכל \( n \), אם \( \Phi_{n}\cup\left\{ \varphi_{n}\right\} \) עקבית אז \( \Phi_{n+1}=\Phi_{n}\cup\left\{ \varphi_{n}\right\} \) ואחרת \( \Phi_{n+1}=\Phi_{n} \). לבסוף נגדיר \( \Phi^{\prime}=\bigcup_{n=0}^{\infty}\Phi_{n} \). ברור ש-\( \Phi^{\prime} \) עקבית בזכות תעלול סטנדרטי שמסתמך על סופיות של הוכחות: אם \( \Phi^{\prime} \) אינה עקבית אז היא מוכיחה דבר והיפוכו, ושתי ההוכחות הללו סופיות ולכן משתמשות במספר סופי של הנחות מתוך \( \Phi^{\prime} \) ולכן, אם \( n \) הוא האינדקס המקסימלי של הנחה שבה משתמשים בהוכחות הללו, כבר \( \Phi_{n} \) אינה עקבית, בסתירה לתהליך הבניה שלנו.

כדי לראות ש-\( \Phi^{\prime} \) עקבית מקסימלית בואו ניקח תורה עקבית כלשהי שמכילה אותה, \( \Phi^{\prime}\subseteq\Psi \) ונראה שהן שוות. אם \( \varphi\in\Psi \) אז בפרט \( \Phi^{\prime}\cup\left\{ \varphi\right\} \) עקבית; נסתכל על המספור של \( \varphi \) בסידור של הפסוקים שלנו, אז \( \varphi=\varphi_{n} \) עבור \( n \) כלשהו. מכיוון ש-\( \Phi^{\prime}\cup\left\{ \varphi_{n}\right\} \) עקבית כך גם \( \Phi_{n}\cup\left\{ \varphi_{n}\right\} \) ולכן הוספנו את \( \varphi_{n} \) ל-\( \Phi_{n+1} \) ומכאן ש-\( \varphi\in\Phi^{\prime} \) כנדרש. בקיצור, ההוכחה הזו פשוטה מאוד.

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

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

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

בואו נעבור כעת לאתגר האמיתי: נתונה לנו תורה עקבית \( \Phi \) ואנחנו רוצים להרחיב אותה לתורה עקבית \( \Phi^{\prime} \) ואת המילון למילון מורחב \( \tau^{\prime} \) כך שקיימת קבוצת עדים \( C \). נזכיר מה זה אומר: זה אומר שלכל נוסחה \( \varphi\left(x\right) \) עם משתנה חופשי יחיד \( x \) קיים קבוע \( c\in C \) כך ש-\( \Phi^{\prime}\vdash\exists x\varphi\left(x\right)\to\varphi\left(c\right) \).

הרעיון הוא כזה: את \( \tau \) נרחיב על ידי כך שניקח קבוצה בת מניה \( C \) של סימנים שלא מופיעים ב-\( \tau \) ונוסיף אותה לאוסף הקבועים של \( \tau \). כעת נמספר את כל הנוסחאות עם משתנה חופשי יחיד, \( \varphi_{1}\left(z_{1}\right),\varphi_{2}\left(z_{2}\right),\varphi_{3}\left(z_{3}\right),\dots \). אני בכוונה משתמש כאן במשתנה \( z \) כדי להבהיר שהאינדקס שלו הוא אינדקס שמתאים ל-\( \varphi \) שלו, לא לערך ה”אמיתי” שלו. מבלבל? הכוונה שלי היא לכך שייתכן ש-\( \varphi_{1} \) היא הנוסחה \( \forall x_{17}\left(x_{17}=f\left(x_{17}\right)\right) \), כלומר כאן \( z_{1}=x_{17} \). למי שעדיין לא עוקב - לא לדאוג, זה חסר כל חשיבות להמשך.

עכשיו נעשה את הדבר הצפוי ביותר בעולם. נגדיר סדרה \( \Phi_{0},\Phi_{1},\Phi_{2}, \) של תורות באופן הבא: \( \Phi_{0}=\Phi \) ולכל \( n\ge1 \) , \( \Phi_{n+1}=\Phi_{n}\cup\left\{ \exists z_{n}\varphi_{n}\left(z_{n}\right)\to\varphi_{n}\left(c_{n}\right)\right\} \), כאשר \( c_{n} \) הוא איבר כלשהו מתוך \( C \) שטרם נבחר (כלומר, אינו שייך לקבוצה \( \left\{ c_{1},c_{2},\dots,c_{n-1}\right\} \) - קיים כזה כי זו קבוצה סופית ואילו \( C \) אינסופית). לבסוף נגדיר \( \Phi^{\prime}=\bigcup_{n=0}^{\infty}\Phi_{n} \). ברור לגמרי שקיבלנו תורה ש-\( C \) היא קבוצת עדים עבורה. השאלה היחידה היא האם \( \Phi^{\prime} \) עקבית. כמו קודם, מספיק להוכיח שאם \( \Phi_{n} \) עקבית אז \( \Phi_{n+1} \) עקבית, כלומר ש-\( \Phi_{n}\cup\left\{ \exists z_{n}\varphi_{n}\left(z_{n}\right)\to\varphi_{n}\left(c_{n}\right)\right\} \) עקבית. כאן סוף סוף נצטרך טיפונת להפשיל שרוולים.

אם כן, הבה ונניח ש-\( \Phi_{n}\cup\left\{ \exists z_{n}\varphi_{n}\left(z_{n}\right)\to\varphi_{n}\left(c_{n}\right)\right\} \) אינה עקבית. באופן כללי, אם \( \Phi\cup\left\{ \psi\right\} \) אינה עקבית אז \( \Phi\vdash\neg\psi \) - זה נובע מהאקסיומות של תחשיב הפסוקים. וכבר ראינו את זה אז (ליתר דיוק אז זה היה שאם \( \Phi\cup\left\{ \neg\psi\right\} \) אינה עקבית את \( \Phi\vdash\psi \) אבל זה אותו הדבר). מכאן ש-\( \Phi_{n}\vdash\neg\left[\exists z_{n}\varphi_{n}\left(z_{n}\right)\to\varphi_{n}\left(c_{n}\right)\right] \). אני טוען שנובעים מכך שני דברים: \( \Phi_{n}\vdash\exists z_{n}\varphi_{n}\left(z_{n}\right) \) וגם \( \Phi_{n}\vdash\neg\varphi_{n}\left(c_{n}\right) \). ראינו את זה בפוסט הקודם אבל זה כל כך קריטי שאסביר שוב למה זה קורה. הטענה, באופן כללי, היא שאם \( \Phi\vdash\neg\left(\alpha\to\beta\right) \) אז \( \Phi\vdash\alpha \) וגם \( \Phi\vdash\neg\beta \). על מנת להוכיח זאת אנו נעזרים בכך שתבנית הפסוק הבא היא טאוטולוגיה של תחשיב הפסוקים ולכן יכיחה מ-\( \Phi \): \( \neg\left(\alpha\to\beta\right)\to\alpha \), וכך גם עבור \( \neg\left(\alpha\to\beta\right)\to\neg\beta \).

כעת מגיע החלק הכי עדין בכל הוכחת משפט השלמות של גדל, לטעמי: אנו יודעים ש-\( \Phi_{n}\vdash\neg\varphi_{n}\left(c_{n}\right) \). עוד אנחנו יודעים ש-\( c_{n} \) הוא סימן קבוע חדש, כזה שלא הופיע כלל ב-\( \Phi_{n} \). פירוש הדבר הוא שאפשר לקחת את סדרת ההוכחה של \( \neg\varphi_{n}\left(c_{n}\right) \) ובכל מקום שבו מופיע בה \( c_{n} \) לכתוב במקומו \( y \) כאשר \( y \) הוא שלא מופיע בהוכחה של \( \neg\varphi_{n}\left(c_{n}\right) \) מ-\( \Phi_{n} \). ההוכחה תמשיך להיות תקפה גם עבורו - צריך להוכיח זאת באינדוקציה, אבל אחמוק מלעשות זאת. המסקנה היא ש-\( \Phi_{n}\vdash\neg\varphi_{n}\left(y\right) \) ומכיוון שניתן להפעיל את Gen (כי \( y \) לא מופיע בהנחות שנדרשו לצורך ההוכחה), נקבל \( \Phi_{n}\vdash\forall y\neg\varphi_{n}\left(y\right) \), או בסימון שונה, \( \Phi_{n}\vdash\neg\exists y\varphi_{n}\left(y\right) \), והרי ראינו ש-\( \Phi_{n}\vdash\exists z_{n}\varphi_{n}\left(z_{n}\right) \), כלומר קיבלנו ש-\( \Phi_{n} \) מוכיחה פסוק ושלילתו (עד כדי הביצוע הפורמלי של החלפת \( z_{n} \) ב-\( y \)), כלומר \( \Phi_{n} \) אינה עקבית. זה מסיים את ההוכחה ש-\( \Phi^{\prime} \) היא עקבית, ולכן מסיים את ההוכחה של משפט השלמות כולו. אבל רק כאשר \( \tau \) היה מילון בן מניה.

מה קורה כאשר \( \tau \) לא בן מניה? כאן אין מנוס - אנחנו זקוקים לכלי מתמטי חזק יחסית - אקסיומת הבחירה. אקסיומת הבחירה, כזכור, שקולה לעקרון הסדר הטוב; הוא מאפשר לנו לסדר בסדר טוב את קבוצת כל הנוסחאות, ולהפעיל עליה אינדוקציה שדומה מאוד לאינדוקציה רגילה - אינדוקציה טרנספיניטית. בפועל זה מתבצע כך: אם \( \alpha \) הוא העוצמה של המילון, ולכן של קבוצת הנוסחאות מעליו, אז מוסיפים קבוצה \( C=\left\{ c_{\beta}\ |\ \beta<\alpha\right\} \) של קבועים, מסדרים את כל הנוסחאות \( \varphi \) בסידור טוב עם אותו סודר, כלומר \( \varphi_{\beta} \) לכל \( \beta<\alpha \), וכעת לכל סודר \( \beta \) מגדירים את \( \Phi_{\beta} \) באופן הבא: \( \Phi_{0}=\Phi \), ו-\( \Phi_{\beta+1}=\Phi_{\beta}\cup\left\{ \exists z_{\beta}\varphi_{\beta}\left(z_{\beta}\right)\to\varphi_{\beta}\left(c_{\beta}\right)\right\} \) - עד כאן בדיוק כמו אינדוקציה רגילה. צריך רק לטפל גם במקרה של סודר גבולי ולהגדיר את \( \Phi_{\beta} \) עבורו באופן הטבעי: \( \Phi_{\beta}=\bigcup_{\gamma<\beta}\Phi_{\gamma} \). יש להראות שגם \( \Phi_{\beta} \) עקבית אם \( \Phi_{\gamma} \) עקבית לכל \( \gamma<\beta \), ופה הסופיות של הוכחה נחלצת לעזרתנו בדיוק כמו קודם - מניחים בשלילה ש-\( \Phi_{\beta} \) לא עקבית, מסתכלים על קבוצת כל הסודרים שמתאימים לקבוצות \( \Phi_{\gamma} \) שבהנחות מתוכן משתמשים בהוכחה של דבר והיפוכו מתוך \( \Phi_{\beta} \), לוקחים את הסודר המקסימלי (יש כזה כי זו קבוצה סופית) ומקבלים \( \Phi_{\gamma} \) שאינה עקבית, בסתירה להנחת האינדוקציה. אם כן, כפי שאנו רואים, עניין המילון הלא בן מניה לא מציב קושי טכני או רעיוני חריג; אבל הוא דורש קצת יותר רקע מתמטי שחבל לדרוש אותו מקוראים שרק רוצים להכיר את משפט השלמות.

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