תורת הקבוצות - אריתמטיקה של סודרים

איך הסודרים נראים?

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

בואו נחשוב על מספרים טבעיים. יש כל מני דרכים לייצג מספרים טבעיים, אבל הדרך החביבה על האנושות בימינו היא הצגה עשרונית. בהצגה עשרונית אני כותב 572 וכולם מבינים שכתבתי מספר שמתקבל בתור מין תרגיל חשבוני: \( 5\times10^{2}+7\times10^{1}+2\times10^{0} \). מה יש לנו פה? ביטוי שמערב שלוש פעולות חשבוניות: חיבור, כפל וחזקה; ומערב שלוש ספרות, במקרה הזה 5,7,2, שהן מספרים בין 0 ל-9; ומערב את המספר המיוחד 10 שמשמש בתור הבסיס של הייצוג העשרוני.

האם יש משהו דומה עבור סודרים באופן כללי? למרבה השמחה, כן. כל סודר \( \alpha>0 \) אפשר לכתוב באופן הבא:

\( \alpha=\omega^{\beta_{1}}\cdot k_{1}+\ldots+\omega^{\beta_{n}}\cdot k_{n} \)

כאשר \( \alpha\ge\beta_{1}\ge\ldots\ge\beta_{n} \) הם סודרים ו-\( k_{1},\ldots,k_{n} \) הם מספרים טבעיים. הייצוג הזה נקרא הצורה הנורמלית של קנטור.

לא תמיד הייצוג הזה עושה את החיים פשוטים יותר: למשל, יש סודרים שמקיימים \( \alpha=\omega^{\alpha} \), אז לא לגמרי ברור האם הייצוג הזה עוזר לנו להבין יותר טוב איך הם נראים; אבל לפחות יש לנו צורה אחידה לכולם שנראית סבירה יחסית.

איך מגדירים אריתמטיקה של סודרים?

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

הדבר הבסיסי שאנחנו מתחילים ממנו הוא קיום הפעולה \( n+1 \) - פעולת העוקב. ראינו איך היא מוגדרת פורמלית: \( n+1\triangleq n\cup\left\{ n\right\} \). ברגע שיש אותה, אפשר להגדיר חיבור כללי \( n+m \) באופן הבא:

• \( n+0\triangleq n \)
• \( n+\left(m+1\right)\triangleq\left(n+m\right)+1 \)

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

באופן מאוד דומה אפשר להגדיר עכשיו כפל \( n\cdot m \), רק שעכשיו 0 לא יהיה נייטרלי אלא “בולעני”, ואת מקום פעולת העוקב תחליף פעולת החיבור שכבר הגדרנו:

• \( n\cdot0\triangleq0 \)
• \( n\cdot\left(m+1\right)\triangleq n\cdot m+n \)

והגדרת חזקה \( n^{m} \) ממשיכה באותה רוח:

• \( n^{0}\triangleq1 \)
• \( n^{m+1}\triangleq n^{m}\cdot n \)

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

כדי לקבל אינטואיציה לגבי מה שנעשה עכשיו, בואו ניזכר לרגע באופן שבו מגדירים במספרים ממשיים את \( a^{\sqrt{2}} \). הרעיון הוא להתבסס על זה שאנחנו יודעים להגדיר חזקה שבה המעריך הוא מספר רציונלי: \( a^{\frac{n}{m}}=\sqrt[m]{a^{n}} \); ומה שאנחנו עושים עכשיו הוא לקחת סדרה של מספרים רציונליים שמתכנסת ל-\( \sqrt{2} \) (תמיד יש כזו; זה מה שנקרא “הרציונליים צפופים בממשיים”): סדרה \( \left\{ r_{n}\right\} _{n=1}^{\infty} \) כך ש-\( \lim_{n\to\infty}r_{n}=\sqrt{2} \), ואנחנו מגדירים \( a^{\sqrt{2}}=\lim_{n\to\infty}a^{r_{n}} \). צריך כמובן להוכיח שזה מוגדר היטב, במובן זה שכל סדרה של רציונליים שמתכנסת אל \( \sqrt{2} \) תניב את אותו מספר, אבל זה עובד.

