שינויים

===תרגיל===יהיו <math>A=\{1חזרה ל[[83-116,2\}, B=\{3,4,5\}</math>. נגדיר את היחס: <math>R=\{(בדידה 1להנדסה,3),(2,4)\}</math>מערכי תרגול|דף מערכי התרגול]]. בדוק האם:

א. ==יחסי סדר=='''הגדרה:''' יחס <math>R^{-1}\circ </math> על קבוצה <math>A</math> נקרא '''יחס סדר חלקי''' אם <math>R=I_A</math>רפלקסיבי, טרנזיטיבי ואנטי-סימטרי.

ב. דוגמאות ליחסי סדר חלקי: *היחס 'קטן-שווה' על המספרים השלמים*היחס 'מוכל-שווה' על קבוצת החזקה <math>RP(\circ R^{-14,5,100\}=I_B)</math>*היחס 'מחלק את' על הטבעיים

==תכונות של יחסים על קבוצה=='''הגדרה: ''' דיאגרמת הסה (או תרשים הסה, Hasse diagram) הינה דיאגרמה של יחס R סדר חלקי על קבוצה A פירושו . כל איבר <math>x</math> מחובר בקשת לאיבר <math>y</math> מתחתיו 'גדול' ממנו ביחס (כלומר <math>x>y</math>), ובינם אין עוד איברים (כלומר אין <math>z</math> כך ש-<math>x>z>y</math>). נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>R\subseteq A=\times A{1,2,3\}</math>.

תהי קבוצה '''הגדרות:''' יהיו <math>A ויחס </math> קבוצה ו-<math>R עליה אזי </math> יחס סדר חלקי על הקבוצה:#R *איבר <math>x\in A</math> נקרא '''רפלקסיבימינימלי''' ביחס ל-<math>R</math> אם כל איבר מקיים את היחס עם עצמו ( מתקיים <math>\forall ay\in A:(ay,ax)\in R\rightarrow y=x</math>). כלומר, אין איבר 'קטן' מ-<math>x</math>. לא חייב להתקיים ש-<math>x</math> ביחס כלשהו עם איבר כלשהו.#R *איבר <math>x\in A</math> נקרא '''סימטרימקסימלי''' ביחס ל-<math>R</math> אם aRb גורר שגם bRa (מתקיים <math>\forall a,by\in A:[(ax,by)\in R \rightarrow (by=x</math>. כלומר,a)אין איבר 'גדול' מ-<math>x</math>. לא חייב להתקיים ש-<math>x</math> ביחס כלשהו עם איבר כלשהו.*איבר <math>x\in R]A</math>)#R נקרא '''טרנזיטיביקטן ביותר''' ביחס ל-<math>R</math> אם יחס בין ראשון לשני, ויחס בין השני לשלישי גורר יחס בין הראשון לשלישי (מתקיים <math>\forall a,b,cy\in A:[((ax,by)\in R) \and ((b</math>. כלומר,c)\in R) \rightarrow ((a<math>x</math> 'קטן' מכל האיברים. <math>x</math> חייב להיות ביחס עם כל האיברים בקבוצה. למשל,c)הקבוצה הריקה תחת יחס הכלה.*איבר <math>x\in R)]A</math>)#R נקרא '''אנטי סימטרי (חלש)גדול ביותר''' ביחס ל-<math>R</math> אם aRb וגם bRa גורר כי a=b (מתקיים <math>\forall a,by\in A:[(ay,bx)\in R \and (b</math>. כלומר,a)\in R \rightarrow a=b]<math>x</math> ובאופן שקול: 'גדול' מכל האיברים. <math>\forall a\neq b\in A: \lnot (aRb\land bRa)x</math>)חייב להיות ביחס עם כל האיברים בקבוצה. למשל, הקבוצה <math>B</math> תחת יחס ההכלה על קבוצת החזקה של <math>B</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 צייר את דיאגרמת הסה של היחס "מחלק את" על הקבוצה <math>A נקרא '''יחס סדר חלקי''' אם R רפלקסיבי=\{1,2,...,10\}</math> מהם האיברים המינימליים והמקסימליים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?צייר את היחס ההפוך של "מחלק את", טרנזיטיבי ואנטי-סימטרי זהו היחס "מתחלק ב". מהם האיברים המינימליים והמקסימליים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?

'''הגדרה.''' דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על תהא <math>A</math> קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר מצא את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>\{ R\subseteq A=\times A:R\text{1,2is an order relation} \land \forall a\in A,3a \text{ is maximal } \}</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=I_A</math>. כלומר, x 'קטן' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה הריקה תחת יחס הכלה)*איבר <math>x\in A</math> נקרא '''גדול ביותר''' ביחס לR אם <math>\forall y\in A:(y,x)\in R</math>. כלומר, x 'גדול' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה B תחת יחס ההכלה על קבוצת החזקה של B)

הערהכיוון ראשון: קל להוכיח מתוך תכונת האנטי-סימטריות שאם קיים איבר קטן ביותר הוא יחיד (למרות שהוא לא חייב להיות קיים), ונכון הדבר לגבי איבר גדול ביותרכל יחס סדר <math>R</math> מקיים <math>I_A\subseteq R</math>.

הערהכיוון שני: קטן ביותר יהי <math>(a,b) \leftarrowin R</math> מינימלי, וכן גדול ביותר אזי כיון ש-<math>\leftarrowa</math> מקסימלינובע <math>b=a</math> ולכן <math>(a, ולא להיפך!b)=(a,a)\in I_A</math> כדרוש.

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

'''הערה:'''עבור הוכח שאם <math>AR</math> קבוצה ויחס יחס סדר חלקי עליה. נסמן , אז גם היחס ההופכי שלו <math>(A,\leq )R^{-1}</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>

*החסם העליון (סופרמום) של <math>B </math> הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן <math>\mathrm{sup}(B)</math>*החסם התחתון (אינפימום) של <math>B </math> הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>\mathrm{inf}(B)</math>

'''דוגמאדוגמה''':

<math>\cup bigcup _{i\in I} A_i </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>.

'''הגדרה.''' יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים <math>[B = \{(ax,b1)| x\in R]\or[mathbb{N} \}</math> אזי <math>\mathrm{inf}(B)=(b1,a1)</math> ו-<math>\in R]mathrm{sup}(B)</math> אזי R נקרא '''יחס סדר מלא'''לא קיים.

למשל: היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא.שימו לב כי זו דוגמא ליחס סדר בלי איברים מינימליים או מקסימלייםש-<math>(1,1)</math> הוא איבר קטן ביותר.