לא מדויק

עברתי דירה (וחידת פרידה)

04 בינואר 2010 מאת gadial

בשעה טובה, לרגל השנה החדשה, החלטתי לעבור דירה:

http://www.gadial.net/

אלו מכם שעוקבים אחרי הבלוג דרך קוראי ה-RSS יצטרכו לעדכן את הכתובת:

http://www.gadial.net/?feed=rss2

אני מקווה שעדכוני הדואר ימשיכו לעבוד כרגיל - אשמח אם תודיעו לי במקרה שזה לא כך.

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

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

בהצלחה!

gadial | שייך לנושא כללי, משחקים וחידות מתמטיות | 11 תגובות »

משוואות דיופנטיות, ולמה בגללן אנחנו מתעניינים במספרים p-אדיים?

01 בינואר 2010 מאת gadial

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

הדוגמה הקלאסית היא משוואות ממעלה שניה. כל תלמיד תיכון יודע שכדי למצוא את פתרונות המשוואה $ax^{2}+bx+c=0$ יש לחשב את $\frac{-b\pm\sqrt{b^{2}-4ac}}{2a}$ , וחלק נכבד מלימודי המתמטיקה בתיכון מוקדש להצבת דברים בנוסחה זו. המתמטיקאי לא מציב בנוסחה זו להנאתו; כשהוא אומר שהוא “פותר משוואות ממעלה שנייה”, כוונתו לכך שהוא מוצא את הנוסחה הזו מלכתחילה. ואכן, על פניו לא ברור למה הנוסחה עובדת בכלל; יש כאן מין “קסם”, שמהנוסחה המפחידה הזו יוצאים הפתרונות של המשוואה. זהו תפקידו של המתמטיקאי לגלות את הקסם ולתרגם אותו לשיטת פעולה פשוטה יחסית - במקרה זה, הצבה בנוסחה.

בפוסט הזה ובהמשכים שלו אני רוצה להתמקד במחלקה מיוחדת וחשובה ביותר של משוואות - משוואות דיופנטיות. משוואה דיופנטית היא משוואה בנעלם אחד או יותר, שכל המקדמים בה הם מספרים שלמים, והפתרונות שאנו מחפשים גם הם מספרים שלמים (לעתים מרשים גם מספרים רציונליים כי ניתן לתרגם משוואה רציונלית שכזו למשוואה בשלמים, אבל ברשותכם לא אכנס לכך). משוואות דיופנטיות הן טבעיות מאוד, כי המספרים שאנו פוגשים בחיי היום-יום הם מספרים שלמים (ורציונליים), ופתרונות שאינם שלמים לרוב אינם מועילים לנו. דוגמה חביבה לכך היא בעיית כדורי התותח: נשאלת השאלה האם ניתן לקחת קבוצת כדורי תותח המסודרת על הקרקע בריבוע מושלם (כלומר, אין בו חורים של כדורים חסרים), ולבנות מהם פירמידה מושלמת (פירמידה במקרה זה מורכבת מריבוע עם אורך צלע $k$ של כדורים, שעליו מושם ריבוע עם אורך צלע $k-1$ וכן הלאה). כלומר, השאלה היא האם קיימים $k,n$ כך ש- $\sum_{i=1}^{k}i^{2}=n^{2}$ . נוסחה ידועה עבור הסכום שבאגף שמאל נותנת את המשוואה $\frac{k\left(k+1\right)\left(2k+1\right)}{6}-n^{2}=0$ . זוהי משוואה בשני נעלמים עם מקדמים רציונליים - את המקדמים הרציונליים אפשר לבטל על ידי הוצאת גורם משותף, כך שמתקבלת בסופו של דבר המשוואה הדיופנטית הבאה: $k\left(k+1\right)\left(2k+1\right)-6n^{2}=0$ . מן הסתם פתרון שאיננו שלם למשוואה הזו הוא חסר טעם - אנחנו לא יכולים להשתעשע עם מחצית כדור תותח, או עם $\frac{1}{\pi}$ כדור תותח. אם כן, מהם פתרונות המשוואה? אפשר לגלות על ידי ניסוי וטעייה ש- $\left(1,1\right)$ ו- $\left(24,70\right)$ הם פתרונות, אבל האם קיימים עוד? מסתבר שלא, אך ההוכחה אינה פשוטה בכלל.

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

דוגמה: המשפט האחרון של פרמה. המשוואה הדיופנטית $x^{2}+y^{2}=z^{2}$ ניתנת לפתרון - למעשה, יש לה אינסוף פתרונות, וזו שאלה מעניינת (אם כי בעלת תשובה פשוטה יחסית) למצוא את כולם. והנה בא פרמה וטען שהוא סגר את כל המשוואות הדומות: שכל משוואה מהצורה $x^{n}+y^{n}=z^{n}$ אינה ניתנת לפתרון כאשר $n$ טבעי גדול מ-2. נדרשו כ-300 שנים להוכחת הטענה הזו, כשבאמצע הדרך מומצא התחום של תורת המספרים האלגברית כדי לטפל במקרים פרטיים שלה. הפתרון מגיע בסופו של דבר מתחום שעוסק בפתרונות של משוואות דיופנטיות אחרות - משוואות מהצורה $y^{2}=x^{3}+ax+b$ - “עקומים אליפטיים”. למעשה, בהקשר של משפט פרמה העניין הוא בפתרונות רציונליים של המשוואה ולא רק שלמים, אך גם לזה לא אוכל להיכנס כרגע.

עוד דוגמה יפה במיוחד היא משוואת פל - משוואה מהצורה $x^{2}-Dy^{2}=1$ עבור $D$ שאינו ריבוע (יש עוד הכללות שלה - ה-1 באגף ימין יכול להיות מוחלף במספרים אחרים, במחיר סיבוך של התורה). המשוואה הזו נראית לא מזיקה ממבט ראשון, אבל יש לה נטייה לצוץ בהקשרים רבים ושונים. אחד מהחביבים עלי הוא בחידה מס’ 100 מפרויקט אוילר: יש קופסה עם כדורים אדומים וכחולים, ואנו שולפים שניים באקראי. מה צריך להיות הרכב הכדורים בתיבה כדי שההסתברות ששני הכדורים שישלפו יהיו כחולים תהיה בדיוק חצי? הרכב אפשרי אחד הוא של 15 כדורים כחולים ו-6 כדורים אדומים, אבל יש מן הסתם הרכבים רבים נוספים. אפשר לתרגם באופן מסויים את מציאתם למציאת פתרונות עבור משוואת פל מסויימת (עם מינוס 1 באגף ימין ולא 1, אך ההבדל כאמור אינו כה גדול).

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

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

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

בואו נביט לרגע במשוואה $2x+4y=3$ . האם קיים למשוואה פתרון? מייד אפשר לראות שהתשובה שלילית. למה? כי המספר שבאגף ימין אי זוגי, ואילו לא משנה מה נציב בתור $x,y$ באגף שמאל, נקבל שם מספר זוגי.

באופן דומה גם למשוואה $3x^{2}+9y^{17}=5$ אין פתרון, הפעם בגלל תכונת התחלקות ב-3. הדרך לטפל באופן מסודר בכללי האצבע הללו היא להסתכל על המשוואות מודולו מספר כלשהו $n$ .

חשבון מודולו $n$ דומה לחשבון רגיל, תחת המגבלה שאחרי שאנו מבצעים פעולה כלשהי אנו מחלקים את התוצאה ב- $n$ ולוקחים רק את השארית. כך למשל אם $n=7$ , אז תוצאת החיבור $5+3$ היא 1, כי $5+3=8$ וכאשר מחלקים $8$ ב- $7$ מקבלים 1. שני מספרים הם שווים מודולו $n$ אם הם מחזירים את אותה שארית בחלוקה ב- $n$ ; כך למשל $3\equiv_{7}10$ . הרעיון בחשבון מודולו $n$ הוא להצטמצם לדיון על אוסף השאריות האפשריות בחלוקה ב- $n$ - בדיוק המספרים $0,1,2,\dots,n-1$ . משוואה דיופנטית שמסתכלים עליה מודולו $n$ היא קלה הרבה יותר לפתרון ממשוואה דיופנטית רגילה, מהטעם הפשוט שיש רק מספר סופי של הצבות ערכים אפשריות לבדוק (אם אנחנו עובדים מודולו $n=7$ וכבר הצבנו $x=3$ , אין טעם להציב גם $x=10$ למשל, כי נקבל את אותה תוצאה). למשל, הבה ונביט במשוואה $3x\equiv_{7}5$ - אפשר פשוט להציב בה את כל המספרים מ-0 ועד $6$ ולראות מתי נקבל 5 (למשל, עבור $x=4$ נקבל ש- $3x=12\equiv_{7}5$ ).

האבחנה המרכזית כאן היא שאם משוואה דיופנטית כלשהי היא פתירה בשלמים, אז היא בוודאי פתירה מודולו $n$ לכל $n$ (למה?). לכן אם נצליח למצוא ולו $n$ אחד ויחיד כך שהמשוואה אינה פתירה מודולו $n$ , ינבע מכך שאין לה פתרון כלל. לרוע המזל, ההפך אינו נכון - קיימות משוואות שהן פתירות מודולו כל $n$ אך למרות זאת אין להן פתרון בשלמים. עם זאת, זו עדיין התקדמות כלשהי, שגם מציגה את דרך העבודה הכללית בתורת המספרים: כדי להגיד משהו מעניין על המספרים השלמים, אנחנו עוברים לבחון את הבעיה בתוך אוסף מספרים אחר (במקרה הזה, אוסף השאריות מודולו $n$ , שמסומן בדרך כלל ב- $\mathbb{Z}_{n}$ ).

