סודרים - התיאור הפורמלי

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

כמו כל דבר אחר בתורת הקבוצות, סודרים הם קבוצות, שהאיברים שלהן הם קבוצות בעצמם, וגם האיברים שלהם הם קבוצות בעצמם וכדומה. אין ביקום שלנו (היקום המתמטי שאנחנו מנסים לתאר; יש כמובן יקומים מתמטיים אחרים ויש גם שמועות שיש יקום לא מתמטי) שום דבר שאינו קבוצה. כדי להתחיל ממשהו, מתחילים מהקבוצה הריקה, \( \emptyset \) - הרי לכם אקסיומה אחת של תורת הקבוצות, לפיה קיימת קבוצה ריקה. אפשר גם קצת אחרת - אחת האקסיומות בתורת הקבוצות (“אקסיומת ההפרדה”) אומרת שאם \( A \) היא קבוצה, אז כל הגדרה בסגנון “האיברים של \( A \) שמקיימים כך וכך” (כש”כך וכך” מנוסח בצורה פורמלית מסויימת) מגדירה קבוצה, כך שאפשר להסתפק באקסיומה “קיימת קבוצה כלשהי”, נקרא לה למשל \( A \), ואז את הקבוצה הריקה אפשר להגדיר בתור הקבוצה \( \left\{ x\in A|x\ne x\right\} \). אבל זהו, לא אתעסק יותר באקסיומות, נשבע!

כפי שתיארתי בפוסט הקודם, הרעיון הוא שהקבוצה הריקה תייצג את המספר 0, ושאם \( \alpha \) היא קבוצה שמייצגת סודר כלשהו, אז גם הקבוצה \( \alpha\cup\left\{ \alpha\right\} \) תייצג סודר. זה מוביל להגדרה של 1 בתור \( 0\cup\left\{ 0\right\} \), ושל 2 בתור \( 1\cup\left\{ 1\right\} =\left\{ 0,1\right\} \), וכדומה. כעת אפשר לשים לב לתכונה מעניינת שכל הסודרים שמוגדרים באופן הזה מקיימים: כל איבר שלהם הוא גם תת קבוצה שלהם. למשל, \( 2\in4=\left\{ 0,1,2,3\right\} \), וגם כל איבר של 2 (שאבריה הם 0,1) הוא איבר של 4. ממש פורמלית אפשר לכתוב את התנאי בתור \( a\in b\Rightarrow a\subseteq b \), או בצורה שקולה, \( x\in a\in b\Rightarrow x\in b \). קבוצה שמקיימת את התכונה הזאת נקראת טרנזיטיבית.

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

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

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

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

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

במבט ראשון לא ברור למה תכונת הטרנזיטיביות הייתה חשובה כל כך. חשיבותה של תכונת הסדר הטוב ברורה, אני מקווה, אבל למה לא לקרוא לכל קבוצה שסדורה בסדר טוב “סודר”? ובכן, בעיקר כי אנחנו רוצים שכל טיפוס סדר אפשרי ייוצג בצורה יחידה. למה הכוונה? שתי קבוצות סדורות \( A,B \) הן איזומורפיות אם קיימת פונקציה חד-חד ערכית, על ומשמרת סדר \( f:A\to B \). חד-חד-ערכית אומר שאם \( f\left(x\right)=f\left(y\right) \) אז \( x=y \); על אומר שלכל \( b\in B \) יש \( a\in A \) כך ש-\( f\left(a\right)=b \); משמרת סדר אומר שאם \( x<y \) אז \( f\left(x\right)<f\left(y\right) \), והמשמעות של איזומורפיזם היא שהקבוצות הן לכל דבר ועניין אותה קבוצה עד כדי שינוי שמות.

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

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

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

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

למה הכוונה? חיבור, למשל, אפשר להגדיר עבור מספרים טבעיים כך:

\( n+0=n \) לכל \( n \)

\( n+\left(m+1\right)=\left(n+m\right)+1 \)

