לא מדויק

למה אין מידה על כל הישר הממשי

3 במרץ, 2010

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

אסתפק כאן בדיבור על מידה על הישר הממשי – $\mathbb{R}$ – אף כי ניתן להגדיר מידה על קבוצות כלליות בהרבה. הבה ונסכם את הדרישות שלנו ממידות: אנחנו רוצים שמידה תהיה פונקציה שלכל תת קבוצה של $\mathbb{R}$ מתאימה מספר ממשי אי שלילי או "אינסוף" (שנסמן באמצעות $\infty$ ). שתי תכונות בסיסיות שאנו מצפים שמידה תקיים תוארו בפוסט הקודם: ראשית, אנו רוצים שעל קטעים המידה תתנהג באופן שמכליל את מושג האורך, כלומר ש- $\mu\left(\left[a,b\right]\right)=b-a$ . שנית, אנחנו רוצים שהמידה תהיה סיגמה-אדיטיבית, כלומר שיתקיים $\mu\left(\bigcup_{i=1}^{\infty}A_{i}\right)=\sum_{i=1}^{\infty}\mu\left(A_{i}\right)$ כאשר ה- $A_{i}$ הן קבוצות זרות – כלומר, שאם בונים קבוצה מכמה קבוצות נפרדות, אז המידה של הקבוצה תהיה סכום המידות של הרכיבים, אחרת צצות אנומליות של "השלם גדול/קטן מסך רכיביו" שלא תואמות את האינטואיציה שלנו לגבי מידה.

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

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

כעת נותרה לנו רק תכונה אחת שתהווה את המסמר האחרון בארון המתים של המידה – אינוריאנטיות להזזות. מאחורי השם המפוצץ הזה מסתתר רעיון פשוט – האורך של $\left[0,1\right]$ והאורך של $\left[1,2\right]$ זהים, אינטואיטיבית, כי אפשר להזיז את $\left[0,1\right]$ ולשים אותו על $\left[1,2\right]$ בצורה כזו שתהיה התאמה מושלמת ביניהם – כל נקודה של $\left[0,1\right]$ תתאים לנקודה של $\left[1,2\right]$ . הדגש כאן הוא על "להזיז", כי אפשר לבצע פעולות אחרות על $\left[0,1\right]$ – למשל, "למתוח" אותו עד שיתאים לקטע $\left[0,2\right]$ . האינטואיציה שלנו היא שהזזות לא אמורות לשנות את ה"אורך" של הקטע, בזמן שמתיחות דווקא כן. למי שעדיין לא משוכנע, נקודת מבט אחרת על העניין היא זו: ההבדל המהותי בין $\left[0,1\right]$ ובין $\left[1,2\right]$ הוא בסך הכל מרחקם מראשית הצירים, מרחק שנקבע באופן שרירותי למדי. אפשר באותה מידה היה להזיז את ראשית הצירים יחידה אחת שמאלה והישר הממשי עדיין היה נראה זהה, אבל הקטע $\left[0,1\right]$ היה הופך באופן קסום לקטע $\left[1,2\right]$ , ולכן גם מידתו הייתה משתנה, אם המידה לא הייתה אינוריאטית להזזות.

פורמלית, אם $A$ היא קבוצה, אז מגדירים $A+x$ כאשר $x$ הוא מספר ממשי, בתור $A+x=\left\{ a+x|a\in A\right\}$ . אינוריאנטיות להזזות פירושה ש- $\mu\left(A+x\right)=\mu\left(A\right)$ לכל $x$ וכל $A$ .

וכעת הפאנץ': לא קיימת מידה על כל תת הקבוצות של $\mathbb{R}$ שהיא גם אינוריאנטית להזזות, גם סיגמה-אדיטיבית וגם נותנת לכל קטע את אורכו. הסיבה: אם $\mu$ מקיימת אינוריאנטיות להזזות וסיגמה-אדיטיביות ומוגדרת על כל תת הקבוצות של $\mathbb{R}$ , אז אפשר להראות ש- $\mu\left(\left[0,1\right]\right)$ הוא או 0 או $\infty$ , אבל בשום פנים ואופן לא 1. ולמה? כי כפי שאראה כעת, ניתן להציג את $\left[0,1\right]$ בתור איחוד בן מניה של קבוצות שהמידה של כולן זהה. כלומר, למצוא סדרה אינסופית של $A_{i}$ -ים זרות זו לזו כך ש- $\left[0,1\right]=\bigcup_{i=1}^{\infty}A_{i}$ וכך שיש מספר ממשי כלשהו $t$ (או אינסוף) כך ש- $\mu\left(A_{i}\right)=t$ לכל $i$ . הסיגמה-אדיטיביות של המידה גוררת שבמקרה זה מתקיים $\mu\left(\left[0,1\right]\right)=\mu\left(\bigcup_{i=1}^{\infty}A_{i}\right)=\sum_{i=1}^{\infty}\mu\left(A_{i}\right)=\sum_{i=1}^{\infty}t$ , וסכום של אינסוף מחוברים זהים זה לזה שהם או חיוביים או 0 יכול להיות רק אינסוף (אם $t>0$ ) או 0 (אם $t=0$ ).

כדי להבין עד כמה ה- $A_{i}$ -ים הללו מוזרים, חשבו על האופן שבו אנו מקרבים עיגול. ראשית אנו מציירים ריבוע גדול במרכז העיגול, שקודקודיו נוגעים בשפת העיגול. כעת "מיצינו" את רוב שטח העיגול וכל מה שנותר הוא כמה פינות שלא הצלחנו להגיע אליהן. גם בתוכן אנחנו מציירים מלבנים – קטנים בהרבה מהריבוע שבמרכז – ואז שוב תפסנו את "רוב השטח" ונשארו רק עוד כמה חורים. גם בהם אנחנו מטפלים באופן דומה, וכן הלאה וכן הלאה – כלומר, בכל פעם אנחנו משפרים את הקירוב שלנו על ידי הוספת קבוצות שהן קטנות משמעותית מקודמותיהן (דהיינו, בעלות מידה קטנה יותר). ה- $A_{i}$ -ים הם סדרת קירובים שלא משתפרת אף פעם – הגודל של כל איבר בסדרה זהה, כך שה"טעות" שלנו לא באמת שואפת לאפס. במילים אחרות, אנחנו מראים שאפשר לקרב את $\left[0,1\right]$ על ידי סדרת קירובים שבכלל לא מהווה קירוב. פלא שמגיעים לסתירה?