האם באמת צריך לנסות ולפתור את המשוואה מודולו כל $n$ ? ובכן, לא. כאן נכנס לעזרתנו משפט מתורת המספרים - “משפט השאריות הסיני“. בבסיסו, המשפט אומר שאם $n=ab$ כאשר $a,b$ זרים זה לזה - אין להם מחלק משותף גדול מ-1, אז משוואה היא פתירה מודולו $n$ אם ורק אם היא פתירה מודולו $a$ ופתירה מודולו $b$ . למעשה, כיוון אחד כאן הוא טריוויאלי - אם המשוואה פתירה מודולו $n$ אותו פתרון טוב הן מודולו $a$ והן מודולו $b$ - הכוח של המשפט נעוץ בכך שהוא מראה כיצד ניתן לבנות מפתרון אחד למשוואה מודולו $a$ ומפתרון אחר למשוואה מודולו $b$ פתרון “משולב” עבור המשוואה מודולו $n$ (ליתר דיוק, זה לא בדיוק מה שהמשפט אומר אלא תוצאה כמעט מיידית שלו).

הנה דוגמה: נניח ש- $n=119$ , כלומר $a=7,b=17$ במקרה זה, ואנו מתבוננים במשוואה $x^{2}=2$ . לא קשה לראות שמודולו 7 המשוואה הזו פתירה עם $x=3$ , ואילו מודולו 17 המשוואה הזו פתירה עם $x=6$ . מהו הפתרון מודולו 119? על ידי חיפוש ממצה אפשר לגלות ש-11 הוא פתרון שכזה, אולם משפט השאריות הסיני (שכבר תיארתי בעבר ולכן לא אפרט עליו כעת) נותן לדרך “לבנות” את 11 באופן אלגוריתמי ויעיל מתוך שני הפתרונות הידועים.

המשפט ניתן להכללה ללא קושי עבור כל פירוק של $n$ לגורמים זרים זה לזה; ולכן הדבר המתבקש ביותר הוא להסתכל על הפירוק ה”מקסימלי” של $n$ , לכמה שיותר גורמים - דהיינו, פירוק לראשוניים. $n=p_{1}^{k_{1}}\dots p_{t}^{k_{t}}$ . מהפירוק הזה עולה שמספיק לבדוק האם המשוואה פתירה מודולו $p_{i}^{k_{i}}$ לכל $1\le i\le t$ כדי לגלות אם היא פתירה מודולו $n$ . אי אפשר לפרק גם את $p_{i}^{k_{i}}$ למכפלות קטנות יותר של $p_{i}$ , שכן אז נקבל מספרים שאינם זרים זה לזה ( $p$ ו- $p^{2}$ הם בעלי מחלק משותף גדול מ-1: $p$ ).

אם כן, הדיון שלנו הצטצמם כעת לבחינת משוואות מודלו $p^{n}$ כאשר $p$ ראשוני ו- $n$ טבעי כלשהו. האינטואיציה הראשונה היא לעסוק במשוואה מודולו $p$ , ולראות האם בהינתן פתרון מודולו $p$ ניתן לבנות ממנו פתרון גם עבור מודולו $p^{2}$ , וממנו פתרון עבור $p^{3}$ וכן הלאה. הסיבה לכך שעבודה מודולו $p$ היא קורצת כל כך היא שלאוסף המספרים מודולו $p$ , $\mathbb{Z}_{p}$ , יש מבנה מוצלח במיוחד: הם מהווים שדה - סגורים לכל ארבע פעולות החשבון. עבור חזקות של ראשוניים זה כבר לא עובד כך (אלו מכם שלמדו על שדות סופיים ודאי זוכרים שכל שדה סופי מכיל $p^{n}$ איברים, עבור $p$ ראשוני ו- $n$ טבעי, אבל חשוב להבין ש- $\mathbb{F}_{p^{n}}$ שונה במבנהו מהקבוצה $\mathbb{Z}_{p^{n}}$ ; בתור התחלה, ב- $\mathbb{Z}_{p^{n}}$ ישנם איברים שונים מאפס שמכפלתם נותנת 0, למשל $p$ ו- $p^{n-1}$ ; ב- $\mathbb{F}_{p^{n}}$ אין דבר כזה).

ובכן, זו התחלה טובה, והיא תיתן לנו אינטואיציה לגבי המשך הדרך - ובסופה של הדרך נגיע לשדה אחר של מספרים, שמכיל בתוכו את המספרים הרציונליים, והאיברים ה”שלמים” בו הם מעין הכללה של המספרים השלמים הרגילים, ואשר מקיים את התכונה שאם משוואה היא פתירה בו בשלמים (ה”שלמים” של אותו שדה, לא השלמים הרגילים) אז אותה משוואה פתירה בשלמים “רגילים” מודולו $p^{n}$ , לכל $n$ . כלומר, אברי השדה הזו מקודדים איכשהו מידע על כל מה שקורה ב- $\mathbb{Z}_{p^{n}}$ , לכל $n$ . לשדה בעל התכונה המעניינת הזו קוראים שדה המספרים ה-p-אדיים (כפי שהשם מרמז, קיים כזה לכל $p$ ראשוני), ואותו אציג בפוסט הבא.

gadial | שייך לנושא תורת המספרים | 2 תגובות »

חידת מעטפות

31 בדצמבר 2009 מאת gadial

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

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

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

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

ובכן, כל מה שידוע לי הוא הערך שנמצא במעטפה שפתחתי, אותו אסמן ב- $x$ . כלל ההחלטה שלי ניתן יהיה לתיאור באופן כללי בתור פונקציה $f\left(x\right)$ שלכל $x$ מתאימה את ההסתברות שאבחר לא להחליף. עד כאן פורמליסטיקה, וכעת נפנה לפתרון כלשהו. האינטואיציה הראשונה שלי בתרגיל הזה היא שככל ש- $x$ גדול יותר, כך אני אתפתה פחות להחליף אותו. הדרך הפורמלית לבצע משהו כזה היא לבחור בתור $f$ פונקציה שעולה תמיד (כלומר, אם $x<y$ אז $f\left(x\right)<f\left(y\right)$ ) ועם זאת ערכיה נמצאים כל הזמן בתוך התחום $\left[0,1\right]$ (אחרת היא לא מייצגת הסתברות). לא קשה לבנות פונקציות כאלו - למשל באמצעות מניפולציה על הפונקציה $\arctan$ (הפונקציה ההופכית לטנגנס) - זוהי פונקציה עולה ממש שערכיה נעים בתחום $\left[-\pi/2,\pi/2\right]$ , כך שרק צריך “לכווץ” אותה מעט ו”להרים” אותה מעט כדי לקבל $f$ כמו שרציתי. ברשותכם אפסח על הפרטים הטכניים הללו.

ובכן, מסתבר ש- $f$ שכזו עובדת מצויין. בואו נחשב את ההסתברות שאנצח, אם אני נעזר ב- $f$ הזו. ההסתברות שאנצח היא ההסתברות שאבחר בהתחלה את $a$ (בהסתברות חצי) ואז בגלל $f$ אבחר להחליף (בהסתברות $1-f\left(a\right)$ ), ועוד ההסתברות שאבחר בהתחלה את $b$ (שוב, בהסתברות חצי) ואז בגלל $f$ אבחר דווקא לא להחליף (בהסתברות $f\left(b\right)$ ). מה ההסתברות שלי לנצח? $\frac{1}{2}\cdot\left(1-f\left(a\right)\right)+\frac{1}{2}\cdot f\left(b\right)=\frac{1}{2}\left(1+f\left(b\right)-f\left(a\right)\right)=\frac{1}{2}+\frac{1}{2}\left(f\left(b\right)-f\left(a\right)\right)$ , והסתברות זו גדולה ממש מחצי כאשר $a<b$ , כי אז $f\left(a\right)<f\left(b\right)$ , כלומר $f\left(b\right)-f\left(a\right)>0$ (אם $a=b$ אז אני מנצח תמיד, כי לא משנה מה אעשה - אסיים עם הסכום הגדול מבין השניים, שבמקרה זה הם שווים).

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

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

הבה ונעשה כעת את החישוב הפורמלי. אנחנו צריכים להבדיל בין ההסתברות של שלושה מקרים: $P\left(y\le a\right),P\left(y>b\right),P\left(a<y\le b\right)$ . אלו שלושת המקרים האפשריים היחידים, ולכן סכום ההסתברויות שלהם הוא 1, וכדי לחשב את ההסתברות שאנצח צריך לכפול כל אחד מהם בהסתברות לנצח בהניתן שהוא קרה. נקבל את הסכום הבא:

$\begin{eqnarray*}<br /> \frac{1}{2}P\left(y\le a\right)+\frac{1}{2}P\left(y>b\right)+P\left(a<y\le b\right) & =\\<br /> & = & \frac{1}{2}\left(P\left(y\le a\right)+P\left(y>b\right)+P\left(a<y\le b\right)\right)+\frac{1}{2}P\left(a<y\le b\right)\\<br /> & = & \frac{1}{2}+\frac{1}{2}P\left(a<y\le b\right)\end{eqnarray*}$

אם כן, שוב קיבלתי הסתברות הצלחה של “חצי ועוד קצת”. כל מה שנדרש ממני הוא שההתפלגות שבה אני בוחר את $y$ תהיה כזו שבה לכל $a<b$ , ההסתברות שיתקיים $a<y\le b$ תהיה חיובית. התפלגות נורמלית היא הדוגמה הקלאסית להתפלגות שבה זה מתקיים, אך כאמור - כל התפלגות עם פונקצית צפיפות הסתברות חיובית תמיד עובדת (ואין בעיה גם עם פונקציות מוגבלות יותר, עם נקודות אי רציפות סליקות - אבל למה לחפור בכך?)

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

gadial | שייך לנושא משחקים וחידות מתמטיות, הסתברות | 12 תגובות »

איך לחזות את מזג האוויר בלי להסתכל בשמיים? (משפט המינימקס)

19 בדצמבר 2009 מאת gadial

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

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

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

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

