תחשיב הפסוקים - משפט הקומפקטיות ואיך משפט השלמות דומה למשפט טיכונוף

בפוסט הקודם על לוגיקה סיימתי להוכיח את משפט השלמות לתחשיב הפסוקים. לפני שנעבור הלאה, אני רוצה להתעכב טיפה על המסקנות מכל זה ולדבר עוד קצת על ההוכחה. בואו נתחיל ממסקנה לא טריוויאלית ממשפט השלמות: משפט הקומפטיות. משפט הקומפטיות אומר בפשטות שלתורה \( \Phi \) יש מודל אם ורק אם לכל תת-תורה סופית \( \Phi^{\prime}\subseteq\Phi \) יש מודל. כיוון אחד הוא מובן מאליו (אם לתורה יש מודל, כך גם לכל תת-תורה שלה) אבל הכיוון השני ממש לא - הכיוון השני אומר שאיכשהו אפשר “למשוך למעלה” מודלים עבור חלקים סופיים קטנים של \( \Phi \) ולקבל מהם מודל עבור כל \( \Phi \), שעשויה להיות גדולה ומסובכת בהרבה.

באופן כללי, תוצאות בסגנון “הנה קבוצה \( A \). אם משהו מתקיים לכל תת-קבוצה סופית של \( A \), הוא מתקיים לכל \( A \)” הן משהו שיש בו קריצה אינטואיטיבית ומובילות להרבה טעויות של מתחילים שעושים אותן כשאי אפשר. דוגמה פשוטה: אם \( A=\left(0,1\right)=\left\{ x\in\mathbb{R}|0<x<1\right\} \), הקטע הפתוח של כל הממשיים בין 0 ו-1 לא כולל, אז מתקיימת התכונה שלכל תת-קבוצה סופית של \( A \) יש איבר מינימלי (איבר שקטן מכל יתר האיברים בקבוצה), פשוט כי בכל קבוצה סופית יש איבר מינימלי, אבל ב-\( A \) עצמה אין איבר מינימלי (טוענים ש-\( a\in A \) כלשהו הוא האיבר המינימלי? נההה, \( \frac{a}{2} \) קטן יותר). אז טענה כמו משפט הקומפקטיות היא לא מובנת מאליה, וחשוב לזכור שמשפט הקומפטיות לא מדבר רק על “תורה” ותו לא; הוא מדבר על כל מה שניתן לתאר באמצעות תחשיב הפסוקים. למשל, הראיתי בפוסט קודם איך תחשיב הפסוקים יכול לתאר צביעות של גרף: \( \Phi \) תיארה מה זו צביעה חוקית, ומודל של \( \Phi \) היה צביעה חוקית שכזו. עם טיפה עבודה אפשר להראות בעזרת משפט הקומפקטיות שלגרף יש צביעה חוקית ב-\( n \) צבעים אם ורק אם לכל תת-גרף סופי שלו יש צביעה חוקית ב-\( n \) צבעים. דוגמה אחרת היא ריצופים של המישור: אפשר להראות בעזרת משפט הקומפקטיות שהמישור כולו ניתן לריצוף על ידי קבוצת אריחים כלשהי אם ורק אם כל תת-קבוצה סופית של המישור ניתנת לריצוף על ידי קבוצת האריחים הזו. אלו לא תוצאות טריוויאליות (אם כי ניתן להוכיח אותן גם בדרכים אחרות).

איך מוכיחים את משפט הקומפקטיות בהינתן משפט השלמות? פשוט: משפט השלמות אומר שאם \( \Phi \) עקבית אז קיים לה מודל. גם הכיוון השני ברור - אם ל-\( \Phi \) יש מודל אז אין סיכוי שהיא תוכיח דבר ושלילתו, כי המודל הזה לא יכול לספק גם את הדבר וגם את שלילתו. לכן כדי להוכיח את משפט הקומפקטיות מספיק להראות ש-\( \Phi \) עקבית אם ורק אם כל תת-תורה \( \Phi^{\prime} \) סופית היא עקבית (כלומר, להוכיח שהתכונה “עקביות” כן ניתנת ל”הרמה כלפי מעלה” מכל תת-הקבוצות הסופיות אל הכל). ההוכחה פשוטה למדי ומתבססת על כך שהוכחות פורמליות הן סופיות: מצד אחד, אם \( \Phi^{\prime} \) היא תת-תורה לא עקבית של \( \Phi \) אז אפשר להוכיח ממנה דבר ושלילתו, ואותה הוכחה בדיוק תקפה גם עבור \( \Phi \) ולכן \( \Phi \) אינה עקבית; בכיוון השני, אם \( \Phi \) אינה עקבית אז ניתן להוכיח ממנה דבר ושלילתו ומכיוון שההוכחות הללו סופיות הן משתמשות במספר סופי של הנחות מתוך \( \Phi \), אז פשוט נגדיר את \( \Phi^{\prime} \) להיות קבוצת כל ההנחות הללו, ואז \( \Phi^{\prime} \) לא תהיה עקבית. הוכחנו ש”\( \Phi^{\prime} \) אינה עקבית אם ורק אם קיימת תת-תורה סופית \( \Phi^{\prime}\subseteq\Phi \) שאינה עקבית”, וזו טענה ששקולה לוגית למה שרצינו להוכיח.

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

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

