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

תהי $A$ קבוצה ונניח ש $S \subseteq A \times A$ יחס שקילות מעל $A$. כיתבו פסוק (בשפה פורמלית) ששקול לכך ש: בכל מחלקת שקילות של $S$ יש בדיוק שני איברים. שימו לב: - בפסוק שאתם כותבים צריך להופיע משתנה חופשי יחיד והוא $S$. - לא צריך להצרין את העובדה ש $S$ שקילות. - אסור להשתמש ב $|\cdot|$ - עוצמת הקבוצה ואסור להשתמש בסימון $X/Y$ לקבוצת מנה. ב. הוכיחו או הפריכו: אם $T \subseteq A \times A$ יחס רפלקסיבי וגם לכל $x \in A$ קיים $y \in A$ יחיד ששונה מ- $x$ כך ש $xTy$, אז $T$ יחס שקילות על $A$.

רמז: בסעיף א, צריך לכתוב שלכל איבר קיים בדיוק איבר אחד נוסף ששונה ממנו ונמצא באותה מחלקה. בסעיף ב, חפשו דוגמה נגדית עם 3 איברים שבה היחס רפלקסיבי ולכל איבר יש בדיוק שכן אחד ביחס, אך אין סימטריה.

פתרון: **א.** מספר תשובות שהתקבלו: $$\forall \langle x, x \rangle \in S. \exists! \langle x, y \rangle \in S. x \neq y$$ $$\forall a \in A. \exists b \in A. a \neq b \land aSb \land \forall c \in A.(c \neq a \land c \neq b) \to \neg aSc$$ $$\forall a \in A. \exists! b \in A. a \neq b \land aSb$$ טעויות נפוצות: שימוש באיוטא (לא אותו דבר כמו "קיים יחיד"), תחביר לא נכון (למשל $\forall [a]_S$ מבלי לציין לאיזו קבוצה שייך משתנה זה, אך שימו לב שהוא שייך ל- $A/S$ ונאסר להשתמש בסימון זה). **ב.** הטענה **לא נכונה**. דוגמה נגדית: $T \subseteq \mathbb{N} \times \mathbb{N}$ $T = \{\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle, \langle 1,2 \rangle, \langle 2,3 \rangle, \langle 3,1 \rangle\}$ יחס זה מקיים את התנאים שבשאלה (רפלקסיבי, ולכל איבר קיים יחיד שונה ממנו ביחס), אבל **לא שקילות** (למשל אינו סימטרי: $1T2$ אבל לא $2T1$). $\blacksquare$