88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 3

יחסי סדר

הגדרה: יחס R על A נקרא אנטי-סימטרי אם מתקיים $\forall x,y\in A:[(x,y)\in R]\and[(y,x)\in R] \rightarrow (x=y)$

כלומר, אם $x\neq y$ אז לא יכול להיות שמתקיים היחס בין x לבין y וגם היחס בין y לx.

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

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

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

הגדרה: דיאגרמת הסה Hassse

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

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

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

הגדרה: יהי R יחס על A, אזי היחס ההופכי מוגדר להיות $R^{-1}=\{(y,x)|(x,y)\in R\}$

תרגיל.

הוכח שאם R יחס סדר חלקי, גם ההופכי שלו יחס סדר חלקי

פתרון.

• רפלקסיביות: לכל איבר a מתקיים $(a,a)\in R$ ולכן $(a,a)\in R^{-1}$
• טרנזיטיביות: נניח $(x,y),(y,z)\in R^{-1}$ לכן מתקיים $(y,x),(z,y)\in R$ לכן לפי הטרנזיטיביות של R מתקיים $(z,x)\in R$ ולכן $(x,z)\in R^{-1}$.
• אנטי-סימטריות: אם x ביחס לy וגם y ביחס לx הדבר נכון באופן זהה לR ולהופכי שלו, ולכן x=y.