משפט טיכונוף אומר שאם יש לנו מרחב מכפלה טופולוגי, \( X=\prod_{\lambda\in\Lambda}X_{\lambda} \) כאשר כל אחד מהאיברים במכפלה \( X_{\lambda} \) הוא קומפקטי, אז גם \( X \) קומפקטי. ההגדרה המקובלת למרחב קומפקטי היא “לכל כיסוי של המרחב על ידי קבוצות פתוחות יש תת-כיסוי סופי”, כלומר אפשר להסתפק רק במספר סופי של קבוצות מאותו כיסוי כדי לכסות את כל המרחב. כשיש לנו מכפלה פשוטה, נאמר \( A\times B \), וכל אחד מהרכיבים קומפקטי, אפשר עוד איכשהו לעבוד עם ההגדרה הזו: מצטמצמים איכשהו להתעסקות קודם כל עם קבוצות מהצורה \( A\times\left\{ b\right\} \) לכל \( b\in B \) ובסופו של דברים מצליחים לאלתר תת-כיסוי סופי מתוך כל כיסוי. אם עשינו את זה למכפלה של שני מרחבים אפשר באינדוקציה לקבל את אותו דבר עבור מכפלה של \( n \) מרחבים לכל \( n \) טבעי, אבל זה נגמר בערך כאן. טיכונוף מטפל במספר כלשהו של מוכפלים, גם (ובעיקר) אינסופי, ואפילו לא בהכרח בן מניה. גישת הכיסויים לא עובדת טוב במיוחד במקרים הללו, והאופן שבו מוכיחים את המשפט הוא באמצעות הגדרה שקולה לקומפקטיות (שהיא גם ההגדרה היותר מעניינת עבורנו, כשאנחנו באים להשתמש בטיכונוף כדי להוכיח את משפט הקומפקטיות).

ההגדרה הולכת כך: קבוצה \( \mathcal{A} \) של תת-קבוצות של מרחב מסויים היא בעלת תכונת החיתוכים הסופיים אם לכל תת-קבוצה סופית של \( \mathcal{A} \), החיתוך של כל האיברים של תת-הקבוצה הזו לא ריק. מרחב הוא קומפקטי אם בהינתן קבוצה \( \mathcal{A} \) של קבוצות סגורות שמקיימת את תכונת החיתוכים הסופיים, החיתוך של כל הקבוצות בה לא ריק. אם כן, המטרה שלנו בהוכחת טיכונוף היא זו: ניקח קבוצה \( \mathcal{A} \) של תת-קבוצות סגורות של \( X \), ונבנה איכשהו איבר ב-\( \bigcap\mathcal{A} \).

בואו נעשה קפיצה זריזה ללוגיקה: חשבו על \( \mathcal{A} \) כעל קבוצה של פסוקים, כשכל פסוק מיוצג על ידי אוסף כל ההשמות שמספקות אותו (אוסף כל המודלים שלו). תכונת החיתוך הסופי אומרת שלכל תת-קבוצה סופית של פסוקים ב-\( \mathcal{A} \) יש מודל, והמטרה שלנו היא לבנות מודל לכל \( \mathcal{A} \). זה דומה, אך לא זהה, לסיטואציה במשפט השלמות; שם מה שידענו על \( \mathcal{A} \) היא לא תכונת חיתוכים סופיים עבורה אלא שהיא עקבית. החוליה החסרה כאן היא הוכחה כלשהי לכך שאם קבוצת נוסחאות היא עקבית אז לכל תת-קבוצה סופית שלה יש מודל (זו בדיוק גם החוליה שאנחנו צריכים בעת הוכחת משפט השלמות מתוך משפט הקומפקטיות). מכיוון שזה טכני לא אכנס לכך כעת.

