כלל ה-0-1 של גרפים - ההוכחה

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה \( T \), שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות \( \mathcal{P} \) עם הסתברות 1. למשל, הפסוק \( \exists v_{1},v_{2},v_{3}\left(E\left(v_{1},v_{2}\right)\wedge E\left(v_{2},v_{3}\right)\wedge E\left(v_{3},v_{1}\right)\right) \) שמתאר את “בגרף קיים משולש” שראינו בפוסט הקודם נמצא בתורה זו. את ההוכחה כעת ניתן לסכם, למי שבקיא במושגים, בתור “התורה הזו עקבית ושלמה, ולכן כל תכונה שניתן לנסח בשפה או נובעת ממנה ואז הסתברותה 1, או ששלילתה נובעת ממנה ואז הסתברותה 0”. כעת ניגש לפרטים ובראש ובראשונה למה שאני מתכוון אליו ב”תורה שלמה”.

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

אם כן, סיכום: אם \( T \) היא עקבית ושלמה, אז אפשר להראות כי נובע מכך שכל פסוק \( \varphi \) שייך לה, או ש-\( \neg\varphi \) שייך לה. זה מסיים את העניין מייד, כי אז לכל תכונה של גרף - שכזכור, מוגדרת באמצעות פסוק \( \varphi \) - או ש-\( \varphi\in T \) ואז הסתברות התכונה היא 1, או ש-\( \neg\varphi\in T \) ואז ההסתברות שהתכונה לא מתקיימת היא 1, כלומר הסתברות התכונה היא 0. שימו לב לקשר היפה שיש כאן בין לוגיקה וקומבינטוריקה - כדי להוכיח את טענת ה-0-1 הקומבינטורית, הכל מצטצמם בסופו של דבר להוכחה שתורה מסויימת היא שלמה. זו גם דוגמה נאה לתורה “מעניינת” שאינה נופלת קורבן למשפט אי השלמות של גדל; הסיבה לכך שהיא חומקת ממנו היא שלא מדובר בתורה אריתמטית, כלומר היא אינה ממדלת את המספרים הטבעיים עם פעולת החיבור והכפל. זו כמובן לא התורה המעניינת היחידה שעושה זאת, אך עוד דוגמה לאוסף כדי להשתיק את מי שאומר “משפט גדל מראה שכל תורה מתמטית איננה שלמה” היא תמיד דבר טוב.

ראשית אני רוצה לטפל בשאלה מדוע אם \( T \) עקבית ושלמה נובע מכך שכל פסוק נמצא בה או ששלילתו נמצאת בה. לשם כך מספיק להראות שהתורה היא “סגורה” במובן זה שאם \( T\vdash\varphi \), אז \( \varphi\in T \). הנה נימוק פשוט לכך: אם \( T\vdash\varphi \) נובע מכך שקיימת קבוצה סופית של פסוקים \( \psi_{1},\dots,\psi_{n}\in T \) כך ש-\( \left\{ \psi_{1},\dots,\psi_{n}\right\} \vdash\varphi \) (למה? ההוכחה שאני חושב עליה היא “אם \( T\vdash\varphi \) אז קיימת הוכחה ל-\( \varphi \) עם אקסיומות מ-\( T \). מכיוון שזו הוכחה סופית, יש בה רק מספר סופי של אקסיומות \( \psi_{1},\dots,\psi_{n} \), ומכיוון שהן מוכיחות את \( \varphi \) הן גם גוררות אותו לוגית” - אבל אני בטוח שיש עוד הוכחות). כלומר, כל מודל של הפסוק \( \psi_{1}\wedge\dots\wedge\psi_{n} \) הוא גם מודל של \( \varphi \), ולכן ההסתברות ש-\( \varphi \) יתקיים גדולה לפחות כמו ההסתברות ש-\( \psi_{1}\wedge\dots\wedge\psi_{n} \) יתקיים (כי כל גרף שנגריל ויקיים את התכונה \( \psi_{1}\wedge\dots\wedge\psi_{n} \) יקיים גם את התכונה \( \varphi \)). לא קשה להראות שההסתברות ש-\( \psi_{1}\wedge\dots\wedge\psi_{n} \) יתקיים היא 1, כי ההסתברות של כל \( \psi_{i} \) היא 1 (נסו להוכיח זאת - זה תרגיל קצר ונחמד).

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

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

