השינוי האחרון נעשה בֹ־30 ביולי 2011 ב־21:06

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

גרסה מ־21:06, 30 ביולי 2011 מאת ארז שיינר (שיחה | תרומות) (←‏יחסי סדר)

יחסי סדר

הגדרה: יחס 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)

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


דוגמא.

נביט בקבוצה A=\{1,2,3,4,5\} ונגדיר עליה יחס סדר חלקי:

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)\}

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

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


הגדרה: יהי 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.

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

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


דוגמא.

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

דוגמא. נביט במספרים הממשיים ובתת הקבוצה של כל המספרים עם מספר סופי של ספרות ששווים לספרות הראשונות של שורש 2. B=\{1,1.4,1.41,1.414,1.4142,...\}. חסמי המלעיל של הקבוצה הינם כל המספרים שגדולים או שווים לשורש 2 ואילו שורש 2 הוא החסם העליון של הקבוצה.

שימו לב, אם נביט בקבוצה B כתת קבוצה של המספרים הרציונאליים, חסמי המלעיל שלה יהיו כל האיברים הגדולים משורש 2 אך מכיוון ששורש 2 אינו רציונאלי, אין לB חסם עליון.

הגדרה. יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים [(a,b)\in R]\or[(b,a)\in R] אזי R נקרא יחס סדר מלא.

דוגמא. נביט בקבוצת השלמים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית (lcm), והאינפימום הוא המחלק המשותף המקסימלי(gcd).


תרגיל ממבחן.

הגדרה: תת קבוצה A של המספרים הממשיים נקראת 'מגניבה' אם לכל x,y בA כך ש-x שונה מ-y מתקיים שההפרש x-y אינו רציונאלי.

תהי B קבוצה מגניבה מקסימלית ביחס להכלה, הוכח שלכל מספר ממשי שאינו שייך לB קיים איבר בB כך שההפרש בינהם הוא רציונאלי.

הוכחה.

נניח בשלילה שקיים איבר ממשי r שאינו בB, ולכל איבר b ב-B ההפרש r-b אינו רציונאלי. לכן אם נוסיף את r ל-B נקבל קבוצה מגניבה המכילה ממש את B (ולא שווה לה) בסתירה למקסימאליות של B.

תרגיל.

נביט בQ אוסף השברים המצומצמים. נביט בR היחס המוגדר על ידי (\frac{m_1}{n_1},\frac{m_2}{n_2}) אם (m_1\leq m_2)\and(n_1\leq n_2). הוכיחו/הפריכו: R הינו יחס סדר חלקי.

פתרון.

נבדוק את תכונות היחס:

  • רפלקסיביות - ברור.
  • אנטי-סימטריות - אם (m_1\leq m_2)\and(n_1\leq n_2) וגם (m_1\geq m_2)\and(n_1\geq n_2) אזי (m_1= m_2)\and(n_1= n_2) ולכן שני השברים המצומצמים שווים.
  • טרנזיטיביות - נובעת מהטרנזיטיביות של המונים והמכנים בנפרד.

לכן R הינו יחס סדר חלקי.