תורת הקבוצות - סודרים

מבוא

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

האינטואיציה היא כזו: נניח שיש לי קבוצה סדורה היטב \( A \). אני רוצה להפוך אותה איכשהו לקבוצה סדורה “קנונית” שאיזומורפית ל-\( A \); הדרך לעשות את זה הוא לבחור איזו צורת ייצוג לאיברים שהיא כמה שיותר חסכונית בפרטים. הרי מבחינתי הקבוצות הסדורות \( \left\{ 1<2<3\right\} \) ו-\( \left\{ 53<7<22\right\} \) (לא כתיב סטנדרטי אבל נו, הבנתם) הן אותו הדבר וכל הקטע הזה של לכתוב “53” זה סתם סירבול שמבלבל. אז אפשר אולי להגיד “האיבר הראשון בקבוצה יהיה 0, השני יהיה 1 וכן הלאה”, אבל זה עדיין מותיר אותנו עם השאלה - איך בכלל מוגדרים המספרים הללו? ובכן, כבר בפוסט המבוא שלי לסדרת הפוסטים על תורת הקבוצות נתתי הגדרה, אבל בואו נשכח ממנה כי א) היא בדיוק שייכת למה שכיניתי קודם “כיוון ראשון” וב) מה שאני הולך לעשות עכשיו ייתן לי אותה בחינם.

הגישה החדשה מתבססת על משפט מחץ אחד: בואו נחליף את אברי \( A \), לפי הסדר, בקבוצת האיברים שמגיעים לפניהם. כלומר, אינטואיטיבית בכל שלב נחליף את \( a\in A \) בקבוצה \( a^{<}=\left\{ b\in A\ |\ b<a\right\} \). זה אומר שהאיבר הראשון של \( A \) יוחלף ב-\( \emptyset \), השני יוחלף ב-\( \left\{ \emptyset\right\} \), השלישי ב-\( \left\{ \emptyset,\left\{ \emptyset\right\} \right\} \) וכן הלאה. הקבוצה שתתקבל אחרי כל ההחלפות הללו תהיה סודר, הסודר שמתאים ל-\( A \).

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

איך מגדירים סודרים?

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

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

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

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

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

בניסוח קצת יותר פורמלי, אקסיומת היסוד אומרת שאם \( A\ne\emptyset \) אז קיים \( a\in A \) כך שלכל \( b\in A \) מתקיים \( b\notin a \). בניסוח שקול, אפשר לומר שמתקיים \( a\cap A=\emptyset \).

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

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

עכשיו, אקסיומת היסוד מוכיחה יותר מאשר \( a\notin a \) אלא משהו כללי יותר: שאין סדרה יורדת אינסופית של קבוצות שסדורות על ידי הכלה. כלומר, לא קיימת סדרה \( a_{0},a_{1},a_{2},a_{3},\ldots \) של קבוצות (לאו דווקא שונות זו מזו) כך ש-\( \cdots\in a_{3}\in a_{2}\in a_{1}\in a_{0} \). כדי לראות את זה, אפשר פשוט להסתכל על הקבוצה \( S=\left\{ a_{0},a_{1},a_{2},\ldots\right\} \); קיים לה איבר מינימלי, והוא זה שהולך “לתקוע” את השרשרת כי אף אחד לא יכול להיות שייך אליו.

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

כמה דוגמאות לסודרים קונקרטיים

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

\( 1=0\cup\left\{ 0\right\} =\left\{ 0\right\} =\left\{ \emptyset\right\} \)

\( 2=1\cup\left\{ 1\right\} =\left\{ 0,1\right\} =\left\{ \emptyset,\left\{ \emptyset\right\} \right\} \)

וכן הלאה. באופן כללי, כל טבעי \( n \) יקיים \( n=\left\{ 0,1,2,\ldots,n-1\right\} \), וכולם יהיו סודרים. למעשה, יחס הסדר ש-\( \in \) מגדיר על הסודרים הללו הוא יחס הסדר הרגיל על המספרים הטבעיים (כלומר, \( a<b \) כשחושבים עליהם בתור מספרים טבעיים פירושו \( a\in b \) כשחושבים עליהם בתור קבוצות).

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

