תורת הקבוצות - הרכבת פונקציות ויחסים

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

ברמת הסימון זה פשוט מאוד: אם \( f,g \) הן פונקציות, אני יכול לכתוב \( g\left(f\left(x\right)\right) \) במשמעות של “מפעילים את \( g \) על התוצאה של הפעלת \( f \) על \( x \)”. כדי לפשט את הסימון אפשר להשמיט את הסוגריים ופשוט לכתוב \( gf\left(x\right) \) באותה משמעות בדיוק. לפעמים גם כותבים \( g\circ f\left(x\right) \) במשמעות הזו, אבל אני לא אוהב את הסימון הזה ועוד נחזור לכך בהמשך. לסיום, אפשר לכתוב פשוט \( gf \) כדי לתאר את הפונקציה שמתקבלת מההרכבה הזו של \( g \) על \( f \): כלומר הפונקציה שלכל \( x \) מחזירה את \( g\left(f\left(x\right)\right) \).

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

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

בואו נראה כמה דוגמאות פשוטות. למשל, \( f,g:\mathbb{R}\to\mathbb{R} \) שמוגדרות על ידי \( f\left(x\right)=x^{2} \) ו-\( g\left(x\right)=x+3 \). קל לראות ש-\( gf\left(x\right)=x^{2}+3 \) ו-\( fg\left(x\right)=\left(x+3\right)^{2}=x^{2}+6x+9 \), וזה גם מראה לנו שהרכבת פונקציות היא לא קומוטטיבית: כלומר, \( fg \) ו-\( gf \) יהיו בדרך כלל פונקציות שונות (ושימו לב שלא בהכרח שתיהן קיימות בכלל - זה תלוי בתחומים והטווחים של הפונקציות).

הנה דוגמא קצת יותר מטורללת: ניקח בתור \( f \) את הפונקציה שעושה איחוד של קבוצות - כלומר, הקלט שלה יהיה זוג של קבוצות והפלט שלה יהיה קבוצה בודדת. פורמלית, אם \( U \) הוא “העולם” שלנו שכל הקבוצות הרלוונטיות הן תת-קבוצות שלו, אז \( f:2^{U}\times2^{U}\to2^{U} \) זו הדרך שלי לכתוב ש-\( f \) לוקחת זוג (זה ה-\( \times \)) של תת-קבוצות של \( U \) (זה ה-\( 2^{U} \)) ומחזירה תת-קבוצה של \( U \), ו-\( f \) מוגדרת על ידי \( f\left(A,B\right)=A\cup B \). עכשיו, ניקח בתור \( g \) את הפונקציה שמקבלת קבוצה בודדת (לא זוג!) ומחזירה את קבוצת החזקה שלה, כלומר \( g\left(A\right)=2^{A} \). אז \( gf\left(A,B\right)=2^{A\cup B} \) ואילו \( fg \) בכלל לא מוגדרת.

עכשיו בואו נחזור שניה לפוסט הקודם. ראינו שם שאם \( f:A\to B \) היא פונקציה חד-חד-ערכית ועל, אז קיימת פונקציה \( f^{-1}:B\to A \) בעלת התכונה הבאה: \( f\left(x\right)=y \) אם ורק אם \( f^{-1}\left(y\right)=x \). קל לראות שההרכבה מקיימת \( f^{-1}f\left(x\right)=x \), וזו הזדמנות להציג טרמינולוגיה חדשה.

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

עכשיו, שימו לב למשהו טריקי קצת. מהי \( ff^{-1} \)? גם זו פונקצית הזהות, אבל איזו פונקציית זהות? אם תחשבו על זה רגע תראו ש-\( ff^{-1}=I_{B} \) . זו פונקציית הזהות על קבוצה אחרת, כי הפכנו את הסדר בין הקלטים לפלטים (\( ff^{-1} \) היא פונקציה שבה \( f^{-1} \) פועלת ראשונה, ולכן הקלט הוא מתוך \( B \)).

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

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

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

נניח שנתונים לנו שני יחסים, \( R,S \), כך ש-\( R\subseteq A\times B \) ו-\( S\subseteq B\times C \). אפשר לתאר אותם גרפית בצורה הזו:

