תורת הקבוצות - יחסי שקילות

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

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

בואו נגדיר את זה פורמלית, עבור יחס \( R\subseteq A\times A \) כללי:

1. \( R \) הוא רפלקסיבי אם לכל \( a\in A \) מתקיים \( \left(a,a\right)\in R \).
2. \( R \) הוא סימטרי אם \( \left(a,b\right)\in R \) גורר \( \left(b,a\right)\in R \).
3. \( R \) הוא טרנזיטיבי אם \( \left(a,b\right)\in R \) וגם \( \left(b,c\right)\in R \) גורר \( \left(a,c\right)\in R \).

יחס שהוא בו זמנית רפלקסיבי, סימטרי וטרנזיטיבי נקרא יחס שקילות מעל \( A \).

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

הנה מקרה קצת יותר מתוחכם - חלוקה ב-3. כמקודם, אני יכול לפרק לשתי קבוצות של “מתחלקים ב-3” ו”לא מתחלקים ב-3”, אבל משתלם לי הרבה יותר לחלק ל-3 קבוצות, על פי השארית בחלוקה ב-3 של המספר. הנה דוגמאות: אם נחלק את 13 ב-3, התוצאה תהיה מנה 4 ושארית 1, כלומר \( 4\times3+1=13 \). אם נחלק את 15 ב-3 נקבל מנה 5 ושארית 0. אם נחלק את \( 11 \) ב-3 נקבל שארית 2. שימו לב שהשאריות הן מספרים בין 0 ל-2; שארית גדולה או שווה ל-3 לא ייתכן, כי במקרה כזה אפשר “לגנוב” מהשארית כדי להגדיל עוד קצת את המנה (כלומר- במקום לומר ש-13 זה \( 3\times3+4 \) אנחנו לוקחים עוד 3 מהשארית ומגדילים את המנה ל-4). את יחס השקילות הזה אני אכנה שקילות מודולו 3.

אני יכול כעת לנסח את יחס השקילות שלי בתור \( \left(a,b\right)\in R \) אם ורק אם ל-\( a \) ו-\( b \) אותה שארית בחלוקה ל-3. אבל זה ניסוח קצת מילולי ומסורבל. הנה משהו פשוט יותר. בפוסט הקודם הגדרתי את יחס החלוקה שעוד נפגוש שוב גם בפוסט הזה. סימנתי אותו \( a|b \). המשמעות שלו היא זו: קיים \( d\in\mathbb{Z} \) (שימו לב שכאן אני מרשה ל-\( d \) להיות שלילי) כך ש-\( ad=b \). כעת, בעזרת יחס החלוקה אני יכול להגדיר את היחס החדש שלי: אסמן \( a\equiv_{3}b \) אם ורק אם \( 3|a-b \). למשל, \( 5\equiv_{3}11 \) כי \( 5-11=-6 \) ולכן \( d=-2 \) יעשה את העבודה.

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

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

טרנזיטיביות היא טיפה יותר מעניינת. אם \( a\equiv_{3}b \) אז \( a-b=3d_{1} \). אם בנוסף \( b\equiv_{3}c \) אז \( a-c=3d_{2} \). עכשיו נחבר את שתי המשוואות הללו ונקבל

\( a-c=\left(a-b\right)+\left(b-c\right)=3d_{1}+3d_{2}=3\left(d_{1}+d_{2}\right) \)

וזה מסיים את ההוכחה ואנחנו רואים ש-\( \equiv_{3} \) הוא יחס שקילות.

תכף נחזור לדבר על \( \equiv_{3} \) ספציפית, אבל בואו ננצל את ההזדמנות לראות כמה אפשר להכליל את ההוכחה הזו. ראשית, אין שום קסם במספר 3: לכל \( n \) טבעי ההוכחה ש-\( \equiv_{n} \) הוא יחס שקילות תעבוד באותו אופן בדיוק. שנית, שימו לב באילו תכונות של מספרים שלמים השתמשנו כאן: עבור הרפלקסיביות השתמשנו בכך ש-0 הוא מספר שלם (“קיום איבר אדיש לחיבור”); עבור הסימטריה בכך שאם \( d \) שלם גם \( -d \) שלם (“סגירות לנגדי”); ועבור טרנזיטיביות השתמשנו בכך שאם \( d_{1},d_{2} \) שלמים כך גם \( d_{1}+d_{2} \) (“סגירות לחיבור”). התכונות הללו ניתנות להכללה באופן טבעי במסגרת של תורת החבורות וזה מוליד את המושג החשוב של חבורות מנה שכבר דיברתי עליו בבלוג; לא אכנס אליו כאן.

עכשיו, בואו נעשה עבור \( \equiv_{3} \) את הדבר הבא: ניקח את 0 ונכתוב את כל מי ששקול ל-0 ביחס הזה. מכיוון ש-0 מתחלק ב-3 ללא שארית, מי ששקולים לו הם בדיוק המספרים שמתחלקים ב-3, כלומר נקבל

\( \left\{ 0,3,6,9,\dots\right\} \)

עכשיו עבור 1. מהדוגמא של 0 אולי כבר קיבלתם את התחושה לפיה כדי לקבל את מי ששקול ל-1 כדאי להוסיף 3 כל הזמן. נקבל:

\( \left\{ 1,4,7,10,\dots\right\} \)

ועבור 2 נקבל

\( \left\{ 2,5,8,11\dots\right\} \)

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

זו סיטואציה כל כך נפוצה וחשובה כשיש לנו יחסי שקילות, שנותנים לה שם. לכל קבוצה כזו של “כל האיברים ששקולים למישהו” קוראים מחלקת שקילות של יחס השקילות. לאוסף של כל מחלקות השקילות קוראים קבוצת המנה של יחס השקילות. בואו נמצא דרך נוחה לסמן את זה. אם יש לי יחס שקילות \( R \) מעל \( A \) ו-\( a\in A \) הוא איבר של \( A \), אני מסמן בתור \( \left[a\right]_{R} \) את מחלקת השקילות של \( a \), כלומר את

\( \left[a\right]_{R}\triangleq\left\{ b\in A\ |\ \left(a,b\right)\in R\right\} \)

על פי רוב אני פשוט אכתוב \( \left[a\right] \) כשהיחס ברור מההקשר. בדוגמא של \( \equiv_{3} \):

\( \left[0\right]=\left\{ 0,3,6,9,\dots\right\} \)

\( \left[1\right]=\left\{ 1,4,7,10,\dots\right\} \)

\( \left[2\right]=\left\{ 2,5,8,11\dots\right\} \)

שימו לב שבאותה מידה גם \( \left[8\right]=\left\{ 2,5,8,11\dots\right\} \), למשל. כל איבר ששייך למחלקת השקילות יכול לתאר אותה ככה. אם אני כותב מחלקת שקילות בתור \( \left[a\right] \), אני אומר ש-\( a \) הוא נציג של המחלקה.

עכשיו קל לתאר את קבוצת המנה. אם \( A \) היא קבוצה ו-\( R \) יחס שקילות מעליה, אז קבוצת המנה היא

\( A/R\triangleq\left\{ \left[a\right]_{R}\ |\ a\in A\right\} \)

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

\( \mathbb{N}/\equiv_{3}=\left\{ \left[0\right],\left[1\right],\left[2\right],\left[3\right],\left[4\right],\left[5\right],\dots\right\} =\left\{ \left[0\right],\left[1\right],\left[2\right]\right\} \)

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

נקודה אחרונה לפני שנעבור לשימוש של זה: אני עדיין רוצה להשתכנע שהדבר הזה קיים בכלל. אחרי האסון של הפרדוקס של ראסל, כל בניה של קבוצה חדשה היא משהו שאני מנסה לראות איך הוא נובע ישירות מהאקסיומות של תורת הקבוצות. יחסי שקילות בוודאי קיימים במובן זה שראינו שיחסים באופן כללי קיימים: כלומר, אם \( A \) קיימת גם \( A\times A \) קיימת ולכן גם תת-קבוצות של \( A\times A \) שאני יכול לתאר עם קריטריון ברור קיימות. בנוסף, אם \( a\in A \) הוא איבר אז הקבוצה \( \left[a\right]_{R} \) היא תת-קבוצה של \( A \) שמוגדרת עם קריטריון ברור ולכן גם היא קיימת. אבל מה עם קבוצת המנה, \( A/R \)? ובכן, גם זה קל: \( A/R \) היא אוסף של תת-קבוצות של \( A \), ולכן היא בעצמה תת-קבוצה של קבוצת החזקה \( \mathcal{P}\left(A\right) \). כלומר, אקסיומת קבוצת החזקה עושה את העבודה במקרה הזה.

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

ובכן, בפוסט הקודם אמרתי שאפשר “להגדיר” את הרציונליים כך בצורה שלא עובדת: \( \mathbb{Q}\triangleq\left\{ \frac{a}{b}\ |\ a,b\in\mathbb{Z},b\ne0\right\} \). הצורה הזו לא עובדת כי הביטוי \( \frac{a}{b} \) לא באמת מוגדר - זה לא אובייקט שקיים בעולם המתמטי שאנחנו מכירים, ויש בו הנחות מובלעות כמו זו ש-\( \frac{1}{2}=\frac{2}{4} \). אז הנה משהו פורמלי יותר. אני אגדיר את הקבוצה \( A=\left\{ \left(a,b\right)\ |\ a,b\in\mathbb{Z},b\ne0\right\} \) של זוגות סדורים (היא בוודאי קיימת; זו תת קבוצה של \( \mathbb{Z}\times\mathbb{Z} \)). על הקבוצה הזו אגדיר יחס שקילות שיזהה דברים כמו \( \frac{1}{2}=\frac{2}{4} \).

לשם כך, בואו נשאל את עצמנו שאלה - באופן כללי, מתי \( \frac{a}{b}=\frac{c}{d} \)? החשבון שלומדים בבית הספר היסודי אומר לנו שאפשר לכפול את שני האגפים ב-\( bd \) ולקבל \( ad=bc \), אז זה יהיה יחס השקילות שלי: \( R=\left\{ \left(\left(a,b\right),\left(c,d\right)\right)\ |\ ad=bc\right\} \) (שימו לב - זה יחס שקילות על הקבוצה \( A \) שהיא מראש קבוצה של זוגות; כלומר, \( R \) הוא אוסף זוגות של זוגות). צריך כמובן להשתכנע בכך ש-\( R \) הוא יחס שקילות. הוא רפלקסיבי כי \( ab=ba \) ולכן \( \left(\left(a,b\right),\left(a,b\right)\right)\in R \). הוא סימטרי כי אם \( ad=bc \) אז גם \( cb=da \), והוא טרנזיטיבי כי… כי… טוב, אולי כדאי שאקח עוד פסקה בשביל זה ונעבוד במסודר.

אם \( \left(a,b\right) \) שקול ל-\( \left(c,d\right) \) אז \( ad=bc \).

אם \( \left(c,d\right) \) שקול ל-\( \left(x,y\right) \) אז \( cy=dx \).

אנחנו רוצים לראות ש-\( ay=bx \). אז בואו ננסה “לחשב” את זה. מכיוון ש-\( d\ne0 \) אפשר לחלק בו ולקבל מ-\( ad=bc \) את \( a=\frac{bc}{d} \). על כן \( ay=\frac{bcy}{d} \) ומכיוון ש-\( cy=dx \) נקבל \( \frac{bcy}{d}=\frac{bdx}{d}=bx \), כפי שרצינו. זה מסיים גם את הטרנזיטיביות.

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

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