שאלת מבחן במתמטיקה בדידה - אוניברסיטת תל אביב 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|$. הוכיחו תשובתכם.

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

פתרון: **(א)** התנאי: $f$ היא **פונקציה קבועה**. **הסבר (לא נדרש להוכיח):** הפרופיל של $f$ הוא הפונקציה $i \mapsto |f^{-1}[\{i\}]|$. אם $f$ **אינה** קבועה, יש לה לפחות שני ערכים שונים ולכן לפחות שתי קבוצות-מקור לא ריקות בתחום; תמיד אפשר להחליף (או לסדר מחדש) אלמנטים בין קבוצות-המקור הללו ולקבל פונקציה $g \neq f$ עם **אותו פרופיל בדיוק** — למשל, אם $f$ חח"ע, כל תמורה לא-טריוויאלית של $\mathbb{N}$ מרכיבה עם $f$ (כלומר $f \circ \pi$) נותנת פונקציה שונה מ-$f$ עם אותו פרופיל (כל המקורות עדיין בגודל $1$). לכן $[f]_R \neq \{f\}$. לעומת זאת, אם $f$ קבועה עם ערך $c$, אז $|f^{-1}[\{c\}]| = \aleph_0$ ו-$|f^{-1}[\{i\}]| = 0$ לכל $i \neq c$ — פרופיל זה מכריח $g(n) = c$ לכל $n \in \mathbb{N}$ עבור כל $g$ בעלת אותו פרופיל (כי $g$ אינה יכולה לקבל אף ערך אחר), ולכן $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$