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

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

כזכור, יחס שקילות הוא יחס רפלקסיבי, טרנזיטיבי וסימטרי. יחס סדר מתקבל משימור שתי התכונות הראשונות - רפלקסיבי וטרנזיטיבי - אבל משינוי מהותי של תכונת הסימטריה למשהו שכמעט מנוגד לה. בואו נסתכל על הדוגמא הקלאסית: היחס “קטן-שווה”, \( a\le b \). אחד הדברים הבסיסיים שלומדים על היחס הזה הוא שאם הראינו ש-\( a\le b \) וגם הראינו ש-\( b\le a \) אז שני אלו הופכים לשוויון: \( a=b \). זה מועיל בתיכון, וזה מועיל גם במתמטיקה אוניברסיטאית שבה לא כזה נדיר לראות “שרשרת” של אי שוויונות שהסוף וההתחלה שלה זהות, מה שמוכיח שכל האיברים בשרשרת שווים זה לזה (משהו בסגנון \( a\le x\le y\le a \) שמוכיח ש-\( a=x=y \)). לתכונה הזו קוראים אנטי-סימטריות:

1. \( R \) הוא אנטי-סימטרי אם \( \left(a,b\right)\in R \) וגם \( \left(b,a\right)\in R \) גוררים \( a=b \)

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

1. היחס \( R \) הוא "סתם" לא סימטרי אם קיים מקרה כלשהו שבו \( \left(a,b\right)\in R \) אבל \( \left(b,a\right)\notin R \).
2. היחס \( R \) הוא א-סימטרי ("ההפך מסימטרי" אם תרצו) אם \( \left(a,b\right)\in R \) גורר תמיד ש-\( \left(b,a\right)\notin R \). שימו לב שבפרט נובע מכך שלכל \( a \), \( \left(a,a\right)\notin R \) (אז \( R \) לא יכול להיות אפילו לא טיפה רפלקסיבי).
3. היחס \( R \) הוא אנטי-סימטרי אם הוא סוג של פשרה בין הקיצוניות של 2 והפחות-קיצוניות של 1: כמעט תמיד \( \left(a,b\right)\in R \) גורר ש-\( \left(b,a\right)\notin R \) אלא אם \( a=b \).

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

לפני הדוגמאות, עוד נקודה הגדרתית אחת. חוץ מהיחס “קטן-שווה” שאנחנו מכירים מהמספרים ומסומן ב-\( \le \) אנחנו מכירים גם את היחס קטן ממש שמסומן ב-\( < \). מה הקשר ביניהם? \( < \) בסך הכל אומר “קטן ולא שווה” כלומר \( a<b \) פירושו “\( a\le b \) וגם \( a\ne b \)”, ובהתאם \( a\le b \) אומר “או \( a<b \) או \( a=b \)”. כלומר, אם יש לנו את אחד מהיחסים הללו, השני מתקבל ממנו בטבעיות. את \( < \) אפשר לאפיין בתור יחס שהוא טרנזיטיבי וא-רפלקסיבי, כלומר \( \left(a,a\right) \) לא כלול בו לאף איבר. מזה גם נובע שהוא לחלוטין לא סימטרי כי אם \( \left(a,b\right) \) ביחס וגם \( \left(b,a\right) \) ביחס אז טרנזיטיביות גוררת ש-\( \left(a,a\right) \) יהיה ביחס.

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

הדוגמא הראשונה היא היחס “מחלק-את” מעל הטבעיים, שסימנתי בתור \( a|b \). בואו ניזכר בהגדרה: \( a|b \) אם ורק אם קיים \( d\in\mathbb{N} \) כך ש-\( a\cdot d=b \). למה זה יחס סדר? ובכן: רפלקסיביות מתקבלת על ידי בחירת \( d=1 \), וטרנזיטיביות מתקבלת מכך שאם \( a\cdot d_{1}=b \) ו-\( b\cdot d_{2}=c \) אז \( a\cdot\left(d_{1}\cdot d_{2}\right)=c \).

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

הסיבה שיחס החלוקה הוא דוגמא טובה לפתוח איתה את הדיון ביחסי סדר היא שהוא חלקי. למשל, עבור \( 3 \) ו-\( 5 \), לא מתקיים \( 3|5 \) וגם לא מתקיים \( 5|3 \). “אי אפשר להשוות” בין שני האיברים הללו. זה מנוגד לאינטואיציה הרגילה שלנו לפיה \( \le \) הוא יחס שמתקיים בין כל שני מספרים ורק צריך להבין מי אמור להיות בצד ימין ומי אמור להיות בצד שמאל. והנה עוד משהו שמנוגד לאינטואיציה: קחו את 0 ומספר כלשהו \( a \). אנחנו יודעים ש-\( a\cdot0=0 \) תמיד, כלומר \( a|0 \) לכל מספר \( a \). אם לרגע הייתי משתמש בסימון \( \le \) כדי לתאר את יחס החלוקה ולא בסימון \( | \), מה שהראיתי כרגע היה אומר ש-\( a\le0 \) לכל \( a \), כלומר \( 0 \) הוא המספר “הגדול ביותר” על פי היחס הזה (הגדרה פורמלית של איבר מקסימלי שכזה תבוא עוד מעט). מוזר? בהחלט. מה גם שמייד אחרי 0 בא 1 שעבורו מתקיים דווקא ההפך: \( 1|a \) לכל \( a \) ולכן הוא “הקטן ביותר”. המסקנה: אפשר להגדיר על אותה קבוצה הרבה יחסי סדר שונים והם יתנהגו בצורות שונות לגמרי.

אם אנחנו כבר כאן בואו נגדיר את \( \le \) “הרגיל” עבור הטבעיים. ההגדרה שלו תהיה דומה לזו של יחס החלוקה בצורה חשודה: \( a\le b \) אם ורק אם קיים \( d\in\mathbb{N} \) כך ש-\( a+d=b \). זו אותה הגדרה כמו יחס החלוקה רק עם פעולת החיבור במקום פעולת הכפל. בהתאם, גם ההוכחה שזה יחס סדר היא דומה - עבור רפלקסיביות משתמשים ב-\( d=0 \), טרנזיטיביות תתבסס על \( a+\left(d_{1}+d_{2}\right)=c \) ואילו אנטי-סימטריות תנבע מכך שאם \( d_{1}+d_{2}=0 \) בטבעיים אז \( d_{1}=d_{2}=0 \) (עבור השלמים ניתן להגדיר את \( \le \) בדיוק באותה צורה; עדיין דורשים ש-\( d \) יהיה טבעי ולא שלם, וזה עובד). אלא שכאן, תמיד מתקיים \( a\le b \) או \( b\le a \); פשוט מסתכלים על \( a-b \). אם הוא אי-שלילי, בוחרים \( d=a-b \). אם הוא שלילי, בוחרים \( d=b-a \). אי אפשר לעשות תעלול דומה עם חלוקה כי אם \( \frac{a}{b} \) אינו שלם גם \( \frac{b}{a} \) לא יהיה שלם.

אם כן, היחס “קטן-שווה” הרגיל על הטבעיים הוא מה שנקרא יחס סדר מלא (או לינארי; שמות שונים לאותו דבר בדיוק). פורמלית, יחס סדר \( \le \) הוא מלא אם לכל שני איברים \( a,b \) או ש-\( a\le b \) או ש-\( b\le a \). אגב, אפשר להגדיר את אותו יחס סדר על הטבעיים בדרך שונה לגמרי אם זוכרים את האופן שבו הגדרתי אותם: כזכור, הרעיון הוא ש-\( n\triangleq\left\{ 0,1,2,\dots,n-1\right\} \). בצורה הזו הטבעיים הם קבוצות ואז אפשר להגדיר \( a<b \) אם ורק אם \( a\in b \), ואז להגדיר \( a\le b \) אם ורק אם \( a<b \) או \( a=b \). נחזור לעניין הזה בהמשך כשנדבר על סודרים.

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

אני אומר ש-\( x\in A \) הוא מינימלי ב-\( A \) אם לא קיים \( a\in A \) ששונה מ-\( x \) כך ש-\( a\le x \). אני אומר ש-\( x\in A \) הוא איבר ראשון ב-\( A \) אם לכל \( a\in A \) מתקיים \( x\le a \). מה ההבדל בין שתי ההגדרות? הן נשמעות כמעט זהות, והן אכן זהות אם \( A \) היא קבוצה סדורה בסדר מלא. אבל אם \( A \) לא סדורה בסדר מלא בהחלט יכולים להיות איברים מינימליים שאינם ראשונים. למשל, נסתכל על \( A=\mathbb{N}\backslash\left\{ 0,1\right\} \) עם יחס החלוקה (כלומר, הסרנו מ-\( \mathbb{N} \) את האיברים 0,1). גם \( 3 \) וגם \( 5 \) הם איברים מינימליים - אין אף מספר ב-\( A \) שמחלק אותם. מצד שני, 3 הוא בוודאי לא איבר ראשון ב-\( A \) כי לא מתקיים \( 3|5 \), ואם 3 היה ראשון ב-\( A \) אז היה צריך להתקיים \( 3|a \) לכל \( a\in A \). אם לעומת זאת אני אסתכל על הקבוצה \( \mathbb{N} \) עם יחס החלוקה, אז יש בה איבר ראשון - 1. שימו לב שהוא יחיד; זה לא במקרה. אם בקבוצה \( A \) יש שני איברים ראשונים \( x,y \) אז מהגדרת איבר ראשון מתקיים \( x\le y \) (כשחושבים על \( x \) בתור איבר ראשון ועל \( y \) בתור איזה שהוא איבר של \( A \)) וגם \( y\le x \) (כשמחליפים את התפקידים שלהם) ומאנטי-סימטריות, \( x=y \).

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

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

ניקח את \( P \) להיות הקבוצה \( \mathbb{Q} \) עם יחס הסדר הרגיל על הרציונליים. בקבוצה הזו אפשר להסתכל על \( A=\left\{ q\in\mathbb{Q}\ |\ 0\le q\right\} \) של כל הרציונליים האי-שליליים. לקבוצה הזו אין חסם מלעיל כי לכל מספר רציונלי שתציעו, אפשר למצוא ב-\( A \) מספר רציונלי גדול יותר. אם תרצו להגיד ש”אינסוף הוא חסם מלעיל” אני לא פוסל את זה - אבל “אינסוף” הוא לא איבר של \( P \) ולכן לא רלוונטי לדיון, שעוסק רק בחסמים מלעיל של \( A \) בתוך \( P \).

הנה קבוצה בעייתית אחרת - \( A=\left\{ q\in\mathbb{Q}\ |\ q<\sqrt{2}\right\} \) שכוללת את כל המספרים הרציונליים שקטנים משורש 2. לקבוצה הזו יש המון חסמים מלעיל - למשל 2 הוא חסם מלעיל. או \( \frac{3}{2} \) (כי \( \sqrt{2} \) הוא בערך \( 1.41 \) משהו וזה כל מה שאני זוכר). הבעיה היא שאין חסם מלעיל מינימלי. הנה הסבר בנפנוף ידיים למה אין כזה. נסתכל על חסם מלעיל כלשהו לקבוצה הזו, אסמן אותו ב-\( b \) כמו קודם. עכשיו, \( b\ne\sqrt{2} \) כי אנחנו יודעים ש-\( \sqrt{2} \) איננו מספר רציונלי. לכן הקטע \( \left(\sqrt{2},b\right) \) הוא לא ריק ואפשר למצוא בתוכו עוד רציונלי כי יש משפט שאומר שבין כל שני מספרים ממשיים אפשר למצוא רציונלי (שימו לב שאני מניח פה ש-\( \sqrt{2}<b \) וזה אכן הכרחי כי אם \( b<\sqrt{2} \) אז אפשר למצוא איבר של \( A \) בתוך \( \left(b,\sqrt{2}\right) \) בסתירה לכך ש-\( b \) חסם מלעיל).

לעומת זאת, הקבוצה \( A=\left\{ q\in\mathbb{Q}\ |\ q<1\right\} \) כן חסומה מלעיל וכן יש איבר מינימלי לקבוצת החסמים מלעיל שלה - פשוט 1. כאן נכנס לפעולה הרעיון של דדקינד: הוא אומר - למה שלא נגדיר את הממשיים בתור קבוצות שכאלו של רציונליים, ש”מתקרבות” לאיזה מספר שאמור להיות החסם מלעיל המינימלי שלהן אבל לא מגיעות עד אליו?

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

עכשיו, איך דדקינד מגדיר את היצורים שלו? אי אפשר לכתוב משהו כמו \( \left\{ q\in\mathbb{Q}\ |\ q<\sqrt{2}\right\} \), זו הרי הנחת המבוקש (כרגע \( \sqrt{2} \) הוא ביטוי חסר משמעות עבורנו). אפשר להתחכם ולכתוב \( \left\{ q\in\mathbb{Q}\ |\ q^{2}<2\right\} \) וזה יעבוד, אבל אז איך מבטאים מספרים כמו \( \pi \)? צריך איזו הגדרה כללית יותר. מה שדדקינד מגדיר נקרא חתך דדקינד ואפשר לחשוב עליו בתור חלוקה של המספרים הרציונליים לשני קטעים כך שנקודת החיתוך היא בדיוק המספר שאותו מגדירים. בשביל הפורמליזם מספיק לי לתאר רק את אחד מהקטעים.

אז אני מגדיר חתך דדקינד בתור קבוצה \( A\subseteq\mathbb{Q} \) שהיא

1. לא ריקה.
2. לא כל \( \mathbb{Q} \).
3. סגורה כלפי מטה, כלומר אם \( a\in A \) ו-\( b\in\mathbb{Q} \) הוא רציונלי כלשהו המקיים \( b<a \) אז \( b\in A \).
4. ללא איבר מקסימלי, כלומר אם \( a\in A \) אז קיים \( b\in A \) כך ש-\( a<b \).

קבוצת כל החתכים מכונה עכשיו בשם \( \mathbb{R} \), והופס - קיבלנו את המספרים הממשיים. האם הקבוצה הזו קיימת בכלל? ובכן, היא תת-קבוצה של \( 2^{\mathbb{Q}} \) ולכן אקסיומת ההפרדה תיתן לנו אותה, בהינתן שאפשר לנסח את ארבע התכונות שלעיל בלוגיקה פורמלית - ואפשר, זה לא קשה. כמעט עשיתי את זה כאן באופן מלא. רק צריך הגדרה ל-\( < \) עבור רציונליים. אם כבר יש לי הגדרה כזו עבור \( \mathbb{Z} \) אפשר להשתמש בה: אינטואיטיבית, \( \frac{a}{b}<\frac{x}{y} \) כאשר המכנים \( b,y \) חיוביים אם \( ay<bx \) כי פשוט כופלים את שני אגפים הביטוי ב-\( by \). אז אפשר להגדיר את היחס בצורה הזו, אבל זה מעלה סכנה לא צפויה - מה שעשינו בפועל הוא להגדיר יחס על קבוצה של מחלקות שקילות על פי נציגים של מחלקות השקילות, וכדי שזו תהיה הגדרה תקינה צריך להראות שהיא איננה תלויה בנציגים.

למעשה, ההגדרה כן תלויה בנציגים ואמרתי את זה בזריזות: אמרתי שאני אקח שני ייצוגים לשברים שבהם המכנים הם חיוביים. זה לא המקרה הכללי. למשל, \( \frac{1}{2} \) ניתן לייצוג גם בתור \( \frac{-1}{-2} \). ועכשיו, \( 1\cdot\left(-2\right)<1\cdot\left(-1\cdot\right) \) כך שההגדרה של “\( ay<bx \) אומר ש-\( \frac{a}{b}<\frac{x}{y} \)” הייתה נותנת לנו \( \frac{1}{1}<\frac{-1}{-2}=\frac{1}{2} \) אלמלא ההגבלה שנתתי. ההגבלה שלי באה לומר שבואו פשוט נתעלם מחלק מהנציגים - נגדיר את היחס על פי בחירה חצי-קנונית שכזו של נציגים (הייצוג הכי קנוני למספר רציונלי הוא זה שבו המכנה חיובי והמונה והמכנה זרים, כלומר אין להם מחלק משותף גדול מ-1).

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