השורה הראשונה ברורה אך השנייה זקוקה להסבר. מה שכתוב בה הוא שאם אנחנו רוצים לחשב את \( n \) ועוד העוקב של \( m \), אנחנו קודם כל צריכים לחשב את \( n+m \) (שהוא כבר ידוע לנו - זה הרעיון ברקורסיה), ואז לקחת עוקב של התוצאה. לעתים מסמנים את פונקציית העוקב באות \( S \), ואז השורה השנייה נכתבת כ-\( n+S\left(m\right)=S\left(n+m\right) \), שכנראה קצת יותר ברור כאן.

ובכן, עבור סודרים ניתן להגדיר את אותו הדבר בדיוק. \( \alpha+0=\alpha \) ו-\( \alpha+\left(\beta+1\right)=\left(\alpha+\beta\right)+1 \). אבל רגע, זה מטפל רק בחיבור עם 0, ובחיבור עם סודר עוקב; מה עושים עם סודר גבולי?

הפתרון פשוט ונחמד: \( \alpha+\beta=\sup\left\{ \alpha+\gamma|\gamma<\beta\right\} \), כאשר \( \sup \) של קבוצת סודרים הוא פשוט האיבר הקטן ביותר שגדול או שווה לכל האיברים בקבוצה (התבוננו בקבוצת “כל הסודרים שגדולים או שווים לכל האיברים בקבוצה; זו קבוצת סודרים ולכן יש לה איבר קטן ביותר). אפשר לחשוב על זה גם בתור איחוד כל הסודרים מהצורה \( \alpha+\gamma \) עבור \( \gamma<\beta \) - זה אותו הדבר.

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

כפל סודרים מוגדר גם הוא בדומה להגדרת כפל טבעיים: \( \alpha\cdot0=0 \), ו-\( \alpha\cdot\left(\beta+1\right)=\alpha\cdot\beta+\alpha \) ו-\( \alpha\cdot\beta=\sup\left\{ \alpha\cdot\gamma|\gamma<\beta\right\} \) עבור סודר גבולי \( \beta \). כמקודם, גם כפל אינו קומוטטיבי: \( 2\cdot\omega=\omega \), אבל \( \omega\cdot2=\omega+\omega \) (הסבירו לעצמכם מדוע).

העלאה בחזקה גם היא מוגדרת כפי שצפוי שתוגדר: \( \alpha^{0}=1 \), ו-\( \alpha^{\beta+1}=\alpha^{\beta}\cdot\alpha \), ו-\( \alpha^{\beta}=\sup\left\{ \alpha^{\gamma}|\gamma<\beta\right\} \). כאן יש סכנה חדשה לבלבול, בקרב מי שלמד את תורת הקבוצות ויודע חשבון מונים (קרדינלים) - העלאה בחזקה של מונים לא זהה להעלאה בחזקה של סודרים! כך למשל \( 2^{\omega}=\omega \), אבל \( 2^{\aleph_{0}}>\aleph_{0} \) (וזאת למרות ש-\( \omega \) הוא בדיוק \( \aleph_{0} \)). זו פינה אפלה שלא אכנס אליה כרגע כי אני לא מעוניין להגדיר מונים והעלאה בחזקה של מונים.

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

\( \omega^{\beta_{1}}c_{1}+\omega^{\beta_{2}}c_{2}+\dots+\omega^{\beta_{k}}c_{k} \)

כאשר \( k \) הוא מספר טבעי (כלומר, יש רק מספר סופי של מחוברים בסכום), \( c_{1},\dots,c_{k} \) הם מספרים טבעיים גם הם, ואילו \( \beta_{1}\ge\beta_{2}\ge\dots\beta_{k}\ge0 \) הם סודרים. אני חושב שהייצוג הזה עוזר מאוד להבנה של “איך כל הסודרים נראים” ולעשיית סדר במחשבה, גם אם הוא נראה קצת מבהיל ממבט ראשון. כדי להבהיל אתכם עוד קצת רק אציין שקיים סודר שמכונה \( \varepsilon_{0} \) המקיים \( \varepsilon_{0}=\omega^{\varepsilon_{0}} \), כך שהאינטואיציה לפיה הסודר שבחזקה הוא בהכרח קטן מהסודר שהצורה הנורמלית של קנטור מתארת היא שגויה (\( \varepsilon_{0} \) אינו הסודר היחיד שמקיים תכונה זו; רק הקטן ביותר).

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