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

נגדיר את היחס הבא: $$R = \left\{\langle f, g\rangle \in (\mathbb{N} \to \mathbb{N})^2 \mid \forall i \in \mathbb{N}.\, \left|f^{-1}[\{i\}]\right| = \left|g^{-1}[\{i\}]\right|\right\}$$ היחס הוא יחס שקילות (אין צורך להוכיח זאת). (א) מצאו תנאי מספיק והכרחי על $f \in \mathbb{N}^{\mathbb{N}}$ כך ש־$[f]_R = \{f\}$. אין צורך להוכיח. (ב) נגדיר $g = \lambda n \in \mathbb{N}.\begin{cases} 0 & n \in \mathbb{N}_{\text{even}} \\ 1 & n \in \mathbb{N}_{\text{odd}} \end{cases}$. מצאו את $|[g]_R|$. הוכיחו תשובתכם.

רמז: בסעיף (א) חשבו מתי פונקציה היא היחידה בעלת אותו "פרופיל" של גדלי מקורות — זה קורה כשהפונקציה חח"ע (קבועה). בסעיף (ב) $|[g]_R| = \aleph$ — בנו פונקציה חח"ע מ-$\{0,1\}^{3\mathbb{N}}$ אל $[g]_R$.

פתרון: **(א)** התנאי: $f$ היא **פונקציה חח"ע (חד-חד-ערכית)**. **(ב)** טענה: $|[g]_R| = \aleph$. **הוכחה:** מצד אחד $[g]_R \subseteq \mathbb{N}^{\mathbb{N}}$ ולכן $|[g]_R| \leq |\mathbb{N}^{\mathbb{N}}| = \aleph$. מצד שני נראה כי $|[g]_R| \geq |\{0,1\}^{3\mathbb{N}}| = 2^{\aleph_0} = \aleph$. נסמן $3\mathbb{N} = \{3n \mid n \in \mathbb{N}\}$. נגדיר פונקציה חח"ע $h$ מ-$\{0,1\}^{3\mathbb{N}}$ אל $[g]_R$: $$h = \lambda f \in \{0,1\}^{3\mathbb{N}}.\lambda n \in \mathbb{N}.\begin{cases} f(n) & n \in 3\mathbb{N} \\ 0 & n+1 \in 3\mathbb{N} \\ 1 & n+2 \in 3\mathbb{N} \end{cases}$$ $h$ מוגדרת היטב. $h$ **חח"ע** שכן לכל $f \in \{0,1\}^{3\mathbb{N}}$ מתקיים $h(f)|_{3\mathbb{N}} = f$. נרצה לטעון כי לכל $f \in \{0,1\}^{3\mathbb{N}}$ מתקיים $h(f) \in [g]_R$, כלומר $\forall i \in \mathbb{N}.\,|g^{-1}(\{i\})| = |h(f)^{-1}(\{i\})|$. - אם $i \geq 2$ אזי $|g^{-1}(\{i\})| = 0 = |h(f)^{-1}(\{i\})|$. - אם $i = 0$ אזי $|h(f)^{-1}(\{0\})| \geq |\{3n+1 \mid n \in \mathbb{N}\}| = \aleph_0$ ולפי **קש"ב** נקבל $|g^{-1}(\{0\})| = \aleph_0 = |h(f)^{-1}(\{0\})|$. - באופן דומה עבור $i = 1$. לסיכום: $$\aleph = |\{0,1\}^{3\mathbb{N}}| \leq |[g]_R| \leq |\mathbb{N}^{\mathbb{N}}| = \aleph$$ ולכן לפי **קש"ב** $|[g]_R| = \aleph$. $\blacksquare$