שאלת מבחן במתמטיקה בדידה - אוניברסיטת תל אביב 2018 - יחסים

סמנו בעיגול את **כל** התכונות $p$ של יחסים $S$ ב-$\mathbb{R}$ עבורן לכל יחס $S$ שמקיים $p$ אז גם $S^{-1}$ מקיים $p$: א. רפלקסיבי. ב. סימטרי. ג. טרנזיטיבי. ד. חד-ערכי. ה. מלא.

רמז: בדקו כל תכונה: אם $(a,b) \in S^{-1}$ פירושו $(b,a) \in S$. חשבו האם כל תכונה נשמרת תחת היפוך סדר הזוגות.

פתרון: **התשובות הנכונות הן: ב (סימטרי) וג (טרנזיטיבי).** נובע מהגדרת התכונות: - **רפלקסיבי**: אם $S$ רפלקסיבי אז $(a,a) \in S$ לכל $a$, ולכן $(a,a) \in S^{-1}$ - כן, נשמר. (תשובה נכונה) - **סימטרי**: אם $(a,b) \in S^{-1}$ אז $(b,a) \in S$, ומסימטריה $(a,b) \in S$, ולכן $(b,a) \in S^{-1}$ - כן, נשמר. (תשובה נכונה) - **טרנזיטיבי**: אם $(a,b),(b,c) \in S^{-1}$ אז $(b,a),(c,b) \in S$, ומטרנזיטיביות $(c,a) \in S$, ולכן $(a,c) \in S^{-1}$ - כן, נשמר. (תשובה נכונה) - **חד-ערכי**: לא בהכרח. יחס רפלקסיבי על קבוצה עם יותר מאיבר אחד הוא לא חד-ערכי, אבל ההופכי שלו גם לא. דוגמה נגדית: $S = \{(1,1),(1,2)\}$ הוא חד-ערכי (פונקציה) אך $S^{-1} = \{(1,1),(2,1)\}$ אינו חד-ערכי. - **מלא**: לא בהכרח נשמר בהיפוך. לפי הפתרון הרשמי: התשובות הנכונות הן **ב (סימטרי) וג (טרנזיטיבי)**. $\blacksquare$