התשובה היא שצריך אקסיומה מיוחדת, שנקראת אקסיומת האינסוף. כשהצגתי אותה בשעתו תיארתי אותה פשוט בתור “הקבוצה \( \mathbb{N} \) קיימת” אבל נהוג יותר ניסוח שהוא קצת יותר עקיף: מניחים שקיימת קבוצה \( A \) כך ש-\( \emptyset\in A \) ואם \( a\in A \) אז גם \( a\cup\left\{ a\right\} \in A \). במילים אחרות, זה מחייב את \( A \) להכיל את כל הטבעיים, על פי הבניה שלהם שראינו; ייתכן ש-\( A \) תכיל עוד איברים בנוסף, אבל אפשר להשתמש באקסיומת ההפרדה כדי לחלץ ממנה את \( \omega \). זה מצריך מאיתנו למצוא קריטריון שאפשר לנסח בלוגיקה פורמלית ואומר מתי איבר של \( A \) הוא מספר טבעי; הקריטריון הוא “\( a \) הוא מספר טבעי אם ורק אם \( a=\emptyset \) או ש-\( a=b\cup\left\{ b\right\} \) עבור \( b \) כלשהו וגם לכל \( c\in a \), או ש-\( c=\emptyset \) או ש-\( c=b\cup\left\{ b\right\} \) עבור \( b\in a \) כלשהו”. משכנע? ובכן, לא, גם אותי זה לא משכנע, בואו ננסה לראות למה זה עובד.

ראשית, ברור שכל מספר טבעי אכן עונה לקריטריון הזה. מספר טבעי הוא או \( \emptyset \) או מהצורה \( n+1=n\cup\left\{ n\right\} \) עבור טבעי \( n \) כלשהו; ומכיוון שכל האיברים של מספר טבעי הם בעצמם מספרים טבעיים (בדיוק אלו שקטנים ממנו) גם הקטע עם “לכל \( c\in a \)” מתקיים. אבל למה רק מספרים טבעיים עונים לקריטריון הזה? כאן מי שתבוא לעזרת אקסיומת האינסוף היא אקסיומת היסוד.

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

יפה. אז הסודר \( \omega \) קיים. ואם הוא קיים, אז קיימים גם \( \omega+1,\omega+2,\ldots \) וכדומה. אבל מזה אפשר לקבל (עם אקסיומת ההחלפה שכבר הזכרתי) שהקבוצה \( \left\{ \omega+1,\omega+2,\ldots\right\} =\left\{ \omega+n\ |\ n\in\mathbb{N}\right\} \ldots \) קיימת, ואפשר לאחד אותה עם \( \omega \) ולקבל את הקבוצה \( \left\{ 1,2,3,\ldots,\omega,\omega+1,\ldots\right\} \). לקבוצה הזו יש סימון: \( \omega\cdot2 \), והמשמעות שלו תתבהר בקרוב כשאדבר על האופן שבו מגדירים פעולות חשבון על סודרים.

איך משווים סודרים?

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

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

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

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

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

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

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

אם \( \alpha\cong\beta \) אני רוצה להסיק מכך ש-\( \alpha=b \). ניקח אם כן את האיזומורפיזם \( f:\alpha\to\beta \) ונראה שהוא פונקציית הזהות. נניח בשלילה שהוא לא ונסתכל על ה-\( \gamma\in\alpha \) המינימלי שמקיים \( \gamma\ne f\left(\gamma\right) \) (קיים איבר מינימלי כזה כי \( \alpha \) סדורה היטב). אלא שמכיוון ש-\( \gamma\in\alpha \) אז ממה שהוכחתי לפני רגע, \( \gamma=\gamma^{<} \), והרי \( \gamma^{<} \) כוללת רק איברים של \( \alpha \) שכן מקיימים שהם שווים ל-\( f \) של עצמם (כי \( \gamma \) היה המינימלי שלא קיים זאת) ולכן \( \gamma^{<}=f\left(\gamma^{<}\right) \). עכשיו, בבירור \( f\left(\gamma^{<}\right)=f\left(\gamma\right)^{<} \): זה טיעון שכבר ראינו כמה פעמים בפעולה; מכיוון ש-\( f \) משמרת סדר, כל איבר ב-\( \gamma^{<} \) חייב לעבור לאיבר שקטן מ-\( f\left(\gamma\right) \), ומכיוון ש-\( f \) על כל האיברים ב-\( f\left(\gamma\right)^{<} \) הולכים להתקבל - והם לא יכולים להתקבל על ידי איברים שגדולים מ-\( \gamma \) כי זה שוב מפר את שימור הסדר.

מהתוצאה שראינו קודם, אנחנו יודעים שמתקיים \( f\left(\gamma\right)=f\left(\gamma\right)^{<} \), כי זה מתקיים לכל איבר של סודר, ולכן קיבלנו בסופו של דבר:

\( \gamma=\gamma^{<}=f\left(\gamma^{<}\right)=f\left(\gamma\right)^{<}=f\left(\gamma\right) \)

וקיבלנו סתירה לכך ש-\( \gamma\ne f\left(\gamma\right) \), ומכאן המסקנה ש-\( f \) היא פונקציית הזהות ולכן \( \alpha=\beta \) אם הם איזומורפיים. זה בפני עצמו כבר מספיק כדי ללמד אותנו שסודר הוא באמת ייצוג קנוני של סדר טוב; כלומר, אין שני סודרים שונים שמייצגים את אותו אוסף של קבוצות סדורות היטב שאיזומורפיות זו לזו.