באיור הזה הקבוצות \( A,B,C \) מיוצגות כולן על ידי אליפסות עם נקודות בתוכן - כל נקודה מייצגת איבר של הקבוצה. את העובדה ש-\( \left(a,b\right)\in R \) אני מייצג על ידי חץ שיוצא מ-\( a \) ונכנס אל \( b \) (ובדומה בתמונה גם עשיתי חץ מ-\( b\in B \) אל \( c\in C \) כדי להמחיש ש-\( \left(b,c\right)\in S \)). חשוב היה לי להדגיש שהיחסים \( R,S \) הללו הם לא בהכרח פונקציות, אז כללתי באיור נקודות ש”מקלקלות” את התכונות של פונקציות: יש נקודה שממנה יוצאים שני חצים (מקלקל את ה”יחידות”) ונקודה שממנה לא יוצאים חצים בכלל (מקלקל את ה”קיום”).

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

אחרי כל ההקדמה הזו הנה סוף סוף ההגדרה:

\( R\circ S\triangleq\left\{ \left(a,c\right)\ |\ \exists b\in B:\left(a,b\right)\in R\wedge\left(b,c\right)\in S\right\} \)

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

עכשיו אני צריך בלב כואב לדבר על שיטת הסימון שבחרתי להשתמש בה. אם תסתכלו באיור, אפשר לראות ש-\( R \) היא בצד שמאל ו-\( S \) בצד ימין. זה בכוונה; זה תואם את האופן שבו בתוך זוג סדור כמו \( \left(a,b\right) \) ה”כיוון” הוא מ-\( a \) אל \( b \). זה הוביל אותי לסמן את ההרכבה, \( R\circ S \), בצורה כזו שהאיבר שפועל קודם (\( R \), שמעביר איבר של \( A \) לאיבר של \( B \)) נמצא בצד שמאל. זה הפוך לגמרי לסימון שבו השתמשתי לפני רגע בפוסט הזה כשדיברתי על הרכבת פונקציות. שם, \( gf \) משמעותו הייתה “קודם להפעיל את \( f \) ואז את \( g \)” כי ככה זה עובד עם סימון הפעלת פונקציות: \( g\left(f\left(x\right)\right) \) אומר בדיוק שקודם מפעילים את \( f \) ואז את \( g \).

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

פתרון נפוץ מאוד הוא פשוט להגדיר הרכבת יחסים הפוך, כמו הרכבת פונקציות: \( S\circ R \) יתאר את מה שכתבתי עד כה למעלה. פתרון אחר, שבו אני נוקט, הוא פשוט לא לסמן הרכבת פונקציות עם \( \circ \) ולשמור את הסימן הזה להרכבת יחסים (כלומר, \( f\circ g \) יהיה התיאור שלי להרכבת הפונקציות \( f,g \) כשאני חושב עליה בתור הרכבת יחסים; זה אומר ש-\( f\circ g\equiv gf \)). כמו רוב ענייני הסימון במתמטיקה זה לא באמת חשוב מה בוחרים, כל עוד זה מוסבר מספיק ברור כדי לא להטעות את הקוראים.

אחרי שסילקנו את זה מהדרך, בואו נעשה קצת כיף!

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

עכשיו, מרגע שהמתמטיקאים ממציאים פעולה, הם רוצים לבצע אותה שוב ושוב כמה שרק אפשרי. במקרה הזה אפשר לדבר על זה כאשר מרכיבים יחס עם עצמו. כדי שאפשר יהיה לעשות את זה, צריך שהתחום והטווח של היחס יהיו אותה קבוצה. כלומר, ניקח יחס \( R\subseteq A\times A \) וכעת אפשר להגדיר \( R^{2}=R\circ R \) ו-\( R^{3}=R\circ R\circ R \) וכדומה. בואו ניתן הגדרה אפילו יותר פורמלית.

ראשית, אני משתמש בסימון של חזקה לא במקרה; זה המשך של האנלוגיה בין הרכבה ובין כפל. אז בואו ניזכר איך מגדירים חזקה טבעית במספרים ממשיים: ראשית מגדירים \( a^{0}\triangleq1 \) לכל \( a \) (כן, אני מגדיר ככה אפילו עבור \( a=0 \)). כעת מגדירים אינדוקטיבית \( a^{n+1}\triangleq a\cdot a^{n} \). המשמעות של לומר “מגדירים אינדוקטיבית” היא שמניחים ש-\( a^{n} \) כבר הוגדר, ועכשיו משתמשים בו כדי להגדיר את \( a^{n+1} \). למשל אם כבר הגדרתי את \( a^{3} \) אז \( a^{4} \) יוגדר להיות \( a^{3}\cdot a \).

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

