שאלת מבחן במתמטיקה בדידה - עוצמות

הוכיחו שקבוצת כל הפונקציות **על** (סורייקציות) מ-$\mathbb{N}$ ל-$\mathbb{N}$ אינה בת-מניה.

רמז: לכל $f: \mathbb{N} \to \mathbb{N}$, הגדירו $\hat{f}: \mathbb{N} \to \mathbb{N}$ על ידי $\hat{f}(2k) = k$ ו-$\hat{f}(2k+1) = f(k)$ לכל $k \in \mathbb{N}$. ודאו ש-$\hat{f}$ על ושהמיפוי $f \mapsto \hat{f}$ חח"ע, ולאחר מכן הסיקו מאי-בת-מניות $\mathbb{N}^{\mathbb{N}}$.

פתרון: לכל $f: \mathbb{N} \to \mathbb{N}$, נגדיר $\hat{f}: \mathbb{N} \to \mathbb{N}$ על ידי: $$\hat{f}(2k) = k, \qquad \hat{f}(2k+1) = f(k) \qquad \forall k \in \mathbb{N}$$ **$\hat{f}$ על:** לכל $n \in \mathbb{N}$, $\hat{f}(2n) = n$, כך שכל $n$ בטווח. $\checkmark$ **$f \mapsto \hat{f}$ חח"ע:** אם $\hat{f} = \hat{g}$, אז לכל $k$: $f(k) = \hat{f}(2k+1) = \hat{g}(2k+1) = g(k)$, לכן $f = g$. $\checkmark$ **סיום:** קיימת העתקה חח"ע $f \mapsto \hat{f}$ מ-$\mathbb{N}^{\mathbb{N}}$ אל קבוצת הסורייקציות. נניח בשלילה שקבוצת הסורייקציות בת-מניה; אז $\mathrm{Im}(f \mapsto \hat{f})$ בת-מניה, ו-$\mathbb{N}^{\mathbb{N}}$ (בביקציה אתה) הייתה בת-מניה — סתירה לאי-בת-מניות $\mathbb{N}^{\mathbb{N}}$ (שהוכחה בלכסון). לכן קבוצת הסורייקציות $\mathbb{N} \to \mathbb{N}$ **אינה בת-מניה**. $\blacksquare$