לא מדויק

אז מה הקטע עם דילוגי אותיות בתורה? (חלק ב')

17 במאי, 2012

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

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

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

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

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

נתניהו אכן זכה, אולם הצופן מנבא שהוא ימות בקרוב…

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

ראשית, "רהמנתניהו" אכן מופיע בדיוק פעם אחת בתורה, בדילוג אחורי של לא פחות מ-19129, החל מאינדקס 259333. שתי המילים האחרות שנמצאות בסמיכות ל"רהמנתניהו" ודרוזנין מציין הן "ביבי" ו"נבחר". אלו שתיהן מילים קצרות ואנחנו בוגרי הפוסט הקודם, כך שאנחנו יודעים שאפשר לצפות שהן יופיעו המון בתורה – "ביבי" עם הי'ם שלו יותר מ"נבחר". ואכן, "ביבי" מופיע בדילוגי אותיות בסך הכל 926,592 פעמים, "נבחר" מופיע 109,969. התנ"ך כולו מפוצץ במילים הללו. כמובן, כדי שלדרוזנין זה יצא יפה הוא משתמש במופע שלהן עם דילוג קטן – 2 עבור ביבי, מינוס 4 עבור נבחר; אבל הקפיצות המדויקות הללו אינן חשובות, כמובן, וכל קפיצה קטנה יחסית הייתה מרשימה את דרוזנין באותה המידה. "נבחר" מופיע 53 פעמים בקפיצה עד גודל 20, ואילו "ביבי" מופיע 453 פעמים. מי שהתרשם מה"ביבי" שהיה כל כך קרוב ל"רהמנתניהו" – אל. התורה מלאה ביבי בכל אשר נפנה. הסתברות של 1 ל-200? אולי, אבל הסתברות של 1 ל-200 שיקרה מה? ש"רהמנתניהו" יופיע כשבסביבה שלו יש את "ביבי" בדיוק בדילוג של 2 ואת "נבחר" בדילוג של בדיוק מינוס 4? או ש"רהמנתניהו" יופיע כשבסביבה שלו יש "ביבי" ו"נבחר" בדילוג כלשהו? או ש"רהמנתניהו" יופיע כשבסביבה שלו יש מילים מעניינות? או שצירוף מילים כלשהו שכולל את שם משפחתו של נתניהו יופיע עם מילים מעניינות ואולי תחילית מעניינת? (כי באמת, כולנו יודעים ש"רהמנתניהו" זה בגלל שלא "בנימיןנתניהו" ולא "ביבינתניהו" לא מופיעים בתורה היודעת-כל) דרוזנין לא אומר, וכמובן שלא מפרט את החישובים.

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

איזה ניסוי ברור שצריך לעשות עכשיו? כמובן, לחפש "רהמפרס" ו"נבחר". ובכן, "רהמפרס" מופיע המון; הדילוג המינימלי שלו הוא 69 החל מ-30,810. "נבחר" מופיע קרוב אליו, בדילוג של מינוס 5, החל מ-31,257. בסמיכות יש גם את כינוי החיבה הישן של פרס, "לוזר", בדילוג של 120 החל מ-30,918. אם כן, אולי היה צריך "לנבא" שפרס ייבחר? הייתי רוצה להגיד שזו טעות נוראית ובעצם התורה התכוונה לבחירה של פרס לנשיא המדינה, אבל "רהמפרס" לא מותיר מקום לספק; פרס מעולם לא נבחר לראשות הממשלה. הייתכן – תחזיקו חזק – שיש נבואות שגויות בתורה?

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

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

שני טקסטים לא דתיים בעליל ששימשו בעבר לחיפוש אחר "צפנים" הם "מובי דיק" ו"מלחמה ושלום" (בשל אורכם, מן הסתם). לי אין עותק דיגיטלי שלהם בעברית, וגם אם היה – אני מעדיף ללכת על משהו יותר אקראי. למרבה המזל, בימינו יש מקור פשוט מאוד לטקסטים אקראיים ארוכים בעברית – ויקיפדיה העברית. אז מה שעשיתי הוא פשוט מאוד וכל אחד יכול לעשות בבית: השתמשתי במנגון של ויקיפדיה שנותן לי רשימת ערכים אקראיים ושאבתי מהם את התוכן (בלי הבחנה – גם לינקים וכדומה – אבל כשאני משאיר רק את האותיות העבריות ותו לא) עד שקיבלתי טקסט באורך דומה לזה של התורה – 300,000 תווים בערך. כמובן, אתם לא חייבים להאמין לי שלא הינדסתי את קובץ הטקסט באופן מושלם לצרכי; לכן אני מזמין אתכם לחזור על הניסויים שלי עם טקסט ויקיפדי שתפיקו בעצמכם. הנה הסקריפט בשפת Ruby שבו השתמשתי לצורך בניית הטקסט.

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

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

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

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

הנה דוגמה יפה ל"מצאנו משהו, בואו נבנה עכשיו נרטיב סביבו", שמקורה בלינק שנתנו לי בתגובות לפוסט הקודם: אבולוציה. בקישור אומרים כי "אבולוציה" מופיעה פעם אחת בלבד בתורה (היא אכן מופיעה בדילוג של 2402 החל מ-246802; עם זאת, היא מופיעה גם ארבע פעמים נוספות בדילוגים אחורה של 4815,5397,18344,31281). כמו כן מצאו באיזור שלה את "צארלס" ואת "דרווין" (לא ביחד, כמובן) ואת "מאובנים". בטקסט מציינים שהמילים הללו מופיעות רק 79, 179 ו-41 פעמים (בהתאמה) בדילוגים של עד 10,000; כמובן שבדילוגים ארוכים יותר המספר ארוך יותר אבל בשביל הדוגמה הזו לא היה צורך בדילוג ארוך יותר. זו בהחלט תוצאה נחמדה ויותר מרשימה מברק אובמה שלי. הבעיה היא רק שלא ברור מה היא אומרת – הרי לא מנסים לטעון פה שהתורה בעד דרווין – ולכן בלינק מנסים לבנות נרטיב סביב ההקשר של המופע של "אבולוציה".

ההקשר הוא מצוות שילוח הקן, והב' של אבולוציה נפלה ישר על "ביצים". והנה בא הנרטיב:

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

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

הבלוג הזה לא עוסק בביולוגיה, ולכן אסתפק בלהגיד – קשקוש מקושקש! חצופים!

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

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

הבדלי איות הם אולי התמרונים המעודנים והחזקים ביותר בכל העניין. נניח שיש לנו 20 מילים שאנו מחפשים, ולכל אחת יש לנו שני איותים שונים. זה אומר שיש $2^{20}=1,048,576$ – מיליון וקצת – קומבינציות אפשריות לחיפוש. לא מדויק להגיד משהו בסגנון "אם ההסתברות הייתה 1 למיליון שהקומבינציה תיתן תוצאה מעניינת, אז קרוב לודאי שאחת מהתוצאות הייתה מעניינת" ולו בגלל שקרוב לודאי שההסתברויות לכך ששתי קומבינציות דומות-אך-לא-זהות יהיו מעניינות הן תלויות זו בזו. אבל אי אפשר להכחיש את זה שיש כאן הרבה, הרבה מקום לתמרן. וכשעושים את אותו הניסוי הרבה פעמים עם פרמטרים קצת שונים, תוצאות לא סבירות יצוצו מתישהו.

תגים: דילוגי אותיות בתורה
שייך לקטגוריות הבלים פסאודו-מתמטיים | 5 תגובות »

איור: המלון של הילברט

16 במאי, 2012

(איור: תמר עקביה. לחצו על התמונה לאיור בגודל מלא)

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

מה רואים כאן? את המלון של הילברט והאופן שבו משכנים בו אוטובוס עם אינסוף אורחים – מקפיצים (מילולית, אצל תמר) כל אורח קיים לחדר שמספרו פי 2 ממספר החדר הנוכחי שלו, ומכניסים את האורחים החדשים לכל החדרים האי זוגיים שהתפנו. במקרה הזה, תמונה אחת שווה $\aleph_0$ מילים.

תגים: איור, המלון של הילברט
שייך לקטגוריות תורת הקבוצות | תגובה אחת »

אז מה הקטע עם דילוגי אותיות בתורה? (חלק א')

14 במאי, 2012

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

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

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

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

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

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

ראשית כל, להגדרה המתמטית. מה זה בכלל דילוג אותיות בתורה? פשוט מאוד: אם ניקח את התורה (בגרסה ללא ניקוד) ונמחק ממנה כל תו שאיננו אות (דהיינו – אין רווחים, אין פסיקים, נקודות, נקודה-פסיק, מקף או כל דבר אחר) נקבל רצף ארוך מאוד של אותיות – 304,805 אם לדייק. כעת, ברצף הזה אנחנו אמורים לקרוא מילים אות-אות, אבל אפשר גם אחרת: למשל, חלק מפסוקים כ"א-כ"ב בבראשית ל"ו הוא "בארץ אדום ויהיו בני לוטן חרי והימם". כעת, אם ניקח את הא' שב"בארץ" ואז נדלג קדימה חמש אותיות, כלומר נפסח על פני ארבע האותיות שבאמצע ("רץאד") ישר אל הו' שאחר כך, ואז שוב נדלג חמש אותיות (ונקפוץ מעל "םויה") נקבל י', ואחרי עוד חמש אותיות נקבל ל', ואחרי עוד חמש אותיות נקבל ר' – והנה, בדילוגים של ארבע בכל פעם גילינו את אוילר, מגדולי המתמטיקאים של כל הזמנים, כשהוא מתחבא לו בתורה! זו התורה כולה; זו כל המשמעות של דילוגי אותיות. רק צריך להעיר שבדרך כלל סופרים גם דילוגים "אחורה": למשל, "ויצו את אשר על ביתו לאמר" (בראשית, מ"ד, א') כולל את אוילר בדילוגים של שתי אותיות, אבל אחורה.

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

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

יש להזכיר, כי ברשותו של הרב וייסמנדל לא היה מחשב פנטיום מתקפל בהסתתרו מן הנאצים בבונקר בברטיסלבה. כיצד ידע אודות רמזים חשובים בדילוג מיוחד זה? אין אנו יודעים… לצאת למבצע של ספירה ידנית של 12,111 אותיות, כמה פעמים ואיך ידע שלא טעה? ושאלה אחרת: מאיפה להתחיל? הרי בוודאי שאי אפשר להעלות על הדעת שהוא השתמש כאן בתהליך של "ניסוי וטעייה".

לא נשמע מרשים ממבט ראשון? נשמע.

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

הסיבה המרכזית להצלחה של דרוזנין, לדעתי, היא תחזית אחת מוצלחת שהוא ביצע – ב-1994 הוא שלח מכתב לראש הממשלה בישראל דאז יצחק רבין, שבו הוא הזהיר מפני העובדה שבמקום היחיד בתורה שבה מופיע השם "יצחק רבין" בדילוגי אותיות (דילוג של 4772 החל ממקום 254245), הוא מצטלב עם המשפט "רוצח אשר ירצח" (שמופיע בדילוגים של 1, כלומר בתורה ה"רגילה") – הצ' של יצחק מצטלבת עם הצ' של "ירצח". התחזית הזו מצביעה על שיטת העבודה של דרוזנין (שהיא פשוטה למדי ובהחלט לא מתקרבת לרמת התחכום של ויצטום וריפס) – חפש מספר דילוגי אותיות שמופיעים בסמיכות זה לזה בתורה כאשר כותבים את התורה בתוך מלבן, וזהו; הספר של דרוזנין מלא במלבנים כאלו עם הדגשות של ביטויים שמופיעים בהם. אין שום ניתוח הסתברותי כלשהו ולא פעלולים מחוכמים יותר. למעשה, הספר אפילו מקמץ במידע וכשהוא מציג דילוגים אפילו לא טורח לומר מה גודל הדילוג. דבר אחד שפה ושם כן מקפידים עליו קצת הוא עקרון כלשהו שקבע ריפס לפיו יש חשיבות גדולה במיוחד לביטוי שמופיע בדילוג המינימלי שלו בתורה (למשל, אם "יצחקרבין" היה מופיע גם בדילוג של 2315 אז הדילוג של 4772 היה "מרשים פחות").

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

בואו נדבר לרגע על המתמטיקה של העניין. כדי לפשט את החישובים אני אניח את ההנחה השגויה לפיה האותיות בעברית מתפלגות באופן אחיד, והתורה בפרט "הוגרלה" כך: כלומר, אם אני הולך לראות מהי האות במקום 235431, יש סיכוי של $\frac{1}{22}$ לכל אות להופיע (זכרו שאין הבדל מבחינתנו בין אותיות סופיות ואותיות רגילות). אם כבר קבעתי אינדקס התחלתי $a$ וגודל קפיצה $b$ , אז ההסתברות שמילה $w$ , שאת אורכה אסמן ב- $\left|w\right|$ , תופיע החל מ- $a$ בקפיצות של $b$ היא $\frac{1}{22^{\left|w\right|}}$ : זו ההסתברות שב- $a$ תהיה האות הראשונה ב- $w$ ( $\frac{1}{22}$ ), כפול ההסתברות שב- $a+b$ תהיה האות השניה ב- $w$ ( $\frac{1}{22}$ ), כפול ההסתברות שב- $a+2b$ תהיה האות השלישית ב- $w$ וכן הלאה – פשוט כופלים את $\frac{1}{22}$ בעצמו $\left|w\right|$ פעמים. בפועל צריך לכפול לא ב- $\frac{1}{22}$ אלא בקבוע שתלוי בשכיחות האות הספציפית ב- $w$ , ולרוב זה יהיה מספר גדול יותר מ- $\frac{1}{22}$ (דווקא "דרוזנין" היא מילה קשה יחסית בגלל ז' הלא שכיח). זה אומר שמילה של שלוש אותיות צפויה להופיע בהסתברות של 1 ל-10,000, בעוד שעבור מילה של ארבע אותיות ההסתברות היא כבר יותר באיזור ה-1 ל-250,000, ועבור מילה מאורך 8 (כמו "יצחק רבין"), ההסתברות היא כבר באיזור ה-1 ל-55 ביליון (ביליון אצלי הוא אלף מיליארדים). נשמע די נמוך, חייבים להודות.

אבל, בל נשכח שזו ההסתברות לכך שעבור זוג ספציפי של $\left(a,b\right)$ תופיע החל ממקום $a$ ובקפיצה $b$ המילה הספציפית $w$ . מה שיותר מעניין הוא כמה פעמים בתוחלת צפויה $w$ להופיע בטקסט כולו. החישוב ההסתברותי כאן הוא קל: מגדירים משתנה מקרי $X_{a,b}^{w}$ שמקבל 1 אם המילה $w$ מופיעה החל מ- $a$ בקפיצות של $b$ ואחרת מקבל 0; אז התוחלת של $X_{a,b}^{w}$ היא בדיוק ההסתברות ש- $w$ יתקבל באקראי, כלומר $\mbox{E}\left[X_{a,b}^{w}\right]=\frac{1}{22^{\left|w\right|}}$ . כעת, נגדיר משתנה $X^{w}=\sum_{\left(a,b\right)}X_{a,b}^{w}$ שסופר את מספר המופעים של $w$ בטקסט כולו; וכעת נשתמש בלינאריות התוחלת כדי לקבל ש- $\mbox{E}\left[X^{w}\right]=\mbox{E}\left[\sum_{\left(a,b\right)}X_{a,b}^{w}\right]=\sum_{\left(a,b\right)}\mbox{E}\left[X_{a,b}^{w}\right]=\frac{\left|\left\{ \left(a,b\right)\right\} \right|}{22^{\left|w\right|}}$ , כאשר $\left|\left\{ \left(a,b\right)\right\} \right|$ הוא סימון קצת עקום ל"מספר הזוגות $a,b$ הרלוונטיים לנו". זו המחשה נאה לכוח של תכונת הלינאריות של התוחלת – היא נכונה גם בלי קשר לשאלה עד כמה המשתנים $X_{a,b}^{w}$ תלויים זה בזה (ורבים מהם תלויים זה בזה בצורה מתוסבכת).

כעת אנחנו צריכים להכניס לתמונה נתון אחד נוסף – אורך הטקסט שלנו, שאסמן $N$ . הגודל המקסימלי האפשרי עבור $b$ הוא $\frac{N}{\left|w\right|}$ (מדוע?), ואם בחרנו $b$ קונקרטי אז $a$ המקסימלי האפשרי עבורו הוא $N-\left|w\right|b$ (מדוע?), ולכן מספר הזוגות $\left(a,b\right)$ החוקיים הוא בערך $\sum_{b=0}^{N/\left|w\right|}N-\left|w\right|b=N\left(N/\left|w\right|\right)-\left|w\right|\frac{\left(N/\left|w\right|\right)^{2}}{2}\approx\frac{N^{2}}{\left|w\right|}-\frac{N^{2}}{2\left|w\right|}\approx\frac{N^{2}}{2\left|w\right|}$ . בקיצור, אחרי כמה הזנחות קטנות מצאתי שמספר המקומות הפוטנציאליים למצוא בהם את $w$ הוא $\frac{N^{2}}{2\left|w\right|}$ . אם מרשים גם חיפושים אחורה ( $b$ שלילי) המספר מוכפל ולכן $\frac{N^{2}}{\left|w\right|}$ הוא הביטוי האלגנטי שאנחנו מקבלים בסוף.

אם נציב $N=300,000$ ו- $\left|w\right|=8$ נקבל שתוחלת מספר המופעים של מילה כלשהי של 8 אותיות היא 0.2. כלומר, כל מילה מאורך 8 תופיע "חמישית פעם", ובניסוח אחר – אנחנו מצפים שבערך חמישית מהמילים מאורך 8 יופיעו. אם במקום 22 אותיות יש לנו רק 18, התוחלת קופצת ל-1. אם אנחנו מתעסקים עם מילה מאורך 7 (ו-22 אותיות) התוחלת היא 5 וקצת. מילה מאורך 4 כבר צפויה להופיע בסביבות ה-100,000 פעמים. זה אומר לנו שני דברים: ראשית, שמילים קצרות יחסית (עד 6 אותיות, נאמר) יופיעו כל כך הרבה פעמים שהתורה (וכל טקסט אחר) פשוט מוצף בהן, ואפשר יהיה למצוא אותן כמעט בכל מקום שנבחר; ושנית, שגם מילים ארוכות יותר יהיו בשפע. אמנם, אם נבחר מילה ארוכה קונקרטית יש סיכוי שהיא לא תופיע, למרבה צערנו; אבל אם נצליח לחשוב על רשימה של אלף מילים "מעניינות" מאורך 8, אפשר לצפות לכך שלפחות מאתיים מהן יופיעו, ועל כל מופע כזה אפשר יהיה לכתוב פרק בספר, אם נצליח למצוא "סביבו" עוד מופעים מעניינים של מילים (שלרוב יהיו מילים קצרות כי מילים קצרות אפשר למצוא בכל מקום). זו המתמטיקה שמאחורי מציאת "ביטויים מעניינים קרובים זה לזה". הגורם הריבועי, $N^{2}$ , פחות או יותר מבטיח שבטקסטים ארוכים למדי ההסתברויות יקפצו לשמיים.

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

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

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

השלב הבא הוא להגיד לסקריפט לחפש מילים קרובות לקת'ולהו. כלומר, לא חיפשתי את המילים בכל התורה (וגם לא הקפדתי על עניין הדילוג המינימלי). בגלל שמצטמצמים לאיזור קרוב לקת'ולהו, חיש קל אפשר לחפש המוני מילים, ולכן כתבתי רשימה ארוכה שלתוכה זרקתי את כל מה שחשבתי שבכלל נשמע קצת רלוונטי לקת'ולהו. למשל: "קריאה", "קריאתו", "רליה", "תמנון", "מפלצת", "מהכוכב", "מהכוכבים", "שקוע", "קוסמי", "משמיד", "נורא", "חולם" וכו' וכו' וכו'. הבנתם את העיקרון. שימו לב שרבות מהמילים הללו הן קצרות למדי, מה שאומר שיש המון מהן פזורות ברחבי התורה, ולכן מתבקש שחלקן יפלו גם קרוב לקת'ולהו. לא התאכזבתי. רוב המילים שחיפשתי לא נמצאו בסביבה של קת'ולהו, אבל כמות נאה דיו של מילים היו קרובות אליו: "קריאה" (דילוג של 103 החל מ-106389), "רליה" (המון מופעים בקרבת קת'ולהו – כפי שמתבקש ממילה קצרה שכזו – למשל 3,105728), "כוכב" (110, 106345), "רשע" (שוב, המון מופעים, כצפוי; למשל 41, 105746), "נורא" (109, 106787), ו-"חולם" (106499, דילוג אחורי של 129).

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

בואו נחזור שניה אל "מגלת" של הרב וייסמנדל. זו מילה בת ארבע אותיות, כך שאפשר לחשוד שהיא תהיה נפוצה למדי. אכן, בדילוגים (גם קדימה וגם אחורה) עד אורך 10,000 היא מופיעה 13,110 פעמים (לא כולל מופעים "אמיתיים" שלה בתורה, כלומר בדילוג של 1). זה אומר שאם תבחרו גודל דילוג כלשהו באופן אקראי, יש סיכוי סביר בהחלט ש"מגלת" יופיע בדילוג הזה. אז עצם העובדה שבדילוג עבור המספר הספציפי 12,111 המילה "מגלת" הופיעה – זה בוודאי לא מעניין. אבל מה שויצטום התלהב ממנו הוא לא רק הופעת המילה "מגלת" בדילוג הזה אלא הסמיכות שלה למילה "אסתר" שמופיעה בתורה רק פעם אחת.

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

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

תגים: חוק המספרים הגדולים באמת בפעולה, דילוגי אותיות בתורה
שייך לקטגוריות מתמטיקה בראי התקשורת, הבלים פסאודו-מתמטיים | 26 תגובות »

משפט Valiant-Vazirani, או: איך להרוג השמות מספקות עם פונקציות תמצות אקראיות

11 במאי, 2012

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

אולי הבעיה הקונקרטית המפורסמת ביותר בתורת הסיבוכיות היא SAT. בבעיה הזו נתון לנו פסוק לוגי בצורת CNF, כלומר הוא נראה כך: $C_{1}\wedge C_{2}\wedge\dots\wedge C_{k}$ , כך שכל $C_{i}$ נראה כך: $\left(l_{1}\vee l_{2}\vee\dots\vee l_{r}\right)$ , כך שכל $l_{j}$ הוא או משתנה $x$ או שלילה של משתנה, $\neg x$ . ל- $l$ כזה קוראים "ליטרל", ל- $C$ כזה קוראים "פסוקית CNF", והשאלה היא זו: האם יש השמה למשתנים של הפסוק $\varphi$ שמספקת אותו? השמה נותנת לכל משתנה ערך $\mbox{T}$ או $\mbox{F}$ (אמת או שקר). אם הליטרל $l$ הוא מהצורה $x$ הוא מקבל את הערך של $x$ ואם הוא מהצורה $\neg x$ הוא מקבל את הערך ההפוך לערך של $x$ ; הפסוקית $C_{i}$ מקבלת את הערך $\mbox{T}$ אם לפחות אחד מהליטרלים שלה קיבל $\mbox{T}$ ואחרת היא מקבלת $\mbox{F}$ ; והפסוק כולו מקבל $\mbox{T}$ רק אם כל הפסוקיות שבו קיבלו $\mbox{T}$ . תחשבו על פסוק $\varphi$ בתור "רשימה של אילוצים", כך שכל אילוץ הוא פסוקית, חייבים שכל האילוצים
יתקיימו בו זמנית, וכל אילוץ קל יחסית לקיים – רק צריך שאחד מהליטרלים בתוכו יתקיים.

דוגמה: $\varphi=\left(x\vee\neg y\right)\wedge\left(\neg x\vee z\right)$ . זה פסוק שדי קל לספק, למשל על ידי ההשמה $x=\mbox{\ensuremath{\mbox{T}},y=\ensuremath{\mbox{F}},z=\ensuremath{\mbox{T}}}$ . יש גם השמות שלא מספקות אותו, למשל $x=\mbox{F},y=\mbox{T},z=\mbox{F}$ . אפשר, אם באמת רוצים, לספור כמה השמות מספקות יש ל- $\varphi$ - די ברור שיש יותר מאחת.

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

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

אז בואו נאמר שאנחנו רוצים להיות מסוגלים להבדיל רק בין שני מקרים – המקרה שבו ל- $\varphi$ אין בכלל השמות מספקות, והמקרה שבו יש ל- $\varphi$ השמה מספקת אחת. ויותר מזה – אנחנו מרשים לאלגוריתם שלנו להיות הסתברותי עם טעות חד-צדדית. כלומר, אם $\varphi$ אינו ספיק, אנחנו דורשים שהאלגוריתם יעצור ובודאות יגיד "לא", אבל אם $\varphi$ ספיק על ידי השמה מספקת אחת בדיוק כל מה שאנחנו דורשים הוא שהוא יעצור ויגיד "כן" בהסתברות נמוכה כלשהי (כמה נמוכה? נדון בכך אחר כך). אם $\varphi$ ספיק על ידי יותר מהשמה מספקת אחת ממש לא אכפת לנו מה האלגוריתם יעשה. האינטואיציה היא זו: אם המקרה הזה קל יותר מהבעיה הכללית, אולי הבנה של הפתרון שלו תעזור לנו להבין איך לפתור את הבעיה הכללית או היכן טמון הקושי בבעיה הכללית; ואילו אם הוא קשה מספיק לכשעצמו אז אולי נקבל אינטואיציה טובה יותר לגבי הקושי הזה. ובכן, משפט VV מראה לנו, באופן די מפתיע, שגם המקרה הזה הוא קשה למדי; ספציפית, אם יש אלגוריתם שפותר אותו נובע מכך שלכל בעיה ב-NP יש אלגוריתם הסתברותי עם טעות חד צדדית שפותר
אותה, בפרט ל-SAT עצמה (בלשון סיבוכיותית, $\mbox{RP=NP}$ ). משפט VV מראה זאת על ידי תיאור של דרך לפתור את $\mbox{SAT}$ בעזרת פתרון לבעיה הפשוטה יותר – הוא עושה זאת באמצעות רדוקציה אקראית, ואסביר עכשיו מה זה בדיוק אומר.

באופן פורמלי, המשפט אומר שאם נתון לנו פסוק CNF $\varphi$ אז אפשר להמיר אותו (באופן הסתברותי) לפסוק $\mbox{CNF}$ $\varphi^{\prime}$ כך ש:

ההמרה מתבצעת בזמן יעיל (פולינומי באורך של $\varphi$ ).
אם $\varphi$ לא ספיק אז גם $\varphi^{\prime}$ לא ספיק.
אם $\varphi$ ספיק אז בהסתברות לא רעה ל- $\varphi^{\prime}$ יש בדיוק השמה מספקת אחת ("הסתברות לא רעה" כאן היא $\frac{1}{8n}$ כש- $n$ הוא מספר המשתנים של $\varphi$ ).

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

הבניה עצמה היא פשוטה באופן מפתיע. מה שנעשה יהיה להוסיף ל- $\varphi$ עוד אילוצים; פורמלית, $\varphi^{\prime}\left(x\right)=\varphi\left(x\right)\wedge\left(h\left(x\right)=0\right)$ , כאשר $h\left(x\right)=0$ כאן הוא קידוד של פסוק CNF שבודק ש- $h\left(x\right)=0$ עבור פונקציה $h$ שמוגרלת באופן מסויים שאסביר בקרוב. מייד נשאלת השאלה איך מקודדים את $h\left(x\right)=0$ בתור פסוק CNF; נדחה את השאלה הזו להמשך.

לב הרעיון, שמשתמשים בו במקומות נוספים בסיבוכיות, הוא לבחור את $h$ מתוך אוסף של פונקציות תמצות בלתי תלויות בזוגות. עזבו אתכם ממה זה אומר באופן כללי ובואו נדבר קונקרטית. אנחנו חושבים על $x$ (שהוא וקטור של $\mbox{T}$ ו- $\mbox{F}$ ) בתור איבר של $\mathbb{Z}_{2}^{n}$ – סדרה מאורך $n$ של אפסים ואחדים – ואנחנו מגרילים מטריצה $A\in\mathbb{Z}_{2}^{k\times n}$ עם $k$ שורות ו- $n$ עמודות, כך ש- $k$ עצמו נבחר באקראי מתוך $\left\{ 2,3,\dots,n+1\right\}$ (למה התחום המוזר הזה? יהיה הסבר, סבלנות) ובנוסף אנחנו מגרילים וקטור $b\in\mathbb{Z}_{2}^{k}$ , וכעת מגדירים $h\left(x\right)=Ax+b$ . כלומר, $h$ תלויה בביטים של $A$ ושל $b$ .

כדאי לחשוב על העניין כך: כל שורה $a^{i}\in\mathbb{Z}_{2}^{n}$ של $A$ מגדירה אילוץ מהצורה $a^{i}\cdot x=b_{i}$ (העברתי את ה- $b$ אגף, ומכיוון שאנחנו מעל $\mathbb{Z}_{2}$ אין צורך לשנות סימן). עכשיו, די בבירור אם אני מגריל את $a$ ואת $b_{i}$ בהתפלגות אחידה אז יש ל- $x$ נתון הסתברות של $\frac{1}{2}$ לקיים את האילוץ, כי אם "נקפיא" את $a$ אז עבור אחד מהערכים האפשריים של $b_{i}$ האילוץ יתקיים ועבור הערך השני של $b_{i}$ האילוץ לא יתקיים, ולכן הוא מתקיים בדיוק עבור חצי מהזוגות $\left(a,b_{i}\right)$ . במילים אחרות, לכל $x$ יש הסתברות של $\frac{1}{2}$ לשרוד כל אחד מהאילוצים, ומכיוון שכל $k$ האילוצים נבחרים באופן בלתי תלוי זה בזה, יש ל- $x$ סיכוי של $2^{-k}$ לשרוד את כל האילוצים. אם כן, $h$ מדללת באופן אקספוננציאלי את כמות ה- $x$ -ים שמספקים את $\varphi$ , ובגלל שיש לנו שליטה על $k$ נוכל לבחור את רמת הדילול המדוייקת שאנחנו צריכים, בהסתברות לא רעה. פורמלית: $\mbox{Pr}_{h}\left[h\left(x\right)=0\right]=2^{-k}$ . אסמן $p=2^{-k}$ לצורך פשטות.

בינתיים כל מה שעשיתי נראה מטופש להפליא. למה בכלל הגרלתי $A$ ? הרי היא לא סייעה לי בטיעון. הייתי יכול להגריל רק את $b$ ולהשוות אותו בכל פעם ל- $x_{1}+x_{2}+\dots+x_{n}$ וחסל. אלא שאני זקוק לעוד תכונה של ה- $h$ שאני מגריל – בדיוק תכונת הבלתי תלויות בזוגות שהוזכרה קודם; בלעדיה אני באמת לא אוכל לעשות הרבה. מה שאני רוצה לומר הוא שלא רק ש- $h$ מדללת "הרבה", אלא גם שהיא מדללת באופן שיוצר פער בין, נאמר, דילול שמשאיר רק השמה מספקת אחת בחיים ודילול שמשאיר שתיים כאלו בחיים. בשביל להראות את זה אני צריך להראות שההסתברות לכך ששתי השמות נתונות שונות זו מזו יישארו בחיים קטן משמעותית מההסתברות של השמה אחת להישאר בחיים. ספציפית, אני רוצה לחשב את $\mbox{Pr}\left[h\left(x\right)=0\wedge h\left(y\right)=0\right]$ עבור $x\ne y$ . כאן מגיע תעלול רעיוני שהוא לב ההוכחה ולטעמי הוא רעיון מקסים ביותר, למרות שהוא גם מאוד פשוט.

הרעיון הוא כזה: מכיוון ש- $x\ne y$ יש ביט, נאמר $i$ , כך ש- $x_{i}=0$ ו- $y_{i}=1$ (או הפוך). נסתכל על אילוץ $\left(a^{k},b_{k}\right)$ כלשהו ש- $x$ מספק, כלומר $a^{k}\cdot x=b_{k}$ . אז מכיוון ש- $x_{i}=0$ , זה אומר שהביט במקום ה- $i$ בוקטור $a^{k}$ לא משנה את הערך של $a^{k}\cdot x$ ; בפרט, אם אגדיר $c^{k}$ כך ש- $a^{k}=c^{k}$ בכל ביט פרט לביט ה- $i$ ושם הם הפוכים, אז יתקיים גם $c^{k}\cdot x=b_{k}$ .

לעומת זאת, לא ייתכן ש- $a^{k}\cdot y=c^{k}\cdot y$ , כי הערכים של $a^{k}\cdot y,c^{k}\cdot y$ נבדלים ב-1 בדיוק (הסבירו את זה לעצמכם!) ולכן $y$ מקיים בדיוק אחד משני האילוצים $a^{k}\cdot y=b_{k}$ ו- $c^{k}\cdot y=b_{k}$ , כלומר $y$ מקיים בדיוק חצי מהאילוצים ש- $x$ מקיים, כלומר ההסתברות לכך ש- $y$ יקיים אילוץ בהינתן ש- $x$ מקיים אותו היא $\frac{1}{2}$ , כלומר ההסתברות ש- $x,y$ יקיימו אילוץ מסויים בו זמנית היא $\frac{1}{4}$ , ולכן ההסתברות ששניהם יקיימו זמנית את כל האילוצים היא $4^{-k}$ , כלומר $\mbox{Pr}\left[h\left(x\right)=0\wedge h\left(y\right)=0\right]=p^{2}$ . אם הבנתם את זה – הבנתם את העיקר בהוכחה (שימו לב שהעיקר הזה הוא תכונה כללית של פונקציות תמצות בלתי תלויות בזוגות; זה לא משהו שייחודי למשפט הנוכחי).

עכשיו בואו נבין איך זה עוזר לנו. נסמן ב- $S$ את קבוצת ההשמות שמספקות את $\varphi$ . בבירור אם $S$ ריקה אז אין השמה שמספקת את $\varphi^{\prime}$ (כי כל השמה שמספקת את $\varphi^{\prime}$ בפרט צריכה לספק את $\varphi$ ). לכן נניח ש- $\left|S\right|\ge1$ . נסמן ב- $N$ את מספר ההשמות ב- $S$ שמקיימות $h\left(x\right)=0$ ; זה משתנה מקרי שתלוי בבחירת $h$ . אנחנו רוצים למצוא מהו $\mbox{Pr}_{h}\left[N=1\right]$ . דרך אחת לעשות זאת היא כך: $\mbox{Pr}_{h}\left[N=1\right]=\mbox{Pr}_{h}\left[N\ge1\right]-\mbox{Pr}_{h}\left[N\ge2\right]$ (הסבירו לעצמכם למה!) ולכן, אם אנחנו רוצים למצוא חסם מלמטה עבור $\mbox{Pr}_{h}\left[N=1\right]$ (אין צורך לחשב את ההסתברות במדויק) מספיק למצוא חסם מלמטה עבור $\mbox{Pr}_{h}\left[N\ge1\right]$ וחסם מלמעלה עבור $\mbox{Pr}_{h}\left[N\ge2\right]$ .

כדי להקל על הסימונים, בואו נסמן בתור $A_{x}$ את המאורע " $h\left(x\right)=0$ " (כלומר, $A_{x}$ היא קבוצת ה- $h$ -ים שמקיימים $h\left(x\right)=0$ ) ובדומה נסמן ב- $A_{x,y}$ את המאורע " $h\left(x\right)=0\wedge h\left(y\right)=0$ ". כעת:

$\mbox{Pr}_{h}\left[N\ge2\right]=\mbox{Pr}\left[\bigcup_{x<y\in S}A_{x,y}\right]\le\sum_{x<y\in S}\mbox{Pr}\left[A_{x,y}\right]=\sum_{x<y\in S}p^{2}={\left|S\right| \choose 2}p^{2}$

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

לחסום את $\mbox{Pr}\left[N\ge1\right]$ מלמטה זה קצת יותר מחוכם. התעלול הוא להשתמש בעקרון הההכלה וההפרדה. כשמפעילים אותו על המקרה הנוכחי, מקבלים:

$\mbox{Pr}\left[N\ge1\right]=\mbox{Pr}\left[\bigcup A_{x}\right]-\mbox{Pr}\left[\bigcup A_{x,y}\right]+\mbox{Pr}\left[\bigcup A_{x,y,z}\right]-\dots$

(למה? ובכן, אם נכפול את שני אגפי המשוואה במספר ה- $h$ -ים הכולל האפשרי, נוכל להפסיק לדבר על הסתברות ולעבור לדבר על קומבינטוריקה סופית טהורה ואז יהיה יותר ברור שעקרון ההכלה וההפרדה תקף כאן). הנקודה הקריטית כאן היא שה"זנב" $\mbox{Pr}\left[\bigcup A_{x,y,z}\right]-\mbox{Pr}\left[\bigcup A_{x,y,z,w}\right]+\dots$ הוא חיובי, כי אפשר לפרק אותו לזוגות של "משהו חיובי פחות משהו קטן ממנו". לכן אפשר להיפטר מהזנב לגמרי:

$\mbox{Pr}\left[N\ge1\right]\ge\mbox{Pr}\left[\bigcup A_{x}\right]-\mbox{Pr}\left[\bigcup A_{x,y}\right]=\left|S\right|p-{\left|S\right| \choose 2}p^{2}$

ועכשיו מחיבור שני האי שוויונות שמצאנו, נקבל:

$\mbox{Pr}\left[N=1\right]=\mbox{Pr}_{h}\left[N\ge1\right]-\mbox{Pr}_{h}\left[N\ge2\right]\ge\left|S\right|p-2{\left|S\right| \choose 2}p^{2}\ge\left|S\right|p-\left(\left|S\right|p\right)^{2}$

עכשיו, את הפונקציה $f\left(t\right)=t-t^{2}$ קל לחקור אם יודעים טיפה אינפי; מהר מאוד רואים שבקטע $\left[\frac{1}{4},\frac{1}{2}\right]$ היא פונקציה עולה, לכן המינימום שלה מתקבל ב- $t=\frac{1}{4}$ והוא $\frac{1}{4}-\frac{1}{16}=\frac{3}{16}>\frac{1}{8}$ . לכן הגענו למסקנה הבאה: אם $\frac{1}{4}\le\left|S\right|p\le\frac{1}{2}$ , אז $\mbox{Pr}\left[N=1\right]\ge\frac{1}{8}$ . לא רע בכלל!

עכשיו, מהו $p$ ? כזכור, $p=2^{-k}$ . ומי זה $k$ ? את $k$ בחרנו באקראי בתחום $\left\{ 2,\dots,n+1\right\}$ . אז כדי שיתקיים $\frac{1}{4}\le\left|S\right|p\le\frac{1}{2}$ צריך שיתקיים $2^{k-2}\le\left|S\right|\le2^{k-1}$ . אבל, מכיוון ש- $1\le\left|S\right|\le2^{n}$ , זה בהכרח קורה לאחד מה- $k$ -ים בדיוק בתחום $\left\{ 2,\dots,n+1\right\}$ , שאני מקווה שעכשיו נראה קצת יותר ברור. לכן ההסתברות שלנו לבחור $k$ "נכון" היא $\frac{1}{n}$ (גודל התחום), ולכן ההסתברות של הרדוקציה כולה לעבור היא לפחות $\frac{1}{8n}$ – בדיוק מה שהבטחתי שאוכיח. סיימנו!

ובכן, לא, עוד לא סיימנו כי עוד לא הסברתי איך לקודד את $h\left(x\right)=0$ . זה לא מובן מאליו; צריך להיזהר ולא לקודד את הביטוי הזה על ידי נוסחת CNF גדולה מדי. כדי לעשות את זה אהיה חייב להשתמש במשתני עזר; קיימת הוכחה לכך שאפילו מקרה פרטי – הנוסחה $x_{1}\oplus\dots\oplus x_{n}=0$ , הידועה גם בתור הפונקציה PARITY – לא ניתן לקודד כפסוק CNF קצר (פולינומי) באופן כזה שכל השמה למשתנים תחזיר את הערך הנכון של הפרדיקט $x_{1}\oplus\dots\oplus x_{n}=0$ . אז מה שאעשה יהיה שונה: אני אקודד את $h\left(x\right)=0$ על ידי פסוק $\psi\left(x,z\right)$ כך ש- $z$ הם משתני עזר, כך שאם $h\left(x\right)=0$ אז קיימת השמה יחידה למשתני העזר כך ש- $\psi\left(x,z\right)=\mbox{T}$ ; ואחרת אף השמה לא תספק את $\psi$ . לבקיאים רק אציין שאפשר לעצור כבר כאן באמירה "ניקח מכונת טיורינג דטרמיניסטית שבודקת אם $h\left(x\right)=0$ ומקבלת אם כן, ו- $\psi$ יהיה קידוד קוק-לוין של הריצה שלה" אבל לטובת אלו מכם שאין להם מושג מה אמרתי, או לא זוכרים
את הפרטים של קוק-לוין, אתן כאן בניה ישירה. ולמען הסר ספק: אני עצמי לא ממש זוכר את הפרטים של קוק-לוין ומעדיף הרבה יותר לראות בניה ישירה מאשר את נפנוף הידיים המתועב הזה.

בואו נתחיל ממשהו פשוט: איך אני מקודד ב-CNF את $x\oplus y$ ? פשוט מאוד: $\left(x\vee y\right)\wedge\left(\neg x\vee\neg y\right)$ . מה קורה פה? אם $x=y$ אז או ש- $x\vee y$ לא יסתפק (אם $x=y=\mbox{F}$ ) או ש- $\neg x\vee\neg y$ לא יסתפק (אם $x=y=\mbox{T}$ ). ההכללה של זה לשלושה משתנים לא מסובכת: את $x\oplus y\oplus w$ נקודד בתור $\left(x\vee\neg y\vee\neg w\right)\wedge\left(\neg x\vee\neg y\vee w\right)\wedge\left(\neg x\vee y\vee\neg w\right)\wedge\left(x\vee y\vee w\right)$ . האם אתם רואים את העקרון? בכל זוג סוגריים צריכים להיות מספר זוגי של שלילות. כך, אם יש לנו השמה כלשהי למשתנים שבה מספר זוגי של משתנים קיבל $\mbox{T}$ , יהיה זוג סוגריים שיחזיר $\mbox{F}$ (בדיוק זה שבו אותם המשתנים מופיעים עם $\neg$ ) ולעומת זאת כל השמה שבה מספר אי זוגי של משתנים קיבל $\mbox{T}$ בהכרח תספק את כל זוגות הסוגריים (כי אז אז או שאחד מהמשתנים שקיבלו $\mbox{T}$ מופיע בלי $\neg$ , או שאחד מהמשתנים שקיבל $\mbox{F}$ מופיע עם $\neg$ ). אלא
שאם יש לנו $n$ משתנים, זה אומר שנצטרך ליצור פסוק עם המון פסוקיות – $2^{n-1}$ (פורמלית, ${n \choose 0}+{n \choose 2}+\dots$ ויש תעלולים שמראים שהסכום אכן יוצא $2^{n-1}$ ). בקיצור, אקספוננציאלי. אז השיטה הישירה לא תעבוד כאן ואנחנו חייבים משהו מתוחכם יותר.

הנה תעלול אפשרי אחד: אם אנחנו רוצים לקודד את $x_{1}\oplus x_{2}\oplus\dots\oplus x_{n}$ , אפשר תחת זאת לקודד את $\left(z_{1}=x_{1}\oplus x_{2}\right)\wedge\left(z_{2}=z_{1}\oplus x_{3}\right)\wedge\dots\wedge\left(z_{n-1}=z_{n-2}\oplus x_{n}\right)\wedge\left(z_{n-1}\right)$ . זה יפתור לנו את הבעיה, בהינתן שאפשר לקודד משהו כמו $z=x\oplus y$ בעזרת פסוק CNF מאורך פולינומי. ובכן, איך מוצאים דבר כזה באופן שיטתי, בלי ניסוי וטעיה? ראשית כותבים את $z\ne x\oplus y$ בתור DNF דווקא; לכתוב DNF זה קל כי פשוט מבצעים $\vee$ על כל ארבע ההשמות האפשריות שיספקו את $z\ne x\oplus y$ : $\left(x\wedge y\wedge z\right)\vee\left(\neg x\wedge\neg y\wedge z\right)\vee\left(\neg x\wedge y\wedge\neg z\right)\vee\left(x\wedge\neg y\wedge\neg z\right)$ . עכשיו מפעילים שלילה על הפסוק כולו ומשתמשים בכללי דה-מורגן, ומקבלים $\left(\neg x\vee\neg y\vee\neg z\right)\wedge\left(x\vee y\vee\neg z\right)\wedge\left(x\vee\neg y\vee z\right)\wedge\left(\neg x\vee y\vee z\right)$ . זה מסיים את ההוכחה כולה.

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

תגים: SAT, עקרון ההכלה וההפרדה, תורת הסיבוכיות, הסתברות
שייך לקטגוריות תורת הסיבוכיות | 3 תגובות »

מרחבי מכפלה פנימית – לפעמים הצמדה היא באמת הצמדה

29 באפריל, 2012

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

תזכורת קצרה: $V$ הוא מרחב מכפלה פנימית אם הוא מרחב וקטורי מעל $\mathbb{C}$ שמוגדרת בו פונקציה $\left\langle \cdot,\cdot\right\rangle :V\times V\to\mathbb{C}$ שהיא לינארית במשתנה הראשון (כלומר, $\left\langle \lambda x+y,z\right\rangle =\lambda\left\langle x,z\right\rangle +\left\langle y,z\right\rangle$ ), הרמיטית – $\left\langle x,y\right\rangle =\overline{\left\langle y,x\right\rangle }$ ("כמעט" סימטרית עד כדי הצמוד למעלה, שאת הסיבות לו הסברתי בעבר) וחיובית, כלומר $\left\langle x,x\right\rangle \ge0$ ושוויון הוא רק כש- $x=0$ . פונקציונל לינארי במקרה שלנו הוא פונקציה לינארית $f:V\to\mathbb{C}$ . הדמיון למכפלה פנימית די ברור – פונקציונל פועל על איבר אחד ואילו מכפלה פנימית על שניים, אבל שניהם מחוייבים ללינאריות מסוג כלשהו. אם המרחב $V$ הוא סוף-ממדי (ואני מתכנן לדבר רק על מרחבי מכפלה פנימית סוף ממדיים; מה שקורה במרחבים אינסוף מימדיים הוא נושא לסדרת פוסטים ארוכה אף יותר מהנוכחית), הדמיון הוא לחלוטין לא מקרי – מסתבר שכל פונקציונל לינארי על
$V$ ניתן לתיאור באופן יחיד באמצעות המכפלה הפנימית (במרחב אינסוף ממדי זה פשוט לא נכון, אם כי לא אציג דוגמאות נגדיות כעת).

בואו ראשית כל נשחק במשחק הבא: ניקח $y\in V$ כלשהו ונחשוב עליו כעל "קבוע". אז אפשר להגדיר פונקציה $f_{y}:V\to\mathbb{C}$ של "מכפלה פנימית ב- $y$ ", כלומר $f_{y}\left(x\right)=\left\langle x,y\right\rangle$ . קל לראות ש- $f_{Y}$ היא פונקציונל לינארי, פשוט בגלל הלינאריות של המכפלה הפנימית; מה שקורה במרחב סוף ממדי הוא שכל פונקציונל לינארי $f$ ניתן להצגה כ- $f_{y}$ עבור $y$ אחד ויחיד ספציפי. איך מוצאים אותו? בעזרת הכלי הסטנדרטי שלנו להתמודדות עם מרחבי מכפלה פנימית – בסיסים אורתונורמליים.

ניקח בסיס אורתונורמלי $u_{1},\dots,u_{n}$ למרחב. בהינתן $x\in V$ כלשהו, אנחנו יודעים ש- $x=\sum\left\langle x,u_{i}\right\rangle u_{i}$ (זוכרים? כשמייצגים איבר בבסיס אורתונורמלי, המקדם של איבר הבסיס $u_{i}$ בצירוף הלינארי הוא בדיוק המכפלה הפנימית של $x$ ב- $u_{i}$ . קוראים לזה "מקדם פורייה" של $x$ בבסיס $u_{1},\dots,u_{n}$ ). אנחנו גם יודעים איך מכפלה פנימית של שני איברים כלליים נראית: אם $y=\sum\left\langle y,u_{i}\right\rangle u_{i}$ הוא איבר תמים אחר של $V$ ואנו כופלים אותו ב- $x$ , נקבל:

$\left\langle x,y\right\rangle =\left\langle \sum\left\langle x,u_{i}\right\rangle u_{i},\sum\left\langle y,u_{j}\right\rangle u_{j}\right\rangle =\sum_{i,j}\left\langle x,u_{i}\right\rangle \overline{\left\langle y,u_{j}\right\rangle }\left\langle u_{i},u_{j}\right\rangle =\sum_{i}\left\langle x,u_{i}\right\rangle \overline{\left\langle y,u_{i}\right\rangle }$

כעת, אם נפעיל את $f$ על $x$ ונשתמש בלינאריות שלו, נקבל ש- $f\left(x\right)=\sum\left\langle x,u_{i}\right\rangle f\left(u_{i}\right)$ . זה מאוד מזכיר את המשוואה שלמעלה, אם $f\left(u_{i}\right)=\overline{\left\langle y,u_{i}\right\rangle }$ , ובניסוח אחר $\left\langle y,u_{i}\right\rangle =\overline{f\left(u_{i}\right)}$ . זה מוביל אותנו להגדרה הבאה: $y\triangleq\sum\overline{f\left(u_{i}\right)}u_{i}$ . כעת קל לוודא שאכן $f\left(x\right)=\left\langle x,y\right\rangle$ לכל $x\in V$ . כדי לוודא ש- $y$ הוא יחיד, נניח כי ישנם $y_{1},y_{2}$ כך ש- $\left\langle x,y_{1}\right\rangle =f\left(x\right)=\left\langle x,y_{2}\right\rangle$ לכל $x$ , כלומר $\left\langle x,y_{1}-y_{2}\right\rangle =0$ לכל $x$ . במרחב סוף ממדי זה יכול לקרות רק אם $y_{1}-y_{2}=0$ , כלומר $y_{1}=y_{2}$ (למה בעצם אם $\left\langle x,y\right\rangle =0$ לכל $x$ זה גורר ש- $y=0$ ? תרגיל טוב).

בפוסט שליעל פונקציונלים לינאריים הערתי שיש איזומורפיזם בין $V$ ובין $V^{*}$ - מרחב הפונקציונלים הלינאריים מעל $V$ , אך הוא אינו "קנוני" – כלומר, עבור בחירות בסיס שונות עבור $V$ נקבל איזומורפיזמים שונים ואין דרך להכריע מי מביניהם יותר "נכון". במקרה שבו $V$ הוא מרחב מכפלה פנימית, קיבלנו איזומורפיזם קנוני לעילא ולעילא – $y\mapsto f_{y}$ , שאינו תלוי בבחירת בסיס זה או אחר למרחב. כמובן שאני קצת משקר כאן – האיזומורפיזם הזה עדיין תלוי בבחירת מכפלה פנימית למרחב, והיא שקולה לבחירת בסיס, אבל נעזוב את זה.

בואו נעבור לדבר עכשיו על משהו אחר – אופרטורים לינאריים, כלומר טרנספורמציות לינאריות $T:V\to V$ מ- $V$ לעצמו. השאלה הראשונה שאני שואל היא שאלה של סימטריה: נניח שיש לי וקטורים $x,y$ , ואני מפעיל את $T$ על $x$ ואז כופל את התוצאה עם $y$ – האם אקבל את אותו הדבר כאילו הפעלתי את $T$ על $y$ וכפלתי את $x$ בזה? כלומר, האם $\left\langle Tx,y\right\rangle =\left\langle x,Ty\right\rangle$ ? התשובה היא שלא תמיד, ושאופרטורים שמקיימים את התכונה הזו הם מעניינים למדי – הם נקראים אופרטורים הרמיטיים (ומעל $\mathbb{R}$ - סימטריים). קחו רגע ונסו להסביר לעצמכם למה השוויון $\left\langle Tx,y\right\rangle =\left\langle x,Ty\right\rangle$ כלל לא מובן מאליו.

אוקיי, אז לא תמיד מתקיים $\left\langle Tx,y\right\rangle =\left\langle x,Ty\right\rangle$ . עדיין, התחושה האינטואיטיבית היא שמידת מה של סימטריה צריכה להיות כאן, והתחושה הזו מדוייקת – לכל אופרטור $T$ מותאם אופרטור $T^{*}$ – הצמוד ההרמיטי של $T$ – כך ש- $\left\langle Tx,y\right\rangle =\left\langle x,T^{*}y\right\rangle$ . זה המשפט העיקרי שאני רוצה להוכיח בפוסט. כעת אפשר לתאר אופרטור הרמיטי בצורה קצת יותר פשוטה: זה אופרטור שמקיים $T=T^{*}$ , כלומר הוא שווה לצמוד ההרמיטי שלו; כלומר הוא צמוד לעצמו. זה עוד שם לאופרטורים הרמיטיים.

הוכחת הקיום של $T^{*}$ היא מחוכמת ואלגנטית. הבה ונקבע את $y$ לרגע, אז אפשר להגדיר פונקציונל לינארי $f\left(x\right)=\left\langle Tx,y\right\rangle$ . במילים אחרות, בהינתן $x$ נתעלל בו על ידי הפעלת $T$ עליו ואז מכפלה פנימית של כל זה עם $y$ . זה אכן פונקציונל כי $T$ היא טרנספורמציה לינארית ומכפלה פנימית היא לינארית. אם $f$ הזו היא פונקציונל, אז יש איזה שהוא $z$ שמגדיר אותה: $f\left(x\right)=\left\langle x,z\right\rangle$ . במילים אחרות, $\left\langle x,z\right\rangle =\left\langle Tx,y\right\rangle$ , ולכן אם קיים בכלל $T^{*}$ שהוא צמוד הרמיטי של $T$ , אז הוא מקיים $\left\langle x,z\right\rangle =\left\langle x,T^{*}y\right\rangle$ . במילים אחרות, אנחנו נדחפים להגדרה $T^{*}\left(y\right)=z$ .

באופן הזה אפשר להגדיר את $T^{*}$ לכל איבר $y\in V$ . צריך לוודא שאכן קיבלנו אופרטור לינארי; שום דבר לא מבטיח לנו שהתנאי ההכרחי שמצאנו עבור $T^{*}$ (שקבע באופן יחיד איך הוא חייב להיראות) הוא גם מספיק כדי שהוא אכן יהיה אופרטור לינארי; זה ה"קסם" שיש כאן. אם כן, יהיו $y_{1},y_{2}$ כך ש- $T^{*}\left(y_{1}\right)=z_{1}$ ו- $T^{*}\left(y_{2}\right)=z_{2}$ ; נרצה להראות ראשית ש- $T^{*}\left(y_{1}+y_{2}\right)=z_{1}+z_{2}$ . נסמן $T^{*}\left(y_{1}+y_{2}\right)=z$ ; אנחנו יודעים ש-

$\left\langle x,z\right\rangle =\left\langle Tx,y_{1}+y_{2}\right\rangle =\left\langle Tx,y_{1}\right\rangle +\left\langle Tx,y_{2}\right\rangle =\left\langle x,z_{1}\right\rangle +\left\langle x,z_{2}\right\rangle =\left\langle x,z_{1}+z_{2}\right\rangle$

השוויון $\left\langle x,z\right\rangle =\left\langle x,z_{1}+z_{2}\right\rangle$ עבור ערך ספציפי של $x$ לא מספיק כדי להסיק ש- $z=z_{1}+z_{2}$ , אבל מכיוון שזה נכון עבור כל $x$ זה מספיק (שוב – למה?). באופן דומה גם מראים ש- $T^{*}\left(\lambda y\right)=\lambda T^{*}\left(y\right)$ ולכן $T^{*}$ אכן לינארית.

עכשיו, אנחנו יודעים שבמרחב סוף-ממדי כל טרנספורמציה לינארית ניתנת לייצוג באמצעות מטריצות; נניח שקבענו איזה בסיס אורתונורמלי של המרחב, $B=\left\{ u_{1},\dots,u_{n}\right\}$ , ואנחנו מסתכלים על $\left[T\right]_{B}$ – המטריצה המייצגת של $T$ ביחס לבסיס הזה. מה הקשר בינה ובין המטריצה המייצגת של $\left[T^{*}\right]_{B}$ ? האם יש לנו תיאור קונקרטי וקל לחישוב של האופן שבו הייצוג הנוח של $T$ הופך לייצוג נוח של $T^{*}$ ? התשובה חיובית, במקרה שבו $B$ אורתונורמלי. זכרו שהעמודה ה- $i$ -ית של המטריצה $\left[T^{*}\right]_{B}$ היא בדיוק וקטור הקואורדינטות לפי $B$ של $T^{*}\left(u_{i}\right)$ (הפעלת $T^{*}$ על איבר הבסיס ה- $i$ ב- $B$ ), או במילים אחרות – הכניסה ה- $j,i$ של $\left[T^{*}\right]_{B}$ היא בדיוק $\left\langle T^{*}\left(u_{i}\right),u_{j}\right\rangle$ . בואו נעשה תעלול אלגברי זריז:

$\left\langle T^{*}\left(u_{i}\right),u_{j}\right\rangle =\overline{\left\langle u_{j},T^{*}\left(u_{i}\right)\right\rangle }=\overline{\left\langle T\left(u_{j}\right).u_{i}\right\rangle }$

אבל מה זה $\left\langle T\left(u_{j}\right).u_{i}\right\rangle$ ? זה בדיוק המקדם של $u_{i}$ בצירוף הלינארי שמגדיר את $T\left(u_{j}\right)$ . במילים אחרות, זו הכניסה ה- $i,j$ של המטריצה $\left[T\right]_{B}$ !

זה מוביל אותנו להגדרה הבאה: אם $A$ היא מטריצה ריבועית כלשהי מעל המרוכבים, אז המטריצה הצמודה שלה מוגדרת בתור $A^{*}=\overline{A^{t}}$ , כלומר ביצוע שחלוף והצמדה, כלומר $A_{ij}^{*}=\overline{A_{ji}}$ . כשמדובר במטריצות קל למדי לראות שמתקיימות התכונות הבאות של הצמדה (שאני מנסח בלשון טרנספורמציות כי הן תקפות באותה מידה גם לטרנספורמציות):

$\left(T+S\right)^{*}=T^{*}+S^{*}$
$\left(\lambda T\right)^{*}=\overline{\lambda}T^{*}$
$\left(TS\right)^{*}=S^{*}T^{*}$
$\left(T^{*}\right)^{*}=T$

ארבע התכונות הללו מראות לנו שיש מבנה אלגברי כלשהו לפעולה של "קח טרנספורמציה והחזר את הצמודה שלה" – בלשון פונקציות, $f\left(T\right)=T^{*}$ . תכונות 1 ו-2 אומרות שהפונקציה הזו היא "כמעט לינארית", עד כדי כך שהוצאת סקלר כרוכה בהצמדה שלו – פונקציה כזו נקראת אנטי-לינארית, או לינארית-צמודה. התכונה הבאה מראה ש- $f$ הופכת איברים בכפל: $f\left(TS\right)=f\left(S\right)f\left(T\right)$ .
לפונקציה שמקיימת $f\left(ST\right)=f\left(S\right)f\left(T\right)$ קוראים הומומורפיזם ולכן ההצמדה שלנו, שעושה מעין היפוך של זה, נקראת אנטי-הומומורפיזם (מאוד אנטי כל העסק – אנטי-לינארי, אנטי-הומומורפיזם…). לסיום, תכונה 4 אומרת ש- $f\left(f\left(T\right)\right)=T$ – לפונקציה שמקיימת את זה קוראים אינבולוציה. בקיצור, ההצמדה שלנו היא פעולה שמקיימת כמה תכונות מוכרות וחביבות על המתמטיקאים.

באופן לא מפתיע, מסתבר שאפשר להשתמש בתכונות הללו כבסיס להכללה; זה הבסיס לתחום במתמטיקה של אלגברות $C$ -כוכב (אלגבראות $C^{*}$ ), שהן אלגבראות בנך עם פונקציה שמקיימת את תכונות 1-4 ועוד כמה תכונות שלא אכנס אליהן כעת (כמו שלא אכנס להגדרה של אלגברת בנך; כל הדברים הללו קשורים לאלגברה לינארית במרחב אינסוף ממדי). לא ארחיב לכיוון הזה עכשיו, אלא אדבר דווקא על דוגמה פשוטה ביותר לפונקציה לא טריוויאלית נוספת שמקיימת את תכונות 1-4, שאולי כבר קפצה לחלקכם לראש – הצמדה של מספרים מרוכבים. תכונות 1,2,4 שלה באות באופן טבעי לחלוטין; תכונה 3 נובעת מכך ש- $\overline{zw}=\overline{z}\cdot\overline{w}$ ומכך שבמספרים מרוכבים הכפל הוא קומוטטיבי, כלומר $\overline{w}\cdot\overline{z}$ . הדמיון הזה מסביר את השם צמוד בהקשר הנוכחי.

הדמיון לא נגמר כאן. במספרים מרוכבים מתקיימת התכונה הנחמדה שאם $z$ הוא מספר מרוכב כלשהו, אז $\frac{z+\overline{z}}{2}$ הוא החלק הממשי של $z$ , ואילו $\frac{z-\overline{z}}{2}$ הוא החלק המדומה של $z$ (בדקו בעצמכם אם אינכם זוכרים/יודעים/מאמינים). בואו נעשה דבר דומה עם טרנספורמציות: ניקח $T$ כלשהי ונגדיר $T_{R}=\frac{T+T^{*}}{2}$ ו- $T_{I}=\frac{T-T^{*}}{2}$ .

עכשיו, $T_{R}^{*}=\frac{1}{2}\left(T+T^{*}\right)^{*}=\frac{T^{*}+\left(T^{*}\right)^{*}}{2}=\frac{T+T^{*}}{2}=T_{R}$ , ולכן $T_{R}$ צמודה לעצמה; בדומה נקבל ש- $T_{I}^{*}=-T_{I}$ – לטרנספורמציה שמקיימת את התכונה הזו קוראים אנטי-הרמיטית. כפי שאתם ודאי שמים לב, $T_{R}$ מתנהג ביחס להצמדה כמו שמספר ממשי מתנהג ביחס אליה, ו- $T_{I}$ מתנהג כמו שמספר מדומה טהור מתנהג ביחס אליה. כעת שימו לב לכך ש- $T=T_{R}+T_{I}$ , כלומר כל טרנספורמציה לינארית במרחב סוף ממדי ניתן לרשום כסכום של טרנספורמציה הרמיטית וטרנספורמציה אנטי-הרמיטית (למעשה, אפשר גם להגדיר $T_{I}^{\prime}=\frac{T-T^{*}}{2i}$ ולקבל טרנספורמציה הרמיטית ואז הפירוק הוא $T=T_{R}+iT_{I}^{\prime}$ – שוב, בדיוק כמו עם מספרים מרוכבים). האנלוגיה הזו הלהיבה אותי מאוד בשעתו; זה תמיד מעניין לראות איך תכונות שקיימות במרוכבים הן ממש לא נחלתם הבלעדית אלא מעידות כנראה על משהו עמוק יותר מתחת לפני השטח.

בפוסט הבא – אופרטורים הרמיטיים ולמה הם מגניבים. יהיה אקשן.

תגים: מרחבי מכפלה פנימית, אופרטור הרמיטי
שייך לקטגוריות אלגברה לינארית | 2 תגובות »

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

24 באפריל, 2012

בפוסט הקודם על לוגיקה סיימתי להוכיח את משפט השלמות לתחשיב הפסוקים. לפני שנעבור הלאה, אני רוצה להתעכב טיפה על המסקנות מכל זה ולדבר עוד קצת על ההוכחה. בואו נתחיל ממסקנה לא טריוויאלית ממשפט השלמות: משפט הקומפטיות. משפט הקומפטיות אומר בפשטות שלתורה $\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}$ ", אבל במשפט טיכונוף הכרחי לגרור פנימה את הלמה של צורן, וגם אז העבודה לא נגמרת, אבל ההוכחה היא יחסית ישירה החל מהשלב הזה – עיקר הקושי הוא ברעיון הבסיסי שכבר הצגתי. מי שמעוניין במלוא הפרטים מוזמן לקרוא את מונקרס, או להמתין ליום שבו אכתוב פוסט (ראוי מאוד) שיוקדש להוכחה הזו.

תגים: משפט טיכונוף, משפט הקומפקטיות, תחשיב הפסוקים
שייך לקטגוריות לוגיקה, טופולוגיה | אין תגובות »

כיצד תעזור לכם המתמטיקה לחמוק מדו"חות תנועה

21 באפריל, 2012

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

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

הידע שכן צריך בשביל להבין על מה קריוקוב מדבר הוא המתמטיקה הבסיסית שעוסקת בתנועה – חשבון דיפרנציאלי ואינטגרלי. למזלי הכינותי מבעוד מועד פוסטים על נגזרות ואינטגרלים, כך שלא אחזור על החומר הזה שוב לעומק. מה שחשוב לענייננו זה שאם יש לנו פונקציה $x\left(t\right)$ שמתארת את המיקום של הרכב כפונקציה של הזמן $t$ , אז המהירות של הרכב היא הנגזרת שלה; ובכיוון ההפוך, האינטגרל של המהירות בין שתי נקודות זמן מתאר את המרחק שהיא עברה בזמן זה.

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

כאן $r_{0}$ הוא המרחק הקבוע של השוטר משלט ה"עצור" (שאותו קובע קריוקוב בתור ראשית הצירים, כלומר $x=0$ בדיוק בנקודה זו). הקשר בין הזווית $\alpha$ שבה השוטר רואה את קריוקוב ובין המרחק $x\left(t\right)$ של קריוקוב משלט ה"עצור" ברגע $t$ נתון על ידי הקשר הטריגונומטרי $\tan\alpha\left(t\right)=\frac{x\left(t\right)}{r_{0}}$ . קריוקוב רוצה את $\alpha\left(t\right)$ עצמה, אז הוא מפעיל את הפונקציה $\arctan$ על שני האגפים ומקבל $\alpha\left(t\right)=\arctan\left(\frac{x\left(t\right)}{r_{0}}\right)$ . כדי לקבל את קצב ההשתנות של $\alpha\left(t\right)$ צריך לגזור את המשוואה (הפשוטה!) הזו: לגזור פונקציות כאלו זה תרגיל בסיסי בחדו"א. בואו נציג במפורש את האופן שבו אפשר לעשות זאת תוך שימוש בכללי הגזירה הבסיסיים, סתם כדי לראות שאנחנו יכולים (קריוקוב לא טורח).

ובכן, כלל הגזירה הבסיסי והחשוב ביותר כאן הוא כלל השרשרת: אם $f,g$ פונקציות גזירות אז $\left(f\left(g\left(x\right)\right)\right)^{\prime}=f^{\prime}\left(g\left(x\right)\right)g^{\prime}\left(x\right)$ . בפרט, אם $g\left(x\right)$ היא פונקציה המקיימת $f\left(g\left(x\right)\right)=x$ (כלומר, $g$ היא "הפוכה" ל- $f$ , בדיוק כמו הקשר בין $\arctan$ ו- $\tan$ ) אז גזירה עם כלל השרשרת נותנת לנו $f^{\prime}\left(g\left(x\right)\right)g^{\prime}\left(x\right)=1$ , כלומר $g^{\prime}\left(x\right)=\frac{1}{f^{\prime}\left(g\left(x\right)\right)}$ – זו הנוסחה של "נגזרת הפונקציה ההופכית".

כעת, $\tan x=\frac{\sin x}{\cos x}$ . זו אחת מהתכונות היסודיות ביותר של סינוס וקוסינוס שהנגזרות שלהם הן $\sin^{\prime}x=\cos x$ ו- $\cos^{\prime}x=-\sin x$ . כמו כן כלל בסיסי בגזירה הוא ש- $\left(\frac{f}{g}\right)^{\prime}=\frac{f^{\prime}g-g^{\prime}f}{g^{2}}$ , וכך נקבל ש- $\tan^{\prime}x=\frac{\cos^{2}x+\sin^{2}x}{\cos^{2}x}=1+\tan^{2}x$ . לכן, מנוסחת הגזירה של הפונקציה ההפוכה, $\arctan^{\prime}x=\frac{1}{1+\tan^{2}\left(\arctan\left(x\right)\right)}=\frac{1}{1+x^{2}}$ . הנה לכם איך מגיעים לנוסחה הזו לכל מי שלא מכיר/זוכר.

עכשיו, בואו נחזור אל $\alpha\left(t\right)=\arctan\left(\frac{x\left(t\right)}{r_{0}}\right)$ ונגזור אותו על פי כלל השרשרת: $\alpha^{\prime}\left(t\right)=\frac{1}{1+\left(\frac{x\left(t\right)}{r_{0}}\right)^{2}}\cdot\frac{x^{\prime}\left(t\right)}{r_{0}}$ . קריוקוב לא כותב את הנוסחה הכללית הזו אלא מציב מראש מקרים פרטיים. יש שני מקרים שמעניינים אותו: הראשון, מה שהשוטר חושב שהוא ראה, שהוא תנועה במהירות קבועה; והשני, מה שקריוקוב טוען שקרה, שהוא תנועה שבה הגוף מאיט בקצב קבוע, ואז מאיץ בקצב קבוע.

במקרה של תנועה במהירות קבועה $v_{0}$ , הפונקציה של מיקום הגוף היא $x\left(t\right)=v_{0}t$ (אם מסכימים על כך ש- $t=0$ הוא הרגע שבו קריוקוב היה בסימן ה"עצור", כלומר ב- $x=0$ ). הנגזרת כאן פשוטה במיוחד: $x^{\prime}\left(t\right)=v_{0}$ . לכן על פי הנוסחה שפיתחנו למעלה, מהירות הרכב שהשוטר רואה היא:

$\frac{v_{0}/r_{0}}{1+\left(\frac{v_{0}}{r_{0}}\right)^{2}t^{2}}$

במילים אחרות, מה שהשוטר רואה נראה כמו הפונקציה $f\left(t\right)=\frac{\alpha}{1+\alpha^{2}t^{2}}$ כאשר $\alpha$ הוא קבוע שתלוי במהירות הרכב ומרחק השוטר משלט ה"עצור". פונקציה כמו $f\left(t\right)$ הזו היא בבירור לא קבועה: ככל ש- $t$ גדול יותר כך היא שואפת מהר מאוד לאפס. המקסימום שלה מתקבל כאשר $t=0$ ואז ערכה הוא $\alpha$ . את הפונקציה קריוקוב מצייר בגרף הבא:

המקרה השני, שבו הרכב קודם מאיט ואחר כך מאיץ, דורש מקריוקוב קצת יותר עבודה כדי למצוא את $x\left(t\right)$ . מה הנתונים שיש לנו הפעם? ובכן, אנחנו יודעים שבזמן $t=0$ הרכב היה בשלט העצור, ובמהירות אפס, כלומר $x\left(0\right)=v\left(0\right)=0$ (השוויון הוא של מספרים; היחידות של $x\left(t\right)$ ושל $v\left(t\right)$ שונות ולכן אין משמעות פיזיקלית לכתיבה של משהו כמו $x\left(t\right)=v\left(t\right)$ באופן כללי). אנחנו גם יודעים (ליתר דיוק, מניחים) שהתאוצה קבועה והיא $a_{0}$ כלשהו. ליתר דיוק, היא $a_{0}$ אחרי העצירה; לפני העצירה היא $-a_{0}$ – אותו גודל, אבל האטה במקום האצה. בגלל הסימטריה של העניין מספיק לבחון את מה שקורה אחרי העצירה.

תאוצה היא נגזרת של המהירות, ומהירות היא נגזרת של המיקום, ולכן על ידי ביצוע שתי אינטגרציות נקבל: $x\left(t\right)=\int\left(\int a_{0}dt\right)dt=\int\left(a_{0}t+c\right)=\frac{a_{0}}{2}t^{2}+ct+d$ כאשר $c,d$ קבועים. נציב $t=0$ ונשתמש בכך ש- $x\left(0\right)=0$ כדי לקבל ש- $d=0$ ; בדומה גם $c=0$ כי $v\left(t\right)=a_{0}t+c$ . לכן קיבלנו ש- $x\left(t\right)=\frac{a_{0}}{2}t^{2}$ (וכאשר $t<0$ , אז $x\left(t\right)=-\frac{a_{0}}{2}t^{2}$ ; במאמר עצמו קריוקוב טיפה מתבלבל פה ופשוט נותן את $x\left(t\right)=\frac{a_{0}}{2}t^{2}$ בתור הנוסחה הכללית). אם נציב את זה בנוסחה של $\alpha^{\prime}$ נקבל את הביטוי הלא מצודד הבא:

$\alpha^{\prime}\left(t\right)=\frac{\left(a_{0}/r_{0}\right)t}{1+\frac{1}{4}\left(\frac{a_{0}}{r_{0}}\right)^{2}t^{4}}$

במילים אחרות, זוהי פונקציה מהצורה $g\left(t\right)=\frac{\alpha t}{1+\frac{1}{4}\alpha^{2}t^{4}}$ עבור קבוע $\alpha$ שתלוי רק בתאוצה ובמרחק השוטר משלט ה"עצור". בגלל ה- $t^{4}$ שבמכנה כל העסק שואף מהר מאוד לאפס כש- $t$ גדול או קטן, אבל ה- $t$ במונה משנה את מה שקורה בסביבות $t=0$ ; כאשר $t=0$ הפונקציה היא ממש אפס (הרי אמרנו שהרכב עוצר…). מצד שני, עבור ערכי $t$ שאינם גדולים אבל גם אינם אפס, הפונקציה דווקא יכולה להיות גדולה למדי – יש לה שתי נקודות מקסימום משני עברי נקודת המינימום שבאפס. ככה זה נראה:

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

אז צריך למצוא מה בדיוק המרחק בין ה"פסגות" של פונקצית המהירות שהשוטר ראה. לצורך כך מבצעים חקירת פונקציה – כלומר, גוזרים את הפונקציה שוב ומשווים לאפס. $\alpha^{\prime}\left(t\right)$ היא שבר וזה סיפור להתעסק עם המכנה, אבל לא צריך; המכנה ממילא לא יכול להתאפס ולכן מספיק לחשב את המונה של הנגזרת השניה, והוא יוצא:

$\frac{a_{0}}{r_{0}}\left(1+\frac{1}{4}\left(\frac{a_{0}}{r_{0}}\right)^{2}t^{4}\right)-\left(\frac{a_{0}}{r_{0}}t\right)\left(\frac{a_{0}}{r_{0}}\right)^{2}t^{3}=\frac{a_{0}}{r_{0}}+\left(\frac{a_{0}}{r_{0}}\right)^{3}\left(\frac{1}{4}-1\right)t^{4}$

על ידי השוואה לאפס והעברת אגפים נקבל:

$\frac{3}{4}\left(\frac{a_{0}}{r_{0}}\right)^{2}t^{4}=1$

ועל ידי חלוקה והוצאת שורש נקבל:

$t=\sqrt[4]{\frac{4}{3}}\sqrt{\frac{r_{0}}{a_{0}}}$

אבל רגע, מה הולך פה? הרי רואים בגרף שלפונקציה של התאוצה יש שלוש נקודות קיצון, לא אחת. איך ייתכן שהחקירה שלנו הניבה אחת בלבד? נסו לחשוב על זה שניה, ובינתיים נדבר על מה שקריוקוב עשה עם הנוסחה הזו. קריוקוב החליט שהוא עצלן ורוצה לעשות לעצמו חיים קלים – הוא הניח ש- $r_{0}=a_{0}=10$ . אני לא יודע מהיכן הוא המציא את הנתון ש- $r_{0}=10$ ; אולי אלו היו העובדות במקרה הזה. את $a_{0}=10$ הוא מנמק בכך שהוא היה מצונן באותו יום והתעטש בדיוק בזמן הבלימה לקראת השלט. אם אני הייתי השופט, בשלב הזה בקריאה (אם הייתי שורד עד אז) הייתי חושד שעושים ממני צחוק. מכל מקום, קריוקוב מקבל שהמקסימום הוא ב- $\sqrt[4]{\frac{4}{3}}\approx1.07$ .

ולמה התקבלה רק נקודת קיצון אחת? כי הפונקציה שאותה חקרנו היא אכן בעלת נקודת קיצון אחת בלבד: כזכור, התעסקנו רק עם מה שקורה עבור $t\ge0$ . כדי לקבל את מה שקורה גם לפני כן צריך "להדביק" לפונקציה הזו את תמונת הראי שלה, $-\frac{\left(a_{0}/r_{0}\right)t}{1+\frac{1}{4}\left(\frac{a_{0}}{r_{0}}\right)^{2}t^{4}}$ (שנקודת הקיצון שלה היא בערך ב- $-1.07$ ) ונקודת הקיצון השלישית מתקבלת בנקודת ההדבקה שלהן (אבל ממילא זו לא הנקודה שמעניינת אותנו).

החישוב האחרון שעוד נותר הוא של "מתי החלה ההסתרה ומתי היא נגמרה". כאן קריוקוב מציין שאורך המכונית שלו הוא 150 אינצ'ים והוא מעריך את אורך המכונית שהסתירה אותו ב-189 אינצ'ים. עכשיו הוא מגדיר $x_{p}$ בתור המרחק מ- $x=0$ שבו נגמרה ההסתרה החלקית, וב- $x_{f}$ את המרחק שבו נגמרה ההסתרה המלאה. אם מניחים שהרכב השני פשוט עמד ב- $x=0$ ולא זז, אז $x_{p}$ הוא סכום האורכים שלהם ו- $x_{f}$ הוא הפרש האורכים שלהם, כלומר $8.16$ מטרים ו- $0.99$ מטרים, בהתאמה. קריוקוב קצת מחליק פה משהו לדעתי – הוא מניח סימטריה מלאה סביב הצירים, כלומר שההסתרה החלקית החלה ב- $-x_{p}$ וההסתרה המלאה החלה ב- $x_{f}$ , אבל כמובן שזה מניח שכשההסתרה החלקית החלה אז ראש הרכב המסתיר היה ב- $x=0$ , וכשהיא נגמרה אז הזנב שלו היה שם; כלומר, הנחה מאוד ספציפית לגבי תנועת הרכב השני. אני תוהה אם השופט שם לב לזה (או שאני סתם מתבלבל). מילא, יש המון פרמטרים שאפשר לשחק איתם כאן.

קריוקוב מחשב ומוצא ש- $t_{p}=1.31$ ו- $t_{f}=0.45$ (שוב, אלו הזמנים שבהם ההסתרות נגמרו, והמינוס שלהם הם הזמנים שבהם ההסתרות החלו). מכאן אנו רואים שהזמן שבו קריוקוב היה בתאוצת שיא הוא זמן שבו קריוקוב כבר היה מוסתר חלקית על ידי הרכב, ושפרק הזמן הקריטי ביותר היה כמובן פרק זמן שבו הוא היה מוסתר לחלוטין. סוף הסיפור.

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

תגים: מתמטיקה פופולרית מוצלחת, חשבון אינפיניטסימלי
שייך לקטגוריות מתמטיקה בראי התקשורת, אנליזה מתמטית | 6 תגובות »

משפט השלמות לתחשיב הפסוקים

8 באפריל, 2012

בפוסט הקודם הצגתי מערכת הוכחה (חלקית, עוד לא גמרנו) לתחשיב הפסוקים והוכחתי שהיא מקיימת את משפט הדדוקציה: אם $\Phi\cup\left\{ \alpha\right\} \vdash\beta$ אז $\Phi\vdash\alpha\to\beta$ . הפעם אני רוצה להמשיך לבנות את מערכת ההוכחה הזו ולהראות שהיא מקיימת את התכונה שלשמה היא קיימת: להוכיח כל מה ש"נכון", דהיינו אם $\Phi\models\varphi$ אז $\Phi\vdash\varphi$ (זכרו: $\Phi$ היא קבוצת פסוקים כלשהי של "הנחות"; מערכת ההוכחה שלנו מסתתרת כולה בתוך הסימן $\vdash$ ). ההוכחה עצמה היא מרהיבה וכוללת לפחות שני רעיונות שלטעמי הם מקסימים; אולי הדבר הכי נחמד בה הוא שעיקר העבודה היא בכלל הוכחה של טענה אחרת שנראית לא קשורה ממבט חטוף ראשון אבל היא בעצם לב העניין. כדי להציג אותה, אזדקק להגדרה אחת אחרונה – עקביות.

אנחנו אומרים שקבוצת פסוקים $\Phi$ היא עקבית אם אי אפשר להוכיח ממנה דבר ושלילתו, כלומר לא קיים $\varphi$ כך שגם $\Phi\vdash\varphi$ וגם $\Phi\vdash\neg\varphi$ . אם $\Phi$ עושה דבר כזה, אז ממשפט הנאותות של מערכת ההוכחה שלנו נובע ש- $\Phi\models\varphi$ וגם $\Phi\models\neg\varphi$ , כלומר כל השמה שמספקת את $\Phi$ בו זמנית מספקת גם את $\varphi$ וגם את $\neg\varphi$ וזה בלתי אפשרי עם ההגדרות שלנו ל"מספקת"; המסקנה היא שאם $\Phi$ היא לא עקבית, אין השמה שמספקת אותה. אם אין השמה שמספקת אותה, אז לכל $\psi$ שלא יהיה מתקיים $\Phi\models\psi$ ("באופן ריק") ולכן, אם מערכת ההוכחה שלנו מקיימת את משפט השלמות, אז $\Phi\vdash\psi$ לכל $\psi$ . במילים אחרות: במערכת הוכחה "נורמלית" (שמקיימת שלמות ונאותות), קבוצה לא עקבית של פסוקים מוכיחה הכל. באנגלית קוראים לזה Principle of Explosion ובעברית אין לי מושג אם יש לזה שם.

(http://xkcd.com/704/)

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

כדי להבין איך הקסם הזה קורה, אני נזקק לעוד תכונה אחת של מערכת ההוכחה שלי: הוכחה בשלילה. אני רוצה לטעון שאם $\Phi\cup\left\{ \neg\varphi\right\}$ אינה עקבית, אז $\Phi\vdash\varphi$ (זוהי בדיוק הוכחה בשלילה כפי שאנחנו מכירים אותה ממתמטיקה יומיומית; יש לנו הנחות $\Phi$ ; אנחנו מניחים ש- $\varphi$ אינו נכון, מוכיחים מכך סתירה, ומסיקים ש- $\varphi$ כן נכון, בהינתן ההנחות $\Phi$ ). לרוע המזל, מערכת ההוכחה שלי עד כה אינה מסוגלת לבצע את הקסם הזה, ולכן אני נזקק לתבנית אקסיומה אחת אחרונה.

ראשית, בואו ננסה להבין מה יש לנו. אם $\Phi\cup\left\{ \neg\varphi\right\}$ אינה עקבית, אז בואו נניח שמערכת ההוכחה שלנו כבר חזקה מספיק כדי שלכל $\psi$ יתקיים $\Phi\cup\left\{ \neg\varphi\right\} \vdash\psi$ , ואז נוכל להסיק ממשפט הדדוקציה $\Phi\vdash\neg\varphi\to\psi$ . עכשיו, כלל ידוע במתמטיקה הוא שלהגיד "אם אלף אז בית" שקול ללהגיד "אם לא בית אז לא אלף". זה בדיוק מה שעשיתי לכם לפני שניה – אמרתי "אם תורה היא לא עקבית אין לה מודל" שהיה שקול ל"אם לתורה יש מודל היא עקבית". מערכת ההוכחה שלנו עדיין לא יודעת לבטא את העקרון הזה בצורה תחבירית (אין לה את היכולת ליצור מחרוזת שזה מה שהיא אומרת), אז נוסיף לה תבנית אקסיומה שאומרת בדיוק את זה: $\left(\neg\alpha\to\neg\beta\right)\to\left(\beta\to\alpha\right)$ . זוהי תבנית אקסיומה מס' 3. אתם מוזמנים לבדוק שזוהי אכן טאוטולוגיה.

עכשיו הוכחה של "משפט ההוכחה בשלילה" היא קלה. בואו נבחר בתור $\psi$ טאוטולוגיה כלשהי ש- $\Phi$ יודעת להוכיח ( $\varphi\to\left(\varphi\to\varphi\right)$ לאלו מכם שרוצים להיות קונקרטיים, אבל זה חסר חשיבות). אז הוכחה של $\varphi$ תיראה כך:

$\neg\varphi\to\neg\psi$ (ממשפט הדדוקציה).
$\left(\neg\varphi\to\neg\psi\right)\to\left(\psi\to\varphi\right)$ (תבנית אקסיומה 3).
$\psi\to\varphi$ ( $\mbox{MP}$ על 1,2).
$\psi$ (טאוטולוגיה שיכיחה מ- $\Phi$ ).
$\varphi$ ( $\mbox{MP}$ על 3,4).

סיימנו עם משפט ההוכחה בשלילה, אבל רק בהנחה שעקרון הפיצוץ אכן מתרחש במערכת ההוכחה שלנו. בפועל זה קורה בדיוק "בזכות" תבנית אקסיומה 3: נניח ש- $\Phi$ אינה עקבית, כלומר $\Phi\vdash\varphi$ וגם $\Phi\vdash\neg\varphi$ עבור $\varphi$ כלשהו. בואו נראה הוכחה של $\psi$ כלשהו:

$\left(\neg\psi\to\neg\varphi\right)\to\left(\varphi\to\psi\right)$ (תבנית אקסיומה 3).
$latex\neg\varphi\to\left(\neg\psi\to\neg\varphi\right)$ (תבנית אקסיומה 1).
$\neg\varphi$ (ניתן להוכחה מ- $\Phi$ ).
$\neg\psi\to\neg\varphi$ ( $\mbox{MP}$ על 2,3).
$\varphi\to\psi$ ( $\mbox{MP}$ על 1,4).
$\varphi$ (ניתן להוכחה מ- $\Phi$ ).
$\psi$ ( $\mbox{MP}$ על 5,6).

בואו נבין עכשיו למה הטענה "אם $\Phi$ עקבית אז יש לה מודל" גוררת את משפט השלמות. יהא $\varphi$ כך ש- $\Phi\models\varphi$ . אם $\Phi\cup\left\{ \neg\varphi\right\}$ אינה עקבית, אז סיימנו; ממשפט ההוכחה בשלילה, $\Phi\vdash\varphi$ . אחרת, אם $\Phi\cup\left\{ \neg\varphi\right\}$ כן עקבית, אז מההנחה שלנו קיים לה מודל. המודל הזה הוא השמה שמספקת בו זמנית את כל פסוקי $\Phi$ ואת $\neg\varphi$ ; אבל מכיוון ש- $\Phi\models\varphi$ כל השמה שמספקת את כל פסוקי $\Phi$ מספקת גם את $\varphi$ – סתירה לכך שההשמה מספקת את $\neg\varphi$ . זה הכל.

שימו לב שההוכחה הזו איננה קונסטרוקטיבית; היא לא מצביעה על האופן שבו אפשר, בהינתן $\varphi$ שמקיים $\Phi\models\varphi$ , לבנות הוכחה עבורו. האם אתם מזהים היכן בהוכחה השלב הלא קונסטרוקטיבי? ההוכחה בסך הכל אומרת "לא ייתכן ש- $\Phi\cup\left\{ \neg\varphi\right\}$ עקבית", ומכאן אנחנו מסיקים ש- $\Phi\vdash\varphi$ ממשפט ההוכחה בשלילה; אבל משפט ההוכחה בשלילה עצמו מניח שבגלל ש- $\Phi\cup\left\{ \neg\varphi\right\}$ לא עקבית, אז קיימת הוכחה במערכת הזו לזוג כלשהו של $\psi$ ו- $\neg\psi$ . אחרי שיש לנו ביד את ההוכחה הזו, כל מה שנשאר הוא כמה צעדים פשוטים ומוגדרים היטב. אבל איך ההוכחה של הזוג הזה נראית, אין לנו מושג.

אפשר לחשוב על מה שעשינו גם כך: לפני רגע רצינו להוכיח טענה על התחביר באמצעות הנחה על הסמנטיקה (הנחנו ש- $\Phi\models\varphi$ ורצינו להסיק $\Phi\vdash\varphi$ ), ועכשיו הפכנו את היוצרות: אנחנו מניחים משהו על התחביר – ש- $\Phi$ עקבית – ורוצים להסיק מזה משהו על הסמנטיקה – שיש ל- $\Phi$ מודל. כל שארית ההוכחה שלנו תעסוק בנסיון לבנות ל- $\Phi$ את המודל הזה. הבניה הזו נתקלת בקושי לא צפוי, עם פתרון לא צפוי, שלטעמי הוא החלק המקסים ביותר כאן: מסתבר שקשה למצוא מודל ל- $\Phi$ דווקא בגלל שיש לנו יותר מדי חופש בחירה – יש יותר מדי השמות שיש להן "פוטנציאל להיות מודל ל- $\Phi$ ". הפתרון יהיה להרחיב את $\Phi$ לתורה עקבית גדולה בהרבה, שהרבה יותר קשה לספק אותה – יהיה לה רק מודל אחד ויחיד. דווקא בגלל אובדן החופש הזה, הרבה יותר קל למצוא את המודל הזה; אין לנו שום בחירה בבניה שלו ולכן הוא ממש "בונה את עצמו".

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

כאמור, המטרה שלי היא למצוא מודל ל- $\Phi$ , אבל זה לא קל. מודל ל- $\Phi$ הוא סדרה של ערכי $\mbox{T/F}$ שאני מציב למשתנים $X_{1},X_{2},X_{3},\dots$ . אני יכול להתחיל בלהגיד "טוב, אם הצבת $\mbox{T}$ ב- $X_{1}$ לא הופכת אף פסוק ב- $\Phi$ לבלתי ניתן לסיפוק, נציב בו $\mbox{T}$ ; אחרת, נציב בו $\mbox{F}$ , ואם גם זה לא יספק אני איכשהו אראה ש- $\Phi$ לא עקבית". נניח לרגע שאני יכול לעשות את ה"איכשהו" הזה, האם זה פתר את בעיותי? לא, כי הצבתי ערך רק למשתנה $X_{1}$ . עכשיו צריך להציב גם ל- $X_{2}$ , בהינתן ההצבה שבחרתי עבור $X_{1}$ . ואז צריך עבור $X_{3}$ בהינתן ההצבה שבחרתי עבור $X_{1},X_{2}$ . ואז ב- $X_{12414}$ אני אתקע פתאום כי אראה שאין לי דרך לספק את $\Phi$ לא כשמציבים $\mbox{T}$ ולא כשמציבים $\mbox{F}$ ב- $X_{12414}$ , אבל, אם רק הייתי בוחר להציב את הערך ההפוך ב- $X_{1}$ , אז כתוצאה מכך הייתה מתקבלת סדרת הצבות שונה לגמרי בכל שאר המשתנים, ואז לא הייתי נתקע ב- $X_{12414}$ . אבל איך אני
יכול לוודא את זה? ואיך אני יכול מראש לבחור בהצבה ה"נכונה" עבור כל משתנה? לא ברור. זו הסיבה שהגישה הנאיבית הזו נתקעת.

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

כדי להסביר מה $\Psi$ יהיה בדיוק אין מנוס מלהכניס למשחק מושג מבלבל: תורה שלמה. $\Psi$ הוא תורה שלמה אם לכל פסוק $\varphi$ מתקיים $\Psi\vdash\varphi$ או $\Psi\vdash\neg\varphi$ . כלומר, $\Psi$ מוכיחה או מפריכה כל פסוק. המילה שלמות כאן והמילה שלמות ב"משפט השלמות לתחשיב הפסוקים" מדברות על דברים שונים לגמרי; השלמות של $\Psi$ היא שלמות של תורה – קבוצת פסוקים, שממנה "נובע כל דבר או שלילתו"; השלמות של משפט השלמות היא שלמות של מערכת ההוכחה – היא אומרת שבהינתן קבוצת פסוקים שממנה נובע לוגית משהו, אז מערכת ההוכחה מאפשרת לנו להוכיח את אותו המשהו מתוך קבוצת הפסוקים. גם אחרי שאוכיח את משפט השלמות, לא תנבע מכך שום תוצאה כמו "כל קבוצת פסוקים $\Phi$ היא שלמה". בקיצור, זוהי בחירה אומללה של שימוש באותה מילה כדי לתאר שני מושגים שונים (אם כי לא בלתי קשורים לזה לזה, כפי שאפשר להבין מכך שאני מדבר על תורה שלמה כחלק מההוכחה של משפט השלמות). הבלבול זלג גם לתחשיב היחסים: ב"משפט השלמות
של גדל" השלמות היא של מערכת ההוכחה (זהו אנלוג מורכב יותר למשפט השלמות שאנחנו מוכיחים כרגע) וב"משפטי אי השלמות של גדל" השלמות היא של תורות מסויימות (אריתמטיות, עקביות ואפקטיביות, אם זה אומר לכם משהו).

הטענה שלי היא שלתורה שלמה ועקבית יש בדיוק מודל יחיד – כלומר, לכל משתנה יש בדיוק ערך אחד שאפשר להציב בו כדי שעדיין נספק את $\Psi$ – אבל קודם כל בואו נבין כיצד ניתן להרחיב את $\Phi$ לתורה שלמה $\Psi$ . התשובה פשוטה: בכוח! נמספר את כל הפסוקים בעולם במספור כלשהו $\varphi_{1},\varphi_{2},\varphi_{3},\dots$ כך שכל פסוק מופיע מתישהו במספור; ועכשיו נבנה סדרה של תורות $\Phi_{0},\Phi_{1},\Phi_{2},\dots$ כך ש- $\Phi_{0}=\Phi$ ולכל $n>0$ , אחד משניים: אם $\Phi_{n-1}\cup\left\{ \neg\varphi_{n}\right\}$ עקבית, אז $\Phi_{n}=\Phi_{n-1}\cup\left\{ \neg\varphi_{n}\right\}$ ; אחרת, $\Phi_{n}=\Phi_{n-1}$ . במילים אחרות, אנחנו עוברים פסוק פסוק ולכל פסוק כזה אנחנו בודקים אם ניתן להוסיף את שלילתו לתורה שלנו. אם אפשר (כלומר, העקביות נשמרת) אנחנו מוסיפים. אחרת לא. בצורה הזו די ברור שכל אחת מה- $\Phi_{n}$ היא עדיין תורה עקבית בפני עצמה. עכשיו בואו ונגדיר $\Psi=\bigcup\Phi_{n}$ , כלומר $\Psi$ כוללת את כל הפסוקים שמופיעים ולו באחד מה-$latex \
Phi_{n}$-ים, ובגלל שבנינו אותם בצורה כזו ש- $\Phi_{0}\subseteq\Phi_{1}\subseteq\Phi_{2}$ , בעצם אפשר לומר שאם פסוק כלשהו נמצא ב- $\Psi$ אז הוא נמצא בכל ה- $\Phi_{n}$ -ים החל ממקום מסויים.

אנחנו צריכים להשתכנע ש- $\Psi$ עקבית וש- $\Psi$ שלמה. הוכחת העקביות מנצלת את העובדה שהוכחה היא תמיד סופית. נניח לרגע ש- $\Psi$ לא עקבית, כלומר $\Psi\vdash\varphi$ וגם $\Psi\vdash\neg\varphi$ עבור איזה שהוא פסוק $\varphi$ . אז יש לנו שתי הוכחות ששתיהן סופיות; מכיוון שהן סופיות, משתמשים בהן במספר סופי של הנחות מ- $\Psi$ ; בשל בניית $\Psi$ נובע מכך שכל ההנחות הללו נמצאות בכל ה- $\Phi_{n}$ -ים החל מ- $n$ מסויים, ולכן החל מ- $n$ מסויים גם $\Phi_{n}\vdash\varphi$ ו- $\Phi_{n}\vdash\neg\varphi$ בסתירה לכך שכל ה- $\Phi_{n}$ עקביות.

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

סיימנו את השלב הזה: הראינו שכל תורה עקבית $\Phi$ ניתנת להרחבה לתורה עקבית ושלמה $\Psi$ . נותר להוכיח רק שלתורה עקבית ושלמה יש מודל. בניגוד למקרה של $\Phi$ כללית, עבור $\Psi$ השלמה אין בעיה להגיד במפורש מה המודל הזה, פשוט כי אין לנו ממש ברירה: לכל משתנה $X_{i}$ , מתקיים בדיוק אחד משניים: $\Psi\vdash X_{i}$ או $\Psi\vdash\neg X_{i}$ , וזאת כי $\Psi$ שלמה. אז אם $\Psi\vdash X_{i}$ נגדיר ש- $X_{i}$ מקבל $\mbox{T}$ בהשמה שלנו, ואם $\Psi\vdash\neg X_{i}$ נגדיר ש- $X_{i}$ מקבל $\mbox{F}$ . עד כדי כך פשוט. רק צריך להשתכנע שההשמה הזו באמת מספקת כל פסוק ב- $\Psi$ . ליתר דיוק, נוכיח את הטענה החזקה יותר "לכל פסוק $\varphi$ , $\Psi\vdash\varphi$ אם ורק אם ההשמה מספקת את $\varphi$ " (חזקה יותר, כי אם $\varphi\in\Psi$ אז בפרט $\Psi\vdash\varphi$ ).

את ההוכחה הזו אפשר לעשות באינדוקציה על המבנה של פסוקים $\mbox{WFF}$ . כזכור, פסוק כזה הוא או $\varphi=X_{i}$ עבור משתנה כלשהו, או שהוא מהצורה $\varphi=\neg\alpha$ , או שהוא מהצורה $\varphi=\alpha\to\beta$ .

במקרה הראשון, אם $\Psi\vdash X_{i}$ אז על פי ההגדרה של ההשמה, $X_{i}$ מקבל $\mbox{T}$ ; ואם $X_{i}$ קיבל $\mbox{T}$ אז בהכרח $\Psi\vdash X_{i}$ (כי אחרת היה מתקיים $\Psi\vdash\neg X_{i}$ ואז $X_{i}$ היה מקבל $\mbox{F}$ בהשמה).

בשני המקרים הבאים נוכל להניח ש- $\alpha,\beta$ כבר מקיימים את התכונה שהם יכיחים מ- $\Psi$ אם ורק אם ההשמה מספקת אותם; זוהי בדיוק הנחת האינדוקציה.

במקרה השני, $\Psi\vdash\neg\alpha$ אם ורק אם $\Psi\not\vdash\alpha$ (כי $\Psi$ עקבית ושלמה), כלומר אם ורק אם ההשמה נותנת ל- $\alpha$ ערך $\mbox{F}$ , כלומר אם ורק אם ההשמה נותנת ל- $\neg\alpha$ ערך $\mbox{T}$ . זה היה קל; המקרה השלישי טיפה יותר קשה.

במקרה השלישי, נניח קודם כל כי $\Psi\vdash\alpha\to\beta$ . אם $\alpha$ מקבלת ערך $\mbox{F}$ בהשמה, סיימנו כי $\alpha\to\beta$ תמיד יקבל ערך $\mbox{T}$ ; אז נניח ש- $\alpha$ מקבלת $\mbox{T}$ ולכן, מהנחת האינדוקציה, $\Psi\vdash\alpha$ , ומכאן ש- $\Psi\vdash\beta$ (כי ההוכחה פשוט מייצרת את $\alpha$ ואת $\alpha\to\beta$ ואז מבצעת $\mbox{MP}$ ) ומהנחת האינדוקציה, $\beta$ מסתפקת על ידי ההשמה. זה מסיים כיוון אחד של ההוכחה; בכיוון השני, נניח כי $\alpha\to\beta$ הסתפקה בהשמה ונוכיח כי $\Psi\vdash\alpha\to\beta$ . יש שתי דרכים שבהן $\alpha\to\beta$ יכלה להסתפק; או ש- $\beta$ קיבלה $\mbox{T}$ , או ש- $\alpha$ קיבלה $\mbox{F}$ . אם $\beta$ קיבלה $\mbox{T}$ אז מהנחת האינדוקציה, $\Psi\vdash\beta$ ולכן בוודאי ש- $\Psi\cup\left\{ \alpha\right\} \vdash\beta$ וממשפט הדדוקציה, $\Psi\vdash\alpha\to\beta$ . במקרה השני, אם $\alpha$ קיבלה $\mbox{F}$ , אז $\Psi\vdash\neg\alpha$
ולכן $\Psi\cup\left\{ \alpha\right\}$ לא עקבית. אם היא לא עקבית, אז היא מוכיחה הכל, כולל $\beta$ ; שוב קיבלנו ש- $\Psi\cup\left\{ \alpha\right\} \vdash\beta$ וממשפט הדדוקציה, $\Psi\vdash\alpha\to\beta$ . זה מסיים את הוכחת משפט השלמות.

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

תגים: תחשיב הפסוקים
שייך לקטגוריות לוגיקה | 5 תגובות »

תחשיב הפסוקים – על נביעה לוגית והוכחות

4 באפריל, 2012

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

האובייקט הבסיסי בתחשיב הפסוקים היה משתנים לוגיים, $X_{1},X_{2},X_{3},\dots$ . ההנחה היא שאנחנו מייחסים למשתנים הללו משמעות כלשהי, אבל מבחינה פורמלית תחשיב הפסוקים לא מתעניין במשמעות הזו. כל מה שהוא מתעניין בו הוא האם המשתנים מקבלים ערך $\mbox{T}$ או $\mbox{F}$ . בואו נתחיל עם דוגמה קונקרטית כדי להבין איך זה הולך. את המושג של גרף אני מניח שרוב הקוראים מכירים, אבל למי שלא: גרף $G=\left(V,E\right)$ מורכב מקבוצה כלשהי (לא בהכרח סופית) של צמתים $V$ , ושל זוגות של צמתים $E\subseteq V^{2}$ שנקראים קשתות. חושבים על כך כאילו אם $\left(u,v\right)\in E$ אז הצמתים $u,v$ מחוברים בקשת, ואחרת לא. עכשיו, את הצמתים של $G$ אפשר לצבוע; אני אניח לצורך פשטות שמותר לצבוע אותם רק באדום, כחול או ירוק. פורמלית, צביעה היא פונקציה $f:V\to\left\{ \mbox{R,G,B}\right\}$ שלכל צומת מתאימה את הצבע שבו הוא נצבע (כל צומת חייב להיצבע). האתגר בדרך כלל הוא למצוא צביעה "חוקית" שבה אין שני צמתים שמחוברים
בקשת וצבועים באותו הצבע – כלומר, $f\left(u\right)\ne f\left(v\right)$ לכל קשת $\left(u,v\right)\in E$ בגרף. לא תמיד יש צביעה כזו; למעשה, הבעיה "האם ניתן לצבוע גרף $G$ נתון באופן חוקי באמצעות שלושה צמתים" היא בעיה $\mbox{NP}$ -שלמה, מה שאומר שהיא ככל הנראה קשה לפתרון מבחינה חישובית. למה זה בכלל מעניין מישהו? ובכן, בעולם הגדול צביעה של גרפים היא הפשטה נאה לבעיות של הקצאת משאבים; בעולם הקטן שלנו היא פשוט דוגמה יפה למה שאני רוצה לדבר עליו.

נניח שנתון לי גרף $G$ . כעת, לכל צומת $v$ אני הולך להגדיר שלושה משתנים: $X_{R}^{v},X_{G}^{v},X_{B}^{v}$ . אם $X_{R}^{v}=\mbox{T}$ , אני מפרש את זה בתור האמירה "הצומת $v$ נצבע בצבע $\mbox{R}$ ". מבחינת תחשיב הפסוקים עצמו, כל מה שהוא יודע זה ש"המשתנה $X_{R}^{v}$ קיבל את הערך $\mbox{T}$ בהשמה" – כל היתר הוא בדמיון שלי (גם לקרוא למשתנה הזה $X_{R}^{v}$ זה בדמיון שלי; בפועל כל המשתנים הם מהצורה $X_{k}$ כאשר $k$ הוא מספר טבעי כלשהו).

כעת, כל השמה למשתנים מגדירה צביעה של הגרף $G$ , אבל אף אחד לא מבטיח לי שהצביעה הזו הגיונית בכלל; ייתכן שיש צומת שנצבע ביותר מאשר צבע אחד; ייתכן שיש צומת שלא נצבע באף צבע; וכמובן, אף אחד לא מבטיח שהצביעה תהיה חוקית במובן זה שכל שני צמתים שכנים לא צבועים באותו הצבע. בכדי להבטיח שהצביעה תהיה בסדר אני צריך להוסיף מגבלות על הצביעה – כלומר, על ההשמות החוקיות. האופן שבו אני עושה את זה הוא להגדיר קבוצה של פסוקים, $,\Phi_{G}$ כך שכל השמה שמספקת את כל הפסוקים של $\Phi_{G}$ חייבת להיות, בפרשנות שלי, צביעה חוקית. אילו פסוקים $\Phi_{G}$ תכיל?

ובכן, לכל צומת $v\in V$ , $\Phi_{G}$ תכיל את הפסוק $X_{R}^{v}\vee X_{G}^{v}\vee X_{B}^{v}$ שאומר "הצומת $v$ צבוע לפחות בצבע אחד". היא תכיל את הפסוק $\neg\left(X_{R}^{v}\wedge X_{G}^{v}\right)\wedge\neg\left(X_{R}^{v}\wedge X_{B}^{v}\right)\wedge\neg\left(X_{G}^{v}\wedge X_{B}^{v}\right)$ שאומר "הצומת $v$ אינה צבועה ביותר מצבע אחד"; ולכל קשת $\left(u,v\right)\in E$ , $\Phi_{G}$ תכיל את הפסוק $\neg\left(X_{R}^{v}\wedge X_{R}^{u}\right)\wedge\neg\left(X_{G}^{v}\wedge X_{G}^{u}\right)\wedge\neg\left(X_{B}^{v}\wedge X_{B}^{u}\right)$ שאומר "הצמתים $v,u$ אינם צבועים באותו הצבע".

זה משלים את התיאור של $\Phi_{G}$ , אבל הכיף רק מתחיל. לא קשה להוכיח (באופן מתמטי "רגיל", לא באופן פורמלי) שאם הגרף $G$ מכיל ולו קשת יחידה, אז לא כל הצמתים בגרף בעלי אותו צבע (כי מה עם שני הצמתים שמחוברים בקשת?). בואו נניח לצורך פשטות ש- $G$ סופי וקבוצת הקשתות שלו לא ריקה, אז הפסוק הבא נכון עבור כל השמה שמספקת את כל פסוקי $\Phi_{G}$ : $\neg\left(\bigwedge_{v\in V}X_{R}^{v}\right)\wedge\neg\left(\bigwedge_{v\in V}X_{G}^{v}\right)\wedge\neg\left(\bigwedge_{v\in V}X_{B}^{v}\right)$ . הפסוק הזה כמובן דומה לפסוקים שהוספנו ל- $\Phi_{G}$ , אבל הוא לא נמצא ב- $\Phi_{G}$ . מצד שני, די בבירור הוא "נובע" מתוך $\Phi_{G}$ – גם מבחינה אינטואיטיבית, אבל גם מבחינה פורמלית; באופן כללי אנחנו אומרים שפסוק $\varphi$ נובע לוגית מקבוצת פסוקים $\Phi$ אם כל השמה שמספקת את $\Phi$ (דהיינו, מספקת את כל הפסוקים ב- $\Phi$ ) מספקת גם את $\varphi$ . מסמנים זאת $\Phi\models\varphi$ . בפרט, פסוקים שכל השמה מספקת אותם נקראים
טאוטולוגיות ומסמנים זאת $\models\varphi$ (אבל כמובן שאם $\varphi$ טאוטולוגיה אז אפשר לכתוב גם $\Phi\models\varphi$ לכל $\Phi$ שרק נרצה).

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

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

נאותות ושלמות קל לתאר: נאותות אומרת "כל מה שניתן להוכחה, נכון", שבהקשר שלנו פירושו "כל מה שניתן להוכחה מתוך $\Phi$ במערכת ההוכחה שלנו נובע לוגית מ- $\Phi$ ". אני אשתמש בסימון $\Phi\vdash\varphi$ כדי לומר " $\Phi$ מוכיח (במערכת הוכחה ספציפית) את $\varphi$ ", ולכן אפשר לנסח את דרישת הנאותות פשוט בתור $\Phi\vdash\varphi\Rightarrow\Phi\models\varphi$ . דרישת השלמות היא הכיוון השני, $\Phi\vdash\varphi\Leftarrow\Phi\models\varphi$ : כאן אני דורש שכל מה שנובע לוגית מ- $\Phi$ יהיה ניתן להוכחה. כבר אינטואיטיבית אפשר להרגיש שזו הדרישה הקשה יותר, אבל נדון על כך בהמשך.

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

שלוש הדרישות שלעיל לא באמת מגדירות בשום צורה איך מערכת ההוכחה תעשה את מה שאנחנו דורשים ממנה, ובצדק; למה להגביל את עצמנו? תחת זאת, אפשר פשוט לדבר על מערכות הוכחה קונקרטיות ולראות שהן מקיימות את הדרישות הבסיסיות שלנו. מה שאציג כעת תהיה מקרה פרטי של מחלקה גדולה של מערכות הוכחה "מערכות הילברט" (שהקרדיט על תיאורן הפורמלי, פחות או יותר, מגיע להילברט ולפרגה). במערכת כזו יש לנו אקסיומות, ויש לנו כללי היסק, והוכחה של $\varphi$ מתוך קבוצת הנחות $\Phi$ היא סדרה סופית של פסוקים $\psi_{1},\dots,\psi_{n}$ כך ש- $\psi_{n}=\varphi$ , וכל $\psi_{i}$ הוא או אקסיומה, או הנחה מתוך $\Phi$ , או שהוא נובע מ- $\psi_{j}$ -ים קודמים על ידי הפעלת כלל היסק. כדי שהמערכת תהיה אפקטיבית רק צריך לבחור אקסיומות שניתן לזהות אותן באופן אלגוריתמי (כלומר, או שתהיה קבוצה סופית של אקסיומות, או – אם זו קבוצה אינסופית – שלפחות יהיה קל לזהות מהי אקסיומה, למשל כי היא מתאימה לאיזו שהיא תבנית ברורה) ולבחור כללי היסק שניתן לזהות את
הפעלתם באופן אלגוריתמי.

מראש ברור שאנחנו מוגבלים בבחירת האקסיומות שלנו – אנחנו יכולים לבחור רק טאוטולוגיות בתור אקסיומות, אחרת אפשר לשכוח מהנאותות (כי לכל $\varphi$ שהוא אקסיומה, מתקיים $\vdash\varphi$ , כלומר יש הוכחה ל- $\varphi$ ללא שום הנחות; ההוכחה הזו היא פשוט הסדרה $\varphi$ עצמה. מנאותות כעת נובע ש- $\models\varphi$ ). עכשיו אפשר אולי להבין במשהו את הקושי שלנו בהוכחת שלמות – יש לנו רק סט מוגבל למדי של מחרוזות – אלו שמייצגות טאוטולוגיות ואלו של $\Phi$ עצמה – ואנחנו יכולים לבצע רק סדרות סופיות של שינויים פשוטים במחרוזות הללו, ואיכשהו אנחנו צריכים לקבל מזה כל מחרוזת אפשרית שנובעת מ- $\Phi$ ? זה נשמע לא פשוט. כדי להקל עלינו, אפשר לפשט קצת את השפה: מספיק להרשות רק משתנים ואת הקשרים $\neg,\to$ , וה"אתגר" שלנו יהיה לבנות רק פסוקים שכתובים בעזרת קשרים אלו (מכיוון שזוהי מערכת קשרים שלמה אנחנו לא "מאבדים כוח" – עדיין נוכל להביע את כל טבלאות האמת כך). כדאי להדגיש שהפישוט הזה הוא אכן רק פישוט; אפשר לקחת את מערכת ההוכחה שאציג עכשיו ולהרחיב אותה כך שתתמודד גם
עם שאר הקשרים. זה פשוט לא מעניין במיוחד, כי אחרי שנסיים עם מערכת הוכחה עבור $\neg,\to$ בלבד כבר נבין את העיקרון.

נעבור להצגת כלל ההיסק שלנו. יש לנו בחירה לא קטנה בנוגע לכללי ההיסק, אבל אני מעדיף להיות שמרן וללכת על כלל מוכר ופופולרי – מודוס פוננס, MP. הרעיון ב-MP הוא זה: נניח שכבר הוכחנו את $\alpha\to\beta$ וגם הוכחנו את $\alpha$ ; משני אלו אפשר להסיק את $\beta$ . ההגיון פשוט: אם הוכחנו ש"אם יורד גשם, אז אנחנו נרטבים" והוכחנו ש"יורד גשם", אז בעצם הוכחנו ש"אנחנו נרטבים". גם מבחינה פורמלית, קל לראות ש-MP משמר את הנאותות של מערכת ההוכחה שלנו: אם $\Phi\models\alpha$ וגם $\Phi\models\alpha\to\beta$ ויש לנו השמה כלשהי שמספקת את $\Phi$ , אז היא מספקת בו זמנית את $\alpha$ ואת $\alpha\to\beta$ . אם היא לא הייתה מספקת את $\beta$ , אז $\alpha\to\beta$ היה פסוק שבו הרישא ( $\alpha$ ) היא $\mbox{T}$ אבל הסיפא היא $\mbox{F}$ – וזה, על פי הסמנטיקה של תחשיב הפסוקים, אומר שהפסוק כולו מקבל $\mbox{F}$ בהשמה, בסתירה לכך שכל השמה שמספקת את $\Phi$ מספקת את $\alpha\to\beta$ . לכן $\Phi\models\beta$ .

טענה ראשונה שאפשר להוכיח על מערכת ההוכחה שלנו כעת היא זו: אם $\Phi\vdash\alpha\to\beta$ אז $\Phi\cup\left\{ \alpha\right\} \vdash\beta$ ; כלומר, אם אנחנו יודעים להוכיח את $\alpha\to\beta$ מתוך $\Phi$ , אז אם נוסיף ל- $\Phi$ את $\alpha$ בתור הנחה, נוכל להוכיח את $\beta$ . הנה ההוכחה הפורמלית:

$\alpha\to\beta$ (ניתן להוכחה מ- $\Phi$ ).
$\alpha$ (הנחה).
$\beta$ ( $\mbox{MP}$ על 1,2).

לא מסובך, נכון? שימו לב שלא נזקקנו כלל לאקסיומות; התוצאה הזו נובעת ישירות מ- $\mbox{MP}$ . למעשה, כל מערכת הוכחה שמקיימת את התכונה הזו בעצם מכילה את MP, גם אם היא לא הצהירה על כך במפורש בכללי ההיסק שלה; דה פקטו, במערכת כזו אם הצלחנו להוכיח את $\alpha\to\beta$ והצלחנו להוכיח את $\alpha$ אז תנבע מכך הוכחה ל- $\beta$ . אם לעומת זאת מערכת ההוכחה שלנו לא מקיימת את התכונה הזו – כלומר, יש $\alpha,\beta$ כך ש- $\Phi\vdash\alpha\to\beta$ וגם $\Phi\vdash\alpha$ אבל לא $\Phi\vdash\beta$ אז אפשר לשכוח מכך שמערכת ההוכחה תהיה שלמה, שהרי $\Phi\models\beta$ בסיטואציה הזו. המסקנה מהדיון הקצרצר הזה הוא ש- $\mbox{MP}$ הוא כלל גזירה שמתבקש מאוד לצרף אלינו; ולא נזדקק לשום כלל גזירה פרט אליו.

עכשיו, ראינו ש- $\Phi\vdash\alpha\to\beta\Rightarrow\Phi\cup\left\{ \alpha\right\} \vdash\beta$ ; מה בדבר הכיוון השני? האם, אם $\Phi\cup\left\{ \alpha\right\} \vdash\beta$ אז נובע מכך ש- $\Phi\vdash\alpha\to\beta$ ? זה כבר לחלוטין לא מובן מאליו; אני טוען שמכך שאני יודע לייצר את המחרוזת $\beta$ עם הוכחה שמורכבת מאברי $\Phi$ ומ- $\alpha$ אז אני אוכל לייצר את המחרוזת $\alpha\to\beta$ שהיא לכאורה מורכבת יותר, וזאת תוך שימוש בפחות הנחות, שהרי אין לי את $\alpha$ כהנחה יותר. זו לא תוצאה מובנית מאליה, והיא מועילה למדי שכן היא מסייעת מאוד בפישוט הוכחות של טענות; במקום שנצטרך להוכיח משהו כמו $\Phi\vdash\left(\alpha\to\beta\right)\to\left(\alpha\to\gamma\right)$ יהיה לנו מספיק להוכיח ש- $\Phi\cup\left\{ \alpha\to\beta\right\} \vdash\alpha\to\gamma$ , ואפילו די יהיה להוכיח ש- $\Phi\cup\left\{ \alpha\to\beta,\alpha\right\} \vdash\gamma$ – פחות עבודה, יותר הנחות. לתוצאה הזו – $\Phi\vdash\alpha\to\beta\Leftarrow\Phi\cup\left\{ \alpha\right\} \vdash\beta$ – קוראים משפט הדדוקציה, וזה הדבר הלא טריוויאלי הראשון שאני רוצה להוכיח. כרגע מערכת ההוכחה שלי (שהיא נטולת אקסיומות) לא יכולה לבצע את הקסם הזה; במהלך ההוכחה של משפט הדדוקציה נראה לאילו אקסיומות אני נזקק.

בואו נתחיל מהדבר המטופש ביותר. $\Phi\cup\left\{ \alpha\right\} \vdash\alpha$ תמיד, בלי קשר ל- $\Phi$ , ולכן $\Phi\vdash\alpha\to\alpha$ תמיד; מה שאנחנו בעצם רוצים לעשות הוא להראות שאפשר להוכיח את $\alpha\to\alpha$ במערכת ההוכחה שלנו, עבור כל פסוק, ובלי שום הנחות (אלא רק בעזרת אקסיומות שהן חלק ממערכת ההוכחה). הפיתוי הראשון הוא להגיד ש- $\alpha\to\alpha$ עצמה תהיה אקסיומה, לכל פסוק $\alpha$ . מותר לנו לעשות את זה – $\alpha\to\alpha$ היא טאוטולוגיה בלי קשר ל- $\alpha$ – אבל זו אינה אקסיומה שימושית במיוחד ואנו מעדיפים שמערכת ההוכחה שלנו תהיה פשוטה ככל האפשר. בואו נחכה קצת עם ההוכחה של $\alpha\to\alpha$ כדי לראות לאילו אקסיומות נזדקק בהוכחה של יתר המשפט ונראה אם הן יעבדו גם כאן.

אם $\beta$ היא אקסיומה או הנחה ב- $\Phi$ , איך נוכיח ש- $\Phi\vdash\alpha\to\beta$ ? שימו לב שגם כאן לא עוזרת לנו הידיעה ש- $\Phi\cup\left\{ \alpha\right\} \vdash\beta$ מהטעם הפשוט שאם $\beta$ היא אקסיומה או הנחה אז $\Phi\vdash\beta$ ממילא, בלי קשר ל- $\alpha$ . מכאן אנחנו נתקלים בתכונה כללית שמערכת ההוכחה שלנו צריכה לקיים: אם הוכחנו כבר את $\beta$ , אז לכל $\alpha$ אנחנו צריכים להיות מסוגלים להוכיח גם את $\alpha\to\beta$ . אפשר אולי להוסיף את זה גם כן כמעין כלל גזירה, אבל אני מעדיף לחשוב על כללי גזירה כפונקציות שלקוחות פסוקים קיימים ומוציאות פלט יחיד, ואילו כאן כלל הגזירה יהיה משהו רב-ערכי שכזה: "לכל $\alpha$ אפשר להוסיף אותו לפני $\beta$ ". אז בואו במקום להוסיף כלל גזירה חדש, נוסיף אקסיומה חדשה: אני ארצה להיות מסוגל להוכיח את $\alpha\to\beta$ באמצעות $\mbox{MP}$ ובאמצעות זה שאני יודע את $\beta$ . האקסיומה שמתאימה כאן כמו כפפה ליד היא $\beta\to\left(\alpha\to\beta\right)$ (בדיקה ישירה מראה כי זוהי
טאוטולוגיה), אז זו בדיוק האקסיומה שאוסיף למערכת ההוכחה שלי. ליתר דיוק, הוספתי כאן תבנית אקסיומה; לא משנה איזה פסוקים נשתיל במקום $\alpha,\beta$ , התוצאה גם היא תהיה אקסיומה של מערכת ההוכחה שלי. לתבנית האקסיומה הזו אני קורא תבנית אקסיומה מס' 1. בעזרתה אפשר להוכיח בקלות את מה שרצינו:

$\beta$ (אקסיומה/הנחה).
$\beta\to\left(\alpha\to\beta\right)$ (תבנית אקסיומה מס' 1).
$\alpha\to\beta$ ( $\mbox{MP}$ על 1,2)

אוקיי, זה היה קל. אז טיפלנו במקרה שבו $\beta$ היא אקסיומה/הנחה; דחינו לעת עתה את המקרה שבו $\beta=\alpha$ ; מה נותר? המקרים שבהם $\beta$ אינה אקסיומה/הנחה/ $\alpha$ ועם זאת מוכיחים את $\beta$ מתוך $\Phi\cup\left\{ \alpha\right\}$ . מסקנה: בסיטואציה כזו, $\beta$ חייבת להתקבל על ידי הפעלת $\mbox{MP}$ על שני פסוקים שניתן להניח באינדוקציה (על אורך ההוכחה) שעליהם משפט הדדוקציה כבר חל. כלומר, יש איזה שהוא פסוק $\gamma$ כך ש- $\Phi\cup\left\{ \alpha\right\} \vdash\gamma\to\beta$ וגם $\Phi\cup\left\{ \alpha\right\} \vdash\gamma$ , ובגלל שאפשר להניח שמשפט הדדוקציה מתקיים עבורם, אז $\Phi\vdash\alpha\to\gamma$ ו- $\Phi\vdash\alpha\to\left(\gamma\to\beta\right)$ . האם די לנו בשני אלו, בתבנית האקסיומה הנוכחית וב- $\mbox{MP}$ כדי להוכיח את $\alpha\to\beta$ ? ובכן, לא. אז מה עושים? מוסיפים עוד תבנית אקסיומה שתפורה בדיוק לסיטואציה הזו: התבנית $\left[\alpha\to\left(\gamma\to\beta\right)\right]\to\left[\left(\alpha\to\gamma\right)\to\left(\alpha\to\beta\right)\right]$ . תסתכלו על הרכיבים של התבנית ותראו אם אתם מזהים מהיכן היא מגיעה; ובדקו באופן כלשהו שהתבנית הזו היא אכן טאוטולוגיה. לתבנית האקסיומה הזו אני קורא תבנית אקסיומה מס' 2.

עכשיו ההוכחה היא טריוויאלית:

$\alpha\to\gamma$ (ניתן להוכחה מ- $\Phi$ ).
$\alpha\to\left(\gamma\to\beta\right)$ (ניתן להוכחה מ- $\Phi$ ).
$\left[\alpha\to\left(\gamma\to\beta\right)\right]\to\left[\left(\alpha\to\gamma\right)\to\left(\alpha\to\beta\right)\right]$ (תבנית אקסיומה מס' 2).
$\left(\alpha\to\gamma\right)\to\left(\alpha\to\beta\right)$ ( $\mbox{MP}$ על 2,3).
$\alpha\to\beta$ ( $\mbox{MP}$ על 1,4).

נשאר לנו רק לטפל בחוב מההתחלה – להראות שאפשר להוכיח את $\alpha\to\alpha$ . עכשיו יש לנו כלי נשק חדש – שתי תבניות אקסיומה שנמצאות ברשותנו ואנחנו לא מהססים להשתמש בהן. מפתה להשתמש בתבנית הראשונה כשמציבים בה $\alpha$ במקום $\beta$ ומקבלים $\alpha\to\left(\alpha\to\alpha\right)$ , רק שזה לא עוזר לנו במיוחד כי אנחנו לא יכולים להוכיח את $\alpha$ בשום צורה. כנראה שתבנית אקסיומה 1 לבדה לא ממש תעזור לנו וצריך להשתמש גם ב-2. בואו נציב גם ב-2 $\alpha$ במקום
הכל ונראה מה נקבל:

$\alpha\to\left(\alpha\to\alpha\right)$ (תבנית אקסיומה מס' 1).
$\left[\alpha\to\left(\alpha\to\alpha\right)\right]\to\left[\left(\alpha\to\alpha\right)\to\left(\alpha\to\alpha\right)\right]$ (תבנית אקסיומה מס' 2).
$\left(\alpha\to\alpha\right)\to\left(\alpha\to\alpha\right)$ ( $\mbox{MP}$ על 1,2).

ו.. נתקענו. כדי להפיק תועלת מ- $\left(\alpha\to\alpha\right)\to\left(\alpha\to\alpha\right)$ נצטרך להוכיח את $\alpha\to\alpha$ , וזה בדיוק מה שאנחנו מנסים להוכיח! אז מה יצא לנו מכל זה?

אם כן, אולי לא כדאי מייד להציב גם ב- $\beta$ וגם ב- $\gamma$ את $\alpha$ ? אולי יש הצבה קצת יותר מועילה שאפשר לעשות? עם זאת, לא כדאי להציב דברים מופרעים יותר מדי: אם אנחנו מתכננים להשתמש ב- $\left[\alpha\to\left(\gamma\to\beta\right)\right]\to\left[\left(\alpha\to\gamma\right)\to\left(\alpha\to\beta\right)\right]$ , זה אומר שנצטרך להפעיל עליה $\mbox{MP}$ . זה אומר שנצטרך להוכיח איכשהו את $\left[\alpha\to\left(\gamma\to\beta\right)\right]$ , וזה אומר ש- $\left[\alpha\to\left(\gamma\to\beta\right)\right]$ חייב להתאים למבנה של תבנית אקסיומה כלשהי – מן הסתם, תבנית אקסיומה מס' 1. שימו לב איך אין לנו ברירה ואנחנו ממש נדחפים לכך שנהיה חייבים לבחור $\beta=\alpha$ , אחרת $\left[\alpha\to\left(\gamma\to\beta\right)\right]$ לעולם לא תתאים לתבנית של אקסיומה מס' 1. לעומת זאת, ל- $\gamma$ יש לנו חופש בחירה מוחלט; בואו נתחיל נסיון הוכחה חדש ונראה מה ישתלם לנו לבחור בתור ערכו של $\gamma$ .

$\left[\alpha\to\left(\gamma\to\alpha\right)\right]\to\left[\left(\alpha\to\gamma\right)\to\left(\alpha\to\alpha\right)\right]$ (תבנית אקסיומה מס' 2).
$\alpha\to\left(\gamma\to\alpha\right)$ (תבנית אקסיומה מס' 1).
$\left(\alpha\to\gamma\right)\to\left(\alpha\to\alpha\right)$ ( $\mbox{MP}$ על 1,2).

אנחנו כמעט שם! רק צריך לבחור ערך ל- $\gamma$ כך ש- $\alpha\to\gamma$ ייראה כמו תבנית האקסיומה $\alpha\to\left(\beta\to\alpha\right)$ . אם כן, מתבקש לבחור $\gamma=\alpha\to\alpha$ , ולקבל:

$\left[\alpha\to\left(\alpha\to\alpha\right)\right]\to\left(\alpha\to\alpha\right)$ (הצבנו $\gamma=\alpha\to\alpha$ ).
$\alpha\to\left(\alpha\to\alpha\right)$ (תבנית אקסיומה מס' 1).
$\alpha\to\alpha$ ( $\mbox{MP}$ על 1,2).

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

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

תגים: תחשיב הפסוקים
שייך לקטגוריות לוגיקה | אין תגובות »

בקשת סיוע מהקוראים – תורת הקבוצות ולוגיקה

2 באפריל, 2012

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

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

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

הנה הלינק לסיכומי ההרצאות:

http://dl.dropbox.com/u/11564496/Lectures.pdf

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

תודה מראש לכולכם!

שייך לקטגוריות כללי | 44 תגובות »

לא מדויק

אז מה הקטע עם דילוגי אותיות בתורה? (חלק ב')

איור: המלון של הילברט

אז מה הקטע עם דילוגי אותיות בתורה? (חלק א')

משפט Valiant-Vazirani, או: איך להרוג השמות מספקות עם פונקציות תמצות אקראיות

מרחבי מכפלה פנימית – לפעמים הצמדה היא באמת הצמדה

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

כיצד תעזור לכם המתמטיקה לחמוק מדו"חות תנועה

משפט השלמות לתחשיב הפסוקים

תחשיב הפסוקים – על נביעה לוגית והוכחות

בקשת סיוע מהקוראים – תורת הקבוצות ולוגיקה

עמודים

Blogroll

פוסטים אקראיים

קטגוריות

ארכיון

כלים