לא מדויק

ארכיון פוסטים שפורסמו בחודש יולי 2008

כיצד פרדוקס יום ההולדת מוליד חוב בבנק

שבת, 26 ביולי 2008

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

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

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

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

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

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

כמה אפשרויות יש לחלוקת $n$ כדורים ל- $k$ תאים כך שאין שני כדורים באותו התא? ראשית צריך לבחור $n$ תאים מתוך כלל ה- $k$ כדי לחלק להם את הכדורים - יש ${k\choose n}$ אפשרויות לעשות כן. אחר כך צריך להחליט באיזה סדר יוכנסו $n$ הכדורים לתאים שבחרנו - יש כאן $n!$ אפשרויות. בסה”כ נקבל שההסתברות היא ${k\choose n}\frac{n!}{k^n}$ .

ידוע כי ${k\choose n}=\frac{k!}{n!(k-n)!}$ , כך שבעצם קיבלנו הסתברות של $\frac{k!}{(k-n)!}\cdot\frac{1}{k^n}$ . את היצור הזה אפשר להציג בתור מכפלה של $n$ איברים:

$\left(\frac{k}{k}\right)\left(\frac{k-1}{k}\right)\cdots\left(\frac{k-\left(n-1\right)}{k}\right)$

ואחרי צמצום קל נקבל:

$1\cdot\left(1-\frac{1}{k}\right)\cdots\left(1-\frac{\left(n-1\right)}{k}\right)$

ובסימון פשוט קצת יותר:

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

אם מציבים $k=365, n=23$ רואים מייד שהערך שמתקבל קטן מחצי - וכזכור, הערך הזה הוא ההסתברות שלא תהיה התנגשות; כלומר, ההסתברות להתנגשות גדולה מחצי. עבור $n=22$ זה דווקא לא יקרה, ולכן 23 הוא המספר המינימלי של אנשים שצריך.

עד כאן לקוריוז החידתי, אבל את הנוסחה הכללית שקיבלנו למעלה אפשר לנתח בצורה יותר כללית מאשר סתם להציב בה ערכים - אפשר לשאול את עצמנו באופן כללי מה צריך להיות סדר הגודל של $n$ (מספר הכדורים) ביחס ל- $k$ (מספר התאים) כדי לקבל סיכוי גבוה להתנגשות. לשם כך אפשר להשתמש בקירוב שחוסם את המכפלה הזו, קירוב שמבוסס על פונקצית האקספוננט $\exp(x)=e^x$ (אלו מכם שמכירים אותה, ייתכן שכבר כשראיתם את המכפלה היא צצה לכם לראש - המכפלה מאוד מזכירה את הגבול שמגדיר את פונקצית האקספוננט).

אי השוויון שמעניין אותנו הוא $1+x\le e^x$ . הוא לא מסובך להוכחה (לא אעשה זאת) והוא מאפשר לנו לחסום כל איבר במכפלה בצורה נוחה: $\left(1-\frac{i}{k}\right)\le e^{-i/k})$ באמצעות החסם הזה אפשר להפוך את המכפלה שלעיל למכפלה של אקספוננטים - והיתרון בכך הוא שאז מקבלים אקספוננט שהמעריך שלו הוא סכום, דהיינו הפכנו את המכפלה לסכום - וסכום חשבוני, שבו אנו יודעים לטפל. מקבלים (אני משתמש ב-exp במקום ב-e בחזקת משהו כי בגישה השנייה מקבלים משהו שנראה מזעזע טיפוגרפית):

$\prod_{i=0}^{n-1}\left(1-\frac{i}{k}\right)\le\prod_{i=0}^{n-1}\exp\left(-i/k\right)=\exp\left(\frac{1}{k}\sum_{i=0}^{n-1}i\right)=\exp\left(-\frac{n\left(n-1\right)}{2k}\right)$

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

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

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

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

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

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

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

אי אפשר לזלזל בתוצאה הזו; היא מראה שלכל פונקציות התמצות יש חולשה בסיסית שלא ניתן להתגבר עליה. בשל כך, חייבים לבחור מראש את גודל התמציות כך שאפילו השורש שלו יהיה גדול מדי בשביל פריצה פרימיטיבית כמו שהצגתי. $2^{80}$ זמן זה הרבה מאוד, יותר ממה שמחשבים בימינו מסוגלים לו; $2^{40}$ זה אפשרי בהחלט. לכן גודל התמצית של פונקצית התמצות SHA-1, אולי הפונקציה הכי פופולרית בתחום זה (שכבר התגלו בה חולשות מהותיות) הוא 160 ביטים ולא משהו נמוך באופן משמעותי. לצורך השוואה - שיטת ההצפנה הסימטרית המקובלת כיום כתקן, AES, מתבססת על מפתח בגודל 128 ביטים (גם כאן החשש הוא מהתקפה שהיא פשוט ניסוי סדרתי של כל המפתחות האפשריים), והשיטה שקדמה לה, DES, השתמשה במפתחות של 56 ביטים.

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

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

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