כעתת נניח כי \( T \) אינה שלמה. אז יש פסוק \( \varphi \) שאינו נובע ממנה, וגם \( \neg\varphi \) אינו נובע ממנה. אז אפשר לבנות שתי תורות חדשות, \( T_{1}=T\cup\left\{ \varphi\right\} \) ו-\( T_{2}=T\cup\left\{ \neg\varphi\right\} \) שיהיו שתיהן עקביות (אם אחת מהן לא הייתה עקבית, פירוש הדבר היה ש-\( \varphi \) או \( \neg\varphi \) נובע מ-\( T \)). לכן יש לשתיהן מודל אינסופי (כי אין ל-\( T \) מודלים סופיים, וכל מודל של \( T_{1} \)ושל \( T_{2} \) הוא גם מודל של \( T \)) ועל פי לוונהיים סקולם, לשתיהן יש מודל מעוצמה \( \kappa \); אבל אמרנו ש-\( T \) היא \( \kappa \)-קטגורית, ולכן שני המודלים הללו (שהם, כאמור, מודלים גם של \( T \)) הם איזומורפיים. זה בלתי אפשרי שכן הם שונים מהותית - באחד \( \varphi \) מתקיים, ובשני \( \neg\varphi \) מתקיים. סתירה.

אם כן, סיימנו את המבוא הלוגי הכללי, ואפשר סוף סוף לגשת ל”בשר” של ההוכחה - האופן שבו מראים שיש ל-\( T \) מודל בן מניה יחיד, ואין לה מודלים סופיים. בתור התחלה כדאי לעצור ולחשוב לרגע - מה זה בכלל אומר, “מודל ל-\( T \)”? הרי \( T \) מלכתחילה היא אוסף של פסוקים, שכל אחד בנפרד אמור להגדיר לנו גרפים; אם \( \varphi\in T \) אז המודלים של \( \varphi \) שהיו לנו בראש מלכתחילה היו של גרפים - וגרפים סופיים. אם כך, איך פתאום נכנסים מודלים אינסופיים לתמונה?

ובכן, די בבירור ל-\( T \) פשוט לא יכול להיות מודל סופי. זאת מכיוון שהתכונה “בגרף יש לפחות \( n \) צמתים” ניתנת לתיאור בלוגיקה מסדר ראשון, ובוודאי שיש לה הסתברות 1 (כזכור, ההסתברות נלקחת על גרף “אקראי” כשמספר הצמתים שואף לאינסוף). הפסוק \( \varphi_{n} \) המתאים הוא פשוט \( \exists v_{1},\dots,v_{n}\left(\bigwedge_{i\ne j}v_{i}\ne v_{j}\right) \). אם ל-\( T \) היה מודל סופי, עם נניח \( n \) איברים, הוא לא היה יכול לספק את \( \varphi_{n+1}\in T \) - סתירה. אז ל-\( T \) אין מודל סופי. לכן היצורים היחידים שכן מספקים את כל הפסוקים שב-\( \varphi \) בו זמנית הם גרפים אינסופיים. אין קושי רעיוני במושג כזה - אנחנו פשוט לא מגבילים את קבוצת הצמתים להיות סופית, וגרפים אינסופיים הם יצורים מאוד נפוצים במתמטיקה. עם זאת, המעורבות שלהם כאן היא עדיין מעניינת - אנחנו מראים שקיים גרף בן מניה יחיד שמקיים בו זמנית את כל התכונות שמתקיימות “כמעט בכל הגרפים הסופיים”, וזה מראה לנו את נכונות כלל ה-0-1.

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

איך מוכיחים ששני מודלים הם איזומורפיים? לצורך הפשטות מספיק לדבר על שני גרפים אינסופיים (בני מניה) \( A,B \) ולא להיכנס לתורה הכללית. מה שצריך להראות הוא פשוט התאמה של אחד-לאחד בין הצמתים של \( A \) והצמתים של \( B \) שמשמרים את הקשתות. כלומר, אם \( V_{A}=\left\{ a_{1},a_{2},a_{3},\dots\right\} \) הם צמתי \( A \) ואילו \( V_{B}=\left\{ b_{1},b_{2},b_{3},\dots\right\} \) הם צמתי \( B \) אנחנו רוצים למצוא פונקציה \( f:V_{A}\to V_{B} \) שהיא חד חד ערכית ועל, ומקיימת ש-\( \left(a_{i},a_{j}\right)\in E_{A} \) אם ורק אם \( \left(f\left(a_{i}\right),f\left(a_{j}\right)\right)\in E_{B} \).

