תרגול 8 תשעז

יחסים

הגדרה: המכפלה הקרטזית של שתי קבוצות A וB הינה אוסף כל הזוגות הסדורים - $A\times B = \{(a,b)|a\in A \and b\in B\}$. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים $(1,2),(2,1)$ והאיבר הבא הינו זוג חוקי $(1,1)$.

ניתן להכליל את ההגדרה לעיל לn-יה סדורה - כלומר n איברים מסודרים.

דוגמא: $A=\{1,2,3\}$ ו$B=\{a,b\}$ אזי מתקיים $A\times B =\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}$

תרגיל

הוכח שלכל קבוצות A,B,C,D מתקיים $(A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)$

פתרון

$(x,y)\in (A\times B)\cap (C\times D) \iff (x,y)\in A\times B \land (x,y)\in C\times D \iff (x\in A \and y\in B) \and (x\in C\and y\in D) \iff (x\in A\and x\in C) \and (y\in B\and y\in D) \iff (x,y)\in (A\cap C)\times (B\cap D)$

יחסים כתת קבוצה של הזוגות הסדורים

הגדרה: יהיו A,B קבוצות, $R\subseteq A\times B$ אזי R יקרא יחס (בין A ל -B). הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי A ל B דוגמא: $A=\{1,2,3\},B=\{0,2,6\}$ ונביט בתת הקבוצה $R\subseteq A\times B$ הבאה: $R=\{(1,2),(1,6),(2,2),(2,6),(3,6)\}$. מה מיוחד בזוגות אלה?

זוגות אלה הינן כל זוגות האיברים (a,b) כך ש $a\leq b$. (כלומר הגדרנו את היחס המייצג "קטן שווה")

הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה $S=\{(1,2),(1,6),(2,0),(2,2)\}$ היא יחס. גם $\emptyset$ היא יחס. וגם $A\times B$ הוא יחס.

סימון: אם זוג מסוים, (a,b), נמצא בקבוצת היחס R נהוג לסמן aRb, או $(a,b)\in R$. (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט $a\leq b$.

דוגמא: נביט בקבוצת האנשים A. נגדיר את יחס "בן של" על ידי קבוצת הזוגות הסדורים $R\subseteq A\times A$ כך ש $(x,y)\in R$ אם"ם x הוא בן של y. שימו לב שיש משמעות לכיוון היחס, שכן יש הבדל בין העובדה שאני הבן של מישהו לבין העובדה שהוא הבן שלי.

הגדרה: בהינתן יחס $R\subseteq A\times B$ היחס ההפוך $R^{-1}\subseteq B\times A$ הוא היחס המוגדר ע"י היפוך הזוגות הסדורים: $R^{-1}=\{(b,a):aRb\}$

הגדרה: תהי קבוצה A. יחס הזהות הוא $R\subseteq A\times A$ כך ש: $I_A=R=\{(a,a):a\in A\}$.

הגדרה: יהיו A,B,C קבוצות, ו$R\subseteq A\times B, S\subseteq B\times C$ היחס ההרכבה/הכפל הוא היחס: $S\circ R=\{(a,c)\in A\times C | \exists b\in B : (a,b)\in R \land (b,c)\in S\}$

תרגיל

יהיו $A=\{1,2\}, B=\{3,4,5\}$. נגדיר את היחס: $R=\{(1,3),(2,4)\}$. בדוק האם:

א. $R^{-1}\circ R=I_A$

ב. $R\circ R^{-1}=I_B$