כל אחד מהשינויים הללו הוא בלתי מורגש ולא משנה את משמעות המסמך. עם זאת, כל צירוף של שינויים נותן לי מסמך חדש. למשל, אם נשחק רק בשני הפרמטרים של “במשך/במהלך” ושל “לכל התשלומים/לכל יתר התשלומים” כבר נקבל ארבעה מסמכים שונים: אחד עם “במשך” ו-”לכל התשלומים”; אחד עם “במהלך” ו-”לכל התשלומים”; אחד עם “במשך” ו-”לכל יתר התשלומים”, והאחרון עם “במהלך” ו-”לכל יתר התשלומים”. כלומר - משני זוגות אפשריים קיבלתי 4 מסמכים; מ- $k$ זוגות שכאלו אקבל $2^k$ מסמכים. מכאן שאני רק צריך לכתוב את החוזה שלי כך שיהיו בו 80 נקודות שאפשר לבחור בכל אחת מהן בין זוג מילים, והצלחתי לייצר $2^{80}$ מסמכים שונים, שכולם אומרים את אותו הדבר בדיוק, ועל פי פרדוקס יום ההולדת כנראה שתהיה התנגשות בין התמציות שלהם. בבית המשפט אולי אפשר יהיה להתלונן שהניסוח של החוזה שאני מציג לא זהה ב-100% לחוזים אחרים שנתתי לאנשים אחרים, אבל זה משהו שאפשר לתרץ באלף ואחת סיבות אנושיות (”המחשב קרס”, “החוזה הזה נכתב על ידי עובד אחר” וכו’), ולא זה מה שיערער על הסמכות שמציעה חתימה דיגיטלית.

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

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

פרדוקס המעטפות

שישי, 25 ביולי 2008

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

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

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

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

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

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

הדרך שבה משתמשים למדוד את כדאיות ההחלפה היא תוחלת הרווח; מעין ממוצע משוקלל של הרווח/הפסד שיכול להיווצר כתוצאה מהפעולה שלכם, כשהשיקלול הוא על פי ההסתברות של המאורע. אפשר לחשוב על תוחלת בתור הרווח הממוצע שיתקבל לאחר הרבה מאוד חזרות על המשחק; כך למשל במונטי הול, תוחלת הרווח במקרה של החלפה (אם אומרים שזכייה ברכב היא רווח 1, והפסד הוא רווח 0) היא $\frac{2}{3}$ .

חישוב התוחלת במקרה שלנו קל מאוד, והנה הוא: $E=\frac{1}{2}A-\frac{1}{2}\cdot\frac{1}{2}A=\frac{1}{4}A$ .

כלומר, תוחלת הרווח במקרה של החלפה היא חיובית. לכן כדאי להחליף.

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

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

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

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

הרעיון הוא כזה: הערכים שיוכנסו למעטפות יהיו חזקות של 10. כלומר, או 10, או 100, או 1,000 וכן הלאה עד אינסוף. הזוג 10 ו-100 יוכנס בהסתברות 1/2; הזוג 100 ו-1,000 יוכנס בהסתברות 1/4, וכן הלאה. בניסוח פורמלי, ההסתברות של הזוג $(10^n,10^{n+1})$ היא $\frac{1}{2^n}$ . קל לראות שמדובר בהתפלגות חוקית (סכום ההסתברויות של כל הזוגות הוא 1). כעת נותר רק לבצע את חישוב התוחלת הישן, שעכשיו הוא מחוכם קצת יותר ואחזור עליו בשלמותו.

נניח שפתחנו את המעטפה וגילינו בפנים סכום של $10^n$ עבור איזה שהוא $n$ טבעי. ברור לנו שאנו נמצאים באחד משני מקרים - או שבמעטפה השנייה יש $10^{n+1}$ (סכום גדול פי 10) או שיש בה $10^{n-1}$ (סכום קטן פי עשר). היוצא מן הכלל היחיד הוא המקרה שבו מצאנו 10 במעטפה, ואז ברור לנו שכדאי להחליף (זה פועל לטובת הפרדוקס - זכרו, הפואנטה בסוף תהיה שתמיד כדאי להחליף).