זה אחד מהמקומות שבהם כתיבה פורמלית מסייעת להבין על מה מדובר. אם $x$ מסמן אסטרטגיה כלשהי של אליס מתוך קבוצת אסטרטגיות $X$ ו- $y$ אסטרטגיה כלשהי של בוב מתוך קבוצת אסטרטגיות $Y$ , אז $\pi:X\times Y\to\mathbb{R}$ היא “פונקצית הרווח” של אליס: $\pi\left(x,y\right)$ הוא הרווח של אליס מהמשחק אם היא נוקטת ב- $x$ ובוב נוקט ב- $y$ (וכזכור, מספר זה מתאר גם את ההפסד של בוב. שיכול להיות גם הרווח של בוב. ואז הוא ההפסד של אליס. לא מבלבל בכלל).

ניקח לדוגמה את משחק הזוג-או-פרט שדיברתי עליו לא מזמן. במשחק הזה האסטרטגיה היא בסך הכל מספר האצבעות שמוציאים. אם נניח שמוציאים בין 0 ל-5 אצבעות, שניצחון במשחק מסומן על ידי רווח בגודל 1, ושאליס היא השחקן של “זוג”, אז $\pi$ היא פונקציה $\pi:\left\{ 0,1,\dots,5\right\} ^{2}\to\mathbb{R}$ שמקיימת למשל $\pi\left(2,2\right)=1$ ו- $\pi\left(3,2\right)=-1$ . כשמדברים על שחמט הסיטואציה מורכבת הרבה יותר, מבחינת איך שכל אסטרטגיה נראית, כי כל אסטרטגיה מכילה הוראות מהצורה “אם הגעת לפוזיציה כזו של הלוח, פעל כך…” (וזה אפילו מורכב עוד יותר, כי גם לאופן ההגעה לפוזיציה יש חשיבות, כי למשל טמון בו מידע מי כבר ביצע הצרחות, כמה מהלכים ללא תזוזת/הכאת רגלי בוצעו, וכדומה). עדיין, קבוצת הפלטים האפשריים של הפונקציה תהיה או 1, או מינוס 1, או 0 (שבא לציין תיקו), ומרגע שכל שחקן החליט מה האסטרטגיה שלו (לפני שהמשחק התחיל!), כל מה שנותר לעשות הוא לשבת ו”להריץ” את המשחק ולראות מה קרה כדי לחשב את $\pi$ . אז אדגיש שוב - לא משנים אסטרטגיות “במהלך” המשחק, על בסיס מידע שצץ במהלך המשחק - האסטרטגיה מראש מתייחסת לכל מידע שעשוי לצוץ במהלך המשחק.

אם המשחק עצמו הוא סופי באופיו (משחק סופי של בחירות, ובכל שלב ניתן לבחור רק במספר סופי של אפשרויות) אז גם מספר האסטרטגיות האפשריות בו יהיה סופי. אני רוצה לדבר רק על הסיטואציה הזו, כי אם המשחק אינו סופי כל מה שאגיד הוא פשוט שגוי. השאלה שמעניינת אותנו כאן היא זו - בהינתן משחק, כמה אליס מסוגלת להרוויח בו ללא תלות במעשיו של בוב? הרי אליס אינה יכולה לדעת איזו אסטרטגיה בוב יבחר, ולהתחיל לנתח אילו אסטרטגיות “סביר” שהוא יבחר כבר יגרור אותנו לניתוחים מסובכים למדי - לכן הבעיה הראשונה שיש לפתור היא את שאלת הרווח-ללא-תלות-בבוב. אחרי שנגמור איתה אפשר יהיה לעבור לדברים מסובכים יותר (אך לא נזדקק להם כאן, ולכן לא אדבר עליהם).לכל אסטרטגיה $x\in X$ שאליס נוקטת בה, יש לבוב מגוון אסטרטגיות $y\in Y$ שהוא יכול לנקוט בהן. אחת מהאסטרטגיות הללו - נאמר, $y_{0}$ - היא הגרועה ביותר מבחינת אליס, במובן זה שהרווח שאליס תקבל אם בוב ישחק את $y_{0}$ (בהינתן שאליס שיחקה את $x$ ) הוא המינימלי: $\pi\left(x,y_{0}\right)\le\pi\left(x,y\right)$ לכל $y\in Y$ . מכיוון שלאליס אין שליטה על מעשיו של בוב ומכיוון שהיא רוצה לדבר על הרווח הגדול ביותר שהיא תוכל לקבל בלי תלות במעשיו של בוב, $\pi\left(x,y_{0}\right)$ הוא בדיוק הרווח הזה. סימון קצת יותר פשוט לכל זה הוא $\min_{y}\pi\left(x,y\right)$ : המינימום על פני כל הערכים של $\pi\left(x,y\right)$ כאשר אנחנו משאירים את $x$ קבוע ומשנים את $y$ .

אם כן, מה הרווח הגדול ביותר שאליס מסוגלת לקבל במשחק ללא תלות במעשיו של בוב? אם לכל $x$ נקבע לנו ערך $\min_{y}\pi\left(x,y\right)$ שאותו $x$ מביא, אנחנו נרצה את ה- $x$ שעבורו הרווח הזה מקסימלי - ואז נסמן את התוצאה כ- $\max_{x}\min_{y}\pi\left(x,y\right)$ .

מן העבר השני, המצב אצל בוב הפוך. מכיוון שהוא מעוניין להרוויח כמה שיותר במשחק, הוא מעוניין לקבל ערך קטן ככל האפשר של $\pi\left(x,y\right)$ . לכן הרווח האופטימלי של בוב הוא $\min_{y}\max_{x}\pi\left(x,y\right)$ . אם תצליחו להצדיק לעצמכם את הנוסחה הזו - כנראה שהבנתם את מה שהלך כאן עד כה.

מה המקסמין של אליס במשחק זוג או פרט? לכל $x$ שלה קיים $y$ של בוב כך ש- $\pi\left(x,y\right)=-1$ , ולכן קל לראות שהערך הזה הוא מינוס 1. בדומה, הערך עבור בוב הוא 1. כלומר, אף אחד משני השחקנים לא מסוגל להבטיח לעצמו משהו שאיננו תבוסה מחפירה. זה מלמד אותנו שני דברים: ראשית, שתמיד מתקיים $\min_{y}\max_{x}\pi\left(x,y\right)\le\max_{x}\min_{y}\pi\left(x,y\right)$ (נסו להוכיח זאת לעצמכם) ושנית - שבינתיים כל הסיפור עם המקסמין והמינמקס לא ממש שיפר משמעותית את מה שאפשר לומר על המשחק.

לכן השלב הבא הוא להכניס הסתברות לתמונה. עד כה דיברנו רק על אסטרטגיות “טהורות”, שחובה עלינו לבחור באחת מהן, וזהו. אבל למה, בעצם? האם מי שמשחק זוג או פרט לא מבצע הגרלה כלשהי כדי להחליט באיזו אסטרטגיה לנקוט, אפילו אם באופן בלתי מודע? האם שחקן שחמט משחק תמיד באותו האופן? במציאות כל אחד מאיתנו נוקט בתערובת של אסטרטגיות טהורות, כשהבחירה מה לעשות היא הסתברותית. אם כן, מבלי להיכנס יותר מדי לפרטים הטכניים, הרעיון הוא שאנחנו מרחיבים את מאגר האסטרטגיות שלנו, כך שכל אסטרטגיה כעת מייצגת ראשית כל הגרלה על פי התפלגות כלשהי של אחת מהאסטרטגיות ה”טהורות”, ואז משחק על פי האסטרטגיה שנבחרה. כדי לא לסבך את החיים עדיין אשתמש ב- $x$ וב- $X$ כדי לתאר אסטרטגיות “מעורבות” שכאלה. את מושג הרווח - $\pi\left(x,y\right)$ - צריך גם כן לתקן קצת כדי שיתאר את הרווח שמתקבל בתוחלת (כלומר, מה יקרה בממוצע אם נשחק הרבה משחקים עם אותה אסטרטגיה מעורבת).

ועכשיו נכנס לתמונה משפט המינימקס: אם האסטרטגיות המותרות במשחק הן מעורבות, אז מתקיים $\min_{y}\max_{x}\pi\left(x,y\right)=\max_{x}\min_{y}\pi\left(x,y\right)$ . כלומר, אם אפשר להגריל אסטרטגיות, הדבר הטוב ביותר שאליס יכולה להבטיח לעצמה הוא בדיוק הדבר הטוב ביותר שבוב יכול להבטיח לעצמו. במשחק הזוג או פרט קל לראות שהדבר הזה הוא בדיוק 0 (שמשמעותו המעשית היא שכשמשחקים הרבה משחקים, בוב ואליס ינצחו בערך אותה כמות פעמים, אם שניהם משתמשים באסטרטגיה המעורבת האופטימלית שעליה דיברתי בפוסט המתאים).

אלא שיש עוד דרך להציג את המשפט - דרך מעט יותר מעניינת, לטעמי, וכזו ששופכת אור על עניין החזאים שלנו. לצורך כך, שאלה פשוטה: האם הטענה “לכל $y$ קיים $x$ כך שמתקיים $P\left(x,y\right)$ ” כש- $P$ זו איזו שהיא תכונה של $x,y$ (שמתקיימת או שאינה מתקיימת) גוררת את הטענה “קיים $x$ כך שלכל $y$ מתקיים $P\left(x,y\right)$ ”? עצרו וחשבו על כך רגע. נסו דוגמאות קונקרטיות של $P$ , וחזרו לקרוא עם המסקנה.

ובכן? התשובה היא - כמובן שלא! נניח ש- $P\left(x,y\right)$ פירושו $x<y$ (כש- $x,y$ שניהם מספרים טבעיים, למשל). אז “לכל $y$ קיים $x$ כך ש- $y<x$ ” היא טענה שנכונה באופן טריוויאלי - בהינתן $y$ , ניקח את $x$ להיות $y+1$ . לכל מספר קיים מספר שגדול ממנו. לעומת זאת, “קיים $x$ כך שלכל $y$ מתקיים $y<x$ ” היא בבירור לא טענה נכונה - לא קיים מספר טבעי $x$ שגדול מכל המספרים הטבעיים. הטענה השניה היא חזקה הרבה יותר, במובן זה שהיא מבטיחה קיום של $x$ ספציפי שטוב לכל $y$ , להבדיל מהטענה הראשונה שלכל $y$ קיים $x$ ספציפי עבורו. לסטודנטים לחדו”א מביניכם שמתקשים בהבנת המושג של רציפות במידה שווה (מושג שגרם לי קשיים רבים בשעתו): רציפות “רגילה” היא טענה מהסוג הראשון, ורציפות במידה שווה היא טענה מן הסוג השני.

