איך אקסיומת הבחירה הופכת אותנו ל(כמעט) יודעי כל

הנה חידה: אליס ובוב משחקים במשחק. אליס בוחרת פונקציה ממשית \( f:\mathbb{R}\to\mathbb{R} \) כלשהי. בוב בתורו בוחר איזה שהוא מספר \( x\in\mathbb{R} \), ואז אליס מגלה לו את ערכי \( f \) על כל מספר ממשי פרט ל-\( x \), דהיינו מגלה לו את הקבוצה \( \left\{ \left(y,f\left(y\right)\right)\ |\ y\ne x\right\} \). כעת בוב מנחש מהו \( f\left(x\right) \), ומצליח בהסתברות 1. איך, בשם גאוס ואוילר, בוב מצליח לעשות משהו כזה?

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

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

עם זאת, החידה הזו מתגמדת אל מול חידת המשך דומה מאוד שגם אותה אני רוצה לתאר: הפעם יש לנו 100 בובים, ולאליס יש פונקציה \( f:\mathbb{N}\to\mathbb{R} \). ראשית כל הם מתייעצים ומסכימים על אסטרטגיה, ואחר כך כל אחד מהם מוכנס לחדר עם אליס ויכול לתחקר אותה על הפונקציה של אליס כרצונו. כלומר, הוא יכול לשאול על כמה ערכים - גם מספר אינסופי שלהם - לחשוב, לשאול על עוד ערכים בהתבסס על התשובות שכבר קיבל, וכן הלאה. בסופו של דבר הוא חייב להגיד את הערך של \( f \) על קלט כלשהו שעליו הוא לא שאל. המטרה היא ש-99 מבין 100 הבובים יענו את התשובה הנכונה. לא “בהסתברות” - אבסולוטית.

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

ראשית כל, אני רוצה לציין את מה שאולי חלקכם כבר שמו אליו לב - החידה הזו דומה מאוד לחידה אחרת שהזכרתי בעבר בבלוג, אפילו כמעט זהה. החידה הוצגה כאן ונפתרה כאן והיא הולכת ככה: יש לנו אינסוף (בן מניה) של אסירים שעל הראש של כל אחד מהם יש כובע שיכול להיות שחור או לבן. כולם רואים את הכובעים של כולם למעט של עצמם. מתישהו מכים בגונג וכולם צריכים בו זמנית לומר מה צבע הכובע שיש להם על הראש, ומותר שרק מספר סופי של אסירים יטעו. באופן די מרהיב, זה ניתן לביצוע בדרך דומה מאוד לפתרון שאציג עכשיו; ההבדל העקרוני בין החידה הזו ובין החידה הנוכחית הוא שכאן מדובר על אינסוף לא בן מניה של אסירים (זה מתבטא בכך שהתחום של \( f \) הוא \( \mathbb{R} \)) ואינסוף לא בן מניה של צבעי כובעים (זה מתבטא בכך שהטווח של \( f \) הוא \( \mathbb{R} \)) ובמקום “מספר סופי של טעויות” מדברים על “הצלחה בהסתברות 1” (תכף נבין למה זה שקול), ואת החידה הזו אפשר לנסח במונחים של אליס ובוב, מה שגורם לכך שלמרות שברור לי ששתי החידות זהות ברמה העקרונית, חידת האסירים והכובעים נראית לי כמו חידה קטנה ונחמדה, ואילו החידה הנוכחית גורמת לי לתחושת “מה לכל הרוחות?!” עזה.

אז איך פותרים? הרעיון פשוט יחסית: נגדיר יחס שקילות על קבוצת כל הפונקציות הממשיות, כך ש-\( f \) שקול ל-\( g \) אם הן נבדלות רק במספר סופי של מקומות. פורמלית, \( f\sim g \) אם ורק אם \( \left|\left\{ x\in\mathbb{R}\ |\ f\left(x\right)\ne g\left(x\right)\right\} \right|<\infty \). קל לראות שזה אכן יחס שקילות (\( f \) נבדלת מעצמה על 0 מקומות; \( f \) נבדלת מ-\( g \) באותם מקומות שבהם \( g \) נבדלת מ-\( f \); אם \( f \) נבדלת מ-\( g \) ב-\( n \) מקומות ו-\( g \) נבדלת מ-\( h \) ב-\( k \) מקומות אז \( f \) נבדלת מ-\( h \) לכל היותר ב-\( n+k \) מקומות).