ההגדרה הזו הסתמכה על מושג הגבול שקיים בחדו”א. עבור סודרים אין דבר כזה, אבל יש משהו דומה. ראשית, בואו נשים לב לכך שאם יש לנו קבוצה \( A \) שכל האיברים שלה הם סודרים, אז \( \bigcup A \) הוא סודר בעצמו. זה די ברור בקבוצה סופית, כי ראינו שלכל זוג סודרים, אחד מוכל בשני, כך שהאיחוד של כולם יהיה פשוט האיבר המקסימלי בקבוצה. אבל אם \( A \) אינסופית זה מצריך הוכחה דומה לאלו של הפוסט הקודם. אני אסמן \( \alpha=\bigcup A \) ואז כדי להראות שזו קבוצה טרנזיטיבית ניקח \( \gamma\in\alpha \). על פי הגדרת \( \alpha \) זה אומר שקיים \( \beta\in A \) כך ש-\( \gamma\in\beta \), ומכיוון ש-\( \beta \) סודר אז \( \gamma\subseteq\beta\subseteq\bigcup A=\alpha \) ולכן \( \gamma\subseteq\alpha \) וקיבלנו ש-\( \alpha \) טרנזיטיבי. עכשיו, האיברים של \( \alpha \) כולם סודרים (כי האיברים של \( A \) הם סודרים ולכן כל האיברים שלהם הם סודרים) וכבר ראינו שהם סדורים בסדר מלא על ידי \( \in \), כך ש-\( \alpha \) הוא סודר.

אבחנה נוספת היא ש-\( \alpha=\sup A \), כלומר האיבר המינימלי של אוסף הסודרים שגדולים או שווים לכל אברי \( A \). איבר כזה בהחלט קיים כי \( \alpha \) הוא סודר כזה, אז מספיק להסתכל על קבוצת כל הסודרים הקטנים או שווים אליו שמקיימים את התכונה הזו והיא סדורה היטב. בנוסף, מכיוון ש-\( \text{sup}A \) גדול או שווה לכל איבר ב-\( A \) הוא מכיל את כולם, ולכן מכיל את האיחוד שלהם שהוא \( \alpha \); והמינימליות שלו פירושה שהוא מוכל ב-\( \alpha \), כך שקיבלנו שהם שווים.

עכשיו אפשר להגדיר גבול, עבור מקרה ספציפי. ניקח סודר גבולי \( \alpha \) וסדרה של סודרים שהאינדקסים שלה הם כל הסודרים עד ולא כולל \( \alpha \), כלומר \( \left\{ a_{\beta}\right\} _{\beta<\alpha} \) (פורמלית, זו פונקציה מ-\( \alpha \) אל קבוצה כלשהי של סודרים, כמו שסדרה רגילה היא פונקציה מ-\( \mathbb{N} \) לקבוצה כלשהי). נניח שהסדרה עולה, כלומר אם \( \beta_{1}<\beta_{2} \) אז \( a_{\beta_{1}}<a_{\beta_{2}} \), ועכשיו אפשר להגדיר את הגבול של הסדרה על ידי

\( \lim_{\beta\to\alpha}a_{\beta}=\sup\left\{ a_{\beta}\ |\ \beta<\alpha\right\} \)

עם ההגדרה הזו אפשר להציג סוף סוף את ההגדרה הפורמלית של פעולות האריתמטיקה של סודרים.

חיבור מוגדר על ידי

• \( \alpha+0\triangleq\alpha \)
• \( \alpha+\left(\beta+1\right)\triangleq\left(\alpha+\beta\right)+1 \) לכל סודר \( \beta \)
• \( \alpha+\beta\triangleq\lim_{\gamma\to\beta}\left(\alpha+\gamma\right) \) לכל סודר גבולי \( \beta>0 \)

כפל מוגדר על ידי

• \( \alpha\cdot0\triangleq0 \)
• \( \alpha\cdot\left(\beta+1\right)\triangleq\left(\alpha\cdot\beta\right)+\alpha \) לכל סודר \( \beta \)
• \( \alpha\cdot\beta\triangleq\lim_{\gamma\to\beta}\left(\alpha\cdot\gamma\right) \) לכל סודר גבולי \( \beta>0 \)

