הבדלים בין גרסאות בדף "תרגול 9 תשעז"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
שורה 1: שורה 1:
−
===תרגיל===
 
−
יהיו <math>A=\{1,2\}, B=\{3,4,5\}</math>. נגדיר את היחס: <math>R=\{(1,3),(2,4)\}</math>. בדוק האם:
 
−
 
−
א. <math>R^{-1}\circ R=I_A</math>
 
−
 
−
ב. <math>R\circ R^{-1}=I_B</math>
 
−
 
−
 
−
==תכונות של יחסים על קבוצה==
 
−
הגדרה: יחס R על קבוצה A פירושו  <math>R\subseteq A\times A</math>
 
−
 
−
תהי קבוצה A ויחס R עליה אזי
 
−
#R נקרא '''רפלקסיבי''' אם כל איבר מקיים את היחס עם עצמו ( מתקיים <math>\forall a\in A:(a,a)\in R</math>)
 
−
#R נקרא '''סימטרי''' אם aRb גורר שגם bRa (מתקיים <math>\forall a,b\in A:[(a,b)\in R \rightarrow (b,a)\in R]</math>)
 
−
#R נקרא '''טרנזיטיבי''' אם יחס בין ראשון לשני, ויחס בין השני לשלישי גורר יחס בין הראשון לשלישי (מתקיים <math>\forall a,b,c\in A:[((a,b)\in R) \and ((b,c)\in R) \rightarrow ((a,c)\in R)]</math>)
 
−
#R נקרא '''אנטי סימטרי (חלש)''' אם aRb וגם bRa גורר כי a=b (מתקיים <math>\forall a,b\in A:[(a,b)\in R \and (b,a)\in R \rightarrow a=b]</math> ובאופן שקול: <math>\forall a\neq b\in A: \lnot (aRb\land bRa)</math>)
 
−
 
−
דוגמאות:
 
−
*יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
 
−
*יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
 
−
*יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
 
−
*יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי
 
−
*יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
 
−
*יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי
 
−
*יחס 'אדם x שמע על אדם y' הינו רפלקסיבי
 
−
 
−
'''הערה:''' יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמא: <math>A=\{ 1,2,3\} , R=\{ (1,1)\} , S=\{ (1,2),(2,1),(3,2)\}</math> ואז R גם וגם, S לא ולא.
 
−
 
 
==יחסי סדר==
 
==יחסי סדר==
 
'''הגדרה:''' יחס R על A נקרא '''יחס סדר חלקי''' אם R רפלקסיבי, טרנזיטיבי ואנטי-סימטרי  
 
'''הגדרה:''' יחס R על A נקרא '''יחס סדר חלקי''' אם R רפלקסיבי, טרנזיטיבי ואנטי-סימטרי  
שורה 34: שורה 6:
 
*היחס 'מוכל-שווה' על הקבוצות
 
*היחס 'מוכל-שווה' על הקבוצות
 
*היחס 'מחלק את ' על הטבעיים
 
*היחס 'מחלק את ' על הטבעיים
 +
 +
'''הערה:'''
 +
עבור <math>A</math> קבוצה ויחס סדר חלקי עליה. נסמן <math>(A,\leq )</math>  את הקבוצה עם היחס
  
 
'''הגדרה.''' דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>A=\{1,2,3\}</math>.
 
'''הגדרה.''' דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>A=\{1,2,3\}</math>.
שורה 51: שורה 26:
 
צייר את היחס ההפוך של "מחלק את", זהו היחס "מתחלק ב". מהם האיברים המינימלים והמקסימלים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?
 
צייר את היחס ההפוך של "מחלק את", זהו היחס "מתחלק ב". מהם האיברים המינימלים והמקסימלים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?
  
−
'''הערה:'''
+
===תרגיל===
−
עבור <math>A</math> קבוצה ויחס סדר חלקי עליה. נסמן <math>(A,\leq )</math> את הקבוצה עם היחס
+
 
 +
תהא <math>A</math> קבוצה. חשב את <math>|\{ R\subseteq A\times A:R\text{ is order relation} \land \forall a\in A. a \text{ is maximally and minimally} \}|</math>
 +
 
 +
====פתרון====
 +
 
 +
נראה שיש רק יחס אחד כזה, והוא הזהות. יחס הזהות אכן מקיים את התנאי. נניח ש-<math>R</math> יחס סדר המקיים את התנאי ונראה ש-<math>R=I_A</math>:
 +
 
 +
כיוון ראשון: כל יחס סדר <math>R</math> מקיים <math>I_A\subseteq R</math>.
  
 +
כיוון שני: יהי <math>(a,b) \in R</math>, אזי כיון ש- <math>a</math> מקסימלי נובע <math>b=a</math> ולכן <math>(a,b)=(a,a)
 +
\in I_A</math> כדרוש.
  
 +
==חסמים==
 
'''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
 
'''הגדרות.''' יהיו 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:(y,x)\in R </math>

גרסה מ־10:16, 20 ביוני 2017

יחסי סדר

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

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

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

הערה: עבור A קבוצה ויחס סדר חלקי עליה. נסמן (A,\leq ) את הקבוצה עם היחס

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


הגדרות. יהיו 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)

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

הערה: קטן ביותר \leftarrow מינימלי, וכן גדול ביותר \leftarrow מקסימלי, ולא להיפך!

צייר את דיאגרמת הסה של היחס "מחלק את" על הקבוצה A=\{1,2,...,10\} מהם האיברים המינימלים והמקסימלים? האם קיים איבר קטן ביותר ואיבר גדול ביותר? צייר את היחס ההפוך של "מחלק את", זהו היחס "מתחלק ב". מהם האיברים המינימלים והמקסימלים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?

תרגיל

תהא A קבוצה. חשב את |\{ R\subseteq A\times A:R\text{ is order relation} \land \forall a\in A. a \text{ is maximally and minimally} \}|

פתרון

נראה שיש רק יחס אחד כזה, והוא הזהות. יחס הזהות אכן מקיים את התנאי. נניח ש-R יחס סדר המקיים את התנאי ונראה ש-R=I_A:

כיוון ראשון: כל יחס סדר R מקיים I_A\subseteq R.

כיוון שני: יהי (a,b) \in R, אזי כיון ש- a מקסימלי נובע b=a ולכן (a,b)=(a,a) \in I_A כדרוש.

חסמים

הגדרות. יהיו 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)

דוגמאות

דוגמא עבור \{A_i\}_{i\in I} אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא \cup _{i\in I} A_i

דוגמא.

נביט בקבוצה 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)\}

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

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

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

למשל: היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא. שימו לב כי זו דוגמא ליחס סדר בלי איברים מינימליים או מקסימליים.

מקור: https://math-wiki.com/index.php?title=תרגול_9_תשעז&oldid=71891