שינויים

אתהא <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\circ R^{-1}=I_B</math>===פתרון====

==תכונות של יחסים על קבוצה==הגדרהכיוון ראשון: כל יחס R על קבוצה A פירושו סדר <math>R</math> מקיים <math>I_A\subseteq A\times AR</math>.

תהי קבוצה A ויחס R עליה אזי #R נקרא '''רפלקסיבי''' אם כל איבר מקיים את היחס עם עצמו ( מתקיים כיוון שני: יהי <math>\forall a\in A:(a,ab)\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 =(ba,a)\in R \rightarrow a=b]I_A</math> ובאופן שקול: <math>\forall a\neq b\in A: \lnot (aRb\land bRa)</math>)כדרוש.

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

==יחסי סדר==פתרון===='''הגדרה*רפלקסיביות:''' יחס לכל איבר <math>a</math> מתקיים <math>(a,a)\in R על A נקרא '''יחס סדר חלקי''' אם </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>*החסם העליון (סופרמום) של <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>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> נגדיר יחס סדר חלקי הנקרא '''הגדרה.היחס המילוני''' דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>A=\{1,2,3\}R</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 Amathbb{N}</math> נקרא '''מקסימלי''' ביחס לR אם נסתכל על <math>\forall ymathbb{N}\in A:(x,y)\in R times \rightarrow y=xmathbb{N}</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>B = \{(למרות שהוא לא חייב להיות קיים1,x)| x\in \mathbb{N} \}</math> אזי <math>\mathrm{inf}(B)=(1, ונכון הדבר לגבי איבר גדול ביותר1)</math>, <math>\mathrm{sup}(B)=(2,1)</math>.

הערה: קטן ביותר אם <math>B = \leftarrow{(x,1) | x\in \mathbb{N} \}</math> מינימליאזי <math>\mathrm{inf}(B)=(1, וכן גדול ביותר 1)</math> ו-<math>\leftarrowmathrm{sup}(B)</math> מקסימלי, ולא להיפך!לא קיים.

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