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

בפוסט הקודם דיברתי על האופן שבו קנטור “המציא” את הסודרים, אך כפי שיתברר בפוסט הזה, כנראה שהמילה “תגלית” יותר הולמת. קנטור הגיע אל הסודרים על ידי כך שהוא הגדיר סדרת קבוצות \( P^{\left(1\right)},P^{\left(2\right)},\dots \) ושם לב שיש משמעות גם לקבוצה \( P^{\left(\infty\right)} \) שמתקבלת כמעין “גבול” של הקבוצות עד אליה, ושאחרי שיש לנו אותה, יש משמעות גם ל-\( P^{\left(\infty+1\right)} \) ושניתן להמשיך את התהליך הזה עוד ועוד; בפוסט הזה אני רוצה להסביר קצת יותר במדויק את המשמעות הפורמלית-מתמטית של הרעיונות הללו. חשוב לציין שמה שאני מציג כרגע הוא את הרעיון שמאחורי סודרים - בשום פנים ואופן לא הגדרה מתמטית מדויקת שלהם. ההגדרה המתמטית-מדויקת היא “סודר הוא קבוצה טרנזיטיבית שסדורה בסדר טוב על פי יחס השייכות” שכרגע לא אומרת לנו כלום; כדי להבין אותה כדאי להבין קודם כל מה אנחנו מנסים להשיג, וזה מה שאעסוק בו בפוסט הזה. מי שרוצה את הפורמליסטיקה המתמטית וכל בלבולי המוח שלי רק יבלבלו אותו צריך לחכות לפוסט הבא (או לפתוח ספר בתורת הקבוצות).

אנחנו רגילים לחשוב על המספרים הטבעיים כמייצגים כמות - יש לי חמישה תפוחים, יש בכיתה 40 תלמידים, יש 10 דיברות וכן הלאה. אלא שלמספרים הטבעיים יש שימוש נוסף, קרוב ברוחו למדידת כמות אך בשום פנים ואופן לא זהה - מספור. אפשר להגיד על עשרת הדיברות משהו יותר חכם מאשר רק “יש 10 דיברות”; אפשר לדבר על הדיבר הראשון, הדיבר השני וכן הלאה. אם תרצו, יש לנו סדרה של דיברות, והמספרים הטבעיים משמשים לתיאור של יחס סדר בין הדיברות עצמן. כאשר מציגים תוצאות של מירוץ, הסדר של המשתתפים בדירוג מעיד על המנצח, התוצאה השניה בטיבה, השלישית בטיבה וכדומה. יש כאן יותר מאשר רק התייחסות לכמות. גם אצל קנטור המספרים הטבעיים שימשו לתיאור משהו שמעבר לכמות - \( P^{\left(2\right)} \) ממש נבע מתוך \( P^{\left(1\right)} \).

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

בדומה, רקורסיה מאפשרת לנו להגדיר סדרת אובייקטים מתמטיים מתוך האובייקטים הקודמים בסדרה. בהגדרה רקורסיבית נותנים מפורשות את האיברים הראשונים בסדר, וכלל שמתאר את האיבר הכללי בסדרה באמצעות כמה מהאיברים שקודמים לו. הדוגמה הקלאסית היא סדרת פיבונאצ'י שמוגדרת באמצעות \( F_{0}=0,F_{1}=1 \) והכלל \( F_{n}=F_{n-1}+F_{n-2} \).

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

1. \( 0 \) (המספר 0) הוא סודר.
2. אם \( \alpha \) הוא סודר, גם \( \alpha+1 \) הוא סודר - זהו "העוקב המיידי" של \( \alpha \).
3. אם \( A \) היא קבוצה של סודרים, אז גם \( \beta=\sup A \) הוא סודר, כאשר \( \sup \) הוא האיבר הקטן ביותר שגדול או שווה לכל אברי \( A \).