\( I_{A}\triangleq\left\{ \left(a,a\right)|\ a\in A\right\} \)

ועכשיו אפשר לתת פורמלית את ההגדרה האינדוקטיבית:

\( R^{0}\triangleq I_{A} \)

\( R^{n+1}\triangleq R\circ R^{n} \)

קל לראות ש-\( R^{1}=R \) בהגדרה הזו, בצורה עקבית עם מה שאנחנו רגילים שחזקת 1 עושה. יותר מזה, אפשר לראות גם שחוקי החזקות הרגילים מתקיימים: \( R^{n+m}=R^{n}\circ R^{m} \) ו-\( R^{nm}=\left(R^{n}\right)^{m} \). ההוכחה קצת מייגעת אבל לא באמת שונה מההוכחה עבור חוקי החזקות הרגילים - מילת המפתח שגורמת לדברים להתנהג דומה היא האסוציאטיביות של פעולת ההרכבה.

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

כל זה סבבה, אבל שימו לב שממש לא בהכרח מתקיים \( R\circ R^{-1}=I_{A} \), כלומר \( R^{-1} \) הוא לא הופכי של \( R \) במובן האלגברי של המילה. למשל, אם \( A=\left\{ 1,2\right\} \) ו-\( R=\left\{ \left(1,2\right)\right\} \) אז \( R\circ R^{-1}=\left\{ \left(1,1\right)\right\} \) וזה בוודאי לא \( I_{A} \) כי \( \left(2,2\right)\in I_{A} \), כלומר עשויים להיות חסרים לי איברים. גרוע מכך, עשויים לצוץ לי איברים שלא אמורים להיות שם: למשל אם \( A=\left\{ 1,2,3\right\} \) ו-\( R=\left\{ \left(2,1\right),\left(3,1\right)\right\} \) אני אקבל \( \left(2,3\right)\in R\circ R^{-1} \). זה כמובן מצער מאוד, אבל תראו, קסם! אם \( R \) היא פונקציה הפיכה אז לא קשה להוכיח שכן יתקיים \( R\circ R^{-1}=I_{A} \) וזה מוביל לכך שלפונקציות הפיכות יש מבנה אלגברי מאוד יפה שבו מעורבת פעולה אסוציאטיבית עם איבר אדיש והופכי - מה שנקרא חבורה. אבל זה סיפור אחר ויסופר בפעם אחרת.

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

1. רפלקסיביות של \( R\subseteq A\times A \) פירושה ש-\( \left(a,a\right)\in R \) לכל \( a\in A \). כלומר, זה פשוט אומר ש-\( I_{A}\subseteq R \), או במילים אחרות \( R^{0}\subseteq R \).
2. סימטריה של \( R\subseteq A\times A \) פירושה שאם \( \left(a,b\right)\in R \) אז גם \( \left(b,a\right)\in R \). כלומר, ש-\( R^{-1}\subseteq R \).
3. טרנזיטיביות של \( R\subseteq A\times A \) פירושה שאם \( \left(a,b\right)\in R \) וגם \( \left(b,c\right)\in R \) אז גם \( \left(a,c\right)\in R \). כלומר, זה פשוט אומר ש-\( R^{2}\subseteq R \) (ומכך נובע \( R^{n}\subseteq R \) לכל \( n\ge2 \)).

אם כל התכונות הללו מתקיימות גם יחס אז \( R \) הוא יחס שקילות, והנה קיבלנו דרך אחרת לתאר יחס שקילות, באמצעות חזקות: \( R \) הוא יחס שקילות אם ורק אם \( R^{k}\subseteq R \) לכל \( k\in\mathbb{Z} \).

לסיום, אני לא יכול להתאפק וחייב להכניס פנימה עוד קשר מתמטי שעשוי להישמע מוזר ממבט ראשון אבל כשחושבים עליו רגע הוא מובן מאליו לגמרי - הרכבת יחסים ממש מזכירה כפל מטריצות. אם אתם לא מכירים או זוכרים כפל מטריצות, יש לי פוסט על זה כאן, ועכשיו אניח שכן מכירים את הרעיון, אבל אזכיר את ההגדרה: בכפל מטריצות יש לנו שתי מטריצות \( R,S \) מעל חוג מסויים (כלומר, משהו שמוגדרות עליו פעולות חיבור וכפל). כדי לכפול אותן, צריך ש-\( R \) תהיה ממימד \( n\times m \) ו-\( S \) ממימד \( m\times t \) (כלומר, מספר העמודות של \( R \) יהיה שווה למספר השורות של \( S \)) ואז מגדירים \( \left[RS\right]_{ij}=\sum_{k=1}^{m}\left[R\right]_{ik}\left[S\right]_{kj} \). אני אפילו אכתוב את זה קצת יותר במפורש כך שרואים את פעולות החיבור והכפל:

