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

הוכיחו בעזרת לכסון שהקבוצה הבאה אינה מעוצמת הרצף ($\aleph$): $$A = \{f \in \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N}) \mid |f^{-1}[\{\mathbb{N}_{\text{EVEN}}\}]| = \aleph\}$$ רמז: ניתן להסתמך על הטענה ש-$\aleph = |\mathcal{P}(\mathbb{N}^+)|$.

רמז: חלקו את $\mathcal{P}(\mathbb{N})$ לשתי קבוצות זרות $P_1, P_2$ כל אחת מעוצמה $\aleph$. השתמשו ב-$P_1$ ללכסון וב-$P_2$ כדי להבטיח שהפונקציה שתבנו אכן ב-$A$.

פתרון: **הוכחה:** נוכיח ש-$|A| > \aleph$, ולכן $|A| \neq \aleph$. תהי $\varphi: \mathcal{P}(\mathbb{N}) \to A$ פונקציה כלשהי. נראה ש-$\varphi$ אינה על, כלומר קיים $f^* \in A$ כך ש-$f^* \notin \text{Im}(\varphi)$. **שלב 1 – חלוקה:** מכיוון ש-$|\mathcal{P}(\mathbb{N})| = \aleph$ ו-$\aleph + \aleph = \aleph$ (עוצמה אינסופית), נחלק $\mathcal{P}(\mathbb{N}) = P_1 \cup P_2$ כאשר $P_1 \cap P_2 = \emptyset$ ו-$|P_1| = |P_2| = \aleph$. תהי $\alpha: \mathcal{P}(\mathbb{N}) \to P_1$ ביקציה (קיימת כי $|\mathcal{P}(\mathbb{N})| = \aleph = |P_1|$). **שלב 2 – בניית $f^*$ בלכסון:** נגדיר $f^*: \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$ כך: - לכל $T \in P_1$: יהי $S = \alpha^{-1}(T)$ (כלומר $T = \alpha(S)$). נגדיר: $$f^*(T) = \begin{cases} \mathbb{N}_{\text{ODD}} & \text{אם } (\varphi(S))(T) = \mathbb{N}_{\text{EVEN}} \\ \mathbb{N}_{\text{EVEN}} & \text{אחרת} \end{cases}$$ - לכל $T \in P_2$: נגדיר $f^*(T) = \mathbb{N}_{\text{EVEN}}$. **שלב 3 – $f^* \in A$:** צריך להראות $|{f^*}^{-1}[\{\mathbb{N}_{\text{EVEN}}\}]| = \aleph$. ${f^*}^{-1}[\{\mathbb{N}_{\text{EVEN}}\}] \supseteq P_2$ (כי לכל $T \in P_2$, $f^*(T) = \mathbb{N}_{\text{EVEN}}$). לכן $|{f^*}^{-1}[\{\mathbb{N}_{\text{EVEN}}\}]| \geq |P_2| = \aleph$. מצד שני ${f^*}^{-1}[\{\mathbb{N}_{\text{EVEN}}\}] \subseteq \mathcal{P}(\mathbb{N})$, לכן $|{f^*}^{-1}[\{\mathbb{N}_{\text{EVEN}}\}]| \leq \aleph$. מקנטור-ברנשטיין: $|{f^*}^{-1}[\{\mathbb{N}_{\text{EVEN}}\}]| = \aleph$, ולכן $f^* \in A$. **שלב 4 – $f^* \notin \text{Im}(\varphi)$:** יהי $S \in \mathcal{P}(\mathbb{N})$ כלשהו. נראה $f^* \neq \varphi(S)$. נסתכל על $T = \alpha(S) \in P_1$. לפי הבנייה: $$f^*(T) \neq (\varphi(S))(T)$$ (כי אם $(\varphi(S))(T) = \mathbb{N}_{\text{EVEN}}$ אז $f^*(T) = \mathbb{N}_{\text{ODD}}$, ואחרת $f^*(T) = \mathbb{N}_{\text{EVEN}}$). לכן $f^*$ ו-$\varphi(S)$ נבדלות בנקודה $T$, כלומר $f^* \neq \varphi(S)$. מכיוון ש-$\varphi$ הייתה פונקציה כלשהי מ-$\mathcal{P}(\mathbb{N})$ ל-$A$, הוכחנו שאין פונקציה על מ-$\mathcal{P}(\mathbb{N})$ ל-$A$, לכן $|A| > |\mathcal{P}(\mathbb{N})| = \aleph$, ובפרט $|A| \neq \aleph$. $\blacksquare$