אז מה הקשר למשפט המינימקס? שמשפט המינימקס הוא דוגמה לסיטואציה שבה טענה מהסוג הראשון כן גוררת טענה מהסוג השני! במקרה הזה $x,y$ הן אסטרטגיות ו- $P\left(x,y\right)$ היא (למשל) התכונה “ $\pi\left(x,y\right)$ הוא לפחות הרווח האופטימלי של אליס”. הרי ברור שלכל $y$ של בוב קיים $x$ של אליס כך שהרווח של אליס הוא לפחות הרווח האופטימלי שלה - אחרת, אם יש $y$ שעבורו אין לאליס מענה הולם, בוב ישחק את $y$ הזה ואז אליס תהיה חייבת לקבל רווח שהוא נמוך מהרווח האופטימלי שלה - סתירה להגדרתו של הרווח האופטימלי (כזכור - הרווח הגדול ביותר שאליס יכולה לקבל בלי תלות בבוב).

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

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

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

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

אלא שהמשחק הזה אינו סימטרי כלל ועיקר. התפקיד של מוריד הגשם הוא להוריד גשם, והתפקיד של החזאי הוא לחזות איך מוריד הגשם יתנהג. מכאן נובע שאם החזאי יודע “מראש” מה האסטרטגיה המעורבת שמוריד הגשם בחר, החזאי מסוגל לתת תחזיות מדוייקות מאוד, כאלו שיעברו את המבחן בקלות (שוב - נימוק של זה דורש קצת פורמליסטיקה ועבודה טכנית, אבל הרעיון ברור). במילים אחרות - לכל $y$ של מוריד הגשם, קיים $x$ של החזאי כך ש- $\pi\left(x,y\right)\ge1$ - זהו בדיוק ה- $x$ ש”תפור” לאסטרטגיה $y$ של מוריד הגשם.

אבל עכשיו נכנס משפט המינימקס לתמונה… אם לכל $y$ קיים $x$ כך ש- $\pi\left(x,y\right)\ge1$ , אז נובע מכך שקיים $x$ כך שלכל $y$ מתקיים $\pi\left(x,y\right)\ge1$ . כלומר - יש לחזאי אסטרטגיה $x$ שמבטיחה לו נצחון במשחק, בלי תלות במעשיו של מוריד הגשם! כל מה שהחזאי צריך לעשות הוא לדווח על התחזיות על פי $x$ , ואין זה משנה בכלל איך מוריד הגשם יתנהג, החזאי ינצח!

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

gadial | שייך לנושא תורת המשחקים | 16 תגובות »

משפט הנישואים היציבים

07 בדצמבר 2009 מאת gadial

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

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

רוס: רייצ’ל, פיבי, מוניקה.

צ’נדלר: מוניקה, פיבי, רייצ’ל.

ג’ואי: רייצ’ל,מוניקה, פיבי.

רייצ’ל: רוס, ג’ואי, צ’נדלר.

מוניקה: צ’נדלר, ג’ואי, רוס.

פיבי: ג’ואי, רוס, צ’נדלר.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

מבלבל? מצד אחד כן - מצד שני, אפשר לחשוב ש”חברים” המקורי היה פחות מבלבל.

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

אני חושב שהמסקנות ברורות.

gadial | שייך לנושא תורת המשחקים | 12 תגובות »

זוג או פרד (כן, עם ד’!)

30 בנובמבר 2009 מאת gadial

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

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

מה שנמצא בבסיס טענת חוסר ההוגנות של שחר היא ההנחה (שהוא עצמו מכיר בכך שהיא בעייתית) שבמשחק כל אחד שולף בין אצבע אחת לחמש אצבעות, והבחירה ביניהן היא אקראית. האם מישהו משחק כך במציאות? בוודאי שלא, אבל מה היה קורה אם כן? ובכן, קל לראות שאז המשחק אינו “הוגן”, במובן זה שאחת האפשרויות יכולה לצאת בהסתברות גדולה יותר מהשנייה. אין צורך אפילו להיכנס לחישובים מורכבים; אם כל אחד מוציא בין אצבע אחת לחמש אז יש $5$ אפשרויות לשחקן, ולכן $25$ תוצאות אפשריות למשחק בכללותו; האפשרויות הללו מתחלקות לזוג ופרט, אבל יש מספר אי זוגי שלהן, ולכן אחת מהאפשרויות תזכה ביותר מקרים מהשניה (לפחות 13 מתוך 25). כמובן שאפשר גם לעשות את החישוב במדוייק: אם השחקנים מגרילים אצבע בין 1 ל-5 הם בעצם מגרילים “זוג” בהסתברות $\frac{2}{5}$ (ההסתברות לבחור או 2 או 4) ו”פרט” בהסתברות $\frac{3}{5}$ . השחקן “זוג” מנצח אם ורק אם שני השחקנים שלפו מספר אצבעות “זוגי” בו זמנית, או מספר אצבעות “אי זוגי” בו זמנית, כלומר ב- $\frac{2}{5}\cdot\frac{2}{5}+\frac{3}{5}\cdot\frac{3}{5}=\frac{4+9}{25}=\frac{13}{25}$ מהמקרים; לכן “זוג” תהיה התוצאה הנפוצה ביותר.

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

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

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

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

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

נניח לרגע שאני השחקן “זוג”. נניח שאני יודע שהיריב שלי מוציא באקראי אצבע בין 1 ל-5; מה משתלם לי להוציא? תגידו, ראינו שגם לך משתלם להוציא אצבע באקראי כי אז יש לך הסתברות זכיה של $\frac{13}{25}$ . האם איני יכול לשפר אותה? אני יודע שהיריב מוציא זוג בהסתברות $\frac{2}{5}$ ופרט בהסתברות $\frac{3}{5}$ ; אם תמיד אוציא פרט בעצמי, אזכה כשהיריב מוציא פרט, כלומר בהסתברות $\frac{15}{25}$ שגדולה מ- $\frac{13}{25}$ . אז האסטרטגיה “תוציא תמיד פרט” עדיפה עבורי.

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

בא השחקן “זוג” ואומר לעצמו “הממ, פרט יודע שאני תמיד ארצה לשחק פרט, ולכן הוא עצמו ישחק תמיד זוג, אז לי כדאי להוציא תמיד זוג, ואז אזכה בהסתברות 1!”

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

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

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

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

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

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

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

gadial | שייך לנושא תורת המשחקים | 18 תגובות »

הפוסט שיודע להדפיס את עצמו

27 בנובמבר 2009 מאת gadial

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

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

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

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

הרעיון הוא לבנות מכונה שמורכבת משתי “תת מכונות”, $A,B$ , כך ש- $A$ עושה משהו ואז עוצרת, והשליטה עוברת ל- $B$ שגם כן עושה משהו ועוצרת, ואחרי שהיא עוצרת על הסרט יהיה כתוב הקידוד של $A$ ולאחר מכן הקידוד של $B$ , מה שאסמן בתור $\left\langle AB\right\rangle$ . על פניו אני קצת מרמה כאן טכנית - בהגדרות מקובלות של קידודי מכונות טיורינג לא מרשים “פירוק” כזה של מכונה לשתי תת מכונות. אלא שאין בעיה עם הגדרה שכן מרשה “פירוק” שכזה; וכפי שנראה בהמשך, ההנחה אפילו לא הכרחית, רק מפשטת את ההבנה של הבניה.

אם כן, מה $A$ תעשה? פשוט מאוד - תכתוב את הקידוד של $B$ (כלומר, $\left\langle B\right\rangle$ ) על הסרט ואז תעצור. אבל רגע, מאיפה $A$ יודעת מה הקידוד של $B$ ? עדיין לא אמרנו מהי $B$ בכלל! אם כן, עלינו להגדיר את $B$ במדוייק, אבל להיות מאוד זהירים כשנעשה זאת; אם $B$ תהיה תלויה באופן כלשהו ב- $A$ , תהיה לנו כאן תלות מעגלית (הקוד של $B$ תלוי ב- $A$ , אבל מכיוון ש- $A$ מדפיסה את הקוד של $B$ , בוודאי שהקוד של $A$ תלוי ב- $B$ !). לכן נגדיר את $B$ בלי לדבר בכלל על $A$ .

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

אם כן, נסמן ב- $M_{w}$ מכונת טיורינג שמה שהיא עושה הוא לכתוב $w$ על הסרט ולעצור. אז מה ש- $B$ עושה הוא לבנות את $\left\langle M_{w}\right\rangle$ ולכתוב אותו ליד הקלט $w$ הקיים, כלומר בסופה של ריצת $B$ יהיה כתוב על הסרט $\left\langle M_{w}\right\rangle w$ . כדי להיות עוד יותר מדוייקים נדבר ממש על פונקציה, $q$ , שמקבלת כקלט $w$ ומוציאה כפלט $M_{w}$ ספציפית (שהרי יש הרבה מכונות שונות שכותבות $w$ על הסרט ועוצרות).

תיארנו את $B$ בלי להזדקק ל- $A$ , ולכן אין בעיה לכתוב מכונה $A$ שכל מה שהיא עושה בחיים הוא לכתוב $\left\langle B\right\rangle$ על הסרט ולעצור. כאן מגיע הפאנץ’: אפשר בתור $A$ לבחור את המכונה $q\left(\left\langle B\right\rangle \right)=M_{\left\langle B\right\rangle }$ ! כלומר, את המכונה שהפונקציה $q$ מחזירה. האם אתם כבר רואים לאן הולכים מכאן?

