שינויים
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
==יחסי סדר==
'''הגדרה:''' יחס <math>R </math> על קבוצה <math>A </math> נקרא '''יחס סדר חלקי''' אם <math>R </math> רפלקסיבי, טרנזיטיבי ואנטי-סימטרי .
דוגמאות ליחסי סדר חלקי:
*היחס 'קטן-שווה' על המספריםהשלמים*היחס 'מוכל-שווה' על הקבוצותקבוצת החזקה <math>P(\{4,5,100\})</math>*היחס 'מחלק את ' על הטבעיים
'''הערה:'''
עבור <math>A</math> קבוצה ויחס סדר חלקי <math>\leq</math> עליה. , נסמן <math>(A,\leq )</math> את הקבוצה עם היחס.
'''הגדרה.:''' דיאגרמת הסה Hesse (או תרשים הסה, 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>.
הערה: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר קטן ביותר הוא יחיד (למרות שהוא לא חייב להיות קיים)גורר מינימלי, ונכון הדבר לגבי איבר וכן גדול ביותרגורר מקסימלי.אבל לא להיפך!
===תרגיל===
תהא <math>A</math> קבוצה. חשב מצא את הקבוצה <math>|\{ R\subseteq A\times A:R\text{ is an order relation} \land \forall a\in A. , a \text{ is maximally and minimallymaximal } \}|</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> כדרוש.
===תרגיל=== הוכח שאם <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> תת קבוצה המוכלת בה וR ו-<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>
*החסם העליון (סופרמום) של <math>B </math> הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן <math>\mathrm{sup}(B)</math>*החסם התחתון (אינפימום) של <math>B </math> הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>\mathrm{inf}(B)</math>
=== דוגמאות ===
'''דוגמאדוגמה''':
עבור <math>\{A_i\}_{i\in I}</math> אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא
<math>\cup bigcup _{i\in I} A_i </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>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>.