תרגול 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)\}$

למתכנתים: זה מאוד דומה ללולאות for מקוננות.

תרגיל

הוכח שלכל קבוצות $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)\}$ היא יחס. גם $\varnothing$ היא יחס, וגם $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$. יחס הזהות על $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$ יחס הכפל הוא היחס: $RS=\{(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)\}$. בדוק האם:

א. $RR^{-1}=I_A$

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

תכונות של יחסים על קבוצה

הגדרה: יחס $R$ על קבוצה $A$ פירושו $R\subseteq A\times A$.

תהי קבוצה $A$ ויחס $R$ עליה אזי:

1. $R$ נקרא רפלקסיבי אם כל איבר מקיים את היחס עם עצמו ( מתקיים $\forall a\in A:(a,a)\in R$).
2. $R$ נקרא סימטרי אם $aRb$ גורר שגם $bRa$ (מתקיים $\forall a,b\in A:[(a,b)\in R \rightarrow (b,a)\in R]$).
3. $R$ נקרא טרנזיטיבי אם יחס בין ראשון לשני ($aRb$), ויחס בין השני לשלישי ($bRc$) גורר יחס בין הראשון לשלישי ($aRc$). (מתקיים $\forall a,b,c\in A:[((a,b)\in R) \and ((b,c)\in R) \rightarrow ((a,c)\in R)]$).
4. $R$ נקרא אנטי סימטרי (חלש) אם $aRb$ וגם $bRa$ גורר כי $a=b$ (מתקיים $\forall a,b\in A:[(a,b)\in R \and (b,a)\in R \rightarrow a=b]$ ובאופן שקול: $\forall a\neq b\in A: \lnot (aRb\land bRa)$)

דוגמאות:

• יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
• יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
• יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
• יחס 'שיוויון מודולו $n$' הינו רפלקסיבי, סימטרי וטרנזיטיבי
• יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
• יחס '$a$ מחלק את $b$' הינו רפלקסיבי וטרנזיטיבי
• יחס 'אדם $x$ שמע על אדם $y$' הינו רפלקסיבי

הערה: יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמה: $A=\{ 1,2,3\} , R=\{ (1,1)\} , S=\{ (1,2),(2,1),(3,2)\}$ ואז $R$ גם וגם, ואילו $S$ לא ולא.