ה”הגדרה” שלמעלה היא קטסטרופלית מבחינה מתמטית - למשל, בקטע עם ה-\( \sup \), למה בכלל קיים איבר כזה? האם תמיד קיים כזה? מהו? איך הוא נראה? “גדול או שווה” - על פי איזה יחס סדר? אלו שאלות מצוינות עם תשובות מצוינות, אבל בינתיים אנחנו רק מנסים להבין את האינטואיציה. מתכונות 1 ו-2 עולה ש-\( 0,1,2,3,\dots \) ובאופן כללי כל המספרים הטבעיים הם סודרים. מתכונה 3 עולה שקיים סודר כלשהו שהוא הקטן ביותר שעדיין גדול מכל הטבעיים - אותו נהוג לסמן ב-\( \omega \). ועכשיו שוב קיימים סודרים \( \omega+1,\omega+2,\dots \) וכדומה, והסודר שגדול מכל הסדרה הזו מסומן ב-\( \omega+\omega \), וכן הלאה. עוד מעט נראה שכל העסק הזה הרבה פחות מבולגן ממה שהוא נראה במבט ראשון.

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

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

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

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

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

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

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

בואו נביט בכלל “המספר \( a_{10} \) הוא 42”. זה עוד כלל מטופש, ואליס יכולה להבטיח נצחון תוך 10 צעדים. אז בואו נדבר על כלל דומה, אבל מעניין יותר: “המספר \( a_{b_{10}} \) הוא 42”. מה זה אומר? זה אומר שדורשים מאליס שהמספר במקום ה-\( b_{10} \) יהיה 42. אבל מהו \( b_{10} \)? זה לא ידוע מראש, זה תלוי בערך שבוב יבחר לו במהלך המשחק.

האם אליס יכולה להבטיח לעצמה נצחון בכלל? כן. שימו לב שהיא חייבת לבחור 42 עבור כל המספרים \( a_{1},\dots,a_{10} \), כי אם למשל היא תבחר ש-\( a_{3}=7 \) ואז בוב יבחר \( b_{10}=3 \) היא הפסידה. אז אליס יכולה פשוט לבחור 42 תמיד, והיא תנצח כאשר נגיע לתור שמספרו הוא המספר שבוב בחר ל-\( b_{10} \). בוב מחוייב לבחור מספר טבעי, ולכן הוא אמנם יכול לדחות את רוע הגזרה הרחק הרחק קדימה (למשל, לבחור \( b_{10}=10^{10^{10^{10^{10}}}} \)) אבל הוא יפסיד בודאות. מתישהו. רק שאי אפשר לדעת מראש תוך כמה זמן הוא יפסיד.

קחו \( n \) טבעי כלשהו. איזה שתרצו. האם המשחק שתיארתי כרגע נמצא ב-\( P_{n} \)? בוודאי שלא. אם תטענו שכן, בוב יעשה מכם חוכא ואיטלולא ויבחר \( b_{10}=n+1 \) ובכך ידגים לכם שאליס פשוט לא יכולה לכפות נצחון תוך \( n \) צעדים. אז מצד אחד יש לנו משחק שבו אליס מנצחת במובהק, ומצד שני גם מובהק שאליס לא יכולה להבטיח נצחון במספר צעדים שהוא מספר טבעי. מצד שלישי, זה לא אומר שהכל נזרק לפח - מה שכן אפשר לדעת הוא שתוך 10 צעדים כן אפשר יהיה לדעת תוך כמה צעדים אליס תנצח. זה שונה, למשל, ממשחק שבו צריך ש-\( a_{b_{1}} \) יהיה 42, ובו כבר אחרי הצעד הראשון אפשר לדעת תוך כמה צעדים אליס תנצח. למעשה, היחס שבין המשחק עם ה-\( a_{b_{10}} \) למשחק עם ה-\( a_{b_{1}} \) דומה מאוד ליחס שבין המשחק עם \( a_{10} \) ובין המשחק עם \( a_{1} \)…

