תרגול 9 תשעז

תרגיל

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

א. $R^{-1}\circ R=I_A$

ב. $R\circ R^{-1}=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 נקרא טרנזיטיבי אם יחס בין ראשון לשני, ויחס בין השני לשלישי גורר יחס בין הראשון לשלישי (מתקיים $\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 לא ולא.