חזקה מוגדרת על ידי

• \( \alpha^{0}\triangleq1 \)
• \( \alpha^{\beta+1}\triangleq\alpha^{\beta}\cdot\alpha \) לכל סודר \( \beta \)
• \( \alpha^{\beta}\triangleq\lim_{\gamma\to\beta}\alpha^{\gamma} \) לכל סודר גבולי \( \beta>0 \)

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

כמה דוגמאות ועוד דרך התבוננות על זה

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

\( 1+\omega=\lim_{n\to\omega}\left(1+n\right)=\sup\mathbb{N}=\omega \)

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

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

בואו ניקח שתי קבוצות זרות \( A,B \) שהן סדורות בסדרים מלאים, \( <_{A},<_{B} \), ונגדיר יחס סדר על \( A\cup B \) שאפשר לתאר בתור “קודם \( A \) ואז \( B \)”. כלומר:

• אם \( a\in A,b\in B \) אז \( a<b \)
• אם \( a,b\in A \) אז \( a<b \) אם ורק אם \( a<_{A}b \)
• אם \( a,b\in B \) אז \( a<b \) אם ורק אם \( a<_{B}b \)

ראינו כבר משהו כזה לא מזמן; בפוסט שלי על קבוצות סדורות היטב לקחתי את \( \mathbb{Z} \) וחילקתי אותה לשני חלקים: \( \mathbb{Z}=A\cup B \) כאשר \( A=\mathbb{N} \) עם יחס הסדר הרגיל ו-\( B=\left\{ -1,-2,-3,\ldots\right\} \) עם יחס הסדר על פי הערך המוחלט. מזה הסקתי יחס סדר חדש ולא סטנדרטי של \( \mathbb{Z} \), שסימנתי \( \mathbb{Z}=\left\{ 0,1,2,\ldots,-1,-2,\ldots\right\} \). עכשיו, כשעושים את זה על קבוצות סדורות היטב, התוצאה היא קבוצה סדורה היטב; ואם \( A\cong\alpha,B\cong\beta \) מקבלים ש-\( A\cup B\cong\alpha+\beta \) (בדוגמא שלנו קיבלנו ש-\( \mathbb{Z} \) עם יחס הסדר המוזר איזומורפית ל-\( \omega+\omega \)). זו הדרך הנוחה לחשוב על זה.

עכשיו אולי קצת יותר ברור עניין ה-\( 1+\omega\ne\omega+1 \). כי \( \omega+1 \) זה “לאינסוף… ומעבר לו!” - זו קבוצת הטבעיים \( \omega \) כשאנחנו מוסיפים עוד איבר 1 (זה ה-\( +1 \)) “בסוף” שלה, אחרי כל הטבעיים. לעומת זאת, \( 1+\omega \) זו קבוצת הטבעיים כשאנחנו מוסיפים איבר חדש בהתחלה, כלומר למשל הקבוצה \( \left\{ -1,0,1,2,\ldots\right\} \) עם יחס הסדר הרגיל, שאיזומורפית ל-\( \mathbb{N} \) עם האיזומורפיזם \( x\mapsto x+1 \).

מה עם כפל? אותו עניין: \( 2\cdot\omega\ne\omega\cdot2 \). כי \( 2\cdot\omega=\lim_{n\to\omega}2\cdot n=\omega \), אבל \( \omega\cdot2=\left(\omega\cdot1\right)+\omega=\omega+\omega \). ושוב נשאלת השאלה האם אפשר לתת תיאור “קבוצתי” של זה, ואפשר! ניקח \( A,B \) כמו קודם ונסתכל על \( A\times B \). על הקבוצה הזו נגדיר סדר לקסיקוגרפי, כלומר כזה שבו קודם כל משווים את האיברים ברכיב אחד, ורק אם הם זהים משווים ברכיב השני. כאן ספציפית משווים קודם את \( B \) ורק אז את \( A \). כלומר, אם יש לנו את \( \left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right)\in A\times B \) אז \( \left(a_{1},b_{1}\right)<\left(a_{2},b_{2}\right) \) אם ורק אם

• \( b_{1}<b_{2} \), או:
• \( b_{1}=b_{2} \) וגם \( a_{1}<a_{2} \)

