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

בהינתן $A, B$ קבוצות, נגדיר: $$G = \lambda S \in \mathcal{P}(A \times B). \lambda X \in \mathcal{P}(A). \bigcup_{a \in X} \{b \in B \mid \langle a, b \rangle \in S\}.$$ הוכיחו או הפריכו את הטענות הבאות: א. (9 נקודות) אם $A, B$ לא ריקות, $G$ חד חד ערכית. ב. (8 נקודות) אם $A, B$ לא ריקות, $G$ על $\mathcal{P}(A) \to \mathcal{P}(B)$.

רמז: לחח"ע: אם S1 ושונה מ-S2, קחו זוג ב-S1\S2 והראו שהפונקציות G(S1) ו-G(S2) נותנות ערכים שונים על הסינגלטון {x}. לעל: שימו לב ש-G(S)(empty)=empty תמיד, אז כל f עם f(empty) לא ריק לא בתמונה.

פתרון: **סעיף א: הוכחה - $G$ חד-חד-ערכית.** יהיו $S_1, S_2 \in \mathcal{P}(A \times B)$, $S_1 \neq S_2$. בלי הגבלת הכלליות קיים זוג $\langle x, y \rangle \in S_1 \setminus S_2$. נראה כי $G(S_1) \neq G(S_2)$. נשים לב כי $y \in G(S_1)(\{x\})$ בעוד $y \notin G(S_2)(\{x\})$ מהגדרת $G$, ומכאן שהפונקציות $G(S_1), G(S_2)$ שונות. $\blacksquare$ **סעיף ב: הפרכה - $G$ אינה על.** נשים לב שמהגדרת $G$, לכל $S \in \mathcal{P}(A \times B)$ מתקיים $G(S)(\emptyset) = \emptyset$. נגדיר את הפונקציה $f \in \mathcal{P}(A) \to \mathcal{P}(B)$ באופן הבא: $f = \lambda X \in \mathcal{P}(A). B$. בפרט $f$ מקיימת $f(\emptyset) = B$ כאשר $B$ אינה ריקה, ולכן לא קיים $S \in \mathcal{P}(A \times B)$ עבורו $G(S) = f$. $\blacksquare$