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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
 
(7 גרסאות ביניים של 3 משתמשים אינן מוצגות)
שורה 1: שורה 1:
 +
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
 +
 
==יחסי סדר==
 
==יחסי סדר==
−
'''הגדרה:''' יחס R על A נקרא '''יחס סדר חלקי''' אם R רפלקסיבי, טרנזיטיבי ואנטי-סימטרי  
+
'''הגדרה:''' יחס <math>R</math> על קבוצה <math>A</math> נקרא '''יחס סדר חלקי''' אם <math>R</math> רפלקסיבי, טרנזיטיבי ואנטי-סימטרי.
  
 
דוגמאות ליחסי סדר חלקי:  
 
דוגמאות ליחסי סדר חלקי:  
−
*היחס 'קטן-שווה' על המספרים
+
*היחס 'קטן-שווה' על המספרים השלמים
−
*היחס 'מוכל-שווה' על הקבוצות
+
*היחס 'מוכל-שווה' על קבוצת החזקה <math>P(\{4,5,100\})</math>
−
*היחס 'מחלק את ' על הטבעיים
+
*היחס 'מחלק את' על הטבעיים
  
 
'''הערה:'''
 
'''הערה:'''
−
עבור <math>A</math> קבוצה ויחס סדר חלקי עליה. נסמן <math>(A,\leq )</math>  את הקבוצה עם היחס
+
עבור <math>A</math> קבוצה ויחס סדר חלקי <math>\leq</math> עליה, נסמן <math>(A,\leq )</math>  את הקבוצה עם היחס.
  
−
'''הגדרה.''' דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>A=\{1,2,3\}</math>.
+
'''הגדרה:''' דיאגרמת הסה (או תרשים הסה, Hasse diagram) הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר <math>x</math> מחובר בקשת לאיבר <math>y</math> מתחתיו 'גדול' ממנו ביחס (כלומר <math>x>y</math>), ובינם אין עוד איברים (כלומר אין <math>z</math> כך ש-<math>x>z>y</math>). נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>A=\{1,2,3\}</math>.
  
 +
'''הגדרות:''' יהיו <math>A</math> קבוצה ו-<math>R</math> יחס סדר חלקי על הקבוצה:
 +
*איבר <math>x\in A</math> נקרא '''מינימלי''' ביחס ל-<math>R</math> אם <math>\forall y\in A:(y,x)\in R \rightarrow y=x</math>. כלומר, אין איבר 'קטן' מ-<math>x</math>. לא חייב להתקיים ש-<math>x</math> ביחס כלשהו עם איבר כלשהו.
 +
*איבר <math>x\in A</math> נקרא '''מקסימלי''' ביחס ל-<math>R</math> אם <math>\forall y\in A:(x,y)\in R \rightarrow y=x</math>. כלומר, אין איבר 'גדול' מ-<math>x</math>. לא חייב להתקיים ש-<math>x</math> ביחס כלשהו עם איבר כלשהו.
 +
*איבר <math>x\in A</math> נקרא '''קטן ביותר''' ביחס ל-<math>R</math> אם <math>\forall y\in A:(x,y)\in R</math>. כלומר, <math>x</math> 'קטן' מכל האיברים. <math>x</math> חייב להיות ביחס עם כל האיברים בקבוצה. למשל, הקבוצה הריקה תחת יחס הכלה.
 +
*איבר <math>x\in A</math> נקרא '''גדול ביותר''' ביחס ל-<math>R</math> אם <math>\forall y\in A:(y,x)\in R</math>. כלומר, <math>x</math> 'גדול' מכל האיברים. <math>x</math> חייב להיות ביחס עם כל האיברים בקבוצה. למשל, הקבוצה <math>B</math> תחת יחס ההכלה על קבוצת החזקה של <math>B</math>.
  
−
'''הגדרות.''' יהיו A קבוצה וR יחס סדר חלקי על הקבוצה:
+
הערה: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר קטן ביותר הוא יחיד (למרות שהוא לא חייב להיות קיים), ונכון הדבר גם לגבי איבר גדול ביותר.
−
*איבר <math>x\in A</math> נקרא '''מינמלי''' ביחס לR אם <math>\forall y\in A:(y,x)\in R \rightarrow y=x</math>. כלומר, אין איבר 'קטן' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
+
−
*איבר <math>x\in A</math> נקרא '''מקסימלי''' ביחס לR אם <math>\forall y\in A:(x,y)\in R \rightarrow y=x</math>. כלומר, אין איבר 'גדול' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.
+
−
*איבר <math>x\in A</math> נקרא '''קטן ביותר''' ביחס לR אם <math>\forall y\in A:(x,y)\in R</math>. כלומר, x 'קטן' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה הריקה תחת יחס הכלה)
+
−
*איבר <math>x\in A</math> נקרא '''גדול ביותר''' ביחס לR אם <math>\forall y\in A:(y,x)\in R</math>. כלומר, x 'גדול' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה B תחת יחס ההכלה על קבוצת החזקה של B)
+
  