וכדי שתראו שזה לא סוף הסיפור, הנה ההמשך: מה קורה אם הכלל של המשחק הוא ש-\( a_{b_{b_{10}}} \) הוא 42? כלומר, בצעד מספר 10 בוב מכריז על מספר \( k \), ובצעד מספר \( k \) הוא מכריז על מספר \( n \), וה-\( n \) הזה הוא מספר הצעדים שאחריהם אליס תנצח. כלומר, כאן תוך 10 צעדים אנחנו יכולים לדעת מה יהיה מספר הצעדים שאחריו אפשר יהיה לדעת מה מספר הצעדים שאחריו אליס תנצח.

ומה על \( a_{b_{b_{10}}} \)? כאן תוך 10 צעדים אנחנו יכולים לדעת מה יהיה מספר הצעדים שאחרי אפשר יהיה לדעת מה מספר הצעדים שאחרי אפשר יהיה לדעת מה מספר הצעדים שאחריו אליס תנצח.

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

באופן דומה \( P_{10} \) היא קבוצת המשחקים שאחרי המהלך הראשון בהם מתקבל משחק ב-\( P_{9} \), ובאופן כללי את \( P_{n+1} \) אפשר להגדיר בתור קבוצת המשחקים שאחרי מהלך אחד בהם מתקבל משחק ב-\( P_{n} \). הנה כי כן בנינו קבוצה נאה של סוגי משחקים - \( \left\{ P_{0},P_{1},P_{2},\dots\right\} \).

כעת נגדיר את \( P_{\omega} \) בתור קבוצת המשחקים שאחרי מהלך אחד בהם מתקבל משחק כלשהו מאחת מהקבוצות בקבוצה \( \left\{ P_{0},P_{1},P_{2},\dots\right\} \). שימו לב שההגדרה הזו מתבססת על כך שכבר הגדרתי את \( P_{0},P_{1},\dots \) - זו דוגמה לרקורסיה טרנספיניטית. כזו שבה האיבר הבא מוגדר באמצעות אינסוף האיברים שקדמו לו (בדומה, \( P_{n+1} \) מוגדר באמצעות \( P_{n} \) - זו רקורסיה “רגילה”). המשך ההגדרה כעת בא באופן טבעי - את \( P_{\omega+1} \) נגדיר בתור משחקים שאחרי המהלך הראשון בהם מגיעים למשחק ב-\( P_{\omega} \), ואז נקבל את \( P_{\omega+n} \) לכל \( n \), ואז נגדיר את \( P_{\omega+\omega} \) להיות קבוצת המשחקים שאחרי מהלך אחד בהם מגיעים ל-\( P_{\omega+n} \) עבור \( n \) טבעי כלשהו. בקיצור אפשר לסמן את \( P_{\omega+\omega} \) כ-\( \omega\cdot2 \), וחיש קל הגענו להגדרה כללית של \( P_{\omega\cdot k} \): זו קבוצת המשחקים שאחרי מהלך אחד בהם מגיעים ל-\( P_{\omega\cdot\left(k-1\right)+n} \) עבור \( n \) טבעי כלשהו. משחק טיפוסי ב-\( P_{\omega\cdot k} \) ניתן לתיאור כך: נגדיר \( c_{1}=b_{1} \), ו-\( c_{i+1}=b_{c_{i}} \), אז המשחק הוא כזה שבו אליס צריכה לשים 42 ב-\( a_{c_{k}} \) (לכתוב מפורשות \( a_{b_{b\dots}} \) יהרוס לחלוטין את הטיפוגרפיה של הפוסט).

עכשיו אפשר ללכת אל הסודר הגבולי הבא ולדבר על \( P_{\omega\cdot\omega} \), או בקיצור \( P_{\omega^{2}} \), שהיא קבוצת המשחקים שאחרי מהלך אחד בהם מגיעים אל \( P_{\omega\cdot k+n} \) עבור \( k,n \) טבעיים כלשהם. האם אתם מסוגלים להעלות על הדעת משחק כלשהו שנמצא ב-\( P_{\omega^{2}} \)?