מה שנעשה הוא לשחק משחק באופן הבא. ראשית, נתאים את \( a_{1} \) ל-\( b_{1} \), פשוט כי לעת עתה אין שום מהלך נבון יותר שניתן לעשות. כעת, למי נתאים את \( a_{2} \)? זה כבר נהיה מורכב מעט יותר - אם \( a_{1} \) מחובר ל-\( a_{2} \), נרצה לבחור \( b_{i}\in V_{B} \) שמחובר ל-\( b_{1} \). מה מבטיח לנו שקיים כזה? ובכן, אם לא היה קיים כזה, אז \( B \) לא היה מודל טוב עבור התכונה “לכל צומת יש לפחות שכן אחד”, שלא קשה לראות שניתן לנסח בשפה מסדר ראשון ושיש לו הסתברות 1 (בגרף עם \( n+1 \) צמתים, לכל צומת יש \( n \) שכנים פוטנציאליים, ולכן ההסתברות שלא יהיה לו אף שכן היא \( \frac{1}{2^{n}} \) - שואפת לאפס).

בואו נעבור לדבר על משהו כללי יותר. נניח שעד כה טיפלתי בכל הצמתים \( a_{1},a_{2},\dots,a_{n} \) ועכשיו אני תוהה לאן להעביר את \( a_{n+1} \). בואו נניח לצורך נוחות ש-\( a_{1} \) עבר ל-\( b_{1} \), ש-\( a_{2} \) עבר ל-\( b_{2} \) וכן הלאה (אם לא, פשוט נשנה את המספור של הצמתים של \( B \)). עכשיו, הצומת החדש \( a_{n+1} \) הולך להיות מחובר לחלק מהצמתים הקיימים, ולחלק מהם - לא. נסמן ב-\( S_{A} \) את קבוצת הצמתים שאליהם \( a_{n+1} \) מחובר, וב-\( S_{B} \) את קבוצת ה”תמונות” שלהם (ה-\( b_{i} \)-ים שמחוברים לאיברים של \( S_{A} \)). מה שאנחנו רוצים לעשות הוא למצוא צומת כלשהו ב-\( V_{B} \) שמחובר לכל הצמתים ב-\( S_{B} \), ולא מחובר לאף צומת מבין \( b_{1},\dots,b_{n} \) שאיננו ב-\( S_{B} \). האם קיים צומת שכזה? אנחנו חייבים שהתשובה תהיה חיובית כדי שהשיטה תצליח; וזה מוביל אותנו לניסוח התכונות שב-\( T \) שיעניינו אותנו, שהן בדיוק התכונות שאומרות “כן! בכל תרחיש דוגמת זה שתיארת למעלה, אפשר למצוא צומת \( b_{n+1} \) מתאים”. מה שצריך להראות הוא שהתכונות הללו ניתנות לניסוח בשפה מסדר ראשון שלנו, ושההסתברות לכך שהן יתקיימו בגרף היא 1. ברגע שהראנו זאת, סיימנו; כי אז התהליך שתיארתי לעיל, אחרי שמכלילים אותו עוד טיפה, מגדיר באופן מושלם את האיזומורפיזם (אם רוצים לדעת לאן \( a_{n} \) עבר, “מריצים” את התהליך במשך \( n \) צעדים ורואים מה קורה; כדי להבטיח שגם כל ה-\( b_n \)-ים יותאמו לאחד מה-\( a_n \)-ים צריך לבחור גם עבורם איברים, לסירוגין).

הבה ננסח במפורש את התכונות שאנחנו רוצים. נסמן ב-\( \mbox{EA}_{n,m} \) את התכונה “לכל קבוצה \( X \) מגודל \( n \) ותת קבוצה \( Y \) מגודל \( m \) שלה, קיים איבר שאינו ב-\( X \) שמחובר לכל אברי \( Y \) ואינו מחובר לאף איבר ב-\( X \) שאינו ב-\( Y \)” (למה \( \mbox{EA} \)? מלשון Extension Axiom, שכן זוהי אקסיומה שאומרת שניתן “להרחיב” את הקבוצה \( X \) באופן שמעניין אותנו - דהיינו, חיבור בדיוק לצמתי \( Y \)). את התכונה הזו אפשר לכתוב בקלות יחסית בשפה מסדר ראשון:

\( \forall v_{1},\dots,v_{n} \) \( \left[\left(\bigwedge_{i\ne j}v_{i}\ne v_{j}\right)\to\exists u\left(\bigwedge_{i}^{n}u\ne v_{i}\wedge\bigwedge_{i\le m}E\left(u,v_{i}\right)\wedge\bigwedge_{i>m}^{n}\neg E\left(u,v_{i}\right)\right)\right] \)