וכמקודם, אם \( A\cong\alpha \) ו-\( B\cong\beta \) אז \( A\times B\cong\alpha\times\beta \). למשל, עבור \( \omega\cdot2 \) אפשר להסתכל על הקבוצה \( \mathbb{N}\times\left\{ 0,1\right\} \); אנחנו משווים איברים \( \left(n,b\right) \) קודם כל על פי ה”ביט” הימני, ואז על פי המספר השמאלי. אנחנו מקבלים שני עותקים של \( \mathbb{N} \): ראשית כל האיברים מהצורה \( \left(n,0\right) \) ולאחר מכן האיברים מהצורה \( \left(n,1\right) \).

אז איך מגיעים לצורה הנורמלית?

כזכור, התחלנו את הפוסט מלדבר על זה שכל סודר ניתן להציג בצורה הנורמלית \( \alpha=\omega^{\beta_{1}}\cdot k_{1}+\ldots+\omega^{\beta_{n}}\cdot k_{n} \). איך מוכיחים את זה? התשובה היא - באינדוקציה. אבל כמו שהייתי זקוק לסוג מיוחד של רקורסיה כדי להגדיר את פעולות האריתמטיקה, אני צריך סוג מיוחד של אינדוקציה בשביל ההוכחה; אני אשמור את ההסבר הפורמלי עליה לפוסט הבא ובואו פשוט נזרום איתה כרגע.

הלב הטכני של ההוכחה הוא משפט ש… ניחשתן נכון… מכליל תוצאה דומה עבור מספרים טבעיים. ספציפית, בטבעיים אנחנו יודעים שאם \( a,b \) הם טבעיים כך ש-\( b>0 \) אז קיימים \( q,r \) יחידים כך ש-\( a=bq+r \) ו-\( 0\le r<a \). מה שנקרא, חילוק עם שארית. עבור סודרים קיים אותו דבר בדיוק: בהינתן \( \alpha,\beta \) כך ש-\( \beta>0 \), קיימים \( \gamma,\rho \) כך ש-\( \alpha=\beta\cdot\gamma+\rho \) ו-\( \rho<\alpha \). גם ההוכחה של זה דומה להוכחה עבור הטבעיים: לוקחים את \( \gamma \) המקסימלי שעבורו \( \alpha\ge\beta\cdot\gamma \) (קיים כזה כי \( \beta\cdot\left(\alpha+1\right)>\alpha \)). עכשיו לוקחים את \( \rho \) המקסימלי שעבורו \( \alpha\ge\beta\cdot\gamma+\rho \) (קיים כזה כי \( \beta\cdot\gamma+\beta=\beta\cdot\left(\gamma+1\right)>\alpha \)). קל לראות ש-\( \alpha=\beta\cdot\gamma+\rho \) אחרת היינו מקבלים סתירה למקסימליות עם \( \beta\cdot\gamma+\rho+1 \).

את המשפט המרכזי של הצורה הנורמלית מוכיחים באינדוקציה על \( \alpha \). עבור \( \alpha=1 \) בוחרים \( \beta=0 \) ומקבלים \( \alpha=\omega^{\beta} \) כך ש-\( \alpha\ge\beta \). עבור \( \alpha>1 \) כלשהו, בוחרים את \( \beta \) להיות הסודר הגדול ביותר כך ש-\( \alpha\ge\omega^{\beta} \). קיים כזה כי \( \alpha\le\omega^{\alpha} \) (ההוכחה היא באינדוקציה; נראה אותה בפוסט הבא בתור דוגמא). על פי משפט החלוקה שראינו, קיימים \( \delta,\rho \) כך ש-\( \rho<\omega^{\beta} \) ומתקיים \( \alpha=\omega^{\beta}\cdot\delta+\rho \). עכשיו שמים לב ש-\( \delta \) חייב להיות מספר טבעי (כי אם היה לפחות \( \omega \) היינו מקבלים \( \omega^{\beta}\cdot\delta\ge\omega^{\beta}\cdot\omega=\omega^{\beta+1} \) בסתירה למקסימליות של \( \beta \)) ואפשר להמשיך באינדוקציה על \( \rho \).

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