88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 3: הבדלים בין גרסאות בדף
| שורה 31: | שורה 31: | ||
*טרנזיטיביות: נניח <math>(x,y),(y,z)\in R^{-1}</math> לכן מתקיים <math>(y,x),(z,y)\in R</math> לכן לפי הטרנזיטיביות של R מתקיים <math>(z,x)\in R</math> ולכן <math>(x,z)\in R^{-1}</math>. | *טרנזיטיביות: נניח <math>(x,y),(y,z)\in R^{-1}</math> לכן מתקיים <math>(y,x),(z,y)\in R</math> לכן לפי הטרנזיטיביות של R מתקיים <math>(z,x)\in R</math> ולכן <math>(x,z)\in R^{-1}</math>. | ||
*אנטי-סימטריות: אם x ביחס לy וגם y ביחס לx הדבר נכון באופן זהה לR ולהופכי שלו, ולכן x=y. | *אנטי-סימטריות: אם x ביחס לy וגם y ביחס לx הדבר נכון באופן זהה לR ולהופכי שלו, ולכן x=y. | ||
'''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי: | |||
*חסם מלעיל של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(y,x)\in R </math> | |||
*חסם מלרע של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(x,y)\in R </math> | |||
*החסם העליון (סופרמום) של B הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן <math>sup(B)</math> | |||
*החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>inf(B)</math> | |||
גרסה מ־13:58, 30 ביולי 2011
יחסי סדר
הגדרה: יחס 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)
הערה: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר מינימום הוא יחיד (למרות שהוא לא חייב להיות קיים), ונכון הדבר לגבי המקסימום.
הגדרה: יהי 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]