אז נשאר רק להראות שכל תכונה כזו מתקיימת בהסתברות 1 בכל גרף. האינטואיציה ברורה - \( n,m \) הם קבועים, ואנחנו שואלים את עצמנו מה קורה בגרפים אקראיים שגודלם שואף לאינסוף. אם נקבע את \( X,Y \), בגרפים כאלו יש כמעט “אינסוף” צמתים \( u \) פוטנציאליים להתאים ל-\( X,Y \), ולכן צומת שכזה אכן יופיע. כך זה בתורת הגרפים (ובמקומות רבים אחרים…) - ברגע שהמבנה שלך גדול מספיק, כל מה שתוכל להעלות על דעתך יווצר בתוכו, כל עוד מה שמעניין אותך הוא תכונה מקומית.

כדי להקל על החישוב נפשט קצת עניינים. אין צורך לדבר על \( \mbox{EA}_{n,m} \) עבור \( n,m \) כלליים - שימו לב שאם \( \mbox{EA}_{2m,m} \) מתקיים בהסתברות 1, אז בוודאי גם \( \mbox{EA}_{n,m} \) מתקיים בהסתברות 1 עבור \( m\le n\le2m \), כי אנחנו מקלים קצת על הדרישות - הקבוצה \( Y \) נותרת זהה, ואנחנו פשוט דורשים פחות דרישות על שאר האיברים ב-\( X \) (כלומר, מעיפים לכל הרוחות את חלקם). לכן די להוכיח כי \( \mbox{EA}_{2m,m} \) מתקיים בהסתברות 1. נקבע את מספר הצמתים בגרף כולו להיות \( n \) (כי השתמשנו ב-\( n \) עד כה למטרה זו וחבל להפסיק - רק צריך לזכור שזה לא אותו \( n \) שהופיע ב-\( \mbox{EA}_{n,m} \)).

מכאן זו באמת קומבינטוריקה פשוטה וקצת אינפי. ניקח צומת שאיננו ב-\( X \). מה ההסתברות שהוא מחובר לכל \( m \) צמתי \( Y \), ואינו מחובר לכל הצמתים של \( X \) שאינם ב-\( Y \)? בדיוק \( \frac{1}{2^{2m}} \), כי יש \( 2m \) הגרלות של קשתות שבכל אחת אנחנו צריכים שתתקבל תוצאה ספציפית. אם כן, ההסתברות שצומת כלשהו לא יקיים את התכונה הרצויה היא \( 1-\frac{1}{2^{2m}} \). על פניו הסתברות גדולה - אבל כאמור, יש המון צמתים שונים. כמה המון? \( n-2m \) צמתים שבגרף אך אינם ב-\( X \). ההסתברות שאף אחד מהם לא יהיה בסדר היא מכפלת ההסתברויות של כל אחד להיות לא בסדר, כלומר \( \left(1-\frac{1}{2^{2m}}\right)^{n} \). זה בפני עצמו שואף לאפס כשמשאיפים את \( n \) לאינסוף, אבל צריך לשים לב שלא סיימנו - אנחנו לא טוענים טענה על קבוצה \( X \) ספיצפית, אלא על כל קבוצה \( X \) מגודל \( 2m \) וכל תת קבוצה \( Y \) שלה מגודל \( m \). אז ההסתברות שמשהו ישתבש הוא שתהיה קבוצה \( X \) כלשהי ותת קבוצה \( Y \) שלה שעבורן האירוע ה”רע” שהסתברותו \( \left(1-\frac{1}{2^{2m}}\right)^{n} \) מתרחש. ההסתברות לכל זה חסומה על ידי מספר תת הקבוצות הללו כפול \( \left(1-\frac{1}{2^{2m}}\right)^{n} \) (בהינתן קבוצת מאורעות, ההסתברות שאחד מהם יתרחש חסומה על ידי סכום ההסתברויות שלהם - זה מה שנקרא Union bound).

אז הסתברות הכישלון שלנו חסומה על ידי \( {n \choose 2m}{2m \choose m}\left(1-\frac{1}{2^{2m}}\right)^{n} \). את כל זה אפשר לחסום על ידי \( n^{2m}\cdot c^{n} \) כש-\( c \) הוא קבוע קטן מ-1. המסקנה ברורה - פולינום כמו \( n^{2m} \) גדל הרבה יותר לאט מאשר פונקציה אקספוננציאלית כמו \( c^{n} \) גדלה, ומכיוון ש-\( c<1 \), \( c^{n} \) שואף לאפס, ולכן \( n^{2m}\cdot c^{n} \) כולו שואף לאפס כש-\( n \) שואף לאינסוף, כלומר ההסתברות ש”משהו יתקלקל” שואפת לאפס, ולכן ההסתברות שהתכונה תתקיים שואפת ל-1. זהו.

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