תרגול 9 תשעז

תרגיל

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

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

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

תרגיל

תהיינה [math]\displaystyle{ A,B,C }[/math] קבוצות, [math]\displaystyle{ R\subseteq A\times B,T,S\subseteq B\times C }[/math]. הוכח או הפרך:

א. [math]\displaystyle{ T\circ R=S\circ R\iff T=S }[/math].

ב. [math]\displaystyle{ T\subseteq S\Rightarrow T\circ R\subseteq S\circ R }[/math]

פיתרון:

א. הכיוון [math]\displaystyle{ \Leftarrow }[/math] בוודאי נכון. אבל הכיוון השני לא מתקיים. דוגמא נגדית: ניקח:

[math]\displaystyle{ A=\{ 1,2\} ,R=T=\{ (1,1)\} \subseteq A\times A,S=\{ (1,1),(2,2)\} \subseteq A\times A }[/math]

ונקבל: [math]\displaystyle{ T\circ R=S\circ R=\{ (1,1)\} }[/math] אבל כמובן [math]\displaystyle{ S\neq T }[/math].

ב. הוכחה: יהי [math]\displaystyle{ (x,z)\in T\circ R }[/math] אזי לפי הגדרה קיים [math]\displaystyle{ y\in B }[/math] כך ש- [math]\displaystyle{ (x,y)\in R\land (y,z)\in T }[/math]. כעת, כיון ש-[math]\displaystyle{ T\subseteq S }[/math] נובע ש- [math]\displaystyle{ (y,z)\in S }[/math], ולכן לפי הגדרת ההרכבה נקבל [math]\displaystyle{ (x,z)\in S\circ R }[/math].

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

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

תהי קבוצה A ויחס R עליה אזי

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])
4. R נקרא אנטי סימטרי (חלש) אם aRb וגם bRa גורר כי a=b (מתקיים [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])

דוגמאות:

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

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