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

נתון: קבוצות $A, B$; פונקציה חח"ע $f: A \to B$; פונקציה $g: B \to A$; $C$ קבוצה חלקית ממש של $f[A]$, המקיימת $g[C] = A$. בחרו את התשובה הנכונה: **[1]** מהנתון נובע ש-$A$ אינסופית. **[2]** טענה [1] אינה נכונה, אבל מהנתון נובע ש-$B$ אינסופית. **[3]** טענות [1] ו-[2] אינן נכונות, אבל מהנתון נובע ש-$|C| < |B|$. **[4]** אף אחת מהטענות [1]–[3] אינה נכונה.

רמז: חשבו מה המשמעות של קיום קבוצה $C \subsetneq f[A]$ כך ש-$g[C] = A$. אם $A$ הייתה סופית, האם יכולה להתקיים סריקה של $A$ על ידי תמונת קבוצה קטנה יותר ממש מ-$f[A]$? השתמשו בחח"ע של $f$ ובעיקרון שפונקציה מקבוצה סופית לקבוצה ממנה קטנה ממש אינה על.

פתרון: נוכיח שמהנתון נובע ש-$A$ אינסופית, כלומר תשובה **[1]** נכונה. **הנחה בדרך השלילה:** נניח ש-$A$ סופית, $|A| = n$. מכיוון ש-$f: A \to B$ היא **חח"ע**, מתקיים $|f[A]| = n$ (תמונת פונקציה חח"ע שווה בעוצמתה לתחום). נתון ש-$C \subsetneq f[A]$ (חלקית ממש), לכן $|C| \leq n - 1 < n$. נתון ש-$g[C] = A$, כלומר הפונקציה $g\big|_C: C \to A$ היא **על** (כי תמונת $C$ תחת $g$ מכסה את כל $A$). אולם, קיימת פונקציה על מ-$C$ אל $A$ רק אם $|C| \geq |A|$, כלומר $|C| \geq n$. קיבלנו סתירה: $|C| \leq n-1 < n \leq |C|$. לכן ההנחה שגויה, ו-$A$ חייבת להיות **אינסופית**. **בדיקה שהנתון אכן ייתכן עבור $A$ אינסופית:** ניקח $A = B = \mathbb{N}$, $f = \mathrm{id}$ (החח"ע הטריוויאלית), $f[A] = \mathbb{N}$, ונבחר $C = \mathbb{N} \setminus \{0\} \subsetneq \mathbb{N}$. נגדיר $g: \mathbb{N} \to \mathbb{N}$ על ידי $g(n) = n - 1$ עבור $n \geq 1$. אז $g[C] = \mathbb{N} = A$. כל התנאים מתקיימים, ו-$A$ אכן אינסופית. $\blacksquare$