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

יחסי סדר

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

כלומר, אם [math]\displaystyle{ x\neq y }[/math] אז לא יכול להיות שמתקיים היחס בין x לבין y וגם היחס בין y לx.

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

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

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

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

הגדרות. יהיו 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{ A=\{1,2,3,4,5\} }[/math] ונגדיר עליה יחס סדר חלקי:

[math]\displaystyle{ R=\{(1,1),(2,2),(3,3),(4,4),(5,5),(2,4),(1,2),(1,4),(3,2),(3,4),(5,2),(5,4)\} }[/math]

(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)

5,3,1 הינם איברים מינימליים שכן אין איבר שקטן מאף אחד מהם. הם אינם מינימום כי אף אחד מהם לא קטן מכל האיברים האחרים.
4 הינו מקסימום של הקבוצה, הוא בוודאי מקסימלי
2 קטן מחלק מהאיברים וגדול מאחרים לכן הוא כלום.

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

תרגיל.

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

פתרון.

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

הגדרות. יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:

חסם מלעיל של B הוא איבר [math]\displaystyle{ x\in A }[/math] כך שמתקיים [math]\displaystyle{ \forall y\in B:(y,x)\in R }[/math]
חסם מלרע של B הוא איבר [math]\displaystyle{ x\in A }[/math] כך שמתקיים [math]\displaystyle{ \forall y\in B:(x,y)\in R }[/math]
החסם העליון (סופרמום) של B הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן [math]\displaystyle{ sup(B) }[/math]
החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן [math]\displaystyle{ inf(B) }[/math]

דוגמא.

נשוב לדוגמא הקודמת. נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד [math]\displaystyle{ B=\{1,3,5\} }[/math]. קבוצת חסמי המלעיל של B הינה [math]\displaystyle{ \{2,4\} }[/math]. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.