−
הערה: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר קטן ביותר הוא יחיד (למרות שהוא לא חייב להיות קיים), ונכון הדבר לגבי איבר גדול ביותר.
+
הערה: קטן ביותר גורר מינימלי, וכן גדול ביותר גורר מקסימלי. אבל לא להיפך!
  
−
הערה: קטן ביותר <math>\leftarrow</math> מינימלי, וכן גדול ביותר <math>\leftarrow</math> מקסימלי, ולא להיפך!
+
צייר את דיאגרמת הסה של היחס "מחלק את" על הקבוצה <math>A=\{1,2,...,10\}</math> מהם האיברים המינימליים והמקסימליים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?
−
 
+
צייר את היחס ההפוך של "מחלק את", זהו היחס "מתחלק ב". מהם האיברים המינימליים והמקסימליים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?
−
צייר את דיאגרמת הסה של היחס "מחלק את" על הקבוצה <math>A=\{1,2,...,10\}</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>A</math> קבוצה. מצא את הקבוצה <math>\{ R\subseteq A\times A:R\text{ is an order relation} \land \forall a\in A, a \text{ is maximal } \}</math>
  
 
====פתרון====
 
====פתרון====
שורה 36: שורה 37:
 
כיוון ראשון: כל יחס סדר <math>R</math> מקיים <math>I_A\subseteq R</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)
+
כיוון שני: יהי <math>(a,b) \in R</math>, אזי כיון ש-<math>a</math> מקסימלי נובע <math>b=a</math> ולכן <math>(a,b)=(a,a)
 
\in I_A</math> כדרוש.
 
\in I_A</math> כדרוש.
  