ובכן, אפשר למשל לדבר על משחק כזה: נגדיר \( c_{1}=b_{2} \), ו-\( c_{i+1}=b_{c_{i}} \), וכעת הכלל הוא שאליס צריכה לשים 42 ב-\( a_{c_{b_{1}}} \). כלומר, אם קודם המשחק אופיין על ידי סדרה של \( k \) “שרשורי אינדקסים” ו-\( k \) היה ידוע מראש, הרי שכעת \( k \) הוא עוד מספר שבוב אומר בהתחלה. ושוב - זה משחק שבו אליס תנצח, בטוח, בלי שאלה בכלל. כעת, איך תאפיינו משחקים ב-\( P_{\omega^{3}} \)? וב-\( P_{\omega^{k}} \)? ומה הולך להיות משחק ב-\( P_{\omega^{\omega}} \)?

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

היכולת שלנו לתאר את המשחקים עם סודרים לא רק מקלה עלינו לסווג אותם, אלא גם להוכיח עליהם דברים - באינדוקציה. כל שצריך להראות הוא שאם \( \alpha \) הוא סודר ומתקיים שאם במשחק ב-\( P_{\alpha} \) אליס מנצחת גם במשחק ב-\( P_{\alpha+1} \) אליס מנצחת; ושאם בכל המשחקים ב-\( P_{\beta} \) עבור סודר \( \beta<\alpha \) אליס מנצחת אז גם במשחק ב-\( P_{\alpha} \) אליס מנצחת - אם הראינו זאת, אז הוכחנו שאליס מנצחת בכל משחק ב-\( P_{\alpha} \), לכל סודר \( \alpha \). אינדוקציה שכזו מכונה אינדוקציה טרנספיניטית, וכמו כל מושג אחר הקשור לסודרים, גם אותה אסביר במדויק בהמשך.

לסיום אתן הגדרה קצת יותר קונקרטית של סודרים. היא עדיין לא תענה על השאלה המציקה “האם סודרים קיימים בכלל, ובאיזה מובן?” אבל אני חושב שהיא כבר מספיק טובה כדי שניתן יהיה להבין איך עובדים עם סודרים. נחשוב על כל סודר כעל קבוצה. נתחיל מהקבוצה הריקה, \( \emptyset \), שאותה נסמן כ-0. כעת, אם \( \alpha \) הוא סודר אז נגדיר סודר חדש, \( \alpha+1 \), בתור הקבוצה \( \alpha\cup\left\{ \alpha\right\} \). במילים אחרות, \( 1=\emptyset\cup\left\{ \emptyset\right\} =\left\{ 0\right\} \); ו-\( 2=\left\{ 0\right\} \cup\left\{ \left\{ 0\right\} \right\} =\left\{ 0,1\right\} \), ו-\( 3=\left\{ 0,1,2\right\} \), ובאופן כללי: \( n=\left\{ 0,1,2,\dots,n-1\right\} \). כלומר, כל מספר טבעי מוגדר כקבוצת המספרים הקטנים ממנו.

את הרעיון הזה אפשר יהיה להמשיך גם אל מעבר לאינסוף - כל סודר יוגדר להיות קבוצת הסודרים שקטנים ממנו. כך למשל \( \omega=\left\{ 0,1,2,\dots\right\} \) הוא פשוט קבוצת הטבעיים; ו-\( \omega+1=\left\{ 0,1,2,\dots,\omega\right\} \); ו-\( \omega+\omega=\left\{ 0,1,2,\dots,\omega,\omega+1,\omega+2,\dots\right\} \). באופן כללי, בכל פעם שבה אתם רוצים להוסיף סודר חדש לקבוצה הנוכחית של כל הסודרים שבניתם עד כה, פשוט קחו את הקבוצה הזו להיות הסודר החדש.

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