ונניח ש-\( \alpha \) איזומורפית לקטע התחלתי של \( \beta \), מה קורה עכשיו? ובכן, קטע התחלתי כזה הוא מהצורה \( \gamma^{<} \) עבור \( \gamma\in\beta \), וכבר ראינו שבמקרה הזה \( \gamma \) הוא סודר ו-\( \gamma=\gamma^{<} \), כלומר קיבלנו ש-\( \alpha\cong\gamma \). לפני שניה ראינו שזה אומר ש-\( \alpha=\gamma \), ולכן בפרט \( \alpha\in\beta \), מה שמסיים את ההוכחה בצורה פשוטה עד להפתיע.

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

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

אז הטריק הוא כזה: בסודרים, ה”מידע” שיש בכל איבר של הסודר הוא בדיוק מי הסודרים שקטנים ממנו (זו המשמעות של \( \alpha^{<}=\alpha \) שראינו). בקבוצה סדורה היטב “סתם”, באיבר יכול להיות מידע “מיותר”. מה שאנחנו רוצים לעשות הוא בדיוק להחליף כל איבר בסודר שלא מכיל מידע מיותר, אז הסודר שיחליף את האיבר \( a \) צריך “לקודד” את המידע על \( a^{<} \). זה מוביל אותנו להגדרה: בהינתן קבוצה סדורה היטב \( A \), נגדיר את הסודר \( \alpha \) בתור קבוצת כל הסודרים שאיזומורפיים לקטעים התחלתיים של איברים ב-\( A \). כמובן, צריך להוכיח ש-\( A\cong\alpha \) וש-\( \alpha \) סודר, אבל לפני זה צריך להסביר למה \( \alpha \) קיים בכלל. זה נובע שוב מאקסיומת ההחלפה שלא תיארתי פורמלית: כל איבר \( a\in A \) שיש סודר שאיזומורפי אל \( a^{<} \) ניתן להחליף בסודר הזה; זה הולך ליצור את \( \alpha \) מתוך \( A \) על ידי החלפה. זה לא פורמלי, אבל זה מספיק טוב עד שנגיע לפוסט על האקסיומה הזו.

אוקיי, אז למה \( \alpha \) היא סודר? ראשית כל, היא קבוצה של סודרים, וראינו שכל זוג סודרים ניתנים להשוואה על ידי \( \in \), אז זו קבוצה סדורה בסדר מלא על ידי \( \in \). שנית, בואו נראה שהיא טרנזיטיבית. ניקח \( \gamma\in\beta\in\alpha \). אנחנו יודעים ש-\( \beta\cong b^{<} \) עבור \( b\in A \) כלשהו, כי זו ההגדרה של כל אברי \( \alpha \); האיזומורפיזם הזה בפרט מעביר את \( \gamma \) לאיבר כלשהו של \( b^{<} \), נאמר \( c\in b^{<} \); אז \( \gamma\cong c^{<} \) על ידי אותו איזומורפיזם בדיוק כשהוא מצומצם אל \( \gamma \). מכיוון שקיבלנו ש-\( \gamma \) איזומורפי לקטע התחלתי של \( A \) אז \( \gamma\in\alpha \), כפי שרצינו. זה מסיים את ההוכחה ש-\( \alpha \) הוא סודר.

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

\( f=\left\{ \left(b,\beta\right)\in A\times\alpha\ |\ b^{<}\cong\beta\right\} \)

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

שאר הדברים קלים יותר: \( f \) היא פונקציה כי היא לא יכולה להעביר את אותו \( b \) לשני סודרים שונים \( \beta_{1},\beta_{2} \), כי אז נקבל \( \beta_{1}\cong b^{<}\cong\beta_{2} \) ולכן הם שווים. \( f \) היא על כי מהגדרת \( \alpha \) כל איבר של \( \alpha \) איזומורפי לקטע ההתחלתי של איבר כלשהו ב-\( A \); ו-\( f \) היא חח”ע כי אם \( b_{1}^{<}\cong\beta\cong b_{2}^{<} \) נקבל ש-\( b_{1}=b_{2} \) כי כזכור, קבוצה סדורה היטב לא יכולה להיות איזומורפית לקטע התחלתי שלה (ולכן לא ייתכן שאחד מהקטעים מוכל בשני) והיא שומרת סדר מסיבה דומה: אם \( b_{1}<b_{2} \) אבל \( \beta_{1}>\beta_{2} \) אז נקבל מ- \( b_{1}^{<}\cong\beta_{1} \) ומ-\( b_{2}^{<}\cong\beta_{2} \) ש-\( b_{2}^{<} \) איזומורפית לקטע התחלתי של \( \beta_{1} \) ולכן ש-\( b_{2}^{<} \) איזומורפית לקטע התחלתי של \( b_{1}^{<} \) וזה כמובן בלתי אפשרי.

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

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