===תרגיל===
יהיו <math>A=\{1,2\}, B=\{3,4,5\}</math>. נגדיר את היחס: <math>R=\{(1,3),(2,4)\}</math>. בדוק האם:
א. <math>R^{-1}\circ R=I_A</math>
ב. <math>R\circ R^{-1}=I_B</math>
==תכונות של יחסים על קבוצה==
הגדרה: יחס R על קבוצה A פירושו <math>R\subseteq A\times A</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' הינו רפלקסיבי, סימטרי וטרנזיטיבי
*יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
*יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי
*יחס 'אדם x שמע על אדם y' הינו רפלקסיבי
'''הערה:''' יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמא: <math>A=\{ 1,2,3\} , R=\{ (1,1)\} , S=\{ (1,2),(2,1),(3,2)\}</math> ואז R גם וגם, S לא ולא.
==יחסי סדר==
'''הגדרה:''' יחס R על A נקרא '''יחס סדר חלקי''' אם R רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
*היחס 'מוכל-שווה' על הקבוצות
*היחס 'מחלק את ' על הטבעיים
'''הערה:'''
עבור <math>A</math> קבוצה ויחס סדר חלקי עליה. נסמן <math>(A,\leq )</math> את הקבוצה עם היחס
'''הגדרה.''' דיאגרמת הסה Hesse הינה דיאגרמה של יחס סדר חלקי על קבוצה. כל איבר המקושר לאיבר מתחתיו 'גדול' ממנו ביחס. נצייר את דיאגרמת הסה ליחס הכלה על קבוצת החזקה של הקבוצה <math>A=\{1,2,3\}</math>.
צייר את היחס ההפוך של "מחלק את", זהו היחס "מתחלק ב". מהם האיברים המינימלים והמקסימלים? האם קיים איבר קטן ביותר ואיבר גדול ביותר?
'''הערה:'''===תרגיל=== עבור תהא <math>A</math> קבוצה ויחס סדר חלקי עליה. נסמן חשב את <math>(|\{ R\subseteq A,\leq )times A:R\text{ is order relation} \land \forall a\in A. a \text{ is maximally and minimally} \}|</math> ====פתרון==== נראה שיש רק יחס אחד כזה, והוא הזהות. יחס הזהות אכן מקיים את הקבוצה עם היחסהתנאי. נניח ש-<math>R</math> יחס סדר המקיים את התנאי ונראה ש-<math>R=I_A</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> כדרוש.
==חסמים==
'''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
*חסם מלעיל של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(y,x)\in R </math>