הבדלים בין גרסאות בדף "תרגול 8 תשעז"
שורה 1: | שורה 1: | ||
=יחסים= | =יחסים= | ||
+ | ==המכפלה הקרטזית== | ||
הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות A וB הינה אוסף כל ה'''זוגות הסדורים''' - <math>A\times B = \{(a,b)|a\in A \and b\in B\}</math>. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים <math>(1,2),(2,1)</math> והאיבר הבא הינו זוג חוקי <math>(1,1)</math>. | הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות A וB הינה אוסף כל ה'''זוגות הסדורים''' - <math>A\times B = \{(a,b)|a\in A \and b\in B\}</math>. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים <math>(1,2),(2,1)</math> והאיבר הבא הינו זוג חוקי <math>(1,1)</math>. | ||
שורה 40: | שורה 41: | ||
ב. <math>R\circ R^{-1}=I_B</math> | ב. <math>R\circ R^{-1}=I_B</math> | ||
+ | |||
+ | ==תכונות של יחסים על קבוצה== | ||
+ | הגדרה: יחס R על קבוצה A פירושו <math>R\subseteq A\times A</math> | ||
+ | |||
+ | תהי קבוצה A ויחס R עליה אזי | ||
+ | #R נקרא '''רפלקסיבי''' אם כל איבר מקיים את היחס עם עצמו ( מתקיים <math>\forall a\in A:(a,a)\in R</math>) | ||
+ | #R נקרא '''סימטרי''' אם aRb גורר שגם bRa (מתקיים <math>\forall a,b\in A:[(a,b)\in R \rightarrow (b,a)\in R]</math>) | ||
+ | #R נקרא '''טרנזיטיבי''' אם יחס בין ראשון לשני, ויחס בין השני לשלישי גורר יחס בין הראשון לשלישי (מתקיים <math>\forall a,b,c\in A:[((a,b)\in R) \and ((b,c)\in R) \rightarrow ((a,c)\in R)]</math>) | ||
+ | #R נקרא '''אנטי סימטרי (חלש)''' אם aRb וגם bRa גורר כי a=b (מתקיים <math>\forall a,b\in A:[(a,b)\in R \and (b,a)\in R \rightarrow a=b]</math> ובאופן שקול: <math>\forall a\neq b\in A:\lor (aRb\land bRa)</math>) | ||
+ | |||
+ | דוגמאות: | ||
+ | *יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי | ||
+ | *יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי | ||
+ | *יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי | ||
+ | *יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי | ||
+ | *יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי | ||
+ | *יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי | ||
+ | *יחס 'אדם x שמע על אדם y' הינו רפלקסיבי |
גרסה מ־13:25, 1 בינואר 2017
תוכן עניינים
יחסים
המכפלה הקרטזית
הגדרה: המכפלה הקרטזית של שתי קבוצות A וB הינה אוסף כל הזוגות הסדורים - . ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים והאיבר הבא הינו זוג חוקי .
ניתן להכליל את ההגדרה לעיל לn-יה סדורה - כלומר n איברים מסודרים.
דוגמא: ו אזי מתקיים
תרגיל
הוכח שלכל קבוצות A,B,C,D מתקיים
פתרון
יחסים כתת קבוצה של הזוגות הסדורים
הגדרה: יהיו A,B קבוצות, אזי R יקרא יחס (בין A ל -B). הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי A ל B דוגמא: ונביט בתת הקבוצה הבאה: . מה מיוחד בזוגות אלה?
זוגות אלה הינן כל זוגות האיברים (a,b) כך ש . (כלומר הגדרנו את היחס המייצג "קטן שווה")
הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה היא יחס. גם היא יחס. וגם הוא יחס.
סימון: אם זוג מסוים, (a,b), נמצא בקבוצת היחס R נהוג לסמן aRb, או . (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט .
דוגמא: נביט בקבוצת האנשים A. נגדיר את יחס "בן של" על ידי קבוצת הזוגות הסדורים כך ש אם"ם x הוא בן של y. שימו לב שיש משמעות לכיוון היחס, שכן יש הבדל בין העובדה שאני הבן של מישהו לבין העובדה שהוא הבן שלי.
הגדרה: בהינתן יחס היחס ההפוך הוא היחס המוגדר ע"י היפוך הזוגות הסדורים:
הגדרה: תהי קבוצה A. יחס הזהות הוא כך ש: .
הגדרה: יהיו A,B,C קבוצות, ו היחס ההרכבה/הכפל הוא היחס:
תרגיל
יהיו . נגדיר את היחס: . בדוק האם:
א.
ב.
תכונות של יחסים על קבוצה
הגדרה: יחס R על קבוצה A פירושו
תהי קבוצה A ויחס R עליה אזי
- R נקרא רפלקסיבי אם כל איבר מקיים את היחס עם עצמו ( מתקיים )
- R נקרא סימטרי אם aRb גורר שגם bRa (מתקיים )
- R נקרא טרנזיטיבי אם יחס בין ראשון לשני, ויחס בין השני לשלישי גורר יחס בין הראשון לשלישי (מתקיים )
- R נקרא אנטי סימטרי (חלש) אם aRb וגם bRa גורר כי a=b (מתקיים ובאופן שקול: )
דוגמאות:
- יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
- יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
- יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
- יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי
- יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
- יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי
- יחס 'אדם x שמע על אדם y' הינו רפלקסיבי