חזרה ל[[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> את הקבוצה עם היחס.
'''הגדרה:''' דיאגרמת הסה (או תרשים הסה, 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=\{1,2,...,10\}</math> מהם האיברים המינימליים והמקסימליים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?
צייר את היחס ההפוך של "מחלק את", זהו היחס "מתחלק ב". מהם האיברים המינימליים והמקסימליים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?
===תרגיל===
יהיו <math>A=\{1,2\}, B=\{3,4,5\}</math>. נגדיר את היחס: <math>R=\{(1,3),(2,4)\}</math>. בדוק האם:
אתהא <math>A</math> קבוצה. מצא את הקבוצה <math>\{ R^\subseteq A\times A:R\text{-1is an order relation}\circ R=I_Aland \forall a\in A, a \text{ is maximal } \}</math>
ב====פתרון==== נראה שיש רק יחס אחד כזה, והוא הזהות. יחס הזהות אכן מקיים את התנאי. נניח ש-<math>R</math> יחס סדר המקיים את התנאי ונראה ש-<math>R=I_A</math>: כיוון ראשון: כל יחס סדר <math>R</math> מקיים <math>I_A\circ subseteq R^{</math>. כיוון שני: יהי <math>(a,b) \in R</math>, אזי כיון ש-1}<math>a</math> מקסימלי נובע <math>b=I_Ba</math>ולכן <math>(a,b)=(a,a)\in I_A</math> כדרוש.
===תרגיל===
תהיינה <math>A,B,C</math> קבוצות, <math>R\subseteq A\times B,T,S\subseteq B\times C</math>. הוכח או הפרך:
א. הוכח שאם <math>T\circ R=S\circ </math> יחס סדר חלקי, אז גם היחס ההופכי שלו <math>R\iff T=S^{-1}</math>יחס סדר חלקי.
ב. ====פתרון====*רפלקסיביות: לכל איבר <math>Ta</math> מתקיים <math>(a,a)\subseteq Sin R</math> ולכן <math>(a,a)\Rightarrow Tin R^{-1}</math>.*טרנזיטיביות: נניח <math>(x,y),(y,z)\circ in R^{-1}</math> לכן מתקיים <math>(y,x),(z,y)\subseteq Sin R</math> לכן לפי הטרנזיטיביות של R מתקיים <math>(z,x)\circ 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>\Leftarrow<'''דוגמה''':היחס 'קטן שווה' על השלמים/math> בוודאי נכוןהממשיים הוא יחס סדר מלא. אבל הכיוון השני לא מתקייםשימו לב כי זו דוגמה ליחס סדר בלי איברים מינימליים או מקסימליים. דוגמא נגדית: ניקח: <math>A=\{ 1,2\} ,R=T=\{ (1,1)\} \subseteq A\times A,S=\{ (1,1),(2,2)\} \subseteq A\times A</math>
ונקבל: <math>T\circ R=S\circ R=\{ (1,1)\}</math> אבל כמובן <math>S\neq T</math>==דוגמא ליחס סדר מעניין====היחס המילוני.
ב. הוכחה: יהי ====תרגיל====הוכיחו שאם <math>(x,z)\in T\circ R</math> אזי לפי הגדרה קיים יחס סדר מלא על <math>y\in BA</math> כך ש- <math>(x,y)\in R\land (y,z)\in T</math>. כעת, כיון שו-<math>T\subseteq S</math> נובע ש- <math>(y,z)a\in S</math>, ולכן לפי הגדרת ההרכבה נקבל <math>(x,z)\in S\circ RA</math>איבר מינימלי יחיד אז הוא גם קטן ביותר.
==תכונות של יחסים על קבוצהחסמים (בד"כ לא מלמדים בהנדסה)==הגדרה: יחס R על '''הגדרות.''' יהיו <math>A</math> קבוצה , <math>B\subseteq A פירושו </math> תת קבוצה המוכלת בה ו-<math>R</math> יחס סדר חלקי:*חסם מלעיל של <math>B</math> הוא איבר <math>x\subseteq in A</math> כך שמתקיים <math>\times 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>
תהי קבוצה 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' הינו רפלקסיבי, סימטרי וטרנזיטיביעבור <math>\{A_i\}_{i\in I}</math> אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא *יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי*יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי*יחס 'אדם x שמע על אדם y' הינו רפלקסיבי<math>\bigcup _{i\in I} A_i </math>.
'''הערה:דוגמה''' יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמא: נביט בקבוצה <math>A=\{ 1,2,3\} , R=\{ (14,1)\} , S=\{ (1,2),(2,1),(3,2)5\}</math> ואז R גם וגם, S לא ולא.ונגדיר עליה יחס סדר חלקי:
==יחסי סדר=='''הגדרה:''' יחס <math>R על A נקרא '''יחס סדר חלקי''' אם 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> לפי
'''הגדרה.''' דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>A=\{1(a_1,2b_1)R(a_2,3b_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> עם הסדר המילוני.
'''הגדרות.''' יהיו A קבוצה וR יחס סדר חלקי על הקבוצה:*איבר <math>x\in A</math> נקרא '''מינמלי''' ביחס לR אם <math>B = \forall y\in A:{(y1,x)| x\in R \rightarrow y=x</math>. כלומר, אין איבר 'קטן' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.*איבר <math>xmathbb{N} \in A}</math> נקרא '''מקסימלי''' ביחס לR אם אזי <math>\forall y\in A:mathrm{inf}(x,yB)\in R \rightarrow y=x</math>. כלומר, אין איבר 'גדול' מx. לא חייב להתקיים ש-x ביחס כלשהו עם איבר כלשהו.*איבר <math>x\in A</math> נקרא '''מינימום''' ביחס לR אם <math>\forall y\in A:(x1,y1)\in R</math>. כלומר, x 'קטן' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה הריקה תחת יחס הכלה)*איבר <math>x\in A</math> נקרא '''מקסימום''' ביחס לR אם <math>\forall y\in A:mathrm{sup}(B)=(y2,x1)\in R</math>. כלומר, x 'גדול' מכל האיברים. x חייב להיות ביחס עם כל האיברים בקבוצה. (דוגמא: הקבוצה B תחת יחס ההכלה על קבוצת החזקה של B)
הערה: קל להוכיח מתוך תכונת האנטיאם <math>B = \{(x,1) | x\in \mathbb{N} \}</math> אזי <math>\mathrm{inf}(B)=(1,1)</math> ו-סימטריות שאם קיים איבר מינימום הוא יחיד <math>\mathrm{sup}(למרות שהוא B)</math> לא חייב להיות קיים), ונכון הדבר לגבי המקסימום.
הערה: מינימום שימו לב ש-<math>\leftarrow</math> מינימלי(1, וכן מקסימום <math>\leftarrow1)</math> מקסימלי, ולא להיפך!הוא איבר קטן ביותר.