שינויים

אתהא <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>R</math> יחס סדר חלקי, אז גם היחס ההופכי שלו <math>R^{-1}</math> יחס סדר חלקי.  ====פתרון====*רפלקסיביות: לכל איבר <math>Ta</math> מתקיים <math>(a,a)\circ 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=Sy</math>. '''הגדרה:''' יהי <math>R</math> יחס סדר חלקי על <math>A</math>. אם לכל שני איברים <math>a,b\circ in A</math> מתקיים <math>[(a,b)\in R]\iff Tor[(b,a)\in R]</math> אזי <math>R</math> נקרא '''יחס סדר מלא'''. '''דוגמה''':היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא. שימו לב כי זו דוגמה ליחס סדר בלי איברים מינימליים או מקסימליים. ====דוגמא ליחס סדר מעניין====היחס המילוני. ====תרגיל====Sהוכיחו שאם <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>*החסם העליון (סופרמום) של <math>B</math> הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן <math>\mathrm{sup}(B)</math>*החסם התחתון (אינפימום) של <math>B</math> הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>\mathrm{inf}(B)</math> === דוגמאות === '''דוגמה''':עבור <math>\{A_i\}_{i\in I}</math> אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא <math>\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>\Leftarrow</math> בוודאי נכון. אבל הכיוון השני לא מתקיים. דוגמא נגדית: ניקח'''הגדרה:''' יהיו <math>A=\{ 1,2\} ,R=T=\{ (1,1)\} \subseteq A\times A,S=\{ (1,1leq),(2B,2\preceq)\} \subseteq A\times A</math>שתי קבוצות סדורות חלקית.

ונקבל: על <math>TA\circ R=S\circ R=\{ (1,1)\}times B</math> אבל כמובן נגדיר יחס סדר חלקי הנקרא '''היחס המילוני''' <math>S\neq TR</math>.לפי

ב. הוכחה: יהי <math>(xa_1,zb_1)\in T\circ R</math> אזי לפי הגדרה קיים <math>y\in B</math> כך ש- <math>(xa_2,yb_2)\in R\land iff (y,z)\in Ta_1 </math>. כעת, כיון ש-<math>T\subseteq S</math> נובע ש- <math>(y,za_2)\in S</math>, ולכן לפי הגדרת ההרכבה נקבל <math>lor (x,z)a_1 = a_2 \in Sland b_1 \circ Rpreceq b_2)</math>.

==תכונות של יחסים על קבוצה==הגדרה'''דוגמה''': יחס R עבור היחס 'קטן שווה' על קבוצה A פירושו <math>R\subseteq Amathbb{N}</math> נסתכל על <math>\mathbb{N}\times A\mathbb{N}</math>עם הסדר המילוני.

תהי קבוצה A ויחס R עליה אזי #R נקרא '''רפלקסיבי''' אם כל איבר מקיים את היחס עם עצמו ( מתקיים <math>B = \forall a\in A:{(a1,ax)| x\in R\mathbb{N} \}</math>)#R נקרא '''סימטרי''' אם aRb גורר שגם bRa (מתקיים אזי <math>\forall a,b\in A:[mathrm{inf}(a,bB)\in R \rightarrow =(b1,a1)\in R]</math>)#R נקרא '''טרנזיטיבי''' אם יחס בין ראשון לשני, ויחס בין השני לשלישי גורר יחס בין הראשון לשלישי (מתקיים <math>\forall a,b,c\in A:[mathrm{sup}((a,bB)\in R) \and ((b,c)\in R) \rightarrow ((a,c)\in R)]</math>)#R נקרא '''אנטי סימטרי (חלש)''' אם aRb וגם bRa גורר כי a=b (מתקיים <math>\forall a2,b\in A:[(a,b1)\in R \and (b,a)\in R \rightarrow a=b]</math> ובאופן שקול: <math>\forall a\neq b\in A: \lnot (aRb\land bRa)</math>).

דוגמאות:*יחס 'שיוויון' הינו רפלקסיביאם <math>B = \{(x, סימטרי וטרנזיטיבי*יחס 'קטן שווה' הינו רפלקסיבי1) | x\in \mathbb{N} \}</math> אזי <math>\mathrm{inf}(B)=(1, טרנזיטיבי ואנטי סימטרי*יחס 'קטן ממש' הינו טרנזיטיבי ואנטי1)</math> ו-סימטרי*יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי*יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי*יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי*יחס 'אדם x שמע על אדם y' הינו רפלקסיבי<math>\mathrm{sup}(B)</math> לא קיים.

'''הערה:''' יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמא: שימו לב ש-<math>A=\{ 1,2,3\} , R=\{ (1,1)\} , S=\{ (1,2),(2,1),(3,2)\}</math> ואז R גם וגם, S לא ולאהוא איבר קטן ביותר.