88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 2

יחסים

הגדרה: המכפלה הקרטזית של שתי קבוצות A וB הינה אוסף כל הזוגות הסדורים - [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].

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

דוגמא: [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]

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

תרגיל

הוכח/הפרך:

1. [math]\displaystyle{ [(a=c)\and(b=d)]\iff \{\{a\},b\}=\{\{c\},d\} }[/math]

2. [math]\displaystyle{ [(a=c)\and(b=d)]\iff \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\} }[/math]

פתרון

1. הפרכה ע"י הדוגמא הנגדית [math]\displaystyle{ a=2,b=\{3\},c=3,d=\{2\} }[/math]

2.

הוכחה: הכיוון משמאל לימין הוא ברור. מימין לשמאל, נניח והקבוצות שוות אזי [math]\displaystyle{ \{a\}=\{c\} }[/math] או ש [math]\displaystyle{ \{a\}=\{c,d\} }[/math].

במקרה הראשון, נובע a=c ובמקרה השני נובע a=c=d, כך או כך a=c. כעת, [math]\displaystyle{ \{a,b\}=\{c,b\}=\{c\} }[/math] או [math]\displaystyle{ \{c,b\}=\{c,d\} }[/math] ונובע משניהם ש b=d.

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

תרגיל

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

פתרון

[math]\displaystyle{ (x,y)\in A\times(B\cap C) \iff (x\in A) \and [(y\in B)\and (y\in C)] \iff [(x\in A)\and(y\in B)] \and [(x\in A)\and(y\in B)] \iff x\in[(A\times B)\cap(A\times C)] }[/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]. מה מיוחד בזוגות אלה?

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

אם זוג מסוים נמצא בקבוצת היחס R נהוג לסמן aRb.

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

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

תהי קבוצה A ויהיה יחס R המוגדר על A (כלומר, [math]\displaystyle{ R\subseteq A\times A }[/math])

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

דוגמאות:

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