נשים לב שהסכום $10^n$ (אם הוא לפחות 100) מוגרל בדיוק פעמיים: פעם אחת בהסתברות $\frac{1}{2^n}$ ואז הוא הסכום הקטן יותר; ופעם אחת בהסתברות $\frac{1}{2^{n-1}$ ואז הוא הסכום הגדול יותר. במילים אחרות, ההסתברות שבמעטפה השנייה יש סכום קטן פי 10 מהסכום במעטפה שלנו היא כפולה מההסתברות שבמעטפה השנייה סכום גדול יותר. אם כן, בהסתברות $\frac{1}{3}$ נרוויח מהחלפת המעטפות, ובהסתברות $\frac{2}{3}$ נפסיד.

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

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

$\frac{1}{3}\cdot 9\cdot 10^n-\frac{2}{3}\cdot 9\cdot 10^{n-1}=30\cdot 10^{n-1}-6\cdot 10^{n-1}=24\cdot 10^{n-1}$

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

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

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

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

לצורך כך, הבה נחשב בפועל את תוחלת הרווח שלנו. לשם כך עלינו לשאול את עצמנו את השאלה הבאה: נניח שאנחנו לא מחליפים; מה ההסתברות שלנו לקבל את המעטפה שהסכום שבה הוא $10^n$ ? התשובה לכך היא שקיימות שתי סיטואציות שבהן זה קורה: או שנבחר הזוג $10^n, 10^{n+1}$ בהסתברות $\frac{1}{2^n}$ ולאחר מכן בחרנו את $10^n$ מבין שתי המעטפות (בהסתברות $\frac{1}{2}$ ; או שנבחר הזוג $10^{n-1},10^n$ בהסתברות $\frac{1}{2^{n-1}}$ ולאחר מכן בחרנו את $10^n$ - שוב, בהסתברות $\frac{1}{2}$ . מכאן שההסתברות הכוללת לקבל $10^n$ היא $\frac{1}{2}\left(\frac{1}{2^n}+\frac{1}{2^{n-1}\right)=\frac{1}{2}\cdot\frac{3}{2^{n}}=\frac{3}{2^{n+1}$ . היוצא מן הכלל הוא 10, שמתקבל בהסתברות 1/4 (למה?)

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

אם כן, אפשר לפנות לחישוב התוחלת של הכסף שמקבלים בסה”כ אם בוחרים באסטרטגיית אי-החלפה. על פי הגדרה, היא שווה לסכום על כל אחת מכמויות הכסף שעשויים לקבל, מוכפלת בהסתברות שכמות הכסף הזו תתקבל. פורמלית זה יוצא $\frac{10}{4}+3\sum_{n=2}^\infty\frac{10^n}{2^{n+1}}=\frac{10}{4}+\frac{3}{2}\sum_{n=2}^\infty\left(\frac{10}{2}\right)^n$ .כאן מגיעים לפאנץ’ ליין, שהוא מה שחשוב גם אם לא עקבתם אחרי החישובים - הטור הזה בכלל לא מתכנס. הסכום שלו יעבור כל מספר טבעי אם רק נסכם מספיק איברים בו. פירוש הדבר הוא שהתוחלת היא אינסופית, כלומר שאם נשחק במשחק הרבה מאוד פעמים, הזכייה “הממוצעת” שלנו תהיה אינסוף.

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

למשל, אם למשל היינו מגדירים את החיסור של אינסוף מאינסוף כאפס, היינו אוכלים אותה בגדול כשהיינו מנסים להחיל את השיטה הזו על הפרש הטורים (שסכום כל אחד מהם אינסוף) הבאים: $\sum_{n=1}^\infty (n+1)-\sum_{n=1}^\infty n$ - ההפרש הוא מצד אחד אפס, על פי ההגדרה המטופשת שלנו ש”אינסוף פחות אינסוף הוא אפס”; ומצד שני, אם נחסר את הטורים איבר-איבר נקבל טור שסכומו עדיין אינסופי. בקיצור, בעיה.

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

למישהו יש הצעות?

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

שאלות ותשובות - מקבץ מס’ 3

שלישי, 22 ביולי 2008

די בזריזות אחרי הפוסט השני הצטברו שאלות רבות, והנה התשובות:

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

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

3) “חוק הפילוג למה עוזר” - במשפט אחד: בלי חוק הפילוג ( $a(b+c)=ab+ac$ ) לא היה שום קשר בין פעולות החיבור והכפל.

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

5) “הגדרת המספר פאי” - ההגדרה הסטנדרטית היא “היחס בין היקף המעגל לקוטרו”. כמובן שבהגדרה הזו מסתתרת ההנחה (שיש להוכיח) שהיחס הזה זהה בכל המעגלים. לכן אפשר להצטמצם למעגל ספציפי - נניח, מעגל היחידה (המעגל שאורך רדיוסו 1). יש עוד הגדרות שקולות לפאי שמתבססות על כך שהוא צץ בתחומי מתמטיקה רבים; הגדרה אפשרית אחת היא בתור שטח עיגול היחידה; הגדרה יצירתית אחרת, שבה נתקלתי בספר האנליזה המרוכבת של Ahlfors, היא כדלהלן: ראשית מגדירים את פונקצית האקספוננט (בתור הפונקציה המרוכבת שמקיימת את המשוואה הדיפרנציאלית $f^\prime(z)=f(z)$ עם תנאי ההתחלה $f(0)=1$ ) ואחר כך מוכיחים שקיים לפונקציה הזו מחזור; את המחזור המינימלי מסמנים בתור $2\pi$ .

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

7) “אופרטור העלאה בחזקה ++C”. אין כזה. יש להשתמש בפונקציה pow שנמצאת בספריה math.h. פינת הפרופגנדה: בשפות שאני אוהב (רובי ופייתון) דווקא יש אופרטור העלאה בחזקה (שעובד גם למספרים לא שלמים) - **.

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

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

10) “כל שפה ב-RE ניתנת לרדוקציה אל בעית העצירה” - כמובן; בהינתן מכונה עבור השפה M, בונים, לכל מילה x, קלט לבעיית העצירה באופן הבא: מכונה שפועלת כמו M, אך אם M עצרה ודחתה, נכנסת ללולאה אינסופית - ואם M עצרה וקיבלה, עוצרת ומקבלת; ואת המילה x. כעת, המילה x הייתה שייכת לשפה המקורית אם ורק אם הצמד של המכונה החדשה ושל x שייך לשפת בעיית העצירה.