בספרו המצויין Topology מציג Munkres את האינטואיציה למה שקורה בהמשך בצורה בהירה ומדוייקת ביותר. הוא מתחיל בדוגמה קונקרטית עבור מכפלה של שני מרחבים, \( X_{1},X_{2} \). האינטואיציה הזו זו: קודם כל נטיל את כל \( \mathcal{A} \) על \( X_{1} \), ונקבל אוסף של קבוצות ב-\( X_{1} \) שעדיין מקיים את תכונת החיתוכים הסופיים (למה?) ומהקומפקטיות של \( X_{1} \) נובע שיש נקודה בחיתוך של האוסף המוטל הזה, \( x_{1} \). בדומה יש נקודה \( x_{2} \) בחיתוך של \( \mathcal{A} \) כשהוא מוטל על \( X_{2} \). כעת ניקח את \( \left(x_{1},x_{2}\right) \) והרי לנו נקודה ב-\( \bigcap\mathcal{A} \) ב-\( X_{1}\times X_{2} \)… אה, לא. כאן מגיעה הבעיה: אף אחד לא ערב לנו ש-\( \left(x_{1},x_{2}\right) \) אכן שייכת לקבוצות של \( \mathcal{A} \).

מונקרס מביא את הדוגמה הקונקרטית הבאה: \( X_{1}=X_{2}=\left[0,1\right] \) (ולכן \( X_{1}\times X_{2} \) הוא ריבוע היחידה הסגור ב-\( \mathbb{R}^{2} \)). בתור \( \mathcal{A} \) הוא בוחר את כל האליפסות עם מוקדים ב-\( p=\left(\frac{1}{3},\frac{1}{3}\right) \) ו-\( q=\left(\frac{1}{2},\frac{2}{3}\right) \). לא אעתיק את הציורים מהספר שלו - יש גבול לפלגיאטים שאני מרשה לעצמי היום - אבל אם תחשבו על זה קצת או תציירו לעצמכם יתברר מייד שהחיתוך של כל האליפסות הללו כולל בדיוק את הקטע הישר שקצותיו הן \( p,q \).

כמו כן, הטלה של \( \mathcal{A} \) על \( X_{1} \) תניב אוסף של קטעים סגורים שכולם מכילים את \( \left[\frac{1}{3},\frac{1}{2}\right] \) והטלה של \( \mathcal{A} \) על \( X_{2} \) תניב אוסף של קטעים סגורים שכולם מכילים את \( \left[\frac{1}{3},\frac{2}{3}\right] \). אז אפשר לבחור \( x_{1}=\frac{1}{2} \) ו-\( x_{2}=\frac{1}{2} \), רק שלמרבה אסוננו \( \left(\frac{1}{2},\frac{1}{2}\right) \) בכלל לא נמצאת על הישר שמחבר את \( p,q \)…

כאן הקורא של מונקרס מתערב: “אהא!” הוא אומר. “ביצעת בחירה גרועה! אם אחרי הבחירה של \( x_{1}=\frac{1}{2} \) היית בוחר \( x_{2}=\frac{2}{3} \) היית מקבל נקודה בחיתוך של \( \mathcal{A} \)”. הבעיה, כפי שמונקרס מציין, היא שהיה לנו יותר מדי חופש בחירה בבחירת הנקודות שלנו ב-\( X_{1} \) ו-\( X_{2} \). ובכן, האם זה לא נשמע מוכר לאלו מכם שראו את הוכחת משפט השלמות? מייד לאחר מכן מונקרס מציג את הפתרון: נרחיב את האוסף \( \mathcal{A} \) תוך שאנו משמרים את תכונת החיתוכים הסופיים שלו; ונרחיב אותו לקבוצה “גדולה ככל האפשר”. בקבוצה הזו כבר לא יהיה לנו חופש בחירה כלל וניתן לקוות שהנקודה היחידה האפשרית שנקבל בשיטה שלעיל תהיה אכן בחיתוך של \( \mathcal{A} \). זה בדיוק הרעיון שהיה גם בהוכחת משפט השלמות. זו כמובן לא הפעם הראשונה ולא הפעם העשירית שאותו רעיון (מחוכם ולא טריוויאלי) עצמו צץ בתחומים שנראים לא קשורים האחד לשני, אבל בכל פעם שזה קורה, זה תענוג.

ההמשך כבר יותר מסובך מאשר במשפט השלמות, פשוט כי הסיטואציה יותר מסובכת. במשפט השלמות היה קל יחסית לבנות את ההרחבה של “\( \mathcal{A} \)”, אבל במשפט טיכונוף הכרחי לגרור פנימה את הלמה של צורן, וגם אז העבודה לא נגמרת, אבל ההוכחה היא יחסית ישירה החל מהשלב הזה - עיקר הקושי הוא ברעיון הבסיסי שכבר הצגתי. מי שמעוניין במלוא הפרטים מוזמן לקרוא את מונקרס, או להמתין ליום שבו אכתוב פוסט (ראוי מאוד) שיוקדש להוכחה הזו.