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

מבוא

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

כזכור, יחס סדר \( \le \) מעל קבוצה \( A \) הוא יחס (קבוצה של זוגות של אברי \( A \), כלומר תת-קבוצה של \( A\times A \)) שהוא

• רפלקסיבי: לכל \( a\in A \) מתקיים \( a\le a \).
• טרנזיטיבי: אם \( a\le b \) וגם \( b\le c \) אז \( a\le c \)
• אנטיסימטרי: אם \( a\le b \) וגם \( b\le a \) אז \( a=b \).

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

יחס סדר הוא מלא (או לינארי) אם אפשר להשוות כל שני איברים, כלומר לכל \( a,b\in A \) או ש-\( a\le b \) או ש-\( b\le a \). ואיבר \( a\in A \) הוא איבר ראשון על פי יחס הסדר, אם לכל \( b\in A \) מתקיים \( a\le b \).

עכשיו אפשר להגדיר מה זה סדר טוב: זה יחס סדר מלא שבו לכל תת-קבוצה לא ריקה של \( A \) קיים איבר ראשון. לזוג \( \left(A,\le\right) \) של הקבוצה ויחס הסדר הטוב עליה קוראים קבוצה סדורה היטב.

בואו נראה דוגמאות. והרבה. כי מה הטעם בהגדרה בלי דוגמאות.

הדוגמא המרכזית, האבטיפוס, נותן ההשראה לכל המושג הזה, היא קבוצת המספרים הטבעיים, \( \mathbb{N} \) עם יחס הסדר הרגיל עליה, כלומר \( 0<1<2<3<\ldots \). זה בוודאי יחס סדר מלא, ואם ניקח תת-קבוצה לא ריקה של טבעיים, האיבר הראשון שבה הוא בסך הכל האיבר המינימלי בגודלו. למשל, \( \left\{ 13,5,81\right\} \) היא תת-קבוצה שכזו, והאיבר הראשון בה, על פי יחס הסדר, הוא 5.

זו תכונה שימושית בצורה יוצאת מן הכלל: הרבה הוכחות במתמטיקה כוללות אספקט שבו לוקחים תת-קבוצה כלשהי של טבעיים ואז מסתכלים על האיבר המינימלי בה. אפילו ההוכחה שהוכחות באינדוקציה עובדות היא כזו: כזכור, הוכחה באינדוקציה אומרת שאם טענה \( P \) כלשהי מתקיימת עבור 0 (מסמנים זאת \( P\left(0\right) \)) ובנוסף, אם היא מתקיימת עבור טבעי \( n \) כלשהו היא מתקיימת גם עבור \( n+1 \) (\( P\left(n\right)\Rightarrow P\left(n+1\right) \)) אז נובע מכך שהיא מתקיימת לכל הטבעיים (\( \forall n\in\mathbb{N}:P\left(n\right) \)). איך מוכיחים את זה? פשוט, מסתכלים על קבוצת הטבעיים שעבורם \( P \) אינה מתקיימת; אם היא ריקה, סיימנו, ואחרת קיים לה איבר ראשון, \( n \). מכיוון ש-\( P\left(0\right) \) אז \( n>0 \) ולכן גם \( n-1\in\mathbb{N} \), אבל מהמינימליות של \( n \) עולה ש-\( P\left(n-1\right) \), ועכשיו אפשר להסיק מכך שגם \( P\left(\left(n-1\right)+1\right)=P\left(n\right) \) - סתירה להנחה ש-\( P\left(n\right) \) לא מתקיים.

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

בואו נתבונן כעת על הקבוצה \( \mathbb{Z}=\left\{ \ldots,-2,-1,0,1,2,\ldots\right\} \) של המספרים השלמים. הקבוצה הזו סדורה בסדר מלא, אבל הוא לא סדר טוב, כי אפילו לכל \( \mathbb{Z} \) עצמה אין איבר ראשון. אותה בעיה תמנע גם מ-\( \mathbb{Q} \) להיות סדורה בסדר טוב. אבל מה קורה אם נפטרים מהבעיה הזו? למשל, בואו נסתכל על \( \mathbb{Q}^{\ge0}=\left\{ q\in\mathbb{Q}\ |\ q\ge0\right\} \). לקבוצה הזו בוודאי יש איבר ראשון: 0. לרוע המזל, זה לא מספיק בשביל שהקבוצה תהיה סדורה בסדר טוב, כי צריך שיהיה איבר ראשון לכל תת-קבוצה לא ריקה של \( \mathbb{Q}^{\ge0} \), והנה דוגמא לתת-קבוצה כזו שאין לה איבר ראשון (אני מסדר את אבריה כך שהגדול ביותר בא תחילה): \( \left\{ 1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\ldots\right\} \). הקבוצה הזו “שואפת לאפס” באיזה מובן אינטואיטיבי, אבל מכיוון ש-0 אינו שייך אליה, אין לתת-הקבוצה הזו איבר ראשון. שימו לב לניואנס הזה: אם \( B\subseteq A \) אז צריך שיהיה ל-\( B \) איבר ראשון בתוך \( B \) עצמה. לא משנה אם קיים ב-\( A\backslash B \) מישהו שנראה כמו אינפימום של \( B \).

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

גם את \( \mathbb{Q}^{\ge0} \) אפשר לסדר די בקלות בסדר טוב, וזה בעצם מה שעושים בהוכחה הסטנדרטית ש-\( \mathbb{Q} \) בת מניה: אנחנו כותבים סדר כמו \( \frac{0}{0},\frac{0}{1},\frac{1}{0},\frac{0}{2},\frac{1}{1},\frac{2}{0},\ldots \) - זה משהו די מגוחך שכולל איברים לא הגיוניים כמו \( \frac{0}{0} \), אבל העיקרון ברור - מהרשימה הזו אנחנו לוקחים רק את המספרים של \( \mathbb{Q}^{\ge0} \), בפעם הראשונה שהם הופיעו, והרשימה עצמה מסודרת כך: ראשית מופיעים כל הביטויים \( \frac{a}{b} \) עם \( a,b\ge0 \) כך ש-\( a+b=0 \); אחר כך כל הביטויים כך ש-\( a+b=1 \) וכן הלאה, כשבכל פעם אנחנו מתחילים מ-\( a=0 \) ומגדילים אותו תוך שאנו מקטינים את \( b \) בהדרגה. זה יניב לנו את

\( \mathbb{Q}^{\ge0}=\left\{ 0,1,\frac{1}{2},2,\frac{1}{3},3,\ldots\right\} \)

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

אם כן, בואו נדבר על איזומורפיזמים.

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

באופן כללי במתמטיקה, איזומורפיזם של שתי קבוצות אומר שהן אותו דבר עד כדי שינוי שמות - כש”אותו הדבר” צריך להתייחס גם למבנה הרלוונטי שיש על הקבוצות בהקשר שעליו מדברים. אם אין שום מבנה, אז איזומורפיזם \( f:A\to B \) של קבוצות הוא בסך הכל פונקציה חח”ע ועל ביניהן; אבל בהקשר שלנו, שבו יש יחסי סדר על הקבוצות שאסמן \( \le_{A},\le_{B} \), איזומורפיזם הוא פונקציה \( f:A\to B \) שהיא חח”ע, על ומשמרת סדר: כלומר, \( a\le b \) אם ורק אם \( f\left(a\right)\le f\left(b\right) \).

הנה דוגמא פשוטה. בואו נסדר את \( \mathbb{Z} \) כך שמספרים חיוביים ושליליים מגיעים זה אחר זה: \( \mathbb{Z}=\left\{ 0,1,-1,2,-2,3,-3,\ldots\right\} \). עם הסדר הזה, \( \mathbb{Z} \) היא בסך הכל \( \mathbb{N} \) בתחפושת. הנה האיזומורפיזם המפורש:

\( f\left(n\right)=\begin{cases} k & n=2k-1\\ -k & n=2k \end{cases} \)

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

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

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

ראשית, נוכיח שאם \( A \) סדורה היטב, אז היא לא איזומורפית לאף קטע התחלתי של עצמה, ואפילו יותר מזה - היא לא איזומורפית לאף תת-קבוצה של קטע התחלתי של עצמה. כלומר, ניקח \( a\in A \) כלשהו ונוכיח שלכל \( B\subseteq a^{<} \) מתקיים \( A\not\cong B \)ֲ. נניח בשלילה שדווקא כן \( A\cong B \) עבור \( B\subseteq a^{<} \) כלשהי, עם איזומורפיזם \( f:A\to B \), ונשאל את עצמנו את השאלה - אל מי \( f \) מעבירה את \( a \)? היא מעבירה אותו לאיבר ב-\( a^{<} \), כלומר למישהו שקטן מ-\( a \):

\( f\left(a\right)<a \)

עכשיו אני יכול להפעיל את \( f \) על שני האגפים של אי השוויון הזה, ומכיוון ש-\( f \) משמרת סדר, אני אקבל

\( f\left(f\left(a\right)\right)<f\left(a\right) \)

וככה אפשר להמשיך באופן כללי ולקבל

\( f^{n}\left(a\right)<f^{n-1}\left(a\right) \)

או במילים אחרות, קיבלתי סדרה יורדת אינסופית של איברים:

\( a>f\left(a\right)>f^{2}\left(a\right)>f^{3}\left(a\right)>\ldots \)

בקבוצה סדורה היטב לא יכולה להיות סדרה כזו, כי אם נסתכל על הקבוצה \( \left\{ f^{n}\left(a\right)\ |\ n\in\mathbb{N}\right\} \), זו תת-קבוצה של \( A \) ומכיוון ש-\( A \) סדורה היטב, צריך להיות בה איבר ראשון, כזה שקטן מכל האיברים האחרים; אבל לכל איבר בסדרה הזו קיים איבר שקטן ממנו. הגענו לסתירה, והמסקנה היא ש-\( A\not\cong B \), כמו שרצינו.

הדבר השני שאני רוצה להוכיח בדרך אל המשפט הגדול הוא שאם \( A\cong B \), אז האיזומורפיזם ביניהם הוא יחיד. כלומר, אם \( f:A\to B \) וגם \( g:A\to B \) הם איזומורפיזמים, אז \( f=g \), או במילים אחרות: \( h=g^{-1}f=\text{Id}_{A} \) הוא איזומורפיזם הזהות.

ה-\( h \) הזה הוא בעצם המפתח להוכחה: אם אנחנו לוקחים \( a\in A \) אז \( h \) היא בפרט איזומורפיזם בין הקבוצות \( a^{<} \) ו-\( h\left(a\right)^{<} \). למה? ובכן, \( h \) היא הרכבה של פונקציות חח”ע, על ושומרות סדר ולכן היא חח”ע, על ושומרת סדר בעצמה; עכשיו, אם \( x\in a^{<} \) זה אומר ש-\( x<a \), ולכן \( h\left(x\right)<h\left(a\right) \) ומכאן ש-\( h\left(x\right)\in h\left(a\right)^{<} \); קיבלנו שהתמונה של \( a^{<} \) על ידי \( h \) מוכלת ב-\( h\left(a\right)^{<} \). מצד שני, אם \( y\in h\left(a\right)^{<} \) אז \( y<h\left(a\right) \) ולכן \( h^{-1}\left(y\right)<a \) ולכן המקור של \( y \) שייך ל-\( a^{<} \). משני אלו נקבל שהתמונה של \( a^{<} \) היא בדיוק \( h\left(a\right)^{<} \) ולכן \( h \) היא איזומורפיזם בין שתי הקבוצות הללו.

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

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

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

ראשית, לפני שנתחיל את הדבר העיקרי, בואו נשים לב לשני דברים שלא הבהרתי בניסוח המשפט:

1. רק אחד משלושת המקרים יכול להתקיים, כי אם שני מקרים מתקיימים בו זמנית אפשר לקבל סיטואציה של קבוצה שאיזומורפית לתת-קבוצה של קטע התחלתי של עצמה, וראינו שזה לא יכול לקרות. למשל, אם \( A\cong B \) עם איזומורפיזם \( f \) וגם \( A\cong b^{<} \) עם עבור \( b\in B \) עם איזומורפיזם \( g \) אז הרכבת האיזומורפיזמים \( gf^{-1} \) היא איזומורפיזם \( B\cong b^{<} \) וזו סתירה. או למשל אם \( A\cong b^{<} \) עם \( f \) ו-\( B\cong a^{<} \) עם \( g \) אז נקבל פונקציה חח"ע ושומרת סדר מ-\( A \) אל \( a^{<} \). היא לאו דווקא על \( a^{<} \), אבל היא על תת-קבוצה של \( a^{<} \), אז אנחנו מקבלים איזומורפיזם של \( A \) עם תת-קבוצה של קטע התחלתי של עצמה.
2. האיזומורפיזם שכן קיים הוא יחיד - זה בדיוק מה שהוכחנו קודם עבור שתי קבוצות כלליות.

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

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

כל זה טוב ויפה, אבל איפה אני נפטר מהעניין הזה של בניה בשלבים? ובכן, אני צריך שלבים רק אם יש לי תהליך שיש בו אפשרויות בחירה כלשהן, אבל אני טוען שאין לנו שום בחירה. לא בחרתי להעביר את \( a \) אל \( b \) כי ככה יצא בבניה הספציפית שלי; אני מעביר את \( a \) אל \( b \) כי \( b \) הוא האיבר היחיד שעבורו מתקיים \( a^{<}\cong b^{<} \). זכרו את מה שראינו: אם \( a^{<}\cong b^{<} \) אז פשוט לא ייתכן ש-\( a^{<} \) יהיה איזומורפי לכל קטע התחלתי אחר של \( B \) (כי קטע כזה יכיל או יוכל ב-\( b^{<} \)) והאיזומורפיזם \( a^{<}\cong b^{<} \) הוא יחיד, אז הוא לא תלוי באיזו \( f \) ספציפית שבניתי עד כה.

זה מוביל אותי אל ההגדרה של \( f \) שבה אנחנו הולכים להשתמש, שהיא לב ההוכחה:

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

הפונקציה הזו היא האיזומורפיזם שאנחנו רוצים. לאיזה מבין המקרים? לכולם! לפי מי מהם שנכון. אם למשל \( A\cong b^{<} \), זה אומר שנקבל את כל הזוגות \( \left(a,b\right) \) עם \( a\in A \); לא כל ה-\( b \)-ים של \( B \) יופיעו, וזה בסדר גמור. אם לעומת זאת \( a^{<}\cong B \) אז זה אומר שכל ה-\( b \)-ים כן יופיעו אבל לא כל ה-\( a \)-ים, וזה עדיין בסדר גמור. הפונקציה עובדת בכל מקרה.

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

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

\( \text{dom}f\triangleq\left\{ a\in A\ |\ \exists b\in B:\left(a,b\right)\in f\right\} \)

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

באותו אופן בדיוק מראים שאם \( \left(a_{1},b\right),\left(a_{2},b\right)\in f \) אז \( a_{1}=a_{2} \), כלומר ש-\( f \) חח”ע. וזה ש-\( f \) היא על הוא שוב עניין של איך מגדירים, ספציפית כאן איך מגדירים את הטווח של \( f \), שפשוט נזהה עם התמונה שלה \( \left\{ b\in B\ |\ \exists a\in A:\left(a,b\right)\in f\right\} \).

אז בבניה שלנו ראינו כבר ש-\( f \) היא פונקציה חח”ע ועל בין תת-קבוצה כלשהי של \( A \) ותת-קבוצה כלשהי של \( B \). אבל מהן הקבוצות הללו? בתור התחלה אני רוצה להראות שאם איבר \( a\in A \) שייך לתחום של \( f \), כך גם כל \( a^{\prime}<a \).

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

כלומר, ראינו שאם \( \left(a,b\right)\in f \) אז לכל \( a^{\prime}<a \) קיים \( b^{\prime}<b \) כך ש-\( \left(a^{\prime},b^{\prime}\right)\in f \) (ובדומה לכל \( b^{\prime}<b \) קיים \( a^{\prime}<a \) מתאים). המסקנה מזה היא כפולה: ראשית, \( f \) משמרת סדר. שנית, אם התחום של \( f \) הוא לא כל \( A \), אז מכיוון ש-\( A \) סדורה היטב אפשר להסתכל על \( A\backslash\text{dom}f \) ולקבוצה הזו יהיה איבר ראשון, \( a \). לא ייתכן שיהיו איברים ב-\( \text{dom}f \) שגדולים מ-\( a \) אחרת מה שראינו כרגע היה מוכיח ש-\( a\in\text{dom}f \), ולכן המסקנה היא ש-\( \text{dom}f=a^{<} \). באותו האופן התמונה של \( f \) היא או \( B \) כולה או \( b^{<} \) עבור \( b\in B \) כלשהו.

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

בונוס: האם כל קבוצה ניתנת לסידור טוב?

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

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

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

אם אנחנו מניחים את אקסיומת הבחירה, אז די פשוט להוכיח שכל קבוצה \( A \) ניתנת לסידור בסדר טוב. ראשית, נסתכל על אוסף כל תת-הקבוצות הלא ריקות של \( A \) (פורמלית, \( X=\mathcal{P}\left(A\right)\backslash\left\{ \emptyset\right\} \)) וניקח פונקציית בחירה \( f \) על האוסף הזה, כלומר נניח שיש לנו פונקציה שמקבלת תת-קבוצה לא ריקה \( B\subseteq A \) ומחזירה \( f\left(B\right)=b\in B \).

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

הנה ההגדרה המרכזית שנזדקק לה: נאמר שלקבוצה \( B\subseteq A \) יש את “תכונה X” אם קיים סדר טוב של \( B \) כך שלכל \( b\in B \) מתקיים \( f\left(A\backslash b^{<}\right) \). במילים אחרות, אם \( f \) מגדירה לנו סדר טוב על \( B \) בצורה הנחמדה שאנחנו מצפים לה: בהינתן כל האיברים שסידרנו עד כה, נבקש מ-\( f \) “תני לנו איבר מ-\( A \) שטרם סידרנו”, היא תחזיר לנו את \( b \) והוא יהיה האיבר הבא בסדר (ולכן קבוצת האיברים שסידרנו עד שהגענו אל \( b \) היא בדיוק \( b^{<} \)). שימו לב שזו לא הגדרה “תהליכית” כך שאנחנו לא צריכים לדבר על רקורסיות על סופיות ושאר ירקות, אבל מצד שני אם נוכיח של-\( A \) עצמה יש את תכונה X, ניצחנו.

האם בכלל יש קבוצות שמקיימות את תכונה X? ובכן, \( \emptyset \) מקיימת אותה באופן ריק, פשוט כי תכונה X מנוסחת בתור “לכל \( b\in B \)…” וב-\( \emptyset \) אין איברים ואפשר “לסדר אותה בסדר טוב” ריק.

בנוסף, לכל קבוצה \( B\subset A \) ששונה מ-\( A \) ומקיימת את תכונה X, אפשר להרחיב אותה באופן טבעי כך שתמשיך לקיים את תכונה X: נבנה את \( B\cup\left\{ f\left(A\backslash B\right)\right\} \), כלומר, נבקש את האיבר “הבא בתור” מ-\( f \), ונרחיב את הסדר הטוב על \( B \) כך שהאיבר הזה יהיה האחרון.

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

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

מה שאני ארצה להראות הוא שאין לקבוצות הרבה גמישות בבואן לקיים את תכונה X; הפונקציה \( f \) מכריחה באופן די קשוח כל קבוצה כזו להשתמש בסדר טוב ספציפי. בניסוח קונקרטי, אם \( B_{1},B_{2}\subseteq A \) הן שתי קבוצות סדורות בסדר טוב שמקיימות את תכונה X ביחס לסדר הטוב הזה, כך ש-\( B_{1}\cong B_{2} \), אז \( B_{1}=B_{2} \) והאיזומורפיזם שלהן הוא הזהות. כלומר, אין כזה דבר, שני סדרים טובים שונים (בין אם על אותה קבוצה ובין אם על קבוצות אחרות) שמאפשרים לקבוצה לקיים את תכונה X.

ההוכחה די פשוטה: ניקח את האיזומורפיזם \( g:B_{1}\to B_{2} \) ונניח שהוא לא פונקציית הזהות, אז יהא \( b\in B_{1} \) האיבר הראשון מבין אלו שמקיימים \( b\ne g\left(b\right) \). המשמעות היא ש-\( b^{<}=g\left(b\right)^{<} \) (כי כל האיברים שקטנים מ-\( b \) עוברים לעצמם בגלל המינימליות של \( b \)).

עכשיו, מכיוון ש-\( B_{1},B_{2} \) מקיימות את תכונת X, המשמעות של זה היא ש-

\( b=f\left(B_{1}\backslash b^{<}\right)=f\left(B_{1}\backslash g\left(b\right)^{<}\right)=g\left(b\right) \)

וזו סתירה להנחה ש-\( b\ne g\left(b\right) \), אז קיבלנו ש-\( g \) היא אכן הזהות.

מה אפשר להסיק מכך? קחו שתי קבוצות \( B_{1},B_{2}\subseteq A \) כלשהן שמקיימות את תכונה X. שתיהן סדורות בסדר טוב כלשהו; המשפט המרכזי שהצגנו קודם אומר שהן או איזומורפיות, או שאחת מהן איזומורפית לקטע התחלתי של השניה. אבל כפי שראינו, בסיטואציה הספציפית שלנו עם תכונה X, אין “איזומורפיזם”. יש רק שוויון. או ש-\( B_{1}=B_{2} \), או שאחת מהן היא קטע התחלתי של השניה. במילים אחרות, כל הקבוצות הללו סדורות באותו סדר טוב.

עכשיו, מה זה סדר טוב? בסופו של דבר זה יחס - קבוצה של זוגות. אם ניקח מכל קבוצה עם תכונה X את הסדר הטוב שלה ונאחד את כל הסדרים הטובים הללו, התוצאה תהיה סדר טוב על איחוד כל הקבוצות הללו, \( C \). כדי לראות שהסדר הזה מקיים את תכונה X, פשוט ניקח \( c\in C \) כלשהו; הוא שייך לאחת מקבוצות ה-X שבאיחוד, והקבוצה הזו כבר מראה שהוא מקיים \( c=f\left(A\backslash c^{<}\right) \). סיימנו!

מה הלאה?

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