תרגול 8 תשעז

חזרה לדף מערכי התרגול.

יחסים

המכפלה הקרטזית

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

ניתן להכליל את ההגדרה לעיל ל-[math]\displaystyle{ n }[/math]-יה סדורה - כלומר [math]\displaystyle{ n }[/math] איברים מסודרים.

דוגמה: [math]\displaystyle{ A=\{1,2,3\} }[/math] ו-[math]\displaystyle{ B=\{a,b\} }[/math] אזי מתקיים [math]\displaystyle{ A\times B =\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\} }[/math]

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

תרגיל

הוכח שלכל קבוצות [math]\displaystyle{ A,B,C,D }[/math] מתקיים [math]\displaystyle{ (A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D) }[/math]

פתרון

[math]\displaystyle{ (x,y)\in (A\times B)\cap (C\times D) \iff }[/math] [math]\displaystyle{ (x,y)\in A\times B \land (x,y)\in C\times D \iff }[/math] [math]\displaystyle{ (x\in A \and y\in B) \and (x\in C\and y\in D) \iff }[/math] [math]\displaystyle{ (x\in A\and x\in C) \and (y\in B\and y\in D) \iff }[/math] [math]\displaystyle{ (x,y)\in (A\cap C)\times (B\cap D) }[/math]

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

הגדרה: יהיו [math]\displaystyle{ A,B }[/math] קבוצות, [math]\displaystyle{ R\subseteq A\times B }[/math] אזי [math]\displaystyle{ R }[/math] יקרא יחס (בין [math]\displaystyle{ A }[/math] לבין [math]\displaystyle{ B }[/math]). הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי [math]\displaystyle{ A }[/math] ל-[math]\displaystyle{ B }[/math].

דוגמה: [math]\displaystyle{ A=\{1,2,3\},B=\{0,2,6\} }[/math] ונביט בתת הקבוצה [math]\displaystyle{ R\subseteq A\times B }[/math] הבאה: [math]\displaystyle{ R=\{(1,2),(1,6),(2,2),(2,6),(3,6)\} }[/math]. מה מיוחד בזוגות אלה?

זוגות אלה הינם כל זוגות האיברים [math]\displaystyle{ (a,b) }[/math] כך ש-[math]\displaystyle{ a\leq b }[/math]. (כלומר הגדרנו את היחס המייצג "קטן שווה").

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

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

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

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

הגדרה: תהי קבוצה [math]\displaystyle{ A }[/math]. יחס הזהות על [math]\displaystyle{ A }[/math] הוא [math]\displaystyle{ R\subseteq A\times A }[/math] כך ש-[math]\displaystyle{ I_A=R=\{(a,a):a\in A\} }[/math].

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

תרגיל

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

א. [math]\displaystyle{ RR^{-1}=I_A }[/math]

ב. [math]\displaystyle{ R^{-1}R=I_B }[/math]

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

הגדרה: יחס [math]\displaystyle{ R }[/math] על קבוצה [math]\displaystyle{ A }[/math] פירושו [math]\displaystyle{ R\subseteq A\times A }[/math].

תהי קבוצה [math]\displaystyle{ A }[/math] ויחס [math]\displaystyle{ R }[/math] עליה אזי:

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

דוגמאות:

• יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
• יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
• יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
• יחס 'שיוויון מודולו [math]\displaystyle{ n }[/math]' הינו רפלקסיבי, סימטרי וטרנזיטיבי
• יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
• יחס '[math]\displaystyle{ a }[/math] מחלק את [math]\displaystyle{ b }[/math]' הינו רפלקסיבי וטרנזיטיבי
• יחס 'אדם [math]\displaystyle{ x }[/math] שמע על אדם [math]\displaystyle{ y }[/math]' הינו רפלקסיבי

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