תרגול 8 תשעז

יחסים

הגדרה: המכפלה הקרטזית של שתי קבוצות 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 C)] \iff (x,y)\in[(A\times B)\cap(A\times C)] }[/math]

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

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

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

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

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

הגדרה: בהינתן יחס [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]