−
==חסמים==
+
===תרגיל===
−
'''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
+
 
−
*חסם מלעיל של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(y,x)\in R </math>
+
הוכח שאם <math>R</math> יחס סדר חלקי, אז גם היחס ההופכי שלו <math>R^{-1}</math> יחס סדר חלקי.
 +
 
 +
====פתרון====
 +
*רפלקסיביות: לכל איבר <math>a</math> מתקיים <math>(a,a)\in R</math> ולכן <math>(a,a)\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>.
 +
*אנטי-סימטריות: אם <math>x</math> ביחס ל-<math>y</math> וגם <math>y</math> ביחס ל-<math>x</math> הדבר נכון באופן זהה ל-<math>R</math> וליחס ההופכי שלו (כי 'וגם' חילופי), ולכן <math>x=y</math>.
 +
 
 +
'''הגדרה:''' יהי <math>R</math> יחס סדר חלקי על <math>A</math>. אם לכל שני איברים <math>a,b\in A</math> מתקיים <math>[(a,b)\in R]\or[(b,a)\in R]</math> אזי <math>R</math> נקרא '''יחס סדר מלא'''.
 +
 
 +
'''דוגמה''':
 +
היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא. שימו לב כי זו דוגמה ליחס סדר בלי איברים מינימליים או מקסימליים.
 +
 
 +
====דוגמא ליחס סדר מעניין====
 +
היחס המילוני.
 +
 
 +
====תרגיל====
 +
הוכיחו שאם <math>R</math> יחס סדר מלא על <math>A</math>, ו- <math>a\in A</math> איבר מינימלי יחיד אז הוא גם קטן ביותר.
 +
 
 +
==חסמים (בד"כ לא מלמדים בהנדסה)==
 +
'''הגדרות.''' יהיו <math>A</math> קבוצה, <math>B\subseteq A</math> תת קבוצה המוכלת בה ו-<math>R</math> יחס סדר חלקי:
 +
*חסם מלעיל של <math>B</math> הוא איבר <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>x\in A</math> כך שמתקיים <math>\forall y\in B:(x,y)\in R </math>
−
*החסם העליון (סופרמום) של B הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן <math>sup(B)</math>
+
*החסם העליון (סופרמום) של <math>B</math> הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן <math>\mathrm{sup}(B)</math>
−
*החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>inf(B)</math>
+
*החסם התחתון (אינפימום) של <math>B</math> הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>\mathrm{inf}(B)</math>
  
 
=== דוגמאות ===
 
=== דוגמאות ===
  
−
'''דוגמא'''
+
'''דוגמה''':
 
עבור <math>\{A_i\}_{i\in I}</math> אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא  
 
עבור <math>\{A_i\}_{i\in I}</math> אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא  
−
<math>\cup _{i\in I} A_i </math>
+
<math>\bigcup _{i\in I} A_i </math>.
−
 
+
−
'''דוגמא.'''
+
  
 +
'''דוגמה''':
 
נביט בקבוצה <math>A=\{1,2,3,4,5\}</math> ונגדיר עליה יחס סדר חלקי:
 
נביט בקבוצה <math>A=\{1,2,3,4,5\}</math> ונגדיר עליה יחס סדר חלקי:
  
−
<math>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>
+
<math>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>
  
 
(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)
 
(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)
  
−
נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד <math>B=\{1,3,5\}</math>. קבוצת חסמי המלעיל של B הינה <math>\{2,4\}</math>. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.
+
נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד <math>B=\{1,3,5\}</math>. קבוצת חסמי המלעיל של <math>B</math> הינה <math>\{2,4\}</math>. המינימום של קבוצה זו הוא <math>2</math> ולכן הוא החסם העליון של <math>B</math>. אין חסם מלרע ל-<math>B</math> ולכן בוודאי אין לה חסם תחתון.
 +
 
 +
'''הגדרה:'''
 +
יהיו <math>(A,\leq),(B,\preceq)</math> שתי קבוצות סדורות חלקית.
 +
 
 +
על <math>A\times B</math> נגדיר יחס סדר חלקי הנקרא '''היחס המילוני''' <math>R</math> לפי
 +
 
 +
<math>(a_1,b_1)R(a_2,b_2)\iff (a_1 < a_2) \lor (a_1 = a_2 \land b_1 \preceq b_2)</math>
 +
 
 +
'''דוגמה''':
 +
עבור היחס 'קטן שווה' על <math>\mathbb{N}</math> נסתכל על <math>\mathbb{N}\times \mathbb{N}</math> עם הסדר המילוני.
 +
 
 +
אם <math>B = \{(1,x) | x\in \mathbb{N} \}</math> אזי <math>\mathrm{inf}(B)=(1,1)</math>, <math>\mathrm{sup}(B)=(2,1)</math>.
  
−
'''הגדרה.''' יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים <math>[(a,b)\in R]\or[(b,a)\in R]</math> אזי R נקרא '''יחס סדר מלא'''.
+
אם <math>B = \{(x,1) | x\in \mathbb{N} \}</math> אזי <math>\mathrm{inf}(B)=(1,1)</math> ו-<math>\mathrm{sup}(B)</math> לא קיים.
  
−
למשל: היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא.
+
שימו לב ש-<math>(1,1)</math> הוא איבר קטן ביותר.
−
שימו לב כי זו דוגמא ליחס סדר בלי איברים מינימליים או מקסימליים.
+

גרסה אחרונה מ־12:13, 8 בינואר 2020

חזרה לדף מערכי התרגול.

יחסי סדר

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

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

  • היחס 'קטן-שווה' על המספרים השלמים
  • היחס 'מוכל-שווה' על קבוצת החזקה P(\{4,5,100\})
  • היחס 'מחלק את' על הטבעיים

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

הגדרה: דיאגרמת הסה (או תרשים הסה, Hasse diagram) הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר x מחובר בקשת לאיבר y מתחתיו 'גדול' ממנו ביחס (כלומר x>y), ובינם אין עוד איברים (כלומר אין z כך ש-x>z>y). נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה 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.

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

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

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

תרגיל

תהא A קבוצה. מצא את הקבוצה \{ R\subseteq A\times A:R\text{ is an order relation} \land \forall a\in A, a \text{ is maximal } \}

פתרון

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

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

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

תרגיל

הוכח שאם R יחס סדר חלקי, אז גם היחס ההופכי שלו R^{-1} יחס סדר חלקי.

פתרון

  • רפלקסיביות: לכל איבר 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.

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

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

דוגמא ליחס סדר מעניין

היחס המילוני.

תרגיל

הוכיחו שאם R יחס סדר מלא על A, ו- a\in A איבר מינימלי יחיד אז הוא גם קטן ביותר.

חסמים (בד"כ לא מלמדים בהנדסה)

הגדרות. יהיו A קבוצה, B\subseteq A תת קבוצה המוכלת בה ו-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 הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן \mathrm{sup}(B)
  • החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן \mathrm{inf}(B)

דוגמאות

דוגמה: עבור \{A_i\}_{i\in I} אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא \bigcup _{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 ולכן בוודאי אין לה חסם תחתון.

הגדרה: יהיו (A,\leq),(B,\preceq) שתי קבוצות סדורות חלקית.

על A\times B נגדיר יחס סדר חלקי הנקרא היחס המילוני R לפי

(a_1,b_1)R(a_2,b_2)\iff (a_1 < a_2) \lor (a_1 = a_2 \land b_1 \preceq b_2)

דוגמה: עבור היחס 'קטן שווה' על \mathbb{N} נסתכל על \mathbb{N}\times \mathbb{N} עם הסדר המילוני.

אם B = \{(1,x) | x\in \mathbb{N} \} אזי \mathrm{inf}(B)=(1,1), \mathrm{sup}(B)=(2,1).

אם B = \{(x,1) | x\in \mathbb{N} \} אזי \mathrm{inf}(B)=(1,1) ו-\mathrm{sup}(B) לא קיים.

שימו לב ש-(1,1) הוא איבר קטן ביותר.

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