תרגול 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 לא ולא.

יחסי סדר

הגדרה: יחס R על A נקרא יחס סדר חלקי אם R רפלקסיבי, טרנזיטיבי ואנטי-סימטרי

דוגמאות ליחסי סדר חלקי:

• היחס 'קטן-שווה' על המספרים
• היחס 'מוכל-שווה' על הקבוצות
• היחס 'מחלק את ' על הטבעיים

הגדרה. דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה [math]\displaystyle{ A=\{1,2,3\} }[/math].

הגדרות. יהיו A קבוצה וR יחס סדר חלקי על הקבוצה:

• איבר [math]\displaystyle{ x\in A }[/math] נקרא מינמלי ביחס לR אם [math]\displaystyle{ \forall y\in A:(y,x)\in R \rightarrow y=x }[/math]. כלומר, אין איבר 'קטן' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
• איבר [math]\displaystyle{ x\in A }[/math] נקרא מקסימלי ביחס לR אם [math]\displaystyle{ \forall y\in A:(x,y)\in R \rightarrow y=x }[/math]. כלומר, אין איבר 'גדול' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
• איבר [math]\displaystyle{ x\in A }[/math] נקרא מינימום ביחס לR אם [math]\displaystyle{ \forall y\in A:(x,y)\in R }[/math]. כלומר, x 'קטן' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה הריקה תחת יחס הכלה)
• איבר [math]\displaystyle{ x\in A }[/math] נקרא מקסימום ביחס לR אם [math]\displaystyle{ \forall y\in A:(y,x)\in R }[/math]. כלומר, x 'גדול' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה B תחת יחס ההכלה על קבוצת החזקה של B)

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

הערה: מינימום [math]\displaystyle{ \leftarrow }[/math] מינימלי, וכן מקסימום [math]\displaystyle{ \leftarrow }[/math] מקסימלי, ולא להיפך!