=יחסים=
==המכפלה הקרטזית==
הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות A וB הינה אוסף כל ה'''זוגות הסדורים''' - <math>A\times B = \{(a,b)|a\in A \and b\in B\}</math>. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים <math>(1,2),(2,1)</math> והאיבר הבא הינו זוג חוקי <math>(1,1)</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:\lor (aRb\land bRa)</math>)
דוגמאות:
*יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
*יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
*יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
*יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי
*יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
*יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי
*יחס 'אדם x שמע על אדם y' הינו רפלקסיבי