כל יחס שקילות משרה חלוקה למחלקות שקילות. כאן יש לנו בבירור אינסוף לא בן מניה של מחלקות שקילות (למשל, כל הפונקציות מהצורה \( f\left(x\right)=c \) כאשר \( c\in\mathbb{R} \) קבוע שייכות למחלקות שקילות שונות). אז אנחנו בוחרים נציג לכל מחלקת שקילות שכזו, אבל לשם כך אנחנו נזקקים לשימוש באקסיומת הבחירה, מה שאולי מסביר למה דברים לא אינטואיטיביים מתחילים לקרות.

בהינתן פונקציה \( f \) בואו נסמן ב-\( \left[f\right] \) את מחלקת השקילות שלה, וב-\( g_{\left[f\right]} \) את הנציגה של אותה מחלקת שקילות. כעת קל להציג את מה שבוב עושה:

• בוב מנחש מספר \( x \) באקראי ובהתפלגות אחידה מתוך הקטע \( \left[0,1\right] \) ושולח אותו אל אליס.
• בוב מקבל מאליס את כל ערכי \( f \) פרט לערך בנקודה \( x \). הוא מסתכל על פונקציה \( f^{\prime} \) שמחזירה 0 על \( x \) וזהה ל-\( f \) בכל מקום אחר, דהיינו \( f^{\prime}\left(y\right)=\begin{cases}f\left(y\right) & y\ne x\\0 & y=x\end{cases} \).
• בוב פולט את \( g_{\left[f^{\prime}\right]}\left(x\right) \), כלומר הוא בודק מה הנציג של מחלקת השקילות של \( f^{\prime} \) ואומר ש-\( f \) מחזירה על \( x \) את מה שאותו נציג מחזיר על \( x \).

עכשיו נשאר להבין למה זה מצליח בהסתברות 1. מה שלא אמרתי במפורש אבל הוא די ברור הוא ש-\( f\sim g \) כאשר \( g \) הוא הנציג שבחרנו בסוף התהליך שתיארתי בצורה מסובכת יותר מן הנדרש עם \( f^{\prime} \). למה? כי אנחנו יודעים ש-\( f^{\prime}\sim g \) שהרי כך בחרנו את \( g \) - הנציג של מחלקת השקילות של \( f^{\prime} \). כמו כן, \( f\sim f^{\prime} \) כי הם נבדלים לכל היותר על \( x \); ולכן מטרנזיטיביות נובע ש-\( f\sim g \). לכן, הסיכוי של בוב לטעות שווה לסיכוי שלו לנחש ערך של \( x \) כך ש-\( f\left(x\right)\ne g\left(x\right) \). מה הסיכוי הזה? קבוצת הנקודות שעליהן \( f,g \) לא מסכימות היא סופית, ולכן גם החיתוך שלה עם הקטע \( \left[0,1\right] \) הוא סופי. בוב בוחר מספר בהתפלגות אחידה מהקטע \( \left[0,1\right] \) ולכן ההסתברות לבחור מספר השייך לקבוצה \( A \) כלשהי שווה למידה של \( A \) ב-\( \left[0,1\right] \), אבל המידה של קבוצה סופית היא 0, כפי שכבר הראיתי בעבר בבלוג (אפשר להוכיח שהמידה שלה קטנה מכל \( \varepsilon \) על ידי כך שמכסים את כל הנקודות שלה עם קטעים שאורך כל אחד מהם \( \frac{\varepsilon}{2\left|A\right|} \) וסכום אורכי הכיסויים יהיה \( \frac{\varepsilon}{2} \)). לכן ההסתברות לבחור \( x \) שעליו \( f,g \) מסכימות הוא 1. סוף הסיפור.

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

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

זה מוזר. מאוד. ואין לי הסבר טוב שיפיס את האינטואיציה במקרה הזה. הדבר היחיד שאני יכול לומר הוא שהשלב הזה שבו בוב משתמש בערכים שאליס נתנה לו כדי “למצוא” את הנציג של מחלקת השקילות של הפונקציה הוא סוג של קסם שלא מובן מאליו שבכלל יכול לקרות. הרי אם הייתי אומר “בוב מקבל מאליס את כל ערכי \( f \) פרט לערך בנקודה \( x \) ואז פולט את \( f\left(x\right) \)” הייתם צועקים עלי שבוב ביצע פה משהו לא חוקי כי מאיפה לו לדעת מהי \( f \); אז באותה מידה אפשר לתהות מאיפה לו לדעת מהי \( g_{\left[f^{\prime}\right]} \). אבל כן, זה הסבר שמרגיש קצת קלוש, רק שאין לי טוב ממנו.

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