\( \left[RS\right]_{ij}=\left[R\right]_{i1}\cdot\left[S\right]_{1j}+\cdots+\left[R\right]_{1m}\left[S\right]_{mj} \)

איך זה קשור ליחסים? ובכן, נניח שיש לי יחסים \( R\subseteq A\times B \) ו-\( S\subseteq B\times C \), כך ש-\( A,B,C \) כולן קבוצות סופיות. נסמן את האיברים שלהן: \( A=\left\{ a_{1},\dots,a_{n}\right\} \) ו-\( B=\left\{ b_{1},\dots,b_{m}\right\} \) ו-\( C=\left\{ c_{1},\dots,c_{t}\right\} \). עכשיו אפשר לייצג יחס באמצעות מטריצה:

\( \left[R\right]_{ij}=\begin{cases} 1 & \left(a_{i},b_{j}\right)\in R\\ 0 & \left(a_{i},b_{j}\right)\notin R \end{cases} \)

\( \left[S\right]_{ij}=\begin{cases} 1 & \left(b_{i},c_{j}\right)\in S\\ 0 & \left(b_{i},c_{j}\right)\notin S \end{cases} \)

כלומר, המטריצות הללו חיות מעל החוג \( \mathbb{Z}_{2} \). בחוג הזה יש לנו את פעולות הכפל והחיבור הרגילות מודולו 2, אבל הן לא יעניינו אותנו הפעם אלא מה שאפשר לקבל מהן. בגלל שבחוג הזה מתקיים ש-\( a^{2}=a \) לכל \( a \), קוראים לו חוג בוליאני ואפשר לקבל ממנו משהו שנקרא אלגברה בוליאנית. לא אכנס לפרטים המלאים, אבל הרעיון הוא שאפשר להגדיר פעולות חדשות, \( a\wedge b=a\cdot b \) ו-\( a\vee b=a+b+a\cdot b \) שמתנהגות מאוד נחמד - בהקשר של \( \mathbb{Z}_{2} \) הפעולות הללו מתנהגות כמו “וגם” (עבור \( \wedge \)) ו”או” (עבור \( \vee \)) שאנחנו מכירים מלוגיקה. צריך לשים לב שעם שתי הפעולות הללו \( \mathbb{Z}_{2} \) אינו חוג, כי אין נגדי חיבורי לפעולת ה-\( \vee \) (ולכן היא לא יכולה לתפקד בתור פעולת החיבור של חוג) לכן אמרתי שנקבל דמיון לכפל מטריצות ולא ממש מקרה פרטי.

עכשיו, זוכרים את ההגדרה של הרכבת יחסים?

\( R\circ S\triangleq\left\{ \left(a,c\right)\ |\ \exists b\in B:\left(a,b\right)\in R\wedge\left(b,c\right)\in S\right\} \)

במקום לכתוב \( \exists \), אפשר, במקרה שבו הקבוצות \( A,B,C \) סופיות, לכתוב משהו יותר מפורש בשביל התנאי שבפנים:

\( \left[\left(a,b_{1}\right)\in R\wedge\left(b_{1},c\right)\in S\right]\vee\dots\vee\left[\left(a,b_{m}\right)\in R\wedge\left(b_{m},c\right)\in S\right] \)

ובמילים - או שאפשר לעבור מ-\( a \) אל \( c \) עם איבר הביניים \( b_{1} \), או שאפשר לעבור עם \( b_{2} \) וכן הלאה, עד \( b_{m} \).

כלומר, קיבלנו ש-\( \left[R\circ S\right]_{ij} \) מוגדר בדיוק כמו כפל מטריצות, פרט לכך שאנחנו מחליפים את התפקידים של חיבור וכפל ב-\( \wedge \) וב-\( \vee \). חמוד? אני מקווה, וגם נותן אינטואיציות מסויימות, אבל אני בעיקר מקווה שחמוד.