אם כן, איך בונים את ה- $A_{i}$ -ים הללו? הבניה מעט מחוכמת (פשוט כי בניה טריוויאלית לא הייתה עובדת כאן – כפי שנראה, כדי שהבניה תעבוד הקבוצות $A_{i}$ צריכות להיות "מוזרות") אך היא אינה מורכבת מדי מבחינה טכנית, ולטעמי היא פשוט יפהפיה. הרעיון הבסיסי, כפי שניתן לשער, הוא לבנות קבוצה מיוחדת $A\subseteq\left[0,1\right]$ , ואת כל ה- $A_{i}$ לקבל כהזזות של אותה $A$ , כך שהמידות של כולן יהיו שוות למידה של $A$ . אלא שמכיוון שאנו עוסקים בנסיון לבנות את $\left[0,1\right]$ , לעבוד עם סתם הזזות יהיה בעייתי, כי הזזה של $A$ יכולה להוציא חלק מנקודות $A$ אל מחוץ ל- $\left[0,1\right]$ , ולכן נשתמש במושג טיפה שונה – "הזזה מודולו 1". הרעיון כאן הוא שאם נקודה עוברת את 1 כשמזיזים אותה, תכף ומייד מחזירים אותה דרך 0. כדי לראות זאת באופן ציורי חשבו כאילו אנו תופסים את קצוות הקטע $\left[0,1\right]$ ו"מדביקים"אותם לקבלת עיגול, וכעת מי שיוצא דרך 1 אכן נכנס תכף ומייד דרך 0. פורמלית אפשר להגדיר זאת כך: עבור $a\in\mathbb{R}$ נגדיר את "הערך השברי" של $a$ בתור "כל מה שנמצא מימין לנקודה העשרונית בפיתוח של $a$ ". למשל, אם $a=3.5$ אז הערך השברי שלו הוא $0.5$ . נהוג לסמן את הערך השברי כ- $\left\{ a\right\}$ , כלומר $\left\{ 7.31\right\} =0.31$ . עם ההגדרה הזו קל להגדיר הזזה מודלו 1: $a+x$ מודולו 1 הוא פשוט $\left\{ a+x\right\}$ . יש כאן לכאורה בעיה כי 1 עובר כך ל-0, ומי שזה ממש מפריע לו יכול לחשוב מעתה על ההוכחה כאילו היא עוסקת בקטע החצי פתוח $[0,1($ , שגם מאורכו שלו אנו מצפים שיהיה 1.

כעת נעבור להגדרת $A$ , ואת זה נעשה באמצעות יחס שקילות (מי שאינו מכיר את המושג כנראה יתקשה טיפונת להבין מה אני מקשקש בהמשך - מומלץ בחום לקרוא הסבר קודם): נגיד ש- $x$ שקול ל- $y$ אם ההפרש שלהם הוא מספר רציונלי: $x-y\in\mathbb{Q}$ . כך למשל $\pi,\pi+\frac{1}{2}$ שקולים כי הפרשם הוא $\frac{1}{2}$ הרציונלי, אבל $\pi,\frac{1}{2}$ אינם שקולים כי אם הפרשם היה רציונלי, גם $\pi$ היה רציונלי (למה?) וידוע שהוא אינו רציונלי. לא קשה לראות שזה יחס שקילות - $x-x=0$ וזה מספר רציונלי, כך ש- $x$ שקול לעצמו; ואם $x-y$ הוא רציונלי כך גם $y-x$ (מינוס של מספר רציונלי הוא רציונלי) ולכן היחס סימטרי, ואם $x-y$ רציונלי וגם $y-z$ רציונלי, כך גם $x-z=\left(x-y\right)+\left(y-z\right)$ כי סכום של רציונליים הוא רציונלי, ולכן היחס טרנזיטיבי. מכאן שאפשר לחלק את כל המספרים בקטע $\left[0,1\right]$ למחלקות שקילות זרות; ו- $A$ שלנו תוגדר בתור אוסף נציגים לכל מחלקות השקילות הללו. כלומר – לכל מחלקת שקילות של היחס שהגדרתי, $A$ תכיל בדיוק איבר אחד מאותה מחלקת שקילות.

משהגדרנו את $A$ אפשר חיש קל להגדיר את כל ה- $A_{i}$ -ים. מה שנעשה יהיה להגדיר מספור כלשהו של הרציונליים בקטע $\left[0,1\right]$ , ו- $A_{i}$ תוגדר בתור $A+q_{i}$ – בתור הקבוצה $A$ כשמזיזים את כל אבריה ברציונלי $q_{i}$ (הרציונלי ה- $i$ ברשימה) מודולו 1, כמו שתיארתי קודם. לראות שה- $A_{i}$ -ים מכסות את $\left[0,1\right]$ זה כמעט מיידי – ניקח $x\in\left[0,1\right]$ כלשהו, אז הוא שייך למחלקת שקילות כלשהי של היחס שהגדרתי קודם; ולכן קיים $y\in A$ ששקול ל- $x$ . כעת, אם $x-y=t$ ו- $t$ הוא חיובי, אז בפרט $t$ הוא רציונלי ב- $\left[0,1\right]$ (רציונלי מהגדרת יחס השקילות; ולא גדול מ-1 כי $x$ אינו גדול מ-1 ו- $y$ חיובי). לכן $t$ משתתף במניה ואנחנו תופסים את $x$ עם הקבוצה $A+t$ . המקרה ההפוך טיפה יותר מבלבל – אם $x-y$ הוא מספר שלילי אז $y-x=t$ הוא חיובי רציונלי, ואז מי שתופס את $x$ הוא דווקא $1-t$ (כלומר, $x\in A+\left(1-t\right)$ ). נסו להוכיח זאת לעצמכם כתרגיל.

מה נותר להראות? רק שהמידה של $A_{i}$ שווה למידה של $A$ . זה נובע מכך שהמידה אינוריאנטית להזזות, אבל מכיוון שיש לנו כאן הזזה מוזרה, מודולו 1, זה לא ברור מיידית. לשם כך אפשר לחשוב על $A+t$ כמורכבת מאיחוד שתי קבוצות זרות – אחת של הנקודות שכאשר מוסיפים להן $t$ לא עוברים את 1, והשניה של הנקודות שכאשר מוסיפים להן $t$ כן עוברים את $1$ , ולכן מוזזים מרחק $t$ "ימינה", אבל גם מרחק $-1$ שמאלה. כלומר, הקבוצה הראשונה מוזזת למרחק $t$ , והשניה מוזזת למרחק (השלילי) $t-1$ , אבל בשני המקרים אלו הזזות "רגילות" ולכן המידה של שתי הקבוצות הללו נשמרת, ולכן איחוד מידותיהן הוא כמידת $A$ . סיימנו.

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

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

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

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

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

למה הרציונליים הם ממידה אפס (או: הטרחן צועק ולבג צודק)

24 בפברואר, 2010

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

נתחיל קודם כל מהמתמטיקה האמיתית – ההוכחה של לבג. לשם כך צריך להבהיר קודם כל מהי מידה, על קצה המזלג. הרעיון הבסיסי שמאחורי מידה הוא הכללה של שלושה מושגים מוכרים שהם בעצם אותו הדבר בממדים שונים – אורך, שטח, ונפח. כולם מהווים מדד מסויים ל"כמות" או ל"גודל", אף שצריך להיות מאוד זהירים עם הנימוקים האינטואיטיביים הללו, כי יש להם פירושים מתמטיים אחרים שונים בתכלית (בפרט למושג ה"גודל" של קבוצות אינסופיות קיים מושג ה"עוצמה" של קנטור, וישנן דוגמאות לקבוצות שעוצמתן גדולה – לא בת מניה – אך המידה שלהן היא אפס). כדי להגדיר אורך באופן מפורש מתחילים מהגדרת אורך של אובייקט פשוט – קטע סגור $\left[a,b\right]$ כלשהו, שאורכו מוגדר פשוט בתור $b-a$ . כלומר, אורך הקטע $\left[0,1\right]$ הוא 1, כמו אורך הקטע $\left[1,2\right]$ , ואילו אורך הקטע $\left[-2,5\right]$ הוא 7, וכן הלאה. זוהי הגדרה שעליה קשה לחלוק.

בעזרת אורך של קטע אפשר להגדיר שטח של מלבן: אם אורך צלעות המלבן הוא $x,y$ בהתאמה, אז שטחו יהיה $x\cdot y$ . בדומה אפשר להגדיר נפח של תיבה באמצעות מכפלת אורכי צלעותיה. אך כל אלו הן צורות "פשוטות"- מה עם צורות מורכבות יותר?

כאן נכנסת לתמונה האינטואיציה הנוספת שלנו ביחס למידה – אם יש לנו שתי קבוצות, $A,B$ , הזרות זו לזו (אין להן נקודות משותפות), אז המידה של $A\cup B$ שווה לסכום המידות של $A,B$ . בצורה זו ניתן להגדיר מידה של קבוצה קצת יותר מתוחכמת, כמו $\left[0,1\right]\cup\left[3,5\right]$ – האורך של הקבוצה יהיה 3, סכום אורכי שני הקטעים שמרכיבים אותה. באופן דומה אפשר לטפל גם בצורות דו ממדיות ותלת ממדיות שניתן להציג כאיחוד של מלבנים ותיבות. כאן כבר נכנס קושי טכני כלשהו לתמונה – לרוב כשנתונה לנו צורה מורכבת שעדיין ניתנת לחלוקה לאיחוד סופי של מלבנים, המלבנים שבאיחוד יהיו חייבים לגעת זה בזה בשפה שלהם. זו לא בעיה אמיתית מכיוון שהמידה של השפה היא 0 (לא אוכיח זאת כאן, אבל לפחות במקרה החד ממדי זה נובע מיידית ממה שכן אוכיח, שכן השפות במקרה זה יהיו קבוצות בנות מניה של נקודות), ולכן לא אתעכב יותר מדי על נקודה זו. לתכונה שהראיתי כעת, על כך שמידה של איחוד שתי קבוצות זרות שווה לסכום המידות של הקבוצות, קוראים אדיטיביות ("חיבוריות").

אלא שאדיטיביות עדיין לא מספיקה לנו כדי לתאר קבוצות שהן מאוד טבעיות, ובראש ובראשונה עיגול. לא משנה כמה נרצה, לא נוכל לתאר עיגול כמורכב ממספר סופי של מלבנים (נימוק מהיר – השפה של כל מלבן היא קו ישר; אם העיגול יתואר ע"י מספר סופי של מלבנים, אז השפה של אחד מהם תהיה גם שפת העיגול; אבל השפה של עיגול היא אף פעם לא קו ישר). עם זאת, אפשר לקרב מצויין עיגולים על ידי מלבנים – נסו לצייר עיגול ולמלא אותו ככל יכולתכם במלבנים – התוצאה תהיה טובה למדי. למעשה, זה בדיוק הרעיון שמאחורי אינטגרל רימן – קירוב שטחים באמצעות מלבנים. אם מרשים לצייר אינסוף מלבנים, אז ניתן לקבל בדיוק את העיגול כולו, למעט שפתו (שכאמור, מידתה היא 0) – כלומר, אפשר איכשהו למלא את שטח העיגול באינסוף מלבנים כך שכל נקודה בעיגול שאיננה על השפה תוכל באחד המלבנים, וכל המלבנים יהיו זרים (למעט חפיפה בשפות שלהם). אם $A_{i}$ היא סדרת המלבנים שמקרבת את העיגול, טבעי יהיה להגדיר את שטח העיגול בתור סכום שטח כל המלבנים בסדרה, כלומר $\mu\left(\bigcup_{i=1}^{\infty}A_{i}\right)=\sum_{i=1}^{\infty}\mu\left(A_{i}\right)$ (כש- $\mu$ הוא סימון מקובל עבור מידה). סכום אינסופי איננו אובייקט בעייתי במיוחד – בחשבון האיניפינטסימלי יש לו הגדרה מדוייקת ונאה, שמתאימה לאינטואיציה שהצגנו כאן. אם כן, תכונה סבירה לדרוש ממידה באופן כללי היא שאם $A_{i}$ היא סדרה של קבוצות זרות זו לזו, אז יתקיים $\mu\left(\bigcup_{i=1}^{\infty}A_{i}\right)=\sum_{i=1}^{\infty}\mu\left(A_{i}\right)$ . לתכונה זו קוראים סיגמה-אדיטיביות (ה"סיגמה"בא לציין שמדובר באדיטיביות על קבוצה אינסופית אך בת מניה של מחוברים).

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

האבחנה הראשונה היא שאם יש לנו שתי קבוצות $A,B$ כך ש- $A\subseteq B$ , אז $\mu\left(A\right)\le\mu\left(B\right)$ . זאת מכיוון שניתן להציג את $B$ בתור איחוד זר של $A$ ושל כל אברי $B$ שאינם ב- $A$ , כלומר $\mu\left(B\right)=\mu\left(A\right)+\mu\left(B\backslash A\right)$ , ומכיוון ששני המחוברים באגף ימין אי שליליים מתקבלת התוצאה.

האבחנה השנייה היא שאם יש לנו אוסף קבוצות $A_{i}$ שאינן בהכרח זרות זו לזו, אז אמנם כבר לא ניתן לומר שהמידה של איחודן היא סכום המידות שלהן, אבל סכום המידות שלהן הוא בוודאי עדיין חסם למידה שלה: $\mu\left(\bigcup A_{i}\right)\le\sum\mu\left(A_{i}\right)$ . נסו להוכיח זאת – זה תרגיל פשוט למדי.

המסקנה משני אלו היא שאם יש לנו קבוצה $A$ , ואנחנו מצליחים איכשהו לכסות אותה באמצעות סדרת קבוצות $B_{i}$ , כלומר שיתקיים $A\subseteq\bigcup B_{i}$ , אז $\mu\left(A\right)\le\sum\mu\left(B_{i}\right)$ . לכן ככל שנצליח לכסות את $A$ על ידי $B_{i}$ עם מידה קטנה יותר, נקבל חסם טוב יותר על מידת $A$ . ועדיין, איך אפשר להשתמש בזה כדי להוכיח שמידת $A$ היא ממש אפס? האם לא צריך לשם כך לכסות את $A$ על ידי קבוצות שמידת כולן אפס? ואילו קבוצות כאלו קיימות? זכרו – כרגע כל מה שאנחנו יודעים את המידה שלו הם קטעים סגורים, אבל המידה של כל קטע סגור לא טריוויאלי גדולה מאפס. אז מה עושים?

כאן נכנס היופי של החשבון האינפיניטסימלי לתמונה במלוא כוחו. כדי להראות ש- $\mu\left(A\right)$ היא אפס, לא צריך אף פעם להראות את השוויון הזה באופן ישיר – די לנו להראות כי לכל מספר גדול מאפס $\varepsilon>0$ , מתקיים $\mu\left(A\right)\le\varepsilon$ . מכיוון שבנוסף לכך $\mu\left(A\right)\ge0$ על פי הגדרת מידה, נובע מכך שמידת $A$ , אם היא מוגדרת, חייבת להיות אפס – כי אם היא הייתה גדולה מאפס, נניח $t$ , אז עבור $\varepsilon=\frac{t}{2}>0$ לא היה מתקיים ש- $\mu\left(A\right)\le\varepsilon$ . הוכחות כאלו הן הלחם והחמאה של החשבון האינפיניטסימלי, והמחשה חזקה מאוד לאופן שבו הוא מצליח, למרות שלכאורה הוא עוסק רק בקירובים והזנחות, לתת תוצאות מדוייקות לחלוטין (כך למשל האינטגרל – מושג שכל כולו קירובים "עקומים"באמצעות מלבנים, מצליח לתת במדוייק ערכים מורכבים רבים – למשל, שטח עיגול).

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

יהי $\varepsilon>0$ כלשהו, ונתבונן במניה כלשהי של הרציונליים: $a_{1},a_{2},a_{3},\dots$ . לכל רציונלי $a_{i}$ נתאים קטע סגור $B_{i}$ שמכיל את $a_{i}$ , כך שהגדלים של ה- $B_{i}$ דועכים אקספוננציאלית. או בעברית: $B_{i}=\left[a_{i},a_{i}+\frac{\varepsilon}{2^{i}}\right]$ . על פי ההגדרה, $\mu\left(B_{i}\right)=\frac{\varepsilon}{2^{i}}$ , ועל כן קיבלנו מייד ש- $\mu\left(\mathbb{Q}\right)\le\sum_{i=1}^{\infty}\mu\left(B_{i}\right)=\sum_{i=1}^{\infty}\frac{\varepsilon}{2^{i}}=\varepsilon$ , כאשר המעבר האחרון נובע מהנוסחה הידועה לסכום של טור הנדסי מתכנס – זוהי בדיוק אותה נוסחה של פרדוקס אכילס של זנון.

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

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

אז איך כבר ניתן לתקוף את ההוכחה הפשוטה הזו?

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

אם $\varepsilon$ מושווה לאפס, הסכימה היא על אינסוף קטעים מנוונים מאורך 0, וסכום אורכיהם הוא מהצורה $\frac{1}{2}\varepsilon+\frac{1}{2^{2}}\varepsilon+\frac{1}{2^{3}}\varepsilon+\dots=0+0+0+\dots=0\cdot\infty$ . ואף אחד לא יודע מה פירושו של $0\cdot\infty$ . $0\cdot\infty$ יכול להיות שווה לכל מספר $a$ , או לאינסוף, או לאפס.

מה שכל כך יפה כאן הוא שהטרחן דווקא נוהג כמתמטיקאי טוב ומזהיר מפני הביטוי המסוכן $0\cdot\infty$ . הוא צודק לחלוטין בכך שהוא אומר שהביטוי הזה יכול להיות שווה לכל דבר – תלוי בהקשר. לרוב $\infty$ לא צץ מעצמו במערכת המספרים שלנו אלא כתוצר של תהליך גבולי כלשהו. למשל, $\lim_{x\to0}\frac{1}{x^{2}}=\infty$ . הביטוי $0\cdot\infty$ יכול לצוץ באופן טבעי, אם כך, אם אנחנו מסתכלים על הגבול של מכפלת שתי פונקציות, שאחת שואפת לאפס והשניה לאינסוף. במקרה הזה אכן לא ברור מיידית מה תהיה התוצאה, וזה תלוי מאוד בזהות הפונקציות. אלא מה? אין לזה שום קשר להוכחה של לבג.

המעבר הבעייתי הוא בין $0+0+0+\dots$ לבין $0\cdot\infty$ . אין לאינסוף שלו שום משמעות קונקרטית כאן – אם יש לנו סכום אינסופי על קבוצת איברים קבועה, זה עדיין לא אומר שהסכום הוא אינסוף כפול האיבר הקבוע של הסדרה, פשוט כי $\infty$ לא הוגדר בתור אובייקט אלגברי, אי אפשר לכפול בו וכו'. גם אם טורחים להגדיר אותו בתור אובייקט אלגברי (ועושים זאת לעתים קרובות כאשר עוסקים בתורת המידה), זה עדיין לא תקף לגבי הטור הזה, שבו אינסוף לא מייצג כמות אלא את מספר הנסכמים. הדרך הנכונה לטפל בטור הזה היא פשוט על ידי ההגדרה הבסיסית של טורים אינסופיים – מסתכלים על גבול סדרת הסכומים החלקיים. כל סכום חלקי הוא 0, ולכן גבולה של סדרת הסכומים החלקיים הוא 0, ולכן הטור הוא 0, וחסל.

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

המתקפה השניה של הטרחן על ההוכחה מעניינת הרבה יותר. במקרה זה אקצר מעט את הקשקשת. ראשית כל, הוא מתמקד רק ברציונליים שבקטע $\left[0,1\right]$ , שעליהם דיבר לבג בהוכחה המקורית (מן הסתם זה לא משנה מאום). כעת הוא אומר דבר כזה – ניקח את הקבוצה המשלימה של $\bigcup B_{i}$ ביחס לקטע $\left[0,1\right]$ – מה שנקבל הוא, לדבריו: "איחוד של קטעים עם אורך כולל של לפחות $1-\varepsilon$ ". ואז הוא מעלה את השאלה "האם ייתכן שיהיה קטע לא מנוון שאין בו מספרים רציונליים?" והתשובה לכך היא כמובן שלילית, בשל צפיפות הרציונליים. מכאן הטרחן מסיק ש"טענת לבג שהוא מסוגל לשמור את הרציונליים מחוץ לאינסוף קטעים ב- $\left[0,1\right]$ איננה אמינה". אוי ווי.

מה הבעיה כאן? שהטרחן לא זוכר דברים בסיסיים בתורת הקבוצות. הוא אמנם צודק בכך שהמשלים של $\bigcup B_{i}$ אינו יכול לכלול בתוכו קטעים כי זה יעמוד בסתירה לצפיפות הרציונליים, אבל הוא לא מבין שאין שום סיבה שהמשלים יכיל קטעים! בפרט, המשלים ממש איננו "איחוד של קטעים"- אם הולכים לפי כללי תורת הקבוצות הבסיסיים מקבלים $\overline{\bigcup B_{i}}=\bigcap\overline{B_{i}}$ , דהיינו מקבלים חיתוך אינסופי של משלימי קטעים (על משלימי קטעים אפשר לחשוב כאיחוד של קטעים). החיתוך הזה הוא שמבטיח שכל קטע אפשרי בתוך $\left[0,1\right]$ לא ישתתף ב- $\bigcap\overline{B_{i}}$ , והנימוק פשוט – ניקח קטע כלשהו, אז מצפיפות הרציונליים הוא מכיל רציונלי $a_{i}$ , כלומר $a_{i}\in B_{i}$ כלומר $a_{i}\notin\overline{B_{i}}$ , כלומר $a_{i}\notin\bigcap\overline{B_{i}}$ . כמובן שההוכחה הפורמלית הזו לא עוזרת "לראות" את הקבוצה המוזרה $\bigcap\overline{B_{i}}$ – חשבו עליה בתור הישר עם המון חורים קטנטנים בתוכו, אבל "לא יותר מדי" – אבל היא מראה שאין שום בעיה פורמלית, בניגוד למה שהטרחן סבור.

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

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

בעיית וויל האנטינג

18 בפברואר, 2010

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

ובכן, נתון גרף (ראו תמונה) ונשאלות עליו השאלות הבאות:

מצאו את מטריצת השכנויות $A$ של הגרף $G$ .
מצאו את המטריצה שנותנת את מספר המסלולים מאורך 3 ב- $G$ .
מצאו את הפונקציה היוצרת של המסלולים מ- $i$ אל $j$ .
מצאו את הפונקציה היוצרת של המסלולים מ- $1$ אל $3$ .

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

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

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

$A=\left(\begin{array}{cccc}0 & 1 & 0 & 1\\1 & 0 & 2 & 1\\0 & 2 & 0 & 0\\1 & 1 & 0 & 0\end{array}\right)$

עד כאן, שום דבר מורכב. התחכום מתחיל בשאלה הבאה – מי שלא בקיא בתורת הגרפים האלגברית (או בתחומים אחרים שבהם אותם רעיונות מופיעים, כמו למשל הילוכים מקריים בדידים) יכול לתהות מה הקשר בין מטריצה ובין מספר המסלולים ומה הולך כאן. כאן נכנסת לתמונה הפעולה של כפל מטריצות. מכיוון שמושג המטריצה, והמוטיבציה להגדרת כפל המטריצות באופן שבו הוא מוגדר, ראויים שניהם לפוסט שלם, לא אכנס לכך בינתיים אלא אניח כי ההגדרות מוכרות כבר לקורא (ועם מי שטרם יודעים הסליחה). כדי לראות כיצד כפל מטריצות עוזר לנו ניאלץ לשלוף את ההגדרה הפורמלית-טכנית של הכפל. אם נכפול את $A$ בעצמה, אז בקוארדינטה ה- $i,j$ של המכפלה נקבל את $\sum_{k=1}^{n}a_{ik}a_{kj}$ . מה המספר הזה אומר? לכל $k$ , $a_{ik}\cdot a_{kj}$ הוא מכפלה של מספר המסלולים מאורך 1 מ- $i$ ל- $k$ , במספר המסלולים מאורך 1 מ- $k$ אל $j$ . כלומר, זה מייצג את מספר הדרכים להגיע בשני צעדים מ- $i$ אל $j$ תוך מעבר בצומת הביניים $k$ . כשסוכמים זאת על כל הערכים האפשריים של $k$ מקבלים את כל הדרכים לעבור מ- $i$ אל $j$ ב-2 צעדים.

באופן דומה אם נכפול את $A^{2}$ ב- $A$ , הקוארדינטה ה- $i,j$ תהיה סכום של מכפלות, כשכל מכפלה היא של מספר הדרכים להגיע מ- $i$ אל $k$ בשני צעדים, ומ- $k$ אל $j$ בצעד אחד. אני מקווה שהרעיון ברור: לכל $m$ טבעי, הקוארדינטה ה- $i,j$ -ית במטריצה $A^{m}$ מייצגת את מספר המסלולים מאורך $m$ מ- $i$ אל $j$ (אפילו עבור $m=0$ זה עובד: $A^{0}$ היא על פי הגדרה המטריצה שבה הכניסה ה- $i,i$ היא 1 לכל $i$ , וה- $i,j$ היא 0 אם $i\ne j$ , וזה מתאים ל"מסלול מאורך 0" מ- $i$ לעצמו שפשוט לא מכיל צעדים). מכאן שכדי לענות על שאלה 2 בסך הכל צריך לחשב את $A^{3}$ . זה חישוב טכני לא מעניין במיוחד ואפשר לתת לתוכנות מחשב דוגמת מטלאב לבצע אותו. מקבלים:

$A^{3}=\left(\begin{array}{cccc}2 & 7 & 2 & 3\\7 & 2 & 12 & 7\\2 & 12 & 0 & 2\\3 & 7 & 2 & 2\end{array}\right)$

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

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

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

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

ובכן, מה שמבקשים מאיתנו הוא הצגה מפורשת לפונקציה $f\left(x\right)=\sum_{n=0}^{\infty}b_{n}x^{n}$ כאשר $b_{n}$ הוא מספר המסלולים מ- $i$ אל $j$ מאורך $n$ . אם נסמן ב- $\left[A\right]_{ij}$ את הכניסה ה- $i,j$ של המטריצה $i,j$ וננפנף בידיים ממש מהר, נקבל את החישוב הבא: $\sum_{n=0}^{\infty}b_{n}x^{n}=\sum_{n=0}^{\infty}\left[A^{n}\right]_{ij}x^{n}=\sum_{n=0}^{\infty}\left[\left(Ax\right)^{n}\right]_{ij}=\left[\sum_{n=0}^{\infty}\left(Ax\right)^{n}\right]_{ij}=\left[\frac{1}{1-Ax}\right]_{ij}$ .

מה שעשיתי כאן היה להשתמש בוריאציה על הנוסחה הישנה והטובה לסכום סדרה הנדסית אינסופית מתכנסת: $1+x+x^{2}+\dots=\frac{1}{1-x}$ . כמובן שצריך להצדיק את השימוש בה עבור מטריצות, אבל אמרתי שאנפנף בידיים.

כעת השאלה היא האם באופן כללי בהינתן מטריצה $B$ , יש נוסחה "יפה"עבור הכניסה ה- $ij$ בהופכית שלה, כלומר $\left[B^{-1}\right]_{ij}$ ? התשובה היא שכן (אם כי "יפה" זה עניין סובייקטיבי כאן) והיא מכונה "כלל קרמר". הכלל מסתמך על שני מושגים לא פשוטים – מטריצה מצורפת (Adjugate) ודטרמיננטה של מטריצה, ולכן עבור מי שאינו מכיר את המושגים הללו הנוסחה תיראה פשוט כמו אוסף של סימנים חסרי משמעות – אבל זה לא חשוב כל כך לבינתיים. הנקודה היא ששני היצורים הללו ניתנים לחישוב יחסית באופן פשוט. כעת, כלל קרמר אומר כי $B^{-1}=\frac{\mbox{Adj}B}{\det B}$ (כאן אנו מחלקים מטריצה – $\mbox{Adj}B$ – בסקלר – $\det B$ ). לכן $\left[B^{-1}\right]_{ij}=\frac{\left[AdjB\right]_{ij}}{\det B}$ . אם רוצים לפשט את הביטוי עוד יותר צריך לחפור בהגדרה של $\mbox{Adj}B$ : הכניסה ה- $ij$ של $\mbox{Adj}B$ מוגדרת בתור $\left(-1\right)^{i+j}M_{ji}$ , כאשר $M_{ji}$ הוא המינור ה- $ji$ -י של $B$ – הדטרמיננטה של המטריצה שמתקבלת ממחיקת השורה ה- $j$ והעמודה ה- $i$ של $B$ . כאן כנראה וויל משתעמם ומשתמש בסימונים שאיני מכיר, כי הנוסחה הסופית שהוא כותב על הלוח היא $\frac{\det\left(B_{ij}\right)}{\det B}$ – אני משער שכוונתו זהה לכוונה שלי (למעשה, הוא לא כותב $B$ אלא $I-Ax$ כמו שכתבתי קודם – ולמעשה, אפילו לא את זה, אלא $I-zA$ , שכמובן אומר את אותו הדבר בדיוק).

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

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

תגים: מטריצות, פונקציות יוצרות, תורת הגרפים האלגברית, דטרמיננטות
שייך לקטגוריות אלגברה לינארית, מתמטיקה בראי התקשורת, קומבינטוריקה, תורת הגרפים | 11 תגובות »

אז מהי השערת רימן?

8 בפברואר, 2010

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

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

בואו נחזור קצת אחורה בזמן, אל אוילר. אוילר התעסק עם הטור $\sum_{n=1}^{\infty}\frac{1}{n^{s}}$ . זה טור מסקרן למדי – אם $s>1$ הוא מתכנס (ואוילר הוכיח כי עבור $s=2$ סכומו הוא $\frac{\pi^{2}}{6}$ ) ואם $s\le1$ הוא מתבדר (כלומר, גדל ועוד ועוד עד לאינסוף). אבל מה שבאמת היה מעניין בטור הזה הוא דרך הצגה שונה שלו, שאוילר גילה – בתור מכפלה אינסופית: $\sum_{n=1}^{\infty}\frac{1}{n^{s}}=\prod_{p}\frac{1}{1-p^{-s}}$ , כאשר המכפלה נלקחת על כל המספרים הראשוניים $p$ . הסיבה לנכונות השוויון היא המשפט היסודי של האריתמטיקה – כל מספר $n$ ניתן להציג בצורה יחידה כמכפלת ראשוניים. על האופן המדוייק שבו השוויון מתקבל כבר הרחבתי בעבר ולא אחזור על כך – הנקודה החשובה כאן היא שהשוויון הזה הוא בעצם דרך אנליטית לתאר את התוצאה הבסיסית ביותר של תורת המספרים.

מכיוון שעבור ערכים שונים של $s$ הטור (והמכפלה) מניבים ערכים שונים, יש הגיון בדיבור על הטור הזה בתור פונקציה של $s$ ; נשתמש בסימון $\zeta\left(s\right)$ (איני בטוח אם רימן המציא את הסימון הזה או לא, וכמובן שזה לא חשוב מדי). כאמור, הפונקציה הזו לא מוגדרת בכלל עבור ערכים קטנים או שווים ל-1, ובוודאי שאינה מוגדרת עבור מספרים מרוכבים. הדבר הראשון שעשה רימן במאמרו היה לטפל בדיוק בעניין הזה – הוא הרחיב את $\zeta\left(s\right)$ לכל המספרים המרוכבים. יותר במדוייק, הוא הראה שקיימת פונקציה מרוכבת יחידה שהיא בעלת תכונות "נחמדות" (תכף אסביר) שעבור ערכים מרוכבים $s=a+bi$ שעבורם $a>1$ מקבלת את אותו הערך כמו $\sum\frac{1}{n^{s}}$ (לא קשה להראות כי לכל $s$ מרוכב שכזה הטור אכן מתכנס).

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

מה שאני בעיקר רוצה להבהיר כאן, מעבר ל" $\zeta\left(s\right)$ היא פונקציה מרוכבת יפה", הוא שלא נכון לחשוב על $\zeta\left(s\right)$ רק בתור הטור $\sum\frac{1}{n^{s}}$ ; זה בלבול נפוץ שגם אני לקיתי בו. עבור ערכי $s$ מרוכב שהחלק הממשי שלהם אינו גדול מ-1, הפונקציה מוגדרת באופן אחר, מסובך יותר; אין לנו נוסחה פשוטה ויפה עבורה (ואם הייתה כזו, הרבה בעיות היו נפתרות…). מה שכן יש, וגם את זה רימן הוכיח במאמרו, הוא מה שנקרא משוואה פונקציונלית – משוואה שבה $\zeta\left(s\right)$ מופיעה יחד עם פונקציות נוספות ומאפשרת ללמוד רבות על ההתנהגות של $\zeta\left(s\right)$ .

בצורה הידידותית ביותר שאני מכיר, אפשר לכתוב את המשוואה הפונקציונלית בתור $\zeta\left(1-s\right)=\gamma\left(s\right)\zeta\left(s\right)$ , כאשר הפונקציה $\gamma\left(s\right)$ היא פונקציה מסובכת יחסית; לצורך שלמות אכתוב אותה במפורש: $\gamma\left(s\right)=\pi^{\frac{1}{2}-s}\Gamma\left(\frac{s}{2}\right)/\Gamma\left(\frac{1-s}{2}\right)$ . גם כאן הסיפור לא נגמר כי לא הסברתי מהי $\Gamma$ ; זוהי פונקציה חשובה בפני עצמה באנליזה מרוכבת המכונה בפשטות "פונקציית גאמה" ( $\Gamma$ היא האות היוונית גאמה). לא אכנס כאן לתכונות שלה יותר מדי; רק אציין שהיא מהווה הרחבה של פונקצית העצרת (שבתורה מוגדרת רק למספרים טבעיים) לכלל המספרים המרוכבים; מתקיים $\Gamma\left(n\right)=\left(n-1\right)!$ .

מה אנחנו יכולים ללמוד מהמשוואה הפונקציונלית? בראש ובראשונה, היכן נמצאים האפסים של $\zeta\left(s\right)$ . נתחיל מכך שידוע כי פונקצית הגאמה "מתנהגת יפה" לכל ערך פרט לערכים מהצורה $-n$ , כלומר מספרים שלמים שליליים ( $-1,-2,-3,\dots$ ). על ערכים כאלו הפונקציה "מתפוצצת" – שואפת לאינסוף. מכאן ש- $\gamma\left(s\right)$ סובלת מ"התפוצצות" דומה עבור ערכים מהצורה $s=-2n$ – כלומר, מספרים שלמים שליליים זוגיים (הסיבה לכך היא ש- $\gamma$ מתפוצצת כאשר הרכיב של $\Gamma\left(\frac{s}{2}\right)$ שבתוכה מתפוצץ, כלומר כאשר $\frac{s}{2}$ הוא שלם שלילי, ולכן בהכרח $s$ הוא שלם שלילי זוגי). מכיוון שעבור $s=-2n$ מתקיים $\zeta\left(1-s\right)=\zeta\left(1+2n\right)$ ו- $\zeta\left(1+2n\right)$ הוא מספר סופי בעליל (אמרנו שהטור שמגדיר את $\zeta$ עבור $s$ -ים שהחלק הממשי שלהם הוא גדול מ-1 מתכנס בכל התחום הזה), בהכרח גם $\gamma\left(s\right)\zeta\left(s\right)$ חייב להיות סופי בעליל, ולכן $\zeta\left(s\right)$ חייב להתאפס ב- $s$ -ים הללו (אחרת שום דבר לא יאזן את ה"התפוצצות" של $\gamma$ ). מסקנה: ל- $\zeta\left(s\right)$ יש אפסים עבור כל המספרים השלמים השליליים הזוגיים. האפסים הללו מכונים "האפסים הטריוויאליים של פונקצית הזטא". מה שמעניין אותנו הוא מיהם האפסים הנותרים.

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

אוקיי, אז איפה עוד יש אפסים? אם החלק הממשי של $s$ גדול מ-1 אז $\zeta\left(s\right)$ שונה מאפס – פשוט בגלל שבתחום הזה הפונקציה מוגדרת באמצעות הטור $\sum\frac{1}{n^{s}}$ והוא מתכנס למספר שונה מאפס (אם $s$ ממשי זה מיידי לראות זאת; אחרת אפשר לקחת את הטור הזה בערך מוחלט). עכשיו, אם $s$ הוא שורש של $\zeta\left(s\right)$ אז מהמשוואה הפונקציונלית נובע שגם $1-s$ הוא שורש של $\zeta$ , אלא אם $s=-2n$ , כלומר אם הוא אחד מהאפסים הטריוויאליים הידועים לשמצה. מדוע? כי אם $\zeta\left(s\right)$ מתאפס ו- $s\ne-2n$ אז $\gamma\left(s\right)$ מתנהג "נחמד" ומכאן ש- $\gamma\left(s\right)\zeta\left(s\right)=0$ , ולכן $\zeta\left(1-s\right)=\gamma\left(s\right)\zeta\left(s\right)=0$ . מכאן נובע מייד שאם החלק הממשי של $s$ קטן מאפס והוא אינו מהצורה $-2n$ , הוא אינו יכול להיות שורש של $\zeta$ אחרת גם $1-s$ היה שורש, אבל $1-s$ הוא במקרה זה מספר שהחלק הממשי שלו גדול מ-1, וראינו שהם לא שורשים. מסקנה: האפסים של פונקצית הזטה חייבים להיות כאלו שערכם הממשי הוא בין 0 ל-1, והם מפוזרים באופן סימטרי; אם $s$ שורש, גם $1-s$ הוא שורש. קל לראות שציר הסימטריה כאן הוא הישר האנכי שעובר דרך $\frac{1}{2}$ (יותר במדוייק, ערכי ה- $x$ משוקפים דרך הישר $x=\frac{1}{2}$ ; ערכי ה- $y$ משוקפים גם הם, דרך $y=0$ ).

בקיצור, אפשר לחשוב על כל האפסים הלא טריוויאליים כאילו הם נמצאים בתוך "רצועה" (שטח אינסופי התחום בין שני קווים אופקיים) שנמתחת באופן סימטרי סביב הישר האנכי שעובר ב- $\frac{1}{2}$ . הרצועה הזו מכונה "הרצועה הקריטית", והשאלה שנשאלת היא מה רוחב הרצועה הזו; והשערת רימן אומרת שהרוחב הוא אפס, כלומר שכל השורשים של פונקציית הזטא נמצאים על הקו האנכי $Re\left(z\right)=\frac{1}{2}$ .

רימן עצמו מעלה את ההשערה הזו כמעט בדרך אגב במאמרו. בעמוד 4 שלו הוא עוסק בפונקציה שהוא מכנה $\xi\left(t\right)$ ושמוגדרת באופן מסויים באמצעות פונקצית הזטא של רימן; הוא מגדיר אותה באמצעות שינוי המשתנה $s=\frac{1}{2}+it$ , כלומר $t$ מתאר "הזזה" של $s$ מהנקודה $\frac{1}{2}$ . אם $t$ ממשי אז ההזה היא רק מעלה ומטה, כלומר ה- $s$ המתאים הוא עדיין בעל חלק ממשי $\frac{1}{2}$ ; ואפס של $\xi$ הוא אפס של $\zeta$ , כך שאפשר לנסח את השערת רימן בתור "השורשים של $\xi$ הם ממשיים", וזה בדיוק מה שרימן עושה (בתרגום חופשי שלי של התרגום לאנגלית):

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

הבה ונחזור כעת לראשוניים. רימן ניסה להעריך את הפונקציה $\pi\left(x\right)$ , שלכל $x$ טבעי מחזירה את מספר הראשוניים הקטנים ממנו. הראשונים שהעלו השערות (אמפיריות, על פי תוצאות "ניסויים" שהם ערכו) לגבי התנהגות הפונקציה הזו היו גאוס ולז'נדר, בנפרד. שניהם ניסו לתאר את הפונקציה הזו באמצעות פונקציה פשוטה יחסית; הפונקציה שהם מצאו הייתה $\frac{x}{\ln x}$ עבור לג'נדר, ופונקציה קצת יותר מורכבת שנקראת $li$ שעליה חשב גאוס. המשמעות המדוייקת של הקירובים של לג'נדר וגאוס היא שהיחס בין $\pi\left(x\right)$ והפונקציות שלהם שואף ל-1 כאשר $x$ שואף לאינסוף; אלא שהם לא הוכיחו זאת. ההוכחה חיכתה בסבלנות מאה שנים, ורק לקראת סוף המאה ה-19 הוכיחו שני מתמטיקאים – פוסן והדמר, כל אחד בנפרד – את התוצאה הזו שמכונה "משפט המספרים הראשוניים". ההוכחות שלהם עשו שימוש מהותי בפונקצית הזטא של רימן וברעיונות שרימן העלה באותו מאמר שלו, כמעט ארבעים שנה לפני כן; בפרט, צעד קריטי בהוכחה היה להראות כי לפונקצית הזטא אין שורשים עם ערך ממשי 1, כלומר אין לה אפסים על "קצוות" הרצועה הקריטית.

אם כן, האם זה סוף הסיפור? ממש לא, שכן הקירוב של משפט המספרים הראשוניים הוא קצת בעייתי. אפשר לדבר על שני סוגי קירובים – חיבורי, וכפלי. קירוב כפלי זה משהו בסגנון "הערך שאני מציע הוא לא יותר מפי 2 מהערך האמיתי"; קירוב חיבורי הוא משהו בסגנון "הערך שאני מציע לא גדול מהערך האמיתי ביותר מ-30". אני מניח שההבדל הרעיוני ברור. אם יש לי פונקציה $f\left(x\right)$ , אז $g\left(x\right)$ היא קירוב כפלי אם $\frac{f\left(x\right)}{g\left(x\right)}\le k\left(x\right)$ עבור $k\left(x\right)$ כלשהו, לכל $x$ החל ממקום מסויים; היא קירוב חיבורי אם $\left|f\left(x\right)-g\left(x\right)\right|\le k\left(x\right)$ עבור $k\left(x\right)$ כלשהו, לכל $x$ החל ממקום מסויים. משפט המספרים הראשוניים נותן קירוב כפלי, לא חיבורי.

בואו נמחיש את ההבדל בין שני סוגי הקירובים. נתבונן בפונקציה $f\left(x\right)=2^{x}+p\left(x\right)$ . כאשר $p\left(x\right)$ הוא פולינום כלשהו. ניקח לפונקציה הזו בתור קירוב את $g\left(x\right)=2^{x}$ . אז לא קשה לראות כי $\frac{f\left(x\right)}{g\left(x\right)}\to1$ כאשר $x$ שואף לאינסוף, שכן $\frac{p\left(x\right)}{g\left(x\right)}\to0$ (פולינום תמיד גדל מהותית לאט יותר מכל פונקציה אקספוננציאלית). לעומת זאת, $\left|f\left(x\right)-g\left(x\right)\right|=p\left(x\right)$ , כלומר הקירוב החיבורי יכול להיות עם שגיאה גדולה מאוד במקרה הזה, אפילו $p\left(x\right)=x^{100^{100}}$ . כלומר, קירוב כפלי טוב הוא עדיין קירוב גס יחסית; כדי לשפר את משפט המספרים הראשוניים, רוצים למצוא קירוב חיבורי טוב.

לצורך קירוב חיבורי, $\frac{x}{\ln x}$ של לג'נדר כבר אינה כל כך מוצלחת, ולכן מתמקדים בפונקציה שעליה גאוס חשב, $li$ (מלשון Logarithmic Integral) המוגדרת בתור $li\left(x\right)=\int_{2}^{x}\frac{dt}{\ln t}$ . זוהי פונקציה שדומה ל- $\frac{x}{\ln x}$ ועוד "תיקונים"; לא אכנס כאן לפרטים. כל עוד מדברים על משפט המספרים הראשוניים, אין הבדל בין $\frac{x}{\ln x}$ ובין $li\left(x\right)$ ; מתקיים גם $\frac{\pi\left(x\right)}{li\left(x\right)}\to1$ ולכן זהו אותו משפט עבור שתיהן. עבור קירוב חיבורי העניינים שונים.

אינטואיציה כלשהי לגבי שתי הפונקציות ומדוע $li$ טובה יותר ניתן לתת באמצעות נפנוף הידיים הבא: בכל איזור נתון של המספרים הטבעיים, ההסתברות שיצוץ מספר ראשוני היא בערך $\frac{1}{\ln n}$ , כש- $n$ הוא המספר הנוכחי שאנחנו בודקים. הקירוב $\pi\left(x\right)\approx\frac{x}{\ln x}$ הוא קירוב "גס" במובן זה שהוא אומר "בואו ניקח את קצה התחום שלנו, $x$ , ונניח שההסתברות עבור כל מספר בתחום שהוא ראשוני שווה להסתברות ש- $x$ עצמו ראשוני, כלומר $\frac{1}{\ln x}$ , ונחשב את מספר הראשוניים על בסיס ההנחה הזו". זו גישה מעט גסה, אבל יש מקרים שבהם היא עובדת מצויין: למשל, אם ניקח מספר טבעי אקראי (אני מנפנף בידיים אז לא ניכנס לשאלה מה זה בכלל אומר, "מספר טבעי אקראי"), ההסתברות שהוא זוגי היא $\frac{1}{2}$ , ואכן – $\frac{x}{2}$ היא הערכה טובה ל"כמות המספרים הטבעיים הזוגיים עד $x$ ". הבעיה עם $\frac{x}{\ln x}$ היא שכאן ההסתברות משתנה (וקטנה) עם הזמן, כך שלהחיל את ההערכה של $\frac{1}{\ln x}$ על כל המספרים גורם לנו לאבד משהו – אלא שכמו שמשפט המספרים הראשוניים הראה, לא מאבדים הרבה.

לעומת זאת, $li\left(x\right)$ מתחשב הרבה יותר במה שקורה באמצע – זו המשמעות של האינטגרל. הוא מבצע מעין "מיצוע" של ההסתברות לקבלת ראשוני על פני כל הישר הממשי עד $x$ (ה-2 בהתחלה מטרתו למנוע שאלות של "מתי האינטגרל מתכנס" והוא לא משנה באופן מהותי את הערך של הפונקציה). מה שחשוב להדגיש כאן הוא שגם $\frac{x}{\ln x}$ וגם $li\left(x\right)$ שתיהן פונקציות פשוטות יחסית – פשוטות להבנה ולניתוח, וגם פשוטות לחישוב, וזאת להבדיל מ- $\pi\left(x\right)$ הבלתי מושגת.

וכעת אנו מגיעים סוף סוף לקשר שבין השערת רימן וכל זה. בערך עשרים שנים לאחר הוכחת משפט המספרים הראשוניים הוכיח הלגה פון-קוך (אותו אחד מ"פתית השלג של קוך") שהשערת רימן שקולה לטענה ש- $li$ מהווה קירוב חיבורי ל- $\pi\left(x\right)$ עם גודל שגיאה שחסום על ידי $\sqrt{x}\ln x$ – גודל שקטן משמעותית מהגודל של $li$ , מה שמצביע על כך ש- $li$ היא קירוב מאוד, מאוד טוב. במובן מסויים (שלא אכנס אליו כרגע) יש קשר הדוק בין רוחב הרצועה הקריטית ואיכות הקירוב של $\pi\left(x\right)$ – ככל שהרצועה הקריטית יותר צרה, הקירוב טוב יותר (ולהפך – קירוב טוב יותר גורר שהרצועה הקריטית צרה יותר), כשהמצב האופטימלי מושג כשהרצועה הופכת להיות הקו האנכי בלבד. כלומר, השערת רימן, בניסוחה השקול, אומרת שהקירוב הטוב ביותר של $\pi\left(x\right)$ שאליו אנחנו יכולים לקוות (עם פונקציות סטייל $li\left(x\right)$ ) הוא אכן מה שאנו משיגים בפועל.

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

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

על טרחני-קנטור וטרחני-טרחני-קנטור

3 בפברואר, 2010

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

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

קנטור הוכיח שלא ניתן למנות את כל המספרים הממשיים. "מספר ממשי" לצורך העניין הוא ביטוי מהצורה $0.a_{1}a_{2}a_{3}\dots$ כשה- $a_{i}$ -ים הם ספרות בין 0 ל-9, וסדרת הספרות נמשכת עוד ועוד עד אין קץ (למשל $0.3$ ניתן לכתיבה כ- $0.3000\dots$ ). כמובן שיש עוד מספרים ממשיים פרט למספרים הללו (כאלו שבהם משמאל לנקודה העשרונית יש משהו שאיננו אפס) אך אם נראה כי כבר את המספרים שהצגתי לא ניתן למנות, בוודאי שלא ניתן למנות את כולם. "למנות" פירושו להתאים מספר טבעי ייחודי לכל אחד מהמספרים בתחום (כלומר, לשני מספרים שונים בתחום יותאמו שני מספרים טבעיים שונים).

הדרך שבה קנטור מוכיח זאת היא גאונית בפשטותה. קנטור מניח בשלילה שקיימת מניה לכל המספרים הממשיים מהצורה הזו ואז בונה מספר ממשי "חדש" שניתן להוכיח שהמניה לא מצליחה לתפוס. כדי לראות איך בונים את המספר הזה, נסמן את המספר הראשון במניה של קנטור בתור $0.a_{1}^{1}a_{2}^{1}a_{3}^{1}\dots$ , את המספר השני בתור $0.a_{1}^{2}a_{2}^{2}a_{3}^{2}\dots$ וכן הלאה – כלומר, $a_{i}^{k}$ פירושו "הספרה ה- $i$ -ית במספר ה- $k$ -י במניה". קצת מבלבל, אך הכרחי לתעלול של קנטור. כעת נגדיר ספרה $b_{i}$ באופן הבא: אם $a_{i}^{i}=1$ , אז $b_{i}=0$ ; ואם $a_{i}^{i}\ne1$ אז $b_{i}=1$ . במילים אחרות, בנינו את $b_{i}$ כדי להיות שונה מהספרה ה- $i$ של המספר ה- $i$ במניה של הממשיים. כעת המספר של קנטור הוא $0.b_{1}b_{2}b_{3}\dots$ . במילים אחרות, קנטור בנה את המספר כך שהספרה ה- $i$ שלו תהיה שונה מהספרה ה- $i$ של המספר ה- $i$ במניה, ולכן הוא אינו יכול להיות המספר ה- $i$ במניה – לאף $i$ ! מכאן שהמספר החדש אינו במניה, וסוף הסיפור (אני מרמה כאן באופן קל למדי – יכולה להיווצר בעיה מכך שמספר שנגמר בסדרה אינסופית של $9$ שקול למספר שנגמר ב-1 ואחריו אינסוף אפסים – אבל אפשר לעקוף את הבעיה הזו בקלות וזה לא פרט שאני רוצה להיכנס אליו כאן). הסיבה שלשיטה הזו קוראים "שיטת האלכסון" היא שאפשר לחשוב על המספרים כאילו הם מסודרים בטבלה, שבה האיבר בשורה ה- $i$ והעמודה ה- $j$ הוא $a_{j}^{i}$ , ואז המספר שנבנה, נבנה באופן כזה שהוא יהיה "הפוך" לאלכסון של הטבלה.

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

כי גם רציונליים אפשר לכתוב כפיתוח עשרוני, כמו הממשיים; אבל לעומת הממשיים, קיימת הוכחה (של קנטור עצמו) שהרציונליים כן בני מניה. אם כן, איך ההוכחה של קנטור מתפרקת? ובכן, המספר של קנטור, אותו $0.b_{1}b_{2}b_{3}\dots$ , לא בהכרח יהיה רציונלי בעצמו, כך שלא נגיע לשום סתירה (הסתירה נובעת מכך שבנינו מספר חדש שהיה אמור להשתתף במניה אך בשל אופן בנייתו ברור כי אינו משתתף בה). זה מעלה את השאלה – מה מבדיל מספר רציונלי מאי-רציונלי, בכל הנוגע לפיתוח העשרוני? והתשובה פשוטה – מספר הוא רציונלי אם ורק אם הפיתוח שלו הופך למחזורי החל משלב מסויים – כלומר, צצה איזו סדרת ספרות סופית כך שאת כל המספר מכאן ואילך ניתן לתאר כחזרה אינסוף פעמים על אותו רצף ספרות (למשל, $0.43223325000\dots$ הוא רציונלי כי הוא מסתיים בסדרת אפסים אינסופית. וגם $0.12345678901234567890\dots$ הוא רציונלי כי הוא מורכב מאינסוף חזרות על רצף הספרות $1234567890$ ). אין שום סיבה להניח שהמספר $0.b_{1}b_{2}b_{3}\dots$ שבנינו אכן יקיים את תכונת המחזוריות הזו.

יפה, אומר הטרחן – אם כן, הבה ונהנדס את הבניה של קנטור כך שמספר קנטור כן יקיים את תכונת המחזוריות. ליתר דיוק, נגרום לכך שבאלכסון יצוץ מספר רציונלי, ואז גם כשניקח את "ההפך" ממנו (שזה מה שעושים כשבונים את $0.b_{1}b_{2}b_{3}\dots$ ) נקבל מספר רציונלי (קל למדי להוכיח זאת – נסו!)

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

איך זה עובד פורמלית? הוא מגדיר "מספר $n$ -מודולרי", לכל $n$ טבעי, בתור מספר $0.a_{1}a_{2}a_{3}\dots$ שהספרה במקום ה- $n$ -י שלו (כלומר $a_{n}$ ) היא בדיוק $n\mbox{ mod 10}$ (כלומר, הספרה הימנית ביותר של $n$ – למשל, אם $n=123$ אז הספרה היא $3$ ). מספר $1$ -מודולרי לדוגמה הוא $0.14345\dots$ . מספר $2$ -מודולרי לדוגמה הוא $0.3241\dots$ וכן הלאה. העיקרון ברור. עכשיו, אם לכל $n$ , בשורה ה- $n$ -ית יהיה מספר $n$ -מודולרי, זה יסיים את ההוכחה של הטרחן: המספר שיווצר באלכסון אכן יהיה רציונלי, וזו תהיה הוכחה לכך שהרציונליים אינם בני מניה (כי אנו מניחים שכל הרציונליים מהצורה $0.a_{1}a_{2}a_{3}\dots$ משתתפים במניה).

אז איך הטרחן מבטיח שבשורה ה- $n$ -ית יהיה מספר $n$ -מודולרי? פשוט מאוד – כאמור, הוא אומר שנסדר את הטבלה מחדש. כאן העניינים מסתבכים. בסעיף 2-9 במאמר שלו, הוא מציע את ה"פרמוטציה" הבאה של הטבלה, שמוגדרת באופן אלגוריתמי כך: מתחילים מטבלת קנטור כלשהי עבור הרציונליים. כעת, עבור השורה ה- $i$ (החל מ- $i=1$ וכן הלאה), אם המספר בשורה $i$ הוא $i$ -מודולרי עוזבים אותו בשקט. אחרת, מחליפים אותו עם אחת מהשורות שנמצאות אחרי $i$ , שהיא כן $i$ מודולרית. בפסקה הבאה, 2-10, הטרחן טוען ש"זה מיידי להוכיח שכל שורה של הטבלה הופכת להיות מודולרית כתוצאה מהפרמוטציה", ואני מסכים איתו לחלוטין: התוצר של האלגוריתם הוא טבלה שבה לכל $n$ , השורה ה- $n$ היא $n$ -מודולרית. אם כן, איפה נפלה הטעות? זה תרגיל חביב (אם כי לא קשה במיוחד) ואני ממליץ לכם לחשוב עליו קצת בעצמכם לפני שניגש לעניין.

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

We will see now a conflictive consequence of this immense and suspicious asymmetry.

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

ובכן, מהי הבעיה עם הבניה? כבר רמזתי על כך קודם: הטרחן טוען שהוא הגדיר "פרמוטציה", אבל התוצר של הבניה שלו איננו פרמוטציה, אלא טבלה "מסוננת", שחסרות בה שורות. דרך פשוטה לראות זאת היא כך: מצד אחד, הטרחן טוען שאחרי שהבניה שלו מסתיימת, כל שורה בטבלה היא $n$ -מודולרית. אלא שקל מאוד לבנות מספרים שאינם $n$ -מודולריים, לאף $n$ ! למשל, $0.0123\dots$ הוא כזה (הספרה במקום מס' 1 היא 0; הספרה במקום מס' 2 היא 1 וכן הלאה). אם כן, לאן המספרים הללו "הולכים" כשמסדרים מחדש את הטבלה? הם פשוט נעלמים ויוצאים ממנה.

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

צריך להבהיר שהעובדה שהבניה היא אינסופית לא מונעת מאיתנו לדבר על האובייקט שהוא התוצר ה"סופי" של הבניה, אפילו מבחינה חישובית: בכל פעם שבה אנו רוצים לדעת מה קורה בשורה ה- $i$ של התוצר הסופי, אנחנו פשוט "מריצים את הבניה" מספיק זמן עד שהיא מסיימת את העבודה על השורה ה- $i$ , ואז מובטח לנו שהשורה ה- $i$ הזו לעולם לא תשתנה שוב – ומכאן שאנחנו יכולים לקרוא את השורה ה- $i$ מתוך הטבלה החצי-מוגמרת, וזה יהיה זהה לחלוטין לסיטואציה שבה אנו קוראים את השורה ה- $i$ מתוך התוצר המוגמר של הבניה. זו דוגמה אחת מני רבות לאובייקטים שנוצרים על ידי תהליך אינסופי, ומוגדרים בתור "גבול" של התהליך הזה – הדוגמאות המפורסמות ביותר הן של פרקטלים, דוגמת קבוצת קנטור, ועקומת פאנו, הראויים לפוסטים בפני עצמם. מה שחשוב לי להדגיש כאן הוא שמדובר בבניה מתמטית לגיטימית – "מותר" לטרחן להגדיר את התהליך שהוא הגדיר ולדבר על התוצרים שלו; הוא פשוט לא יכול להעמיד פנים שהתוצר הוא פרמוטציה. הוא לא, בלי קשר לקנטור או מספרים אי רציונליים או לכל דבר אחר – מספיקה ההבחנה שכל מספר שאיננו $n$ -מודולרי לאף $n$ לא מופיע בתוצר, למרות שהוא יכל להופיע במקור. לכן אין זה מפתיע שאחרי ה"סידור מחדש" הזה של הטבלה יהיו מספרים רציונליים שאינם מופיעים בה. למעשה, הטענה של הטרחן הופכת לטריוויאלית – ה- $0.b_{1}b_{2}b_{3}\dots$ ("היפוך" האלכסון) שנבנה מהטבלה אחרי הסידור מחדש שלה הוא מספר שבבירור איננו $n$ מודולרי לאף $n$ (למה?) ולכן מן הסתם הוא לא יופיע בטבלה, שהרי "סיננו" מהטבלה את כל המספרים שאינם $n$ -מודולריים לאף $n$ !

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

Cantor's diagonal argument and all its formal consequences should be suspended until it is proved the impossibility of defining a rational antidiagonal in all possible reorderings of T's rows.

לא פחות – יש "להשעות" את האלכסון של קנטור עד שיוכיחו לטרחן שאי אפשר לעשות את מה שהוא מנסה לעשות. בדומה יש להשעות את הטענה ש- $0.999\dots=1$ ואת כל המסקנות ממנה עד שיוכח שאין דרך לחשב את הגבול שמגדיר את $0.999\dots$ באופן שבו לא יצא 1, ויש להשעות את המשפט היסודי של האריתמטיקה עד שלא יוכח שאין דרך לכתוב מספר כשתי מכפלות שונות מהותית של ראשוניים, וכו' וכו'. יומרנות כזו היא סימן היכר מובהק של טרחנים, שמנסים לבטל בהבל פיהם את כל המתמטיקה כי משהו לא מסתדר להם בראש.

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

Why not? Because the construction of the re-ordering is invalid… The re-ordering is, itself, self-contradictory.

Here's the problem: you're constructing a chosen rational number. That is, you know what rational number you're re-ordering the rows to create. Since it's a rational, it's got to be in the table. And since you know what rational it is, you've got to know what row in the table it's going to be. So go look at that row.

By the definition of the diagonalization, the value of the diagonal must be different from the value of any of the rows by at least one digit. So the rational number that you're forming must be different from itself by at least one digit.

Bzzt. No good. The re-ordered rational diagonalization is self-contradictory. In fact, it's a classic self-referential foulup.

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

אבל זה בדיוק מה שהטרחן ניסה להוכיח!

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

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

כל זה לא היה מרגיז כל כך, אלמלא עיקר ההתקפה של GMBM על טרחני-קנטור הייתה שהם לא טורחים להתייחס לגופה של ההוכחה של קנטור:

You see, 99 times out of 100, Cantor cranks claim to have some construction that generates a perfect one-to-one mapping between the natural numbers and the reals, and that therefore, Cantor must have been wrong. But they never address Cantors proof. Cantors proof shows how, given any purported mapping from the natural numbers to the real, you can construct at example of a real number which isn't in the map. By ignoring that, the cranks' arguments fail: Cantor's method still generates a counterexample to their mappings. You can't defeat Cantor's proof without actually addressing it.

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

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

הגופים האפלטוניים, נוסחת אוילר לפאונים, וכדורגל

31 בינואר, 2010

כשאומרים "נוסחת אוילר", לרוב מתכוונים לנוסחה $e^{\pi i}+1=0$ , או לניסוח הכללי שלה, $e^{i\theta}=\cos\theta+i\sin\theta$ . לעתים רחוקות יותר מדברים על הנוסחה $V-E+F=2$ , וקצת חבל, כי זוהי נוסחה יפה כמעט באותה מידה – נוסחה שמצביעה על גישה שונה שנקט אוילר ביחס לבעיות שעסקו בהן כבר היוונים הקדמונים, ומצביעה על תובנה שחמקה מעיני המתמטיקה במשך אלפיים שנים לערך – ונוסחה שממחישה איך אוילר היה אבי הטופולוגיה. אז מהי הנוסחה ומה היא אומרת? ניסוח נפוץ בימינו של הנוסחה עוסק בגרפים מישוריים, אך במקור אוילר דיבר על פאונים קמורים, ולכן צריך ראשית כל להציג אותם.

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

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

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

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

במובן מסויים אלו הן הצורות התלת-ממדיות הסימטריות ביותר האפשריות. מייד נשאלת השאלה – מי הן, ואיך הן נראות?

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

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

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

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

הגישה של אוילר היא די טבעית במובן מסויים: פאון הוא גוף תלת ממדי, שבנוי מגופים דו ממדיים (המצולעים שמהווים פאות). נקודת המפגש בין כל שני גופים דו ממדיים שכאלו היא יצור חד-ממדי (הצלעות) והמפגש בין כל שני יצורים חד-ממדיים הוא יצור אפס-ממדי (קודקוד). הרעיון של אוילר היה לא להתעלם מאף מימד, והתוצאה הייתה רווחית ביותר. אם נסמן את מספר הקודקודים של הפאון ב- $V$ , את מספר הצלעות ב- $E$ ואת מספר הפאות ב- $F$ , אז מה שאוילר שם לב אליו הוא שמתקיים, לכל פאון שהוא בדק, ש- $V-E+F=2$ . בויכוח על האם המתמטיקה מתגלית או מומצאת, זו דוגמה נאה במיוחד לקשר שבין שני המושגים: אין ספק שהנוסחה הזו התגלתה על ידי אוילר, ואפילו באמצעות חקירה אמפירית; אבל הרעיון לספור בנפרד את הפאות, הצלעות והקודקודים הוא ללא ספק המצאה של אוילר. מרגע שהומצאה הטרמינולוגיה הנכונה והיה ברור "איפה צריך להסתכל", נחשף לאוויר העולם הקשר שהיה קיים תמיד והיה צריך לגלות.

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

עלינו לשאול את עצמו מה מאפיין גוף אפלטוני. ברור שמאפיין אחד הוא סוג המצולע שמשמש בתור פאה – זה חייב להיות מצולע משוכלל, אבל אנחנו יכולים לשחק עם מספר הצלעות שלו, שנסמן $n$ . עבור הטטרהדרון $n=3$ ; עבור הקוביה $n=4$ ; עבור הדודקהדרון, $n=5$ ; אבל עבור האוקטהדרון והאיקוסהדרון גם כן מתקיים $n=3$ , כך שברור שזהות המצולע עצמו לא קובעת באופן יחיד את הגוף האפלטוני. צריך קריטריון נוסף.

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

וכאן נכנסת נוסחת אוילר לתמונה, יחד עם מספר טיעונים קומבינטוריים פשוטים. הבה ונקבע זוג $\left(n,k\right)$ וננסה להבין מה נובע מכך על $V,E,F$ . ראשית, כל פאה תורמת $n$ צלעות לקבוצת הצלעות של הפאון, אך צריך לשים לב לכך שכל צלע נספרת פעמיים שכן כל צלע נמצאת על שתי פאות שונות (צלע, כזכור, היא איזור מפגש בין שתי פאות). לכן מתקיים הקשר $E=\frac{nF}{2}$ . כמו כן, כל פאה תורמת $n$ קודקודים לקבוצת הקודקודים של הפאון (זכרו – מספר הצלעות והקודקודים של מצולע הוא זהה – למה?), אבל כל קודקוד נספר $k$ פעמים באופן הזה. לכן מתקיים הקשר $V=\frac{nF}{k}$ . אם נציב את הערכים הללו בנוסחת אוילר נקבל $\frac{nF}{k}-\frac{nF}{2}+F=2$ , כלומר $F\left(\frac{n}{k}-\frac{n}{2}+1\right)=2$ , כלומר $F\left(\frac{2n-kn+2k}{2k}\right)=2$ , כלומר $F=\frac{4k}{2n-kn+2k}$ .

עכשיו, $F$ הוא מספר טבעי, שערכו לפחות 3 (כי בפאון לא יכולות להיות רק שתי פאות – כדי שהוא יהיה סגור יהיה הכרחי "לעקם" את הפאות לשם כך). לכן הצטמצמנו לשאלה עבור אילו ערכים טבעיים של $n,k$ , המספר $\frac{4k}{2n-kn+2k}$ הוא מספר שלם גדול מ-3. זו דוגמה קלאסית למשוואה דיופנטית, אך לא משוואה קשה במיוחד, אף שהיא עשויה להיראות מעט מפחיד בהתחלה. האינטואיציה היא ש- $kn$ גדל מהר מאוד ביחס לשני האיברים האחרים במכנה, שאפשר לכתוב בקיצור $2\left(n+k\right)$ ; ואם $-kn$ שבמכנה גדול מדי, נקבל מספר שלילי והמשחק נגמר. יותר מכך, אנחנו יודעים שמתקיים $n,k\ge3$ בגלל המשמעות הגאומטרית שלהם – $k$ הוא מספר הפאות שנפגשות בכל קודקוד, ובכל קודקוד חייבות להיפגש לפחות שלוש פאות (למה? שוב, שיקולים גאומטריים), ו- $n$ הוא מספר הצלעות של כל פאה, ולמצולע חייבות להיות לפחות שלוש צלעות (למה? שוב, שיקולים גאומטריים). לכן חיפוש ממצה על מרחב כל הפתרונות הסבירים יהיה עניין קצר מאוד.

נתחיל מבדיקת כל הערכים האפשריים של $n$ אם $k=3$ : במקרה זה נקבל $F=\frac{12}{2n-3n+6}=\frac{12}{6-n}$ . ברור מהמשוואה הזו שהערכים הלגיטימיים היחידים של $n$ הם $3,4,5$ ; ( $2$ לא לגיטימי כי $n\ge3$ ). אם $k=4$ נקבל $F=\frac{16}{8-2n}$ ולכן הערך הלגיטימי היחיד של $n$ הוא $3$ ; ואם $k=5$ נקבל $F=\frac{20}{10-3n}$ וגם כאן $n$ יכול להיות רק 3; ואילו עבור $k=6$ נקבל כבר $F=\frac{24}{12-4n}$ ועבור $n\ge3$ נקבל מספר לא חיובי במכנה, וכך יקרה גם לכל ערך גדול יותר של $k$ . סוף המשחק.

לסיכום, קיבלנו שהזוגות האפשריים היחידים הם $\left(3,3\right),\left(4,3\right),\left(5,3\right),\left(3,4\right),\left(3,5\right)$ , והם מגדירים בדיוק את הגופים האפלטוניים – זה משחק פשוט וחביב לבדוק איזה זוג מגדיר כל גוף ומה $F$ עבורו.

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

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

למעשה, אפשר לחשוב על נוסחת אוילר בתור מקרה פרטי של מאפיין כללי של משטחים. אפשר לשאול את עצמנו באופן כללי מהו $V-E+F$ עבור משטח (שיש בו מושג של קודקודים, צלעות ופאות…), גם כזה שאיננו של פאון קמור. התוצאה שנקבל לא תהיה בהכרח 2, אבל היא תהיה זהה לכל זוג משטחים שהם הומיאומורפיים – כלומר, שקולים מבחינה טופולוגית (להגדרה המדוייקת לא אכנס כעת). כלומר, קיבלנו אינוריאנטה של משטחים – וזה אחד מהדברים המרכזיים שהעוסקים בטופולוגיה מחפשים, שכן אינוריאנטות שכאלו עוזרות לסווג מרחבים טופולוגיים. בעיה קשה ומרכזית בטופולוגיה היא הבעיה הבאה: בהינתן שני מרחבים טופולוגיים, יש לקבוע האם הם אינם הומיאומורפיים. אין לבעיה פתרונות פשוטים, ושיטת הפתרון הנפוצה היא לחפש אינוריאנטה שיש לאחד מהמרחבים ולשני אין. לאינוריאנטה שעולה ממשפט אוילר קוראים מאפיין אוילר.

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

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

עוד כמה דברים על מספרים p-אדיים

24 בינואר, 2010

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

נתחיל מהנורמה ה-p-אדית. כזכור, הגדרנו אותה על מספרים טבעיים באופן הבא: $\|a\|_{p}=\frac{1}{p^{\mbox{ord}_{p}\left(a\right)}}$ כאשר $\mbox{ord}_{p}\left(a\right)$ הוגדר להיות החזקה הגבוהה ביותר של $p$ שמחלקת את $a$ (למשל $\mbox{ord}_{3}\left(54\right)=3$ כי $3^{3}$ מחלק את 54 אבל לא $3^{4}$ ). ההרחבה שלה למספרים רציונליים (ואחר כך לגבולות של סדרות של מספרים רציונליים) מתבצעת באופן "טבעי" כדי לשמור על התכונות הרצויות של נורמה (כפליות ורציפות). כזכור, אחת הדרישות שלנו מנורמה הייתה קיום סוג של אי שוויון המשולש: $\|a+b\|_{p}\le\|a\|_{p}+\|b\|_{p}$ . מסתבר שהנורמה ה-p-אדית מקיימת תכונה זו בצורה חזקה למדי. החשבון די פשוט: אם $p^{n}$ מחלק את $a$ ו- $p^{m}$ מחלק את $b$ , ונניח ש- $n<m$ , אז $p^{n}$ מחלק את $a+b$ , ולכן $\|a+b\|_{p}\le\frac{1}{p^{n}}$ (ייתכן שאת $a+b$ מחלקת חזקה גדולה יותר של $p$ , אבל אז הנורמה תהיה קטנה יותר מ- $\frac{1}{p^{n}}$ ). באופן כללי ניתן לתאר את האבחנה הזו כך: $\|a+b\|_{p}\le\max\left\{ \|a\|_{p},\|b\|_{p}\right\}$ . כלומר, הנורמה של סכום אינה יכולה להיות גדולה יותר מכל אחת מהנורמות של המחוברים (הסבירו לעצמכם מדוע תכונה זו גוררת מייד את אי שוויון המשולש "הרגיל"). לנורמות שמקיימות תכונה זו קוראים "נורמות לא ארכימדיות". זה תרגיל לא קשה במיוחד להראות גם כשמרחיבים את הנורמה על כל הרציונליים התכונה הזו נשמרת.

כזכור, השתמשנו בנורמות כדי להגדיר מטריקות – פונקציות מרחק, באופן הבא: $d\left(a,b\right)=\|a-b\|$ . בלשון מטריקות, תכונת הלא-ארכימדיות מתורגמת באופן הבא: לכל $x,y$ ו"נקודת ביניים" $z$ מתקיים $d\left(x,y\right)\le\max\left\{ d\left(x,z\right),d\left(z,y\right)\right\}$ . במילים אחרות – אם פעם כל מה שאמרנו הוא שהדרך הישירה מ- $x$ אל $y$ היא יותר קצרה מכל טיול שעובר בנקודת ביניים $z$ , עכשיו אנחנו אומרים שהיא יותר קצרה אפילו מ"חצי טיול" שכזה! (כמובן שזה לא תיאור מדויק של מה שהולך שם). ההשלכה הראשונה של התכונה הזו היא שכל משולש בעולם שלנו הוא שווה שוקיים: נניח ש- $a,b,c$ הן שלוש נקודות במרחב. אם $d\left(a,b\right)=d\left(a,c\right)$ אז המשולש שהן קודקודיו הוא שווה שוקיים על פי הגדרה; לכן נניח ש- $d\left(a,b\right)\ne d\left(a,c\right)$ ובפרט, בלי הגבלת הכלליות, אפשר להניח ש- $d\left(a,b\right)>d\left(a,c\right)$ כעת, מהי $d\left(b,c\right)$ ? אנו יודעים כי $d\left(b,c\right)\le\max\left\{ d\left(a,b\right),d\left(a,c\right)\right\} =d\left(a,b\right)$ . מצד שני, $d\left(a,b\right)\le\max\left\{ d\left(a,c\right),d\left(b,c\right)\right\}$ , ומכיוון שידוע לנו שלא מתקיים $d\left(a,b\right)\le d\left(a,c\right)$ אז בהכרח $d\left(a,b\right)\le d\left(b,c\right)$ . קיבלנו שכל אחד מהמספרים הללו קטן או שווה מהשני ולכן $d\left(a,b\right)=d\left(b,c\right)$ – משולש שווה שוקיים.

בואו נעבור לתופעה משעשעת נוספת: ניקח נקודה $a$ ומרחק $r\in\mathbb{R}$ כלשהו, ונתבונן בקבוצה $B\left(a,r\right)=\left\{ x|d\left(a,b\right)<r\right\}$ – לקבוצה הזו קוראים "הכדור הפתוח ברדיוס $r$ סביב $a$ " כעת בואו ניקח נקודה $b\in B\left(a,r\right)$ כלשהי ונתבונן בכדור הפתוח ברדיוס $r$ סביבה. את מה הוא מכיל? אם $x\in B\left(a,r\right)$ אז $d\left(a,x\right)<r$ . מצד שני, $d\left(b,x\right)\le\max\left\{ d\left(a,x\right),d\left(a,b\right)\right\} <r$ (כי שני האיברים שעליהם נלקח המקסימום קטנים מ- $r$ ) ולכן $x\in B\left(b,r\right)$ , כלומר $B\left(a,r\right)\subseteq B\left(b,r\right)$ . מאותו שיקול בדיוק $B\left(b,r\right)\subseteq B\left(a,r\right)$ , ולכן $B\left(a,r\right)=B\left(b,r\right)$ . מסקנה: לכל כדור פתוח מתקיימת התכונה שכל נקודה בתוכו יכולה לשמש בתור ה"מרכז" שלו!

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

ובכן, במספרים p-אדיים מה שטוב מכדי להיות אמיתי הוא אמיתי. הסיבה לכך היא פשוטה ביותר – שוב, תכונת הלא-ארכימדיות של הנורמה ה-p-אדית. אם אנו לוקחים שני סכומים חלקיים של הטור $\sum a_{n}$ , נאמר $S_{n}=\sum_{i=1}^{n}a_{i}$ ו- $S_{m}=\sum_{i=1}^{m}a_{i}$ כש- $n>m$ , אז מקבלים שגודל ההפרש ביניהם מקיים $\|S_{n}-S_{m}\|_{p}=\|a_{m+1}+\dots+a_{n}\|_{p}\le\max\left\{ \|a_{m+1}\|_{p},\dots,\|a_{n}\|_{p}\right\}$ , ומכאן הוכחה שסדרת הסכומים החלקיים היא סדרת קושי היא תרגיל סטנדרטי בחדו"א.

נעבור כעת לתיאור של המספרים ה-p-אדיים שהוא שונה מהתיאורים שנתתי עד כה ונותן ככל הנראה את האינטואיציה הטובה ביותר לגבי האופן שבו הם "נראים" ואיך שחשבון מבוצע בהם. לפני כן, הבה נזכר איך כותבים מספרים ממשיים "רגילים": כשאנו כותבים מספר כמו 123 בבסיס עשרוני, אנו מתכוונים למספר $1\cdot10^{2}+2\cdot10^{1}+3\cdot10^{0}$ . כלומר, יש לנו סכום של חזקות של 10, כשהמקדם של כל חזקה הוא ספרה של המספר שלנו. ספרות שאחרי הנקודה מציינות חזקות שליליות: כך למשל 10.1 הוא המספר $1\cdot10^{1}+0\cdot10^{0}+1\cdot10^{-1}$ . מספר ממשי יכול להיכתב כשיש אינסוף ספרות מימין לנקודה; כך למשל $0.333\dots$ מייצג את המספר $3\cdot10^{-1}+3\cdot10^{-2}+\dots$ , שניתן גם לכתוב באופן מקוצר בתור $\sum_{n=1}^{\infty}\frac{3}{10^{n}}$ , וחישוב שמשתמש בנוסחת הסכום של טור הנדסי יראה כי זהו אכן המספר $\frac{1}{3}$ הישן והטוב. בדומה מקבלים גם כי $0.999\dots$ הוא בעצם 1.

נחזור למספרים p-אדיים. כזכור, ההגדרה ה"אלגברית" שלי עבור שלמים p-אדיים הייתה בתור סדרה $a_{1},a_{2},\dots$ של מספרים טבעיים כך ש- $a_{n+1}\equiv a_{n}\left(\mbox{mod }p^{n}\right)$ . מבחינה אינטואיטיבית נכון לחשוב על זה בתור "סדרת קירובים" למספר, כמו ש- $1,1.4,1.41,1.414,\dots$ היא סדרת קירובים לשורש הממשי של 2. ניתן להראות (באופן מעט טכני אבל ממש לא מסובך) שעבור כל שלם p-אדי $\alpha$ ניתן לבחור סדרה "קנונית" שדומה לסדרת הקירובים של שורש מבחינת גדלי האיברים בה – האיבר $a_{n}$ יהיה מספר טבעי ששקול ל- $\alpha$ מודולו $p^{n}$ בטווח $0,\dots,p^{n}-1$ . אנו רוצים לומר משהו בסגנון " $a_{n+1}$ הוא כמו $a_{n}$ רק עם ספרה אחת נוספת"; כדי שזה יעבוד, צריך להציג את המספרים לא בבסיס 10 אלא בבסיס $p$ . כלומר, כותבים $a_{n}=b_{0}\cdot p^{0}+b_{1}\cdot p^{1}+\dots+b_{n-1}p^{n-1}$ כשכל "ספרה" $b_{i}$ היא מספר בין $0$ ל- $p-1$ ; ומכיוון ש- $a_{n+1}\equiv a_{n}\left(\mbox{mod }p^{n}\right)$ נובע חיש קל ש- $a_{n+1}=b_{0}p^{0}+\dots+b_{n-1}p^{n-1}+b_{n}p^{n}$ כך ש- $b_{0},\dots,b_{n-1}$ זהים לאלו שהיו ב- $a_{n}$ , ו- $b_{n}$ היא "הספרה החדשה". כעת אפשר לייצג את $\alpha$ באופן הבא: $\alpha=b_{0}p^{0}+b_{1}p^{1}+\dots$ , כלומר על ידי סדרת הספרות האינסופית $b_{0},b_{1},\dots$ .

דוגמה פשוטה: המספר "שבע עשרה" יוצג בבסיס $p$ כאשר $p=7$ בתור $23$ (כי הוא שווה ל- $2\cdot7^{1}+3\cdot7^{0}$ ). במקרה הזה הסדרה שלנו היא $b_{0}=3,b_{1}=2,b_{2}=0,\dots$ וכן הלאה – כל הספרות החל מה-2 הן אפס ולכן לא כותבים אותן במפורש. לכל מספר טבעי זה יקרה – החל ממקום מסויים כל הספרות יהיו אפס ובינתיים לא קרה שום דבר מעניין.

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

איך עובד חשבון במספרים p-אדיים? בדיוק כמו חשבון "רגיל" – ספרה ספרה. כך למשל $\dots111+\dots111=\dots222$ . לדוגמה יותר מעניינת הבה נניח ש- $p=3$ ונתבונן במכפלה $\dots1112\cdot2$ . אם נכפול את שני המספרים בשיטת בית הספר נגלה שהתבנית קבועה – כפול של $2$ ב- $2$ נותן $4$ , ומאחר ואנו בבסיס $p=3$ אז התוצאה היא הספרה $1$ ועוד יתרה של $1$ שאותה "מעבירים הלאה" למכפלה הבאה; ומכאן ואילך נקבל $2\cdot1+1=3$ , שמתורגם לספרה 0 ועוד יתרה של 1, ואותה יתרה תביא לכך שגם בהכפלת $2$ ב- $1$ הבא בתור נקבל ספרה 0 ויתרה 1, וכו' וכו' עד אינסוף – היתרה "נדחקת לאינסוף" עד שהיא "נעלמת" ואנו מקבלים שתוצאת הכפל היא $1$ (או יותר מדוייק, $\dots0001$ ). במילים אחרות, $\dots1112$ הוא ההופכי של $2$ בחוג השלמים ה-3-אדיים – האיבר המקביל לחצי בשדה המספרים הרציונליים ה"רגילים" (תרגיל למתקדמים: להראות ש- $\dots1112$ אכן זהה למספר $\frac{1}{2}$ , כשבונים את ה-3-אדיים באמצעות סדרות קושי של מספרים רציונליים – כלומר, שהסדרה הקבועה $\frac{1}{2},\frac{1}{2},\dots$ והסדרה שמגדירה את $\dots1112$ מתכנסות לאותו גבול – או במילים אחרות, ההפרש ביניהן שואף לאפס).

עד כה דיברתי על שלמים p-אדיים (וכפי שראינו, מכיוון שגם חצי הוא שלם 3-אדי, המילה "שלם" כאן היא במובן רחב יותר מזה ה"רגיל"). מספרים p-אדיים כלליים ניתנים לתיאור בתור $p^{n}\varepsilon$ כאשר $\varepsilon$ הוא שלם p-אדי הפיך, ומכך נובע שההצגה ה"כללית" של מספרים p-אדיים היא בתור ביטוי בבסיס $p$ שיכול להכיל אינסוף ספרות משמאל לנקודה, אבל רק מספר סופי מימין לה. למשל $\dots1112.12121$ . שימו לב להיפוך – במספרים ממשיים אינסוף הספרות היו מימין לנקודה. שוב, ההבדל נובע מכך שבמספרים ממשיים, הספרות שמימין לנקודה ייצגו מספרים שהגודל שלהם (הנורמה שלהם) הלך וקטן; במספרים p-אדיים הגודל הולך וקטן דווקא כשהולכים שמאלה.

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

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

מספרים p-אדיים – בניה "אנליטית"

12 בינואר, 2010

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

הבניה השניה היא של קנטור. קנטור מסתמך על כך שקיים ברציונליים מושג של מרחק. המרחק בין $a,b$ מוגדר בתור $d\left(a,b\right)=\left|a-b\right|$ , ומרגע שיש לנו פונקצית מרחק שכזו אפשר להגדיר באמצעותה את המושג של סדרת קושי – סדרה שהמרחק בין איבריה הולך וקטן לאפס, ובניסוח מתמטי פורמלי, לכל $\varepsilon>0$ קיים מקום בסדרה, $N$ , כך שלכל $n,m>N$ מתקיים $d\left(a_{n},a_{m}\right)<\varepsilon$ . האינטואיציה שמאחורי ההגדרה היא שכל סדרה מתכנסת (שאבריה מתקרבים עוד ועוד עד לנקודה אחת מובחנת, ה"גבול" של הסדרה) מהווה סדרת קושי; ולכן אם ההפך אינו נכון וקיימות סדרות קושי שאינן מתכנסות, טבעי לנסות ו"להשלים" את המרחב שלנו על ידי זיהוי הנקודות שבו עם אוסף סדרות הקושי שמתכנסות אליהן.

כל זה נשמע מבלבל מאוד, עד שמגיעים לשורה התחתונה. איך מיוצג המספר 1? באמצעות הסדרה $\left(1,1,1,\dots\right)$ (מדוע זו סדרת קושי?) ובאופן דומה מיוצג כל מספר רציונלי. ואיך מיוצג מספר אי רציונלי כמו $\sqrt{2}$ באמצעות סדרת מספרים רציונליים? ובכן, כבר הראיתי דוגמה בפוסט הקודם: למשל, הסדרה $\left(1,1.4,1.41,\dots\right)$ . כלומר, סדרה שבה כל איבר מקרב את $\sqrt{2}$ ברמת דיוק של ספרה אחת יותר מהקודמת. הראיתי בפוסט הקודם שבסדרה הזו מתקיים $d\left(a_{n},a_{n+1}\right)\le\frac{1}{10^{n}}$ ובעזרת קריטריון זה לא קשה להראות שמדובר בסדרת קושי.

וכעת עולה השאלה – האם ההרחבה הזו של הרציונליים היא ההרחבה האפשרית היחידה שמשתמשת בתעלול עם סדרות הקושי? התשובה נעוצה בשאלה האם ניתן להגדיר "מרחק" בצורה אחרת – ולכן, כמובן, בשאלה מהו "מרחק" בהקשר של הרציונליים. במתמטיקה קיים מושג כללי של "מרחק" שמכליל את המרחק הרגיל המוכר לנו; לפונקצית מרחק "כללית" שכזו קוראים מטריקה. פונקציה $d:X\times X\to\mathbb{R}$ היא מטריקה אם היא מקיימת את שלוש התכונות הבאות:

$d\left(x,y\right)\ge0$ ו- $d\left(x,y\right)=0$ אם ורק אם $x=y$ . כלומר: מרחק בין שתי נקודות הוא תמיד חיובי ממש אלא במקרה שבו שתי הנקודות זהות ואז המרחק ביניהן הוא תמיד 0.
$d\left(x,y\right)=d\left(y,x\right)$ , כלומר המרחק הוא סימטרי – המרחק מ- $x$ ל- $y$ הוא כמו המרחק מ- $y$ ל- $x$ (ולכן הכי פשוט לדבר על המרחק בין $x$ ו- $y$ ).
אי שוויון המשולש: $d\left(x,y\right)\le d\left(x,z\right)+d\left(z,y\right)$ לכל $x,y,z\in X$ . במילים: המרחק בין $x$ ל- $y$ הוא הקצר ביותר האפשרי; אם ננסה ללכת ב"דרך עקיפה", דרך איזו נקודת ביניים $z$ , סכום המרחקים שנלך יהיה גדול יותר.

הפאנץ' כאן הוא שכל פונקציה שמקיימת את התכונות הללו נקראת "מרחק", למרות שיש פונקציות מאוד מוזרות שממש לא מתנהגות כמו המרחק הרגיל שאנחנו מכירים. דוגמה לפונקציה שכזו היא פונקציה שנותנת 1 לכל $x,y$ שונים זה מזה ו-0 ל- $x=y$ – "המטריקה הדיסקרטית". קל לראות ששלוש התכונות שדרשנו מתקיימות עבורה, אבל מה ההגיון כאן? הפונקציה אומרת שהמרחק בין כל שתי נקודות ב"עולם" שלנו הוא 1; אם ה"עולם" שלנו הוא המספרים הרציונליים, הרי שפונקצית מרחק כזו מנותקת לחלוטין מהתפיסות המקובלות שלנו.

לכן אני הולך להשית עוד מגבלה על פונקצית ה"מרחק" שאדבר עליה – אדרוש שהיא תנבע ממושג כלשהו של "אורך", או במתמטית: נורמה. מה שאני הולך לתאר כאן הוא נורמה של שדות – כלומר, של קבוצות שבהן יש פעולת חיבור וכפל של איברים במרחב (ההקשר הנפוץ יותר הוא של מרחבים וקטוריים, אבל ההבדל אינו גדול עד כדי כך מבחינה רעיונית). במקום לקשקש יותר מדי פשוט אגש להגדרה: אם $x\in\mathbb{F}$ הוא איבר בשדה מסמנים את הנורמה שלו (שהיא מספר ממשי) ב- $\|x\|$ ודורשים שהיא תקיים תכונות שדי מזכירות את אלו של המטריקה:

$\|x\|\ge0$ ו- $\|x\|=0$ אם ורק אם $x=0$ .
$\|x+y\|\le\|x\|+\|y\|$
$\|xy\|=\|x\|\cdot\|y\|$

תכונת הסימטריה של המרחק נעלמה לה כי נורמה מוגדרת רק עבור איבר בודד, אבל שתי התכונות האחרות נשתמרו באופן מסויים. התכונה השלישית מתארת את התנהגות הנורמה ביחס לפעולת הכפל – הנורמה של מכפלת איברים היא מכפלת הנורמות שלהן. הקשר למטריקות אינו מקרי: אם יש לנו נורמה, אז קל לבדוק שהפונקציה $d\left(x,y\right)=\|x-y\|$ היא מטריקה. מה שחשוב לשים לב אליו הוא שלא כל מטריקה אפשר לקבל כך! יש מטריקות שלא ניתן לקבל באמצעות נורמות. את המטריקה הדיסקרטית ה"מטופשת" שתיארתי למעלה דווקא כן ניתן לקבל באמצעות נורמות – נגדיר $\|0\|=0$ ו- $\|x\|=1$ לכל $x\ne0$ . לנורמה הזו קוראים "הנורמה הטריוויאלית".

חזרה לרציונליים. אנחנו מכירים נורמה אחת עבור הרציונליים – הערך המוחלט, כלומר $\|x\|=\left|x\right|$ . האם אנחנו מכירים עוד נורמות? ובכן, למשל $\|x\|=\sqrt{\left|x\right|}=\left|x\right|^{\frac{1}{2}}$ גם כן עובדת – נסו להוכיח זאת לעצמכם. למעשה, $\|x\|=\left|x\right|^{\alpha}$ עבור כל $1\ge\alpha>0$ ממשי. ויש לנו עוד קבוצה מעניינת במיוחד של נורמות שהן – אולי כבר ניחשתם – הנורמות ה-p-אדיות. אבל אני עדיין לא רוצה להציג אותן אלא לשמור אותן בסוד עד לשלב שבו הן יצוצו באופן טבעי. דווקא דברים שנראים "טבעיים" יחסית כמו $\|x\|=\left|x\right|^{2}$ לא עובדים: $\|1+1\|=\left|1+1\right|^{2}=4>\left|1\right|^{2}+\left|1\right|^{2}=\|1\|+\|1\|$ מראה שאי שוויון המשולש לא מתקיים עבור "נורמה" כזו.

בואו נביט שניה על שתי הנורמות $\|x\|_{1}=\left|x\right|$ ו- $\|x\|_{2}=\left|x\right|^{\frac{1}{2}}$ . ברור שהן נותנות מושג שונה של "גודל", אבל האם הן משפיעות על מה שהיה המושג הבסיסי בדיון שלנו – סדרות קושי? כלומר, האם קיימת סדרה שנחשבת לסדרת קושי על פי הנורמה הראשונה אבל לא על פי השניה? אם שתי הנורמות מגדירות בדיוק את אותן סדרות קושי, נאמר שהן שקולות. זו לא סתם הגדרה שרירותית – אם שתי הנורמות מגדירות את אותן סדרות קושי אז כשנבצע השלמה למרחב ונוסיף לו את כל הגבולות של סדרות הקושי הלא מתכנסות שבו, נקבל בדיוק את אותה התוצאה. על פי ההגדרה הזו, די קל לראות ש- $\|\|_{1}$ ו- $\|\|_{2}$ הן שקולות. למי שלא מפחד מאינפי, הנה הוכחה:

ניקח סדרת קושי $a_{1},a_{2},a_{3},\dots$ על פי הנורמה $\|\|_{1}$ ; כדי להראות שהיא קושי על פי הנורמה $\|\|_{2}$ צריך, בהינתן $\varepsilon>0$ כלשהו, למצוא מקום בסדרה שהחל ממנו אברי הסדרה קרובים עד כדי $\varepsilon$ על פי הנורמה $\|\|_{2}$ . לשם כך ראשית נמצא מקום $N$ בסדרה שהחל ממנו אברי הסדרה קרובים עד כדי $\varepsilon^{2}$ על פי $\|\|_{1}$ ; כלומר, לכל $n,m>N$ מתקיים $\|x_{n}-x_{m}\|_{1}<\varepsilon^{2}$ . כעת נוציא שורש לשני האגפים ונקבל $\|x_{n}-x_{m}\|_{1}^{\frac{1}{2}}<\varepsilon$ , כלומר $\left|x_{n}-x_{m}\right|^{\frac{1}{2}}<\varepsilon$ , כלומר $\|x_{n}-x_{m}\|_{2}<\varepsilon$ . באופן דומה מטפלים גם בכיוון השני (להראות שסדרה שהיא קושי על פי $\|\|_{2}$ היא קושי גם על פי $\|\|_{1}$ ).

את ההוכחה הזו ניתן לבצע באותו האופן לכל $1\ge\alpha>0$ , ובכך לראות שכל הנורמות מהצורה $\|x\|=\left|x\right|^{\alpha}$ שקולות זו לזו – וכשמשלימים את הרציונליים על פיהן, מקבלים את הממשיים. מי נותר?

ובכן, מתברר שהתנהגות הנורמות על הרציונליים נקבעות בצורה חזקה מאוד על פי ערכן על המספרים הטבעיים. עד כדי כך שניתן להוכיח כי אם קיים טבעי $n$ כך ש- $\|n\|>1$ , אז הנורמה היא בהכרח מהצורה $\|x\|=\left|x\right|^{\alpha}$ . ההוכחה מעט טכנית ולא אכנס אליה, אך היא אינה מסובכת במיוחד. אם כן, הנורמות שנותרו הן אלו שלכל טבעי נותנות ערך לכל היותר 1. זו כבר התנהגות מוזרה – הרי אינטואיטיבית היינו מצפים שככל שהמספר הטבעי יגדל כך גם הנורמה שלו תגדל; אך זה לא נובע מהדרישות שהצבנו לנורמה.

אם כן, הבה וניקח נורמה כלשהי שמקיימת $\|n\|\le1$ לכל $n$ ונבין איך היא מתנהגת. אם היא איננה הנורמה הטריוויאלית שנותנת 1 לכל טבעי, אז קיים $n_{0}$ קטן ביותר עבורו $\|n_{0}\|<1$ , ואותו $n_{0}$ חייב להיות ראשוני; כי אחרת קיימים שני טבעיים $a,b<n_{0}$ (ומכיוון שהם קטנים יותר מ- $n_{0}$ הנורמה שלהם היא 1, כי $n_{0}$ המינימלי שעבורו זה לא כך) כך ש- $1=\|a\|\cdot\|b\|=\|ab\|=\|n_{0}\|<1$ – סתירה. שימו לב שכאן השתמשנו בכפליות הנורמה – כלומר, עבור פונקצית מרחק "סתם" ההוכחה נשברת כבר בשלב זה. מכיוון ש- $n_{0}$ הוא ראשוני, אסמן אותו מעתה בתור $p$ .

השלב הבא הוא להבין איך הנורמה מתנהגת על כל המספרים הטבעיים. הדרך לחקור את כל הטבעיים עוברת לעתים קרובות דרך כל הראשוניים, וכאן נעשה אותו הדבר: ניקח ראשוני $q\ne p$ ונשאל את עצמנו מהי $\|q\|$ . היעד שלי הוא להראות ש- $\|q\|=1$ , והדרך לכך עוברת בשילוב חביב של אנליזה ותורת המספרים. ראשית, משפט בסיסי בתורת המספרים אומר שאם $x,y$ שני מספרים שלמים הזרים זה לזה (אין להם מחלק משותף הגדול מ-1) אז קיימים שני מספרים שלמים $a,b$ כך ש- $ax+by=1$ (באופן כללי יותר – תמיד ניתן לכתוב את המחלק המשותף המקסימלי של שני מספרים כצירוף לינארי בשלמים שלהם). כעת נשתמש בתעלול אנליטי סטנדרטי. נניח ש- $\|q\|<1$ , אז קיים $n$ שעבורו $\|p\|^{n}<\frac{1}{2}$ וגם $\|q\|^{n}<\frac{1}{2}$ (כי אם $0<t<1$ אז ככל שמעלים אותו בחזקה גבוהה יותר כך הוא מתקרב יותר ויותר לאפס). עכשיו נשלב את שני אלו לקבלת סתירה:

$1 = \|1\|=\|ap^{n}+bq^{n}\|\le\|a\|\cdot\|p\|^{n}+\|b\|\cdot\|q\|^{n}<\frac{1}{2}+\frac{1}{2}=1$

כאן השתמשנו גם בכפליות הנורמה וגם באי שוויון המשולש, וכמובן גם בכך ש- $p^{n},q^{n}$ זרים (כי הם חזקות של ראשוניים שונים – אם במקום $q$ היינו לוקחים מספר טבעי "כלשהו" זה לא היה עובד).

מסקנה: $\|q\|=1$ לכל ראשוני שונה מ- $p$ . מכאן אנחנו מסוגלים להסיק את הערך של הנורמה על כל מספר טבעי $a$ : נכתוב את $a$ בתור $a=p^{k}\cdot\prod q_{i}^{k_{i}}$ ( $k$ יכול להיות גם אפס), ואז מכפליות הנורמה נקבל $\|a\|=\|p\|^{k}\cdot\prod\|q_{i}\|^{k_{i}}=\|p\|^{k}$ . בואו נסמן את $\|p\|$ בתור $\rho$ ונשתמש בסימון המוזר $k=\mbox{ord}_{p}\left(a\right)$ כדי לסמן את החזקה הגבוהה ביותר של $p$ שמחלקת את $a$ ; אז קיבלנו ש- $\|a\|=\rho^{\mbox{ord}_{p}\left(a\right)}$ . מכאן ההכללה עבור מספרים רציונליים היא קלה: מתכונת הכפליות של הנורמה עולה שבהכרח $\|\frac{1}{b}\|=\frac{1}{\|b\|}$ , ולכן $\|\frac{a}{b}\|=\frac{\|a\|}{\|b\|}=\frac{\rho^{\mbox{ord}_{p}\left(a\right)}}{\rho^{\mbox{ord}_{p}\left(b\right)}}=\rho^{\mbox{ord}_{p}\left(a\right)-\mbox{ord}_{p}\left(b\right)}$ (שימו לב שעבור מספרים רציונליים הנורמה עשויה לתת ערכים גדולים מ-1).

ובכן, זוהי הנורמה ה-p-אדית המדוברת. מכיוון ש- $\rho<1$ , היא בעלת התכונה שככל ש- $a$ מתחלק על ידי חזקה גדולה יותר של $p$ , כך הנורמה שלו קטנה יותר. כדי להבין עד כמה זה מוזר, שימו לב ש- $\|n!\|\to0$ על פי הגדרת הנורמה הזו. למעשה, עוד לא סיימתי כי לא ברור מיהו $\rho$ , אלא שזה לא משנה: אפשר להראות שעבור כל שני ערכי $0<\rho_{1},\rho_{2}<1$ הנורמה שנקבל על ידי ההגדרה שלעיל תהיה זהה – הדבר היחיד שמשנה הוא $p$ . לכן כשמגדירים את הנורמה באופן מסודר נוהגים לבחור $\rho=\frac{1}{p}$ (זו אינה בחירה שרירותית לגמרי – יש בה הגיון "אסתטי" כלשהו שאציג בפוסט הבא).

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

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

אז מהו שדה המספרים ה-p-אדיים?

5 בינואר, 2010

בפוסט הקודם דיברתי על משוואות דיופנטיות, והפעם אגש ישר לעניין. נניח שמבקשים מאיתנו לפתור את המשוואה $x^{2}\equiv2\left(\mbox{mod }7\right)$ . אפשר לשאול למה בכלל ידוע שיש למשוואה הזו פתרון, ואפשר לדבר על דרכים כלליות לפתור אותה, אבל לא אכנס לכך כרגע – רק אעיר שבגלל ש- $7$ ראשוני, יש דרכים שיטתיות לעשות זאת – אריתמטיקה מודולרית היא פשוטה יותר כשאנחנו מודולו מספר ראשוני. במקרה שלנו אפשר לראות ששני הפתרונות (כשאנחנו מגבילים את עצמנו לתחום $0,\dots,6$ , שכל מספר שלם אחר שקול לאיבר מתוכו מודולו 7) הם $x=3,4$ (אין זה מקרה ש- $3+4=7$ ; אפשר לחשוב על $4$ גם בתור $-3$ , ולכן כשמעלים אותו בריבוע מקבלים אותו דבר כמו $3$ בריבוע).

האתגר הבא שלנו, כפי שכתבתי בפוסט הקודם, הוא לפתור את המשוואה מודולו $7^{n}$ , עבור כל $n\ge2$ . אם אצליח למצוא שיטה כללית לעשות זאת (ולא רק עבור 7 אלא עבור כל ראשוני), אוכל להשתמש במשפט השאריות הסיני כדי לפתור כל משוואה מודולו כל מספר שלם.

אם כן, נתחיל מלנסות ולפתור את המשוואה מודולו $7^{2}$ . האבחנה הראשונה היא שאם $a^{2}\equiv2\left(\mbox{mod }7^{2}\right)$ , אז $a\equiv3,4\left(\mbox{mod 7}\right)$ – כלומר, מודולו 7, $a$ נראה בדיוק כמו אחד הפתרונות של המשוואה המקורית. מדוע? כי אם $a^{2}\equiv2\left(\mbox{mod }7^{2}\right)$ אז המשמעות של כך, ממש מן ההגדרה, היא $7^{2}|a^{2}-2$ , כלומר $7^{2}$ מחלק את ההפרש בין $a^{2}$ ובין 2, כשחושבים על שניהם כמספרים שלמים. אם $7^{2}$ מחלק את ההפרש, ודאי שגם $7$ מחלק את ההפרש, ולכן $a^{2}\equiv2\left(\mbox{mod }7\right)$ , כלומר מודולו 7 $a$ הוא אחד מהפתרונות של המשוואה המקורית, וכבר אמרנו שהם $3,4$ .

אם כן, בואו נחפש את כל הפתרונות ששקולים ל-3 מודולו 7. אפשר לומר שהצורה הכללית של פתרון $a$ שכזה היא $a=3+7\cdot k$ , כאשר $k$ הוא מספר שלם כלשהו. בואו נציב את זה למשוואה המקורית ונראה מה קורה: $2\equiv a^{2}\equiv\left(3+7k\right)^{2}\equiv3^{2}+14bk+7^{2}k^{2}\equiv9+14\cdot3k\left(\mbox{mod }7^{2}\right)$ ( $7^{2}k$ נעלם כשלוקחים את הכל מודולו $7^{2}$ ). אחרי העברת אגפים נקבל ש- $7+14\cdot3k\equiv0\left(\mbox{mod }7^{2}\right)$ , כלומר $7^{2}|7+14\cdot3k$ ; אבל אפשר להוציא מאגף שמאל את הגורם המשותף 7, ולכן נקבל ש- $7|1+6k$ , או $1+6k\equiv0\left(\mbox{mod 7}\right)$ , וממשוואה זו קל לחלץ את $k$ : $k\equiv1\left(\mbox{mod }7\right)$ . אם כן, איזה פתרון חדש קיבלנו? את $a=3+7=10$ (עבור הערך הבא של $k$ , $k=8$ , נקבל $a=3+7\cdot8=59\equiv10\left(\mbox{mod }7^{2}\right)$ ). השיטה שלנו עבדה.

אפשר מן הסתם להמשיך עם השיטה הזו עוד, ועוד, ועוד, כשעל כל פתרון ישן אנחנו מקבלים פתרון חדש. בואו ננסה לתאר את זה בצורה מסודרת: התחלנו ממספר $a_{1}$ שמקיים $a_{1}^{2}\equiv2\left(\mbox{mod 7}\right)$ , ובנינו ממנו מספר $a_{2}$ שמקיים $a_{2}^{2}\equiv2\left(\mbox{mod }7^{2}\right)$ ; ואותו מספר קיים בנוסף ש- $a_{2}\equiv a_{1}\left(\mbox{mod }7\right)$ . באופן כללי, בהינתן $a_{n}$ שמקיים $a_{n}^{2}\equiv2\left(\mbox{mod 7}^{n}\right)$ , אפשר לבנות $a_{n+1}$ שמקיים $a_{n+1}^{2}\equiv2\left(\mbox{mod 7}^{n+1}\right)$ , ובנוסף לכך $a_{n+1}\equiv a_{n}\left(\mbox{mod }7^{n}\right)$ . אפשר לחשוב על המידע על אוסף הפתרונות הזה כאילו הוא מקודד בתור סדרה, $a_{1},a_{2},\dots$ .

הבה ונעבור לרגע לדון במשוואה $x^{2}=2$ מעל המספרים הממשיים. הפתרון של המשוואה ניתן לכתיבה בתור $\sqrt{2}=1.4142\dots$ , כשהנקודות מציינות שהספרות ממשיכות וממשיכות עד אין קץ, ובלי שתהיה בהן מחזוריות קבועה – זו המשמעות של היות $\sqrt{2}$ אי רציונלי. המספר שאנחנו כותבים בפועל הוא פשוט קירוב רציונלי ל- $\sqrt{2}$ האי רציונלי. הבה ונכתוב את האיברים הראשונים בקירוב:

$b_{0}=1,b_{1}=1.4,b_{2}=1.41,b_{3}=1.414,b_{4}=1.4142$ וכן הלאה (התחלתי הפעם את המספור מ-0 לצורכי נוחות שיתבררו בקרוב).

אם נעלה את $b_{4}$ בריבוע, נקבל את המספר המגוחך $1.99996164$ . ההפרש בינו לבין 2 הוא $0.00003836\dots$ – הפרש פצפון. ככל שנתקדם עוד יותר בסדרה נקבל הפרשים עוד יותר קטנים. כלומר, המרחק שבין אברי $b_{n}$ ובין 2 הולך ושואף לאפס. נהוג לסמן זאת $\lim_{n\to\infty}\left|2-b_{n}^{2}\right|=0$ , ובקיצור: $\lim_{n\to\infty}b_{n}^{2}=2$ . על בסיס הרעיון הזה טבעי להגדיר את $\sqrt{2}$ מלכתחילה בתור גבול הסדרה $\lim_{n\to\infty}b_{n}$ . זה כמובן מעלה את התמיהה מדוע צריך "להגדיר את $\sqrt{2}$ " – האם הוא לא היה קיים מאז ומעולם? ובכן, תלוי בגישה שלנו לחיים; אם כל מי שאנחנו מכירים כרגע הוא מספרים רציונליים (שנבנו באופן מסודר מהשלמים, שנבנו באופן מסודר מהטבעיים, שאותם קיבלנו מאלוהים), אז לא – עדיין אין לנו בנמצא מספרים אי רציונליים ויש להגדיר אותם.

שימו לב לתכונה מעניינת נוספת של סדרת הקירובים $a_{n}$ . ההפרש בין שני איברים סמוכים מקיים $\left|b_{n+1}-b_{n}\right|\le10^{-n}$ , כלומר אם נחסר שני איברים סמוכים זה מזה, נקבל מספר עם הרבה אפסים בהתחלה ( $n+1$ במספר). אפשר לומר ששני המספרים הללו קרובים זה לזה עד כדי חזקה קטנה של $n$ .

אם כן, נסכם: אפשר לחשוב על $\sqrt{2}$ כאילו הוא מקודד סדרה של קירובים הולכים ומשתפרים עבור פתרון למשוואה $b^{2}=2$ , כשהדרך שבה אנחנו מודדים קרבה היא על ידי הערך המוחלט של ההפרש. הסדרה הזו מקיימת את התכונות ש- $\left|b_{n}^{2}-2\right|\le10^{-n}$ ובנוסף $\left|b_{n+1}-b_{n}\right|\le10^{-n}$ . נראה מוכר?

הפאנץ' הוא שגם על סדרת המספרים שהצגתי קודם, זו שמקיימת $a_{n}^{2}\equiv2\left(\mbox{mod }7^{n}\right)$ ו- $a_{n+1}\equiv a_{n}\left(\mbox{mod }7^{n}\right)$ אפשר לחשוב בתור "סדרת קירובים שהולכים ומשתפרים" לפתרון של המשוואה $x^{2}\equiv2$ מודולו חזקות הולכות וגדלות של 7. יש הגיון רב בגישה הזו: הרי אם $a_{n}^{2}\equiv2\left(\mbox{mod }7^{n}\right)$ , אז גם $a_{n}^{2}\equiv2\left(\mbox{mod }7^{k}\right)$ לכל $k<n$ (מאותו נימוק שנתתי קודם, כי $7^{k}$ מחלק את $7^{n}$ ולכן מחלק כל מה שמתחלק על ידי $7^{n}$ ), ולכן הפתרון $a_{n}$ איכשהו כבר מקודד את כל הפתרונות הקודמים, בדומה לאופן שבו $1.4142$ מקודד את כל הקירובים הקודמים של שורש 2. מן הסתם הסדרה $a_{n}$ הזו לא נגמרת לעולם, כשם שסדרת הקירובים הרציונליים של $\sqrt{2}$ שהצגתי לא נגמרת לעולם; אבל אם אפשר לחשוב על "מספר" ממשי, שאפילו מסומן בתור $\sqrt{2}$ , שמייצג את סדרת הקירובים הרציונליים כולה, למה לא לחשוב על מספר שמהווה גבול לסדרה $a_{n}$ שלנו? אפשר להגדיר מספרים כאלו בדיוק באותו האופן שבו הגדרנו את המספרים הממשיים. ובכן, התשובה לשאלה "למה לא" היא פשוטה – אין סיבה לא לעשות זאת, ואכן עושים זאת, ולתוצאה, במקרה זה, קוראים מספרים $7$ -אדיים.

מכיוון שכל הדיון הזה עסק במשוואה ספציפית, $x^{2}\equiv2\left(\mbox{mod }7^{n}\right)$ , התמונה הגדולה קצת התפספסה – מה התכונה המאפיינת של $a_{n}$ שאינה קשורה למשוואה שאותה $a_{n}$ באה לנסות ולפתור? ובכן, שמתקיים $a_{n+1}\equiv a_{n}\left(\mbox{mod }7^{n}\right)$ . אם כן, זה כל מה שנדרוש. הבה ונגדיר זאת פורמלית: שלם $7$ -אדי הוא סדרה $\left(a_{1},a_{2},\dots\right)$ שאבריה מקיימים $a_{n+1}\equiv a_{n}\left(\mbox{mod }7^{n}\right)$ . ובאופן כללי: סדרה שאבריה מקיימים $a_{n+1}\equiv a_{n}\left(\mbox{mod }p^{n}\right)$ עבור ראשוני $p$ כלשהו נקראת שלם p-אדי.

שימו לב שקראתי ליצור שהתקבל שלם p-אדי, ולא "מספר" p-אדי. הסיבה לכך היא שעדיין לא הגענו לסוף הסיפור. מן הסתם קבוצה של מספרים איננה מעניינת כל כך לכשעצמה – ברגע שמוגדרות עליה פעולות חשבון היא נהיית מעניינת יותר. הגדרת חיבור וכפל על השלמים ה-p-אדיים נובעת באופן די טבעי: $\left(a_{1},a_{2},\dots\right)+\left(b_{1},b_{2},\dots\right)=\left(a_{1}+b_{1},a_{2}+b_{2},\dots\right)$ ו- $\left(a_{1},a_{2},\dots\right)\cdot\left(b_{1},b_{2},\dots\right)=\left(a_{1}\cdot b_{1},a_{2}\cdot b_{2},\dots\right)$ (לא קשה לראות שגם הסכום והמכפלה מקיימים את הדרישה משלם p-אדי). אם כן, השלמים ה-p-אדיים הם חוג; ומכיוון ש- $\left(a,a,a,\dots\right)$ הוא שלם p-אדי, אפשר לחשוב עליהם כעל חוג שמרחיב את חוג השלמים.

כאשר נתקלים במתמטיקה בחוגי מספרים שכאלו אשר מרחיבים את השלמים, אחד מהגישושים הראשונים שמבצעים כדי להבין איך החוגים "נראים" הוא למצוא את ההכללה המתאימה למשפט היסודי של האריתמטיקה עבורם. עבור שלמים המשפט היסודי של האריתמטיקה אומר שכל מספר ניתן להצגה באופן יחיד כמכפלה של מספרים ראשוניים, עד כדי שינוי של הסדר שלהם והכפלה באיברים הפיכים (בשלמים ההפיכים היחידים הם $1,-1$ ). כך למשל את 15 ניתן להציג כ- $3\cdot5$ , אך גם כ- $\left(-1\right)\cdot5\cdot\left(-1\right)\cdot3$ . די ברור ששתי ההצגות זהות באופן עקרוני.

בחלק מהחוגים שמרחיבים את השלמים המצב כבר לא כך כך נחמד. דוגמה פשוטה היא החוג $\mathbb{Z}\left[\sqrt{-5}\right]$ , החוג שמתקבל מהשלמים על ידי הוספת $\sqrt{-5}$ למשחק , כך שאברי החוג הם מהצורה $a+b\sqrt{-5}$ עם $a,b\in\mathbb{Z}$ . זהו אמנם חוג, אך מתקיים בו $6=2\cdot3=\left(1+\sqrt{-5}\right)\left(1-\sqrt{-5}\right)$ , וניתן לבדוק שכל האיברים שמופיעים בפירוקים הללו הם בעצם אי פריקים ("אי פריק" הוא המושג המעניין כאן ולא "ראשוני"; בחוג השלמים שני המושגים הללו מזדהים, ומכאן ה"בלבול" בשמות – לאיברים ראשוניים הגדרה וחשיבות משל עצמם). מצד אחד, זו תוצאה מצערת למדי (שחירבה לחלוטין הוכחה בת המאה ה-19 למשפט האחרון של פרמה). מצד שני, בעיה זו היוותה את הבסיס לתורת המספרים האלגברית – נושא שראוי בעצמו לפוסטים רבים, ולא אגע בו כעת.

למרבה המזל, בשלמים ה-p-אדיים המצב נחמד ופשוט מאוד: כל שלם p-אדי השונה מאפס ניתן להצגה בתור $\alpha=p^{n}\varepsilon$ , כאשר $\varepsilon$ הוא שלם p-אדי הפיך. זה כמובן מעלה את השאלה מיהם האיברים ההפיכים; התשובה היא פשוטה ונחמדה בעצמה: כל שלם $\left(a_{1},a_{2},\dots\right)$ שעבורו $a_{1}\not\equiv0\left(\mbox{mod }p\right)$ (זה תרגיל נחמד להוכיח זאת). מכאן שלמשל, כל המספרים השלמים שאינם מתחלקים בידי $p$ הם הפיכים בחוג השלמים ה-p-אדיים.

מכיוון שישנה הצגה כל כך פשוטה לשלמים ה-p-אדיים, לא קשה לראות בעזרתה שאין בחוג מה שנקרא "מחלקי אפס" – איברים שונים מאפס שמכפלתם היא 0 (למשל, בחוג $\mathbb{Z}_{6}$ , האיברים $2,3$ הם מחלקי אפס כי מכפלתם היא אפס). ההוכחה פשוטה: מכפלה של שני שלמים היא מהצורה $p^{n}\varepsilon_{1}\cdot p^{m}\varepsilon_{2}=p^{n+m}\left(\varepsilon_{1}\varepsilon_{2}\right)$ . אם זה שווה לאפס אפשר לכפול בהופכי של האיבר ההפיך $\varepsilon_{1}\varepsilon_{2}$ ולקבל כי $p^{n+m}=0$ – סתירה.

כעת הגענו לפאנץ': מכיוון שחוג השלמים הוא ללא מחלקי אפס, ניתן להרחיב אותו באופן כזה שלכל איבר יהיה הופכי, בדיוק באותו תהליך שבו משתמשים כדי לבנות את הרציונליים מתוך השלמים – תהליך של בניית שדה שברים של חוג (גם כאן, מדובר על תהליך סטנדרטי עבור חוגי הרחבה של השלמים). התוצאה מסומנת לרוב ב- $\mathbb{Q}_{p}$ ונקראת, סוף סוף, "שדה המספרים ה-p-אדיים". הבניה אינה נגמרת כאן – כשם ש- $\mathbb{R}$ אינו סגור אלגברית (לא לכל פולינום יש שורש) והוא מורחב ל- $\mathbb{C}$ , גם את $\mathbb{Q}_{p}$ ניתן להרחיב עוד; עם זאת, לא אציג זאת כאן (ההרחבה מסובכת יותר מההרחבה של $\mathbb{R}$ ).

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

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

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

1 בינואר, 2010

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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