הדבר הראשון שחשבתי עליו הוא לקחת את הפתרון של החידה שלעיל ולנסות להשתמש בו. כאן \( f \) היא פונקציה מהטבעיים אל הממשיים, ואפשר לחשוב על פונקציה כזו בתור סדרה, אז מגדירים יחס שקילות על סדרות של ממשיים: \( \left\{ a_{n}\right\} \sim\left\{ b_{n}\right\} \) אם \( \left\{ a_{n}\right\} \) ו-\( \left\{ b_{n}\right\} \) נבדלות רק במספר סופי של איברים. כעת, מה קורה אם לוקחים את הפתרון לחידה המקורית ומנסים להשתמש בו? בוב יוכל לנחש מספר טבעי, לשאול את אליס על ערכי הסדרה ביתר המקומות, למצוא את הנציג של מחלקת השקילות של הסדרה של אליס ולענות בהתאם. הבעיה היא שהפתרון הזה הוא הסתברותי ואנחנו צריכים פתרון שעובד תמיד; וחוץ מזה, לא ברור איך לנחש מספר טבעי - אין התפלגות אחידה על כל הטבעיים - ובבירור הסתברות ההצלחה של בוב היא לא 1. בקיצור, העובדה שעכשיו ההסתברות היא על מרחב בדיד (\( \mathbb{N} \)) ולא מרחב רציף מקלקלת לנו את כל עניין ה”בהסתברות 1”. צריך גישה אחרת.

אם כן, נכניס לתמונה תעלול חדש. נמספר את הבובים מ-\( 0 \) עד 99, ולבוב מספר \( k \) נקצה את תת-הסדרה \( h_{k} \) שמוגדרת כך: \( h_{k}\left(n\right)=f\left(100n+k\right) \). במילים אחרות, \( h_{k} \) היא תת-הסדרה שמתקבלת מ-\( f \) על ידי לקיחת האיברים שבמקומות ששקולים ל-\( k \) מודולו 100. כעת נסמן ב-\( g_{k} \) את הנציג של מחלקת השקילות \( \left[h_{k}\right] \) תחת יחס השקילות שהגדרנו על הסדרות.

עכשיו, בוב מספר \( k \) יפעל כך: ראשית, הוא יבקש מאליס את הערכים של \( f \) על כל הקלטים שאינם מהצורה \( 100n+k \), כלומר הוא בעצם יקבל את הערכים של כל ה-\( h_{t} \) עבור \( t\ne k \).

שנית, לכל \( h_{t} \) שכזה, בוב מצליח באופן קסום (אקסיומת הבחירה?) להשיג את \( g_{t} \). הוא משווה את \( h_{t} \) עם \( g_{t} \) ומוצא מה האינדקס המקסימלי שבו הם לא מסכימים: \( E_{t}=\max\left\{ n\ |\ h_{t}\left(n\right)\ne g_{t}\left(n\right)\right\} \).

עכשיו בוב יודע את \( E_{t} \) של כל הבובים האחרים מלבדו. הוא מקווה שיש לו מזל ושה-\( E_{k} \) שלו עצמו לא גדול יותר מזה של כל האחרים. הפואנטה המרכזית כאן היא שעבור אחד מהבובים זה לא יהיה נכון, ולכן אותו בוב עשוי להיכשל; אבל עבור כל 99 הבובים האחרים, זה יעבוד. אם כן, בוב מספר \( k \) יחשב את \( E=\max\left\{ E_{t}\ |\ t\ne k\right\} \). בהנחה שאכן \( E_{k}\le E \), הרי ש-\( g_{k}\left(E+1\right)=h_{k}\left(E+1\right) \) ולכן בוב רק צריך למצוא את \( g_{k} \). בשביל לעשות את זה הוא צריך להכיר את \( h_{k} \) באופן כמעט מלא, אז הוא פשוט ישאל את אליס על כל ערכי \( h_{k} \) פרט ל-\( E+1 \), יחשב את \( g_{k} \) מתוך מה שהוא קיבל, ולבסוף יפלוט את \( g_{k}\left(E+1\right) \).

בבירור הפתרון עובד לכל בוב שעבורו \( E_{k} \) הוא לא המקסימלי (ולמעשה, אם \( E_{k} \) המקסימלי התקבל עבור שני בובים או יותר, אז כולם יענו נכון).

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

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