11) “נוסחת אוילר, אלוהים” - ייתכן שהכוונה בכך היא לסיפור המפורסם על כך שאוילר, במהלך ויכוח תאולוגי, טען את הטענה הבאה: “ $\frac{a+b^n}{n}=x$ , ולכן אלוהים קיים!” ובן שיחו המסכן שלא ידע מתמטיקה לא יכל לענות. כנראה שמדובר באגדה אורבנית. הנוסחה שבטענה של אוילר אינה נוסחת אוילר המפורסמת, אבל לפעמים מקשרים גם אותה לאגדה הזו. מה שכן, יש הטוענים שנוסחת אוילר (האמיתית) גורמת להם לאמונה באלוהים. לי זה גורם בעיקר לאמונה במתמטיקה.

שייך לנושא שאלות ותשובות | 3 תגובות »

זה לא ראשוני, זה אפילו לא פריק

ראשון, 20 ביולי 2008

לגמרי במקרה נתקלתי בכתבה עתיקת יומין מ”הארץ” על אלגוריתם AKS המפורסם לבדיקת ראשוניות.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

הקרב האחרון - סכום נגד “סכום”

שבת, 19 ביולי 2008

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

זה, כמובן, לא הניסוח המתמטי המדוייק שהבאתי כאן, אבל הרעיון הבסיסי, המהותי, נמצא פה: “הפרש קטן ככל שנחפוץ“. זהו האפסילון ( $\varepsilon$ ) שהופיע בניסוח המתמטי שלי.

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

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

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

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

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

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

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

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

האם בכלר בוחר לתאר מהו סכום ללא מרכאות? לא. תחת זאת הוא ממשיך באותה מתקפה שהחל בה קודם:

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

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

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

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

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

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

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

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

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

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

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

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

שוב, הכוכב הראשי של הפסקה הוא השרירותיות האינטואיטיבית של בכלר: “איננו מסוגלים לדמיין משהו שאינו אפס ואינו סופי”. מי אמר? למה זה נכון? למה אין הבדלה בין “אינו סופי” ו”אינו ניתן לתיאור סופי”? האם איננו יכולים לדמיין את הסדרה האינסופית $a_n=n$ ? בכלר אולי התכוון כאן ל”שאיננו יכולים לצייר בראשנו את כולו בבת אחת”; ומצד שני, אולי לא. ככה זה כשאין הגדרות.

שייך לנושא הבלים פסאודו-מתמטיים, אנליזה מתמטית | 9 תגובות »

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

שישי, 18 ביולי 2008

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

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

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

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

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

הנה דרך פשוטה ונאה “לשים סימנים” כך: $f(t)=t$ . הפונקציה הזו אומרת, לכל זמן $0\le t\le 1$ איפה הייתי באותו הזמן. מכיוון ש- $t$ הוא מספר ממשי, בעזרת הסימון הקטן והקומפקטי הזה הצלחתי לבצע מספר לא בן מניה של סימונים, פשוט כי סיפקתי דרך לחשב את כולם. ב”עולם האמיתי” אין שום הכרח שהפונקציה שמתארת את התנועה תהיה ניתנת לחישוב, כמובן; אבל לעת עתה, כדי להקל על האינטואיציה, סיפקתי אותה. כעת השאלה האמיתית היא - מדוע הפונקציה הזו לא יכולה לתאר תנועה?

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

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

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

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

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

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

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

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

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

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

שייך לנושא בעיות מתמטיות מפורסמות, הבלים פסאודו-מתמטיים, אנליזה מתמטית | 10 תגובות »

הקרב נפתח ביריית חץ

רביעי, 16 ביולי 2008

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שייך לנושא בעיות מתמטיות מפורסמות, הבלים פסאודו-מתמטיים, אנליזה מתמטית | אין תגובות »

האם יש לנו ודאות לוגית שיש אינפורמציה במתמטיקה?

שני, 14 ביולי 2008

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שייך לנושא הבלים פסאודו-מתמטיים | 15 תגובות »

אין גבול לפורמליזם

שבת, 12 ביולי 2008

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

אז יש לנו סדרה, $a_1, a_2, a_3,\dots$ . אנחנו אומרים על מספר $A$ שהוא הגבול שלה אם לכל מספר ממשי חיובי $\varepsilon>0$ קיים מקום בסדרה, $N$ , כך שהחל ממנו, דהיינו לכל $n>N$ מתקיים $|a_n-A|<\varepsilon$ , ובמילים - המרחק בין האיבר $a_n$ ובין $A$ קטן מ- $\varepsilon$ . הסימון המקובל לכך הוא $\lim_{n\to\infty}a_n=A$ .

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

עוד דרך לחשוב על הגדרת הגבול היא בתור “משחק” ביני לבין איזה שהוא יריב ערמומי. אני מתחיל את המשחק בכך שאני מצהיר ש-A כלשהו הוא גבול הסדרה; כעת היריב מציב לי אתגר בדמות $\varepsilon$ (ה”עיגול” סביב הנקודה שהצהרתי עליה). כעת מחובתי לספק $N$ טבעי בתור מענה ל- $\varepsilon$ של היריב (בפרט, התשובה שלי תהיה שונה עבור ערכים שונים של $\varepsilon$ ); כעת הכדור חוזר לידיים של היריב. אם הוא מצליח למצוא נקודה כלשהי $a_n$ שמקיימת $n>N$ וגם $|a_n-A|\ge \varepsilon$ , הוא ניצח; אחרת, אני ניצחתי, ו”הוכחתי” ש- $A$ הוא אכן גבול הסדרה.

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

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

מבחינה פורמלית זה מה שקורה: נניח שיש שני גבולות, $A_1\ne A_2$ . נגדיר $\varepsilon=\frac{|A_1-A_2|}{2}$ (כלומר, אנחנו לוקחים בתור אפסילון חצי מהמרחק בין שתי הנקודות - זה מבטיח ששני ה”עיגולים” שנצייר סביבם לא ייחתכו). כעת, על פי הגדרת הגבול, קיימים $N_1,N_2$ כך שלכל $n>N_1$ מתקיים $|a_n-A_1|<\varepsilon$ ולכל $n>N_2$ מתקיים $|a_n-A_2|<\varepsilon$ . כעת אני נוקט בתעלול פשוט מאוד - מתבונן באברי הסדרה שהאינדקס שלהם גדול גם מ- $N_1$ וגם מ- $N_2$ , דהיינו בוחר $N=\max\left\{N_1,N_2\right\}$ , ולכן לכל $n>N$ מתקיים גם $|a_n-A_1|<\varepsilon$ וגם $|a_n-A_2|<\varepsilon$ .

כבר הגענו לסתירה שלנו, ורק נותר להראות זאת במפורש. ניקח אם כן $n>N$ ונראה כי $a_n$ הוא סתירתי במהותו, כי הוא נאלץ להיות בשני מקומות שונים בעת ובעונה אחת (ובמתמטיקה, בניגוד לתורת הקוונטים, זה לא קורה - אלא אם רוצים להמציא סוג חדש של מתמטיקה, ולרוב בנסיונות כאלו מקבלים מתמטיקה “ישנה” בתחפושת מסובכת). ההוכחה עצמה היא תעלול חשבוני לא מורכב מדי, שהחלק העמוק ביותר בו הוא שימוש באי שוויון המשולש, $|a+b|\le |a|+|b|$ . אי שוויון המשולש הוא התכונה החשובה והמהותית ביותר של ערך מוחלט - בלעדיו כל התורה הייתה קורסת.

אם כן, הנה החישוב:

$2\epsilon=|A_1-A_2|=|(A_1-a_n)+(a_n-A_2)|\le|A_1-a_n|+|a_n-A_2|<\varepsilon+\varepsilon=2\varepsilon$

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

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

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

אם כן, ההגדרה הפורמלית היא כדלהלן: לפונקציה $f(x)$ יש גבול $L$ בנקודה $x_0$ אם לכל $\varepsilon>0$ קיים $\delta>0$ כך שאם $0<|x-x_0|<\delta$ אז $|f(x)-L|<\varepsilon$ (שימו לב שלא דורשים שהערך של הפונקציה בנקודה $x_0$ עצמה יהיה קרוב ל- $L$ . הסימון המקובל במקרה זה הוא $\lim_{x\to x_0}f(x)=L$ .
מה זה אומר? אם בסדרות דיברנו על “כל אברי הסדרה החל ממקום מסויים”, כאן אנחנו מדברים על “כל הנקודות שקרובות ל- $x_0$ עד כדי רמה מסויימת”. הרעיונות דומים, אך הדלתא מסבך קצת יותר את ההבנה - לכן לרוב מעדיפים להתחיל מדיבורים על גבול של סדרות.

למעשה, קיים ניסוח שקול להגדרת הגבול של פונקציות שאינו משתמש בדלתא, אלא במושג הגבול הקיים של סדרה. ל- $f(x)$ יש גבול $L$ בנקודה $x_0$ אם לכל סדרת ממשיים $a_1,a_2,a_3,\dots$ ששואפת ל- $x_0$ , הסדרה $f(a_1),f(a_2),f(a_3),\dots$ שואפת אל $L$ .

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

אבל מה עוד אפשר לעשות עם מושג הגבול? להתווכח עליו, כמובן! ועל כך - בהמשך.

שייך לנושא אנליזה מתמטית | 10 תגובות »

21 סיבות לא לראות את 21

ראשון, 06 ביולי 2008

(טוב, הכותרת היא סתם. אני לא אוהב פוסטים “רשימתיים”, ואני לא בטוח שאצליח לגרד 21 סיבות)

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

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

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

זה נכון, במובן מסויים; רפסון פרסם את שיטתו ב-1690, ואילו ניוטון פרסם את הספר שלו על החשבון הדיפרנציאלי רק ב-1731. אלא מה? הספר נכתב (ככל הנראה - לא נתקלתי במקור שטוען שהוא יודע זאת ב-100%, אבל זו הטענה הרווחת) כבר בשנות השבעים של המאה ה-17 (בין 1671 ו-1677, למיטב ידיעתי), כך שניוטון אמנם המציא את השיטה קודם - או לפחות, באופן בלתי תלוי ברפסון. עם זאת, ניוטון ניסח את השיטה באופן מעט שונה מרפסון והניסוח של רפסון הוא הפשוט והמוצלח יותר, ולכן זה שנלמד כיום.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

המשוואה ברורה: חיי הזוהר 1, חיי האקדמיה 0.

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

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

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

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

ארכיון פוסטים שפורסמו בחודש יולי 2008

כיצד פרדוקס יום ההולדת מוליד חוב בבנק

פרדוקס המעטפות

שאלות ותשובות - מקבץ מס’ 3

זה לא ראשוני, זה אפילו לא פריק

הקרב האחרון - סכום נגד “סכום”

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

הקרב נפתח ביריית חץ

האם יש לנו ודאות לוגית שיש אינפורמציה במתמטיקה?

אין גבול לפורמליזם

21 סיבות לא לראות את 21

עמודים

ארכיונים

נושאים

כלים

בלוגרול