אז מה ש- $A$ עושה הוא לכתוב $\left\langle B\right\rangle$ על הסרט ולעצור. אז $B$ “מתעוררת”, רואה קלט $w=\left\langle B\right\rangle$ ( $w$ הוא הקידוד של $B$ , אך $B$ לא “יודעת” זאת), ומחשבת את $q\left(\left\langle B\right\rangle \right)=M_{\left\langle B\right\rangle }=\left\langle A\right\rangle$ . לסיום היא כותבת את הפלט הזה משמאל ל- $w$ שהיא קיבלה, כלומר בסיום ריצת $B$ כתוב על הסרט $\left\langle AB\right\rangle$ , בדיוק כפי שרצינו. תעלול פשוט, אך מבריק.

כעת אפשר להסביר מדוע ההנחה שהקידוד של המכונה מורכב קודם כל מהקידוד של $A$ ולאחר מכן מהקידוד של $B$ היא לגיטימית - כי מה שקורה ל- $B$ בסופו של דבר היא שהיא מחזיקה אצלה הן את הקידוד של $A$ (בתור ה- $q\left(w\right)$ והן את הקידוד של $B$ (בתור ה- $w$ ) והיא יכולה לעשות איתם מה שמתחשק לה. אנחנו ביקשנו ממנה לרשום אותם האחד אחרי השני, אבל אם היה צורך להשתמש בהם באופן מחוכם יותר, $B$ הייתה יכולה לעשות גם את זה. בעצם כל מה שאנחנו מניחים הוא שאם יש לנו מכונה שמורכבת משתי תת-מכונות $A,B$ ויש לנו את הקוד של אותן שתי תתי-מכונות, אז אפשר לבנות את הקוד של המכונה ה”מורכבת” - וזה דבר שאני מניח שתסכימו איתי שהוא אפשרי.

עכשיו אפשר לקחת את הבניה הזו צעד אחד קדימה ולבנות מכונה שיודעת להשתמש בקוד של עצמה כמה שתרצה. לצורך העניין, נחשוב על מכונה $T$ שמקבלת שני פרמטרים, $\left\langle M\right\rangle ,w$ , כאשר $w$ הוא הקלט ה”רגיל” של המכונה ואילו $\left\langle M\right\rangle$ הוא קידוד של מכונה כלשהי, ו- $T$ פועלת כפונקציה של שני הקלטים הללו. מה שאנחנו רוצים להראות הוא קיום של מכונה $R$ כך ש- $R\left(w\right)=T\left(\left\langle R\right\rangle ,w\right)$ . כלומר, $R$ מתנהגת כמו $T$ בכל הנוגע לקלט $w$ , ועבור הקוד $\left\langle M\right\rangle$ שלה עצמה. מבלבל? אז חשבו על תוכנית מחשב שמקבלת קלט מהמשתמש ועוד משתנה של “הקוד שלי”; אנחנו רוצים לגרום לתוכנית לרוץ כך שהמשתנה “הקוד שלי” יכיל את הערך הנכון.

אין כאן שום גאונות חדשה, אלא רק הרחבה פשוטה של הבניה שכבר ראינו. נוסיף את הקוד של המכונה $T$ למשחק, כך שהיא תתחיל לפעול אחרי $B$ , ולכן הקוד של המכונה ה”משולשת” יהיה $\left\langle ABT\right\rangle$ . מה ש- $A$ יעשה הפעם יהיה לכתוב $\left\langle BT\right\rangle$ על הסרט, ואילו $B$ יעשה בדיוק את אותו הדבר כמו קודם ויחשב את $\left\langle A\right\rangle$ . כש- $B$ יסיים את ריצתו על הסרט יהיה כתוב $\left\langle ABT\right\rangle$ וזה בדיוק מה ש- $T$ תראה כאשר היא תתחיל את ריצתה (ואיפה הקלט של $T$ נמצא? אפשר להניח שכבר $A$ שמרה אותו בצד - זה לא גורר שינוי משמעותי בהגדרות שלנו).

ועכשיו - לקוד בפועל, בשפת רובי, שמשתמש בדיוק ברעיונות שתיארתי כאן:

output = <<’END’
def q(w)
“output = <<’END’\n#{w}END\n”
end

a = q(output)
print a + output
END
def q(w)
“output = <<’END’\n#{w}END\n”
end

a = q(output)
print a + output

לא צריך לדעת יותר מדי רובי כדי להבין מה קורה כאן. הדבר המחוכם ביותר הוא האופן שבו אני מתאר מחרוזת: דרך אפשרית אחת לתאר מחרוזות ברובי שכוללות שורות רבות היא באמצעות כתיבת $<<$ ואחריו שם מזהה כלשהו (במקרה שלנו END) כך שכל מה שייכתב מעתה והלאה יהיה חלק מהמחרוזת עד אשר המזהה יופיע שוב בתחילת שורה (כך שמופעים של END שמופיעים באמצע השורה לא אומרים שהמחרוזת נגמרה). כל זה מושם בתוך המשתנה output; חשבו על זה בתור הריצה של $A$ , שכותבת את המחרוזת שמתארת את $B$ לא על ה”סרט” (כי אין סרט) אלא לתוך המשתנה output.

לאחר ה-END מגיע התיאור של $B$ . ראשית, הפונקציה $q$ שמקבלת $w$ ופולטת תוכנית שמה שהיא עושה בחיים הוא להדפיס את $w$ . אם תשימו לב, התוכנית הזו מוגדרת בדיוק כמו ה- $A$ שלי, רק שאני משתמש בדרך תיאור שונה קצת (במקום לרדת שורה בתוך המחרוזת אני כותב את הסימן n\ שמייצג ירידת שורה; ואת התוכן של $w$ אני מכניס לתוך המחרוזת באמצעות הביטוי $\mbox{\#\{w\}}$ שאומר לרובי “קחי את הערך של $w$ ותשתילי אותו בתוך המחרוזת”). לאחר הגדרת $q$ מגיע יתר הקוד של $B$ ; ראשית היא מחשבת את $q$ על “תוכן הסרט” הנוכחי (כלומר, על המשתנה output ואת התוצאה מכניסה למשתנה $a$ (שמייצג את $\left\langle A\right\rangle$ ); וכעת היא פולטת את השרשור של $a$ עם output, בדיוק כמו ש- $B$ התיאורטית שלי עבדה.

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

gadial | שייך לנושא תכנות, חישוביות | 4 תגובות »

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

04 בנובמבר 2009 מאת gadial

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

gadial | שייך לנושא קומבינטוריקה, לוגיקה | 9 תגובות »

כלל ה-0-1 של גרפים - הקדמה

02 בנובמבר 2009 מאת gadial

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

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

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

הזכרתי שפות מסדר ראשון לא מזמן, ואחזור על כך שוב, בהקשר הספציפי של גרפים: השפה שעליה אנחנו הולכים לדבר כוללת סימנים של משתנים כמו $v,u$ וכדומה; את הסימן $E\left(x,y\right)$ שמסמן את הטענה “יש קשת בין $x$ ל- $y$ ”; את סימן השוויון $=$ , כך שמשמעות $x=y$ היא “ $x$ הוא אותה הצומת כמו $y$ ”; קשרים לוגיים, כמו $\wedge$ (וגם), $\vee$ (או), $\to$ (גורר) ו- $\neg$ (לא); וכמתים - $\exists$ שמציין “קיים” ו- $\forall$ שמציין “לכל”. מכל היצורים הללו בונים פסוקים - סדרות של סמלים שמייצגות טענות מתמטיות. לא אכנס לפרטים המדוייקים של איך הבניה הזו עובדת פורמלית ומה נחשב פסוק חוקי, אלא אסתפק בדוגמאות. למשל, $\forall v\exists u\left(E\left(v,u\right)\right)$ הוא פסוק שאומר את הטענה “לכל צומת $v$ קיים צומת $u$ שמחובר אליו בקשת” - במילים אחרות, אין צומת מבודד. דוגמה נוספת: $\exists v_{1},v_{2},v_{3}\left(E\left(v_{1},v_{2}\right)\wedge E\left(v_{2},v_{3}\right)\wedge E\left(v_{3},v_{1}\right)\right)$ פירושו “קיימים שלושה צמתים $v_{1},v_{2},v_{3}$ שכולם מחוברים האחד אל השני” - במילים אחרות, בגרף יש משולש.

כאן נכנס לתמונה המושג של מודל עבור פסוקים. מודל (בנפנוף ידיים פרוע) הוא קבוצה של איברים, שהם הערכים שהמשתנים יכולים לקבל, ושל יחסים - במקרה הזה, יחס אחד שמותאם ליחס $E$ שיש בשפה שתיארתי. גרף הוא מודל לגיטימי כאן, עם המשמעות הרגילה - אבריו הם הצמתים, והיחס הוא “בין $v$ ל- $u$ יש קשת”. מצד שני, אפשר לחשוב גם על מודלים אחרים; למשל, המספרים הטבעיים עם היחס “קטן מ-”. כלומר, $E\left(v,u\right)$ , תחת הפרשנות של “ $u,v$ הם מספרים טבעיים ו- $E$ הוא היחס “קטן מ-”". אם כן, קצת רימיתי קודם - $\forall v\exists u\left(E\left(v,u\right)\right)$ לא באמת אומר “לכל צומת $v$ קיים צומת $u$ שמחובר אליו בקשת” - כאן אנחנו מייחסים משמעות לסמלים - אלא רק אומר “לכל $v$ קיים $u$ כך שמתקיים ביניהם היחס $E$ ”. מהם $v,u$ ומהו היחס $E$ ? זה תלוי בפרשנות שלנו, וזה מה שמודל מנסה לעשות - לתת פרשנות. במודל של המספרים הטבעיים, הפסוק הזה ניתן לתרגום בתור “לכל מספר $v$ קיים מספר $u$ הגדול ממנו”, וזו בוודאי טענה שנכונה במספרים הטבעיים. לעומת זאת, הפסוק השני שהבאתי, עם ה”משולש”, לא נכון במספרים הטבעיים - לא קיימים שלושה מספרים טבעיים כך שכל אחד גדול מקודמו; רק בציורים של אשר, אולי.

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

דיון רגיל בלוגיקה מתחיל בשלב הזה לדבר גם על הוכחות, אלא שלא נזדקק לכך כלל; אנחנו מתעניינים כרגע בלוגיקה בתור שיטת תיאור של אובייקטים, לא בתור שיטה למדל הוכחות באופן פורמלי. רק נעיר שיש מערכת הוכחה לשפות מסדר ראשון שמאפשרת לנו, בהינתן פסוקים קיימים, להסיק מהם פסוקים חדשים כך שכל מודל של הפסוקים המקוריים מספק גם את כל הפסוקים החדשים. אפשר להימנע מכניסה לנושא ההוכחות אם מסתפקים בתכונה הזו: אם כן, בהינתן שתי קבוצות של פסוקים $T_{1},T_{2}$ נאמר ש- $T_{1}$ גוררת לוגית את $T_{2}$ ונסמן $T_{1}\vdash T_{2}$ אם כל מודל של $T_{1}$ הוא גם מודל של $T_{2}$ .

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

אם כן, נצטמצם באופן הבא: ראשית, נדבר רק על גרפים עם $n$ צמתים. שנית, הליך ההגרלה של הגרף יהיה כזה: נעבור על כל זוג צמתים $\left(u,v\right)$ ונטיל מטבע כדי לקבוע אם תהיה בינם קשת או לא. ליצור הזה, גרף שבו כל קשת קיימת בהסתברות כלשהי, קוראים “גרף מקרי“; אסמן אותו בתור $G_{\frac{1}{2}}\left(n\right)$ , כש- $n$ מסמן שיש בו $n$ צמתים וה- $\frac{1}{2}$ הוא ההסתברות לקיום קשת (כל מה שאראה בהמשך תקף גם להסתברויות קבועות אחרות, ואפילו לחלק מההסתברויות שתלויות ב- $n$ ; לא ארחיב על כך). את השאלה אפשר כעת לנסח באופן יותר מדוייק - מה ההסתברות שהגרף המקרי $G_{\frac{1}{2}}\left(n\right)$ יהיה קשיר? כלומר, מה ההסתברות שאם נבצע את אותה הגרלת קשתות שתיארתי, מה שנקבל יהיה קשיר?

התשובה היא שההסתברות היא גבוהה מאוד, אך לא אוכל להראות זאת כרגע. לכן אסתפק בתכונה “צנועה” יותר - קיום משולש בגרף. הבה נסמן ב- $p_{n}$ את ההסתברות שאם נגריל גרף מגודל $n$ יהיה בו משולש. ברור ש- $p_{1}=p_{2}=0$ , כי לא יכול להיות משולש בגרף שיש בו רק שני צמתים; לעומת זאת $p_{3}=\frac{1}{8}$ , כי כדי שיהיה לי משולש בגרף בן שלושה צמתים צריך שכל שלוש הקשתות ביניהם יתקיימו (יש הסתברות $\frac{1}{2}$ לכל קשת, ולכן ההסתברות שכל הקשתות יהיו בגרף היא $\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{8}$ ). ומהו $p_{4}$ ? כאן החישוב כבר נעשה מסובך יותר כי יש הרבה אפשרויות, והן תלויות זו בזו; אבל די ברור שההסתברות תהיה גדולה מ- $\frac{1}{8}$ , כי יש הרבה יותר “משולשים פוטנציאליים”. אם נמשיך ונגדיל את $n$ , גם $p_{n}$ ימשיך לגדול. נשאלת השאלה - עד מתי? האם נגיע לאיזה שהוא מחסום, למשל נראה שלכל $n$ , ההסתברות $p_{n}$ היא לא יותר מחצי? או שמא היא תשאף עוד ועוד ל-1, כלומר באופן מעשי יהיה אפשר לומר “בגרפים גדולים דיו, כמעט כולם מכילים משולש”? מסתבר שהתשובה היא ש- $p_{n}$ אכן ישאף ל-1, והמשפט שאליו אני חותר מוכיח זאת בקלות.

הבה ונעבור לתכונה אחרת - “כל שני צמתים בגרף מחוברים” (לגרף כזה קוראים “קליק”, מלשון Clique). את התכונה הזו אפשר לתאר עם השפה מסדר ראשון שתיארתי קודם בקלות: $\forall v,u\left(E\left(v,u\right)\right)$ . מה ההסתברות של התכונה הזו? כאן החישוב הוא קל מאוד: בגרף עם $n$ צמתים, יש ${n \choose 2}=\frac{n\left(n-1\right)}{2}$ קשתות פוטנציאליות; מכיוון שכולן חייבות להיות בגרף, ההסתברות לכך שגרף יהיה קליק היא $\frac{1}{2^{\frac{n\left(n-1\right)}{2}}}$ . האיברים הראשונים בסדרת ההסתברויות הזו הם $1,\frac{1}{2},\frac{1}{8},\frac{1}{64},\dots$ ולא קשה לראות ש- $p_{n}$ הולך וקטן בקצב מהיר למדי ככל ש- $n$ גדל. אם כן, עבור ערכים גדולים של $n$ , $p_{n}$ יהיה אפס לכל צורך מעשי - אם נגריל גרף גדול, ההסתברות שנקבל קליק היא אפסית.

הבה ונכליל את מה שדיברנו עליו עד כה. נניח ש- $\mathcal{P}$ היא תכונה כלשהי של גרף. נסמן ב- $p\left(\mathcal{P}\right)$ את הערך שאליו ההסתברות לקיום $\mathcal{P}$ שואפת ככל שמגדילים את מספר הצמתים בגרף. פורמלית, למי שמעוניין, ההגדרה תהיה $p\left(\mathcal{P}\right)=\lim_{n\to\infty}p_{n}\left(\mathcal{P}\right)$ . ראינו כי $p\left(\mathcal{P}\right)=1$ עבור התכונה “הגרף מכיל משולש” ו- $p\left(\mathcal{P}\right)=0$ עבור התכונה “הגרף הוא קליק”. האם נוכל למצוא מקרים מעניינים יותר, שאינם 0 או 1?

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

והנה עוד תכונה טיפשית: “בגרף יש מספר זוגי של צמתים”. למה טיפשית? כי היא בכלל לא תלויה בקשתות, שזה מה שאנחנו מגרילים כאן. אם $n$ הוא זוגי, אז $p_{n}=1$ כי בכל גרף שנגריל על $n$ צמתים נקבל גרף עם מספר זוגי של צמתים, ואם $n$ אי זוגי אז $p_{n}=0$ . זה מראה לנו שאי אפשר להגיד שההסתברות “הולכת” לשום מקום - היא מזפזפת כל הזמן בין 0 ו-1, והגבול $\lim_{n\to\infty}p_{n}\left(\mathcal{P}\right)$ בכלל לא קיים; במקרה הזה אומרים ש- $p\left(\mathcal{P}\right)$ לא מוגדר.

תכונה אחת לסיום, שגם בה יש “זפזופ” שכזה אבל הוא מזיק הרבה פחות - התכונה “הגרף הוא שידוך מושלם”. שידוך מושלם הוא גרף שבו הצמתים מחולקים לזוגות-זוגות, כך שבין כל זוג יש קשת ואין עוד קשתות (תחשבו על קשת כמייצגת שני בני זוג; השידוך הוא “מושלם” למי שתומך בנישואים מונוגמיים). די ברור שבגרף עם מספר אי זוגי של צמתים נקבל שוב $p_{n}\left(\mathcal{P}\right)=0$ , כי בכל חלוקה לזוגות יישאר רווק הולל; ואילו עבור מספר זוגי של צמתים נקבל ש- $p_{n}\left(\mathcal{P}\right)$ גדול מאפס (זה תרגיל נחמד בקומבינטוריקה לחשב אותו במדוייק), אבל לא “יותר מדי”; לא קשה להראות ש- $p_{n}\left(\mathcal{P}\right)$ שואף לאפס, כאשר $n$ מקבל ערכים זוגיים. אם כן, למרות שיש “זפזופ” בין הסתברות אפס והסתברות שאינה אפס, אנחנו עדיין מקבלים $p\left(\mathcal{P}\right)=0$ .

גם את התכונה של השידוך המושלם אני יכול לתאר באמצעות השפה שלי: $\forall v\exists u\left(E\left(v,u\right)\wedge\forall w\left(E\left(v,w\right)\to u=w\right)\right)$ , כלומר “לכל צומת $v$ קיים שכן $u$ , והשכן הזה הוא יחיד, דהיינו אם גם $w$ הוא שכן של $v$ אז $u=w$ ”.

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

כעת אפשר סוף סוף לעבור לדבר על המשפט עצמו. מה שמשותף לכל התכונות שכן הצלחתי לתאר באמצעות השפה שלי הוא שההסתברות שלהן הייתה או 0, או 1. לא היה $\frac{1}{2}$ ולא היה “לא מוגדר” כמו במקרים של הגרף עם המספר זוגי של צמתים/קשתות. מה שהמשפט אומר הוא שאין זה מקרה - אם תכונה של גרפים ניתנת לתיאור באמצעות השפה מסדר ראשון שתיארתי, אז ההסתברות של התכונה קיימת, והיא או 0 או 1.

אפשר “להשתמש” במשפט בכמה דרכים. ראשית, מכיוון שהתכונה “יש בגרף מספר זוגי של צמתים” מובילה להסתברות לא מוגדרת (ובפרט לא ל-0 או 1) נובע מיידית שהתכונה הזו לא ניתנת לתיאור באמצעות לוגיקה של סדר ראשון. אם כן, אפשר להוכיח עם המשפט שתכונות מסויימות של גרפים אינן בנות-הגדרה בלוגיקה מסדר ראשון. שנית, את התכונה של “הגרף הוא שידוך מושלם” ראיתי שניתן להגדיר בלוגיקה מסדר ראשון, וגם ראיתי שעל אינסוף ערכים של $n$ מקבלים $p_{n}\left(\mathcal{P}\right)=0$ ; מכאן שבהכרח $p\left(\mathcal{P}\right)=0$ , ולכן אני יודע שההסתברות לקבלת גרף שהוא שידוך מושלם, גם כאשר מגרילים גרף על מספר זוגי של צמתים, שואפת לאפס - וזאת מבלי שהייתי צריך לחשב את ההסתברות הזו בכלל! זה “שימוש” אחר של המשפט. באופן דומה אפשר לראות שההסתברות שבגרף יהיה משולש שואפת ל-1, בלי להיכנס לחישובים מסובכים יותר מאלו שהצגתי כאן: ההסתברות היא תמיד גדולה מ- $\frac{1}{8}$ (כי בגרף עם שלושה צמתים היא $\frac{1}{8}$ , ובגרף גדול יותר היא תהיה רק גדולה יותר כי יש עוד הזדמנויות לקיום משולש), ומכיוון שנתתי נוסחה מסדר ראשון לתיאור התכונה של “בגרף יש משולש”, היא או 0 או 1, אבל 0 היא לא יכולה להיות כי היא גדולה מ- $\frac{1}{8}$ , ולכן היא 1.

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

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

gadial | שייך לנושא קומבינטוריקה, לוגיקה | 5 תגובות »

המשפט היסודי של האלגברה - הוכחה אלגברית

29 באוקטובר 2009 מאת gadial

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

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

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

הבה וננסה לנסח את המשפט בצורה פשוטה מעט יותר. ראשית, אין צורך לדבר על משוואות אלא על פולינומים, ומספיק לדבר על פולינומים מתוקנים, כלומר כאלו שבהם המקדם של החזקה הגבוהה ביותר הוא 1, כלומר משהו מהצורה $f\left(x\right)=x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$ (אם הפולינום לא מתוקן, לכפול אותו בקבוע ש”יתקן” אותו לא משנה את השורשים). אם לפולינום יש שורש, נניח $\alpha$ , אז ניתן לכתוב את הפולינום בתור $f\left(x\right)=g\left(x\right)\left(x-\alpha\right)$ כאשר $g\left(x\right)$ הוא ממעלה נמוכה יותר; לכן לטעון ש”לכל פולינום ממעלה 1 ומעלה יש שורש” שקול לטענה “לכל פולינום ממעלה $n$ יש בדיוק $n$ שורשים” כי פשוט נוכל לחלק את $f\left(x\right)$ שוב ושוב בשורשים שנגלה. שימו לב - הכוונה איננה ל- $n$ שורשים שהם בהכרח שונים זה מזה; למשל, לפולינום $x^{2}-4x+4$ יש בדיוק שורש יחיד: $x=2$ , שכן $x^{2}-4x+4=\left(x-2\right)^{2}$ . על שורש כזה אומרים שיש לו ריבוי 2; ובאופן כללי, כל פולינום ניתן לכתיבה בצורה $f\left(x\right)=\left(x-\alpha_{1}\right)^{k_{1}}\cdots\left(x-\alpha_{t}\right)^{k_{t}}$ , ועל $k_{i}$ אומרים שהוא הריבוי של השורש $\alpha_{i}$ . זה סוגר את עניין ה”בדיוק”.

מה שטרם התייחסתי אליו הוא מהם המקדמים של $f\left(x\right)$ - האם הם ממשיים, או שהם יכולים להיות גם מרוכבים? חלק ניכר מכוחו של המשפט נובע מכך שהמקדמים יכולים להיות מרוכבים - הרי את המרוכבים מכניסים מלכתחילה לתמונה כדי לפתור משוואות שאין להן פתרון במספרים ממשיים; אם כחלק מהתהליך הזה היינו יוצרים משוואות חדשות שלא ניתנות לפתרון במרוכבים, זה היה בבחינת “צעד אחד קדימה, שני צעדים אחורה”. ובכן, אנחנו רוצים להוכיח את המשפט עבור מקדמים מרוכבים, אלא שמסתבר שדי להוכיח עבור מקדמים ממשיים. הבה נניח לשניה של- $f\left(x\right)$ , שהוא פולינום במקדמים מרוכבים, אין פתרון במרוכבים; אז כך גם לפולינום $\overline{f\left(x\right)}$ שמתקבל מ- $f\left(x\right)$ על ידי הצמדת כל המקדמים. כזכור (למי שאמור לזכור), הצמדה של מספר מרוכב היא היפוך הסימן של החלק המדומה שלו, כלומר $\overline{a+bi}=a-bi$ ; בפרט, מספר מרוכב שווה לצמוד שלו אם ורק אם הוא ממשי טהור (ללא חלק מדומה).

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

כעת נכנסת האנליזה למשחק - הטענה הראשונה שלי היא שלכל פולינום ממעלה אי זוגית קיים שורש ממשי אחד לפחות. הדבר נובע ממשפט אלמנטרי באנליזה - משפט ערך הביניים: אם $f\left(x\right)$ היא פונקציה רציפה, ו- $\left[a,b\right]$ הוא קטע כלשהו, אז $f$ מקבלת כל ערך בין $f\left(a\right)$ ו- $f\left(b\right)$ . במילים - אם אנחנו מציירים פונקציה בלי להרים את העפרון מהדף, אז העפרון חייב לגעת בכל קו מאוזן שבין הגובה שממנו הוא מתחיל, לגובה שבו הוא מסיים. אין “קפיצות”.

היישום של המשפט כאן הוא פשוט למדי. כל פולינום הוא פונקציה רציפה. בגלל שהמקדם המוביל בפולינום הוא חיובי, אז ככל שמציבים בפולינום ערכים גדולים יותר ויותר, מקבלים בחזרה ערכים גדולים יותר ויותר - בפרט יש $b$ שהחל ממנו והלאה הפולינום מחזיר ערך חיובי, ולא משנה כמה קטנים שאר המקדמים. אפילו $x^{2}-10^{100^{100}}x$ יהפוך לחיובי עבור ערך גדול דיו של $x$ . להראות את זה - שוב, זו קצת אנליזה.

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

אם כן, $f\left(a\right)<0<f\left(b\right)$ - מקרה קלאסי של משפט ערך הביניים. המסקנה? יש נקודת ביניים $a<c<b$ שבה $f\left(c\right)=0$ , וזהו בדיוק שורש של הפולינום, וסיימנו במקרה זה.

אם כן, למה אנליזה היא כנראה הכרחית כאן? בנפנוף ידיים כלשהו - מכיוון שהמספרים הממשיים הם יצורים אנליטיים מעצם הגדרתם. הבה וניזכר בבניית המספרים - השלמים והרציונליים נבנו מהטבעיים באופן “אלגברי”, על ידי בנייה פשוטה וסופית (בכל פעם כל איבר חדש הורכב מזוג איברים “ישנים”, זיהוי מסויים של חלק מהאיברים החדשים כשקולים, והגדרה מחוכמת של פעולות החשבון על הזוגות). אלא שברציונליים המשפט שציטטתי למעלה על הפולינום אינו נכון - למשל, ל- $f\left(x\right)=x^{3}-2$ אין שורש רציונלי. אפשר להמשיך מכאן בשתי דרכים שונות - האחת היא לבנות באופן אלגברי שדה שמכיל את הרציונליים ובו לכל פולינום רציונלי יהיה שורש - בניה כזו אפשרית, אך היא מסובכת למדי וראויה לפוסט נפרד; התוצאה היא תת שדה של המספרים המרוכבים - “שדה המספרים האלגבריים” - שאינו מכיל יצורים כמו $\pi$ או $e$ - והשניה היא לזרום עם הבניה הקיימת של הממשיים שממילא פותרת את הבעיה. אם הולכים בגישה השניה, ואחר כך מגדירים את המרוכבים באמצעות הממשיים, אני לא רואה מנוס מהוכחת המשפט על הפולינום ממעלה אי זוגית באופן שיתייחס ישירות למהות של המספרים הממשיים; אלא שהם יצורים אנליטיים לחלוטין (המחשה טובה לכך היא ההגדרה שלהם באמצעות סדרות קושי - “סדרות מתכנסות”, שמתארות תהליך גבולי והתיאור שלהן הוא אינסופי) ולכן הוכחה אנליטית היא ככל הנראה בלתי נמנעת.

אוקיי, אז נפנוף הידיים הזה מאחורינו ואנחנו מצויידים בכל הכלים שאנחנו רוצים - נותר כעת להוכיח את המשפט היסודי באופן כללי, ובלי להשתמש עוד בטענות מאנליזה. ההוכחה תהיה, איך לא, באינדוקציה. אנחנו כבר יודעים לטפל בפולינום ממעלה אי זוגית; אם יש לנו פולינום שהמעלה שלו היא $n$ נוכל לכתוב אותה גם כ- $n=2^{k}\cdot m$ כאשר $m$ הוא אי זוגי (כלומר, $k$ אומר לנו “עד כמה $n$ זוגי”) והאינדוקציה תהיה על $k$ , כאשר הבסיס - $k=0$ - כבר טופל.

אוקיי, אז נניח כי $k\ge1$ , ונתבונן ב- $f\left(x\right)$ - הפולינום ממעלה $n$ מעל $\mathbb{R}$ שעליו אנו מדברים. אנחנו מתבססים על תוצאה בסיסית בתורת השדות - שקיים שדה הרחבה כלשהו של $\mathbb{R}$ שמכיל את כל שורשיו של $f\left(x\right)$ . זו תוצאה שטרם הראיתי ואציג אותה בעתיד; היא אינה מסובכת במיוחד אך כן דורשת כמה וכמה הסברים מוקדמים. נסמן את השורשים הללו ב- $\alpha_{1},\dots,\alpha_{n}$ (לא כולם בהכרח שונים זה מזה) ונתבונן בהרחבה של $\mathbb{R}$ שמתקבלת מהוספת כל השורשים הללו ובנוסף לכך גם $i$ , כלומר ב- $\mathbb{K=R}\left(\alpha_{1},\dots,\alpha_{n},i\right)$ . זוהי הרחבת גלואה; הסיבה לכך היא שהרחבה על ידי הוספת כל שורשיו של פולינום אי פריק (מעל שדה ממציין אפס, דוגמת $\mathbb{R}$ ) היא הרחבת גלואה, ושבהינתן מספר הרחבות גלואה של אותו שדה אז ההרחבה הקטנה ביותר שמכילה את כולן היא עצמה גלואה (הרחבה שכזו נקראת “קומפוזיטום” - איני מכיר תרגום טוב לעברית). אם כן, $K$ הוא שדה הרחבה של $\mathbb{R}$ שמכיל את $\mathbb{C}$ (כי הוא מכיל את $\mathbb{R}$ שמורחב באמצעות $i$ , וזהו בדיוק $\mathbb{C}$ ) וגם את שורשי $f\left(x\right)$ .

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

ובכן, לכל מספר ממשי $t\in\mathbb{R}$ אנחנו מגדירים פולינום $L_{t}$ באופן הבא: $L_{t}=\prod_{1\le i<j\le n}\left[x-\left(\alpha_{i}+\alpha_{j}+t\alpha_{i}\alpha_{j}\right)\right]$ . במילים - זהו פולינום ששורשיו הם בדיוק האיברים מהצורה $\alpha_{i}+\alpha_{j}+t\alpha_{i}\alpha_{j}$ לכל זוג אפשרי $\alpha_{i},\alpha_{j}$ של שורשים של $f\left(x\right)$ . הפאנץ’ הוא שלמרות שהפולינום הזה מכיל שורשים שהם יצורים די מפחידים, המקדמים שלו הם ממשיים. איך אפשר לראות את זה? באמצעות תורת גלואה - אם ניקח אוטומורפיזם כלשהו של $K/\mathbb{R}$ , תורת גלואה אומרת לנו שהאוטומורפיזם הזה מבצע בסך הכל פרמוטציה על השורשים של $f\left(x\right)$ (יותר מכך - לכל גורם אי פריק של $f\left(x\right)$ הוא מבצע פרמוטציה על השורשים של אותו גורם - אבל זה לא חשוב) כלומר, אנחנו בסך הכל “מערבבים” את השורשים $\alpha_{i},\alpha_{j}$ . אלא ש- $L_{t}$ הוא פולינום סימטרי ביחס לשורשים הללו ולכן פרמוטציה שלהם לא משנה כלום, ולכן כל אוטומורפיזם של השדה משמר את הפולינום כמות שהוא.

מבלבל? בוודאי. הנה דוגמה פשוטה לפולינום סימטרי אחר. נניח שיש לנו שלושה שורשים, $a,b,c$ , ואנחנו מסתכלים על הפולינום $\left(x-ab\right)\left(x-ac\right)\left(x-bc\right)$ . עכשיו ניקח פרמוטציה על השורשים, נניח $a\to b$ , $b\to c$ , ו- $c\to a$ . מה נקבל? את הפולינום $\left(x-bc\right)\left(x-ba\right)\left(x-ca\right)$ . אמנם, הכתיב של הפולינום הזה שונה, אבל עם קצת משחק בחוק החילוף נקבל את הפולינום המקורי שלנו. זה אותו הרעיון גם כאן.

ובכן, כל אוטומורפיזם של $K/\mathbb{R}$ משמר את $L_{t}$ , כלומר לא משנה את המקדמים שלו. מה המסקנה? מכיוון ש- $K/\mathbb{R}$ היא הרחבת גלואה, אז כל איבר שכל האוטומורפיזמים של $K/\mathbb{R}$ משמרים אותו שייך בהכרח ל- $\mathbb{R}$ . זו נקודה חשובה - אם ההרחבה לא הייתה גלואה, היא לא הייתה נכונה; איבר שהיה משתמר על ידי כל האוטומורפיזמים היה עשוי להיות שייך לשדה גדול יותר מאשר $\mathbb{R}$ , ואז לא היה יוצא לנו כלום מכל העסק. מכיוון שההרחבה כן הייתה גלואה, המסקנה היא שכל המקדמים של $L_{t}$ שייכים ל- $\mathbb{R}$ . לכן אם $L_{t}$ ממעלה כזו שמאפשרת לנו להפעיל עליו את הנחת האינדוקציה שלנו, נקבל שיש לו שורש מרוכב.

כמובן שכל ההוכחה הזו מהונדסת באופן זהיר כדי שהמעלה של $L_{t}$ תקיים את התכונה הזו. מהי? ובכן, $L_{t}$ מורכב ממכפלה של גורמים ממעלה ראשונה, כך שמעלתו שווה לכמות האיברים במכפלה, שהיא בדיוק מספר האפשרויות לבחור שני מספרים מתוך $n$ : ${n \choose 2}=\frac{n\left(n-1\right)}{2}=\frac{2^{k}m\left(2^{k}m-1\right)}{2}=2^{k-1}\left(m\left(2^{k}m-1\right)\right)=2^{k-1}m^{\prime}$ , כאשר $m^{\prime}$ הוא מספר אי זוגי. שימו לב: אנחנו לא טוענים כאן שהמעלה של $L_{t}$ היא נמוכה יותר מ- $n$ , אלא שהיא “פחות זוגית מ- $n$ ”. לכן ניתן להפעיל עליה את הנחת האינדוקציה, ולקבל של- $L_{t}$ יש שורש מרוכב.

טוב, אז סיכום ביניים: לכל $t\in\mathbb{R}$ קיימים $1\le i<j\le n$ שעבורם $\alpha_{i}+\alpha_{j}+t\alpha_{i}\alpha_{j}\in\mathbb{C}$ . מכיוון שיש מספר סופי של זוגות $i,j$ שכאלו אבל מספר אינסופי של $t\in\mathbb{R}$ שניתן לבחור, קיימים $i,j$ כך שגם $\alpha_{i}+\alpha_{j}+t\alpha_{i}\alpha_{j}\in\mathbb{C}$ וגם $\alpha_{i}+\alpha_{j}+s\alpha_{i}\alpha_{j}\in\mathbb{C}$ , עבור $t,s\in\mathbb{R}$ .

מכאן זה כבר חישוב פשוט כדי לראות כי $\alpha_{i}+\alpha_{j}\in\mathbb{C}$ וגם $\alpha_{i}\alpha_{j}\in\mathbb{C}$ ; אם נחסר את שני האיברים שלמעלה נראה כי $\left(t-s\right)\alpha_{i}\alpha_{j}\in\mathbb{C}$ ולכן ברור כי $\alpha_{i}\alpha_{j}\in\mathbb{C}$ , ולכן אם נחסר את $t\alpha_{i}\alpha_{j}$ מ- $\alpha_{i}+\alpha_{j}+t\alpha_{i}\alpha_{j}$ נקבל גם ש- $\alpha_{i}+\alpha_{j}\in\mathbb{C}$ . זה מוביל אותנו לשלב האחרון של ההוכחה, שמחזיר אותנו לבית הספר התיכון - נוסחאות וייטה.

נוסחאות וייטה (למשוואה ממעלה שנייה) אומרות שאם $\alpha_{i},\alpha_{j}$ הם השורשים של פולינום מתוקן, אז המקדמים שלו הם בדיוק $\alpha_{i}\alpha_{j}$ ו- $-\left(\alpha_{i}+\alpha_{j}\right)$ . בדיקה שלהן היא פשוטה: פשוט פותחים את הסוגריים של $\left(x-\alpha_{i}\right)\left(x-\alpha_{j}\right)$ ומקבלים $x^{2}-\left(\alpha_{i}+\alpha_{j}\right)x+\alpha_{i}\alpha_{j}$ . מסקנה? $\alpha_{i},\alpha_{j}$ הם השורשים של פולינום ממעלה שניה במקדמים מרוכבים. אבל עבור פולינום ממעלה שניה אפשר להוכיח באופן ישיר ששורשיו הם מרוכבים, פשוט באמצעות נוסחת השורשים: אם $x^{2}+bx+c$ הוא פולינום ממעלה שניה במקדמים $b,c\in\mathbb{C}$ אז $\alpha_{1,2}=\frac{-b\pm\sqrt{b^{2}-4c}}{2}$ הם השורשים שלו, אבל אלו בבירור מספרים מרוכבים כי הם התוצאה של פעולות כפל, חיבור, חילוק, חיסור והוצאת שורש ריבועי על מרוכבים. הדבר היחיד שאולי אינו ברור הוא שהוצאת שורש ריבועי של מספר מרוכב מחזירה מספר מרוכב, אבל זה נובע באופן די מיידי מהתכונות הבסיסיות של מספרים מרוכבים (שורש של המספר המרוכב $re^{i\theta}$ הוא $\sqrt{r}e^{i\frac{\theta}{2}}$ , שגם הוא מספר מרוכב).

זהו סוף ההוכחה, כי קיבלנו ש- $\alpha_{i},\alpha_{j}$ - שורשיו של $f\left(x\right)$ , כזכור - הם מרוכבים. ייתכן ששניהם הם אותו איבר, ולכן המסקנה הסופית היא שיש ל- $f\left(x\right)$ לפחות שורש מרוכב אחד, וזה בדיוק מה שרצינו.

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

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

gadial | שייך לנושא אלגברה מופשטת | 5 תגובות »

לא מדויק

עברתי דירה (וחידת פרידה)

משוואות דיופנטיות, ולמה בגללן אנחנו מתעניינים במספרים p-אדיים?

חידת מעטפות

איך לחזות את מזג האוויר בלי להסתכל בשמיים? (משפט המינימקס)

משפט הנישואים היציבים

זוג או פרד (כן, עם ד’!)

הפוסט שיודע להדפיס את עצמו

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

כלל ה-0-1 של גרפים - הקדמה

המשפט היסודי של האלגברה - הוכחה אלגברית

עמודים

ארכיונים

נושאים

כלים

בלוגרול