תורת הקבוצות - מבוא ליחסים

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

מה אנחנו עושים עם מספרים טבעיים? ובכן, אנחנו מחברים ומחסרים וכופלים ומחלקים אותם וכאלה, אבל עוד לפני זה אנחנו משווים אותם. כנראה שנלמד ש-2 גדול מ-1 עוד לפני שנלמד ש-1 ועוד 2 שווה 3. במתמטיקה אנחנו מסמנים השוואה כזו ב-\( \le \). בדוגמא שלנו, \( 1\le2 \). מה זה ה-\( \le \) הזה באופן כללי? איך אני קורא לו? איך אני מגדיר אותו?

ובכן, \( \le \) (קראו את זה “קטן-שווה”) הוא מה שנקרא במתמטיקה יחס. זה משהו שבא לתאר קשר כלשהו בין זוג אובייקטים - קשר שיכול להתקיים, או לא להתקיים. אבל איך אני מגדיר את הקשר הזה? ובכן, הנה דרך פורמלית לעשות זאת: \( a\le b \) אם ורק אם קיים \( n\in\mathbb{N} \) כך ש-\( a+n=b \). אם כן, מהו בעצם היחס \( \le \), פורמלית? האם הוא המחרוזת “\( a\le b \) אם ורק אם קיים \( n\in\mathbb{N} \) כך ש-\( a+n=b \)”? זה קצת… נפנוף ידיים? ומה עם זה שבכלל לא הגדרתי את \( + \) עדיין?

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

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

כבר אמרתי מה זה זוג סדור, אבל בואו ניזכר בזה מחדש: אני מסמן זוג סדור ב-\( \left(x,y\right) \) והרעיון הוא ש-\( \left(x,y\right)=\left(a,b\right) \) אם ורק אם \( x=a \) וגם \( y=b \). ראיתי שאפשר “לממש” זוג סדור על ידי קבוצות, בעזרת הבניה הקצת-מתוחכמת \( \left(a,b\right)\triangleq\left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \). בפוסט הקודם ראינו את אקסיומת הזיווג שבעזרתה אפשר להראות שאם \( a,b \) קיימים אז גם \( \left(a,b\right) \) קיים, כך ששאלת הקיום של זוגות סדורים לא ממש מוטלת בספק. עם זאת, שאלת הקיום של קבוצה של זוגות סדורים זה כבר עניין אחר - ראינו שבעזרת חלק מהאקסיומות אפשר להוכיח לכל מספר טבעי \( n \) שהוא קיים, אבל בשביל להוכיח את הקיום של \( \mathbb{N} \) - קבוצת כל המספרים הטבעיים - היינו זקוקים לאקסיומה נפרדת. בואו נראה אם צריך עוד אחת גם כאן.

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

\( A\times B\triangleq\left\{ \left(a,b\right)\ |\ a\in A,b\in B\right\} \)

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

בואו נכתוב שוב את \( A\times B \) אבל הפעם בלי הסוגריים העגולים הללו שמסתירים מאיתנו את הלכלוך:

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

מה יש לנו פה? \( A\times B \) היא קבוצה שאבריה הן בעצמן קבוצות - קבוצות מהצורה \( \left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \). כלומר, קבוצות שהאיברים שלהן הן בעצמן קבוצות. עכשיו, איפה קבוצה כמו \( \left\{ a,b\right\} \) “חיה”? על פי ההגדרה, \( \left\{ a,b\right\} \in\mathcal{P}\left(A\cup B\right) \), כאשר \( \mathcal{P} \) הוא הסימון שלי לקבוצת החזקה; על פי ההגדרה, \( \mathcal{P}\left(X\right) \) הוא אוסף כל תתי-הקבוצות של \( X \). במקרה שלנו, \( \left\{ a,b\right\} \) היא תת-קבוצה של \( A\cup B \) ולכן שייכת ל-\( \mathcal{P}\left(A\cup B\right) \). בדומה גם \( \left\{ a\right\} \) שייך ל-\( \mathcal{P}\left(A\cup B\right) \).

במילים אחרות, קיבלנו שהקבוצה \( \left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \) היא בעלת התכונה שכל איבר שלה שייך ל-\( \mathcal{P}\left(A\cup B\right) \). דרך אחרת לסמן זאת: \( \left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \subseteq\mathcal{P}\left(A\cup B\right) \). כעת, אם \( \left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \) היא תת-קבוצה של \( \mathcal{P}\left(A\cup B\right) \) זה אומר שהיא איבר של קבוצת החזקה של הדבר הזה: \( \left\{ \left\{ a\right\} ,\left\{ a,b\right\} \right\} \in\mathcal{P}\left(\mathcal{P}\left(A\cup B\right)\right) \).

אם כן, ראינו ש-\( A\times B \) היא קבוצה של איברים, כך שכל אחד מהאיברים הללו שייך ל-\( \mathcal{P}\left(\mathcal{P}\left(A\cup B\right)\right) \). המסקנה? \( A\times B \) היא תת-קבוצה של \( \mathcal{P}\left(\mathcal{P}\left(A\cup B\right)\right) \), וזה מה שרצינו להראות. המסקנה: הקיום של \( A\times B \) נובע מהקיום של \( A,B \) ומאקסיומות הזיווג, האיחוד, החזקה וההפרדה. בפרט, למרבה השמחה, לא נזקקנו לאקסיומה חדשה פה. תחת זאת ראינו המחשה ראשונה ל”כוח” שיש לקבוצת החזקה - שתי הפעלות של \( \mathcal{P} \) על הקבוצה \( A\cup B \) יצרו לנו עולם עשיר של קבוצות שיכולנו לקחת ממנו את מה שנוח לנו כדי למדל זוגות סדורים.

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

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

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

ראשית, מה זה אומר “עותק של \( \mathbb{N} \) שממנו הוסר 0”? זה מושג חדש שטרם דיברתי עליו - הפרש של קבוצות. הנה ההגדרה הכללית: \( A\backslash B \) זו קבוצה שכוללת את אברי \( A \) למעט אלו שהם גם אברי \( B \). פורמלית:

\( A\backslash B\triangleq\left\{ a\in A\ |\ a\notin B\right\} \)

מההגדרה הזו ברור מייד שאם \( A,B \) קיימות אז גם \( A\backslash B \) על פי אקסיומת ההפרדה, כך שפעולת ההפרש היא עוד פעולה חוקית סטנדרטית בתורת הקבוצות. בפרט אפשר להגדיר כעת \( \mathbb{N}^{+}\triangleq\mathbb{N}\backslash\left\{ 0\right\} \) ונקבל את הקבוצה שכיוונתי אליה (יש שמועות זדוניות לפיהן קיימים - כן כן! - כאלו אשר מגדירים את המספרים הטבעיים מראש ללא 0! הייתם מאמינים?!)

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

במקרה הנוכחי, אפשר לעשות את זה בדיוק עבור \( \mathbb{N} \) ו-\( \mathbb{N}^{+} \) שלנו ונקבל את הקבוצה \( \left\{ \left(n,0\right)\ |\ n\in\mathbb{N}\right\} \cup\left\{ \left(n,1\right)\ |\ n\in\mathbb{N}^{+}\right\} \). כעת, הסימון המקובל ל-\( \left(n,0\right) \) יהיה פשוט \( n \) בעוד שהסימון המקובל של \( \left(n,1\right) \) יהיה פשוט \( -n \) וקיבלנו את \( \mathbb{Z} \) שלנו. זו לא הגדרה שלמה; הקבוצה הזו אמורה לבוא גם עם פעולות חשבון - חיבור, חיסור, כפל, חילוק, העלאה בחזקה וכדומה - אבל אני לא מדבר עליהן כאן; זה מתאים יותר לקורס באלגברה. סמכו עלי שזה אפשרי, אחרי שנתאר את המושג המתמטי (פונקציה) שבעזרתו מגדירים “פעולות”.

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

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

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