יחידה 6: פונקציות חח"ע ועל¶

פונקציה חד-חד-ערכית (חח"ע)¶

הגדרה¶

הגדרה: פונקציה חח\"ע

פונקציה $f: A \to B$ נקראת חד-חד-ערכית (injective, one-to-one) אם:

\[\forall x_1, x_2 \in A. f(x_1) = f(x_2) \Rightarrow x_1 = x_2\]

או באופן שקול:

\[\forall x_1, x_2 \in A. x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)\]

כלומר, לאיברים שונים יש תמונות שונות.

דוגמאות

$f(x) = 2x + 3$ על $\mathbb{R}$ - חח"ע (פונקציה לינארית)
$f(x) = x^2$ על $\mathbb{R}$ - לא חח"ע (כי $f(2) = f(-2) = 4$)
$f(x) = x^2$ על $\mathbb{R}^+$ (המספרים החיוביים) - חח"ע

שיטות להוכחת חח"ע¶

שיטה 1: ישירה

נניח $f(x_1) = f(x_2)$ ונוכיח $x_1 = x_2$.

שיטה 2: קונטרפוזיציה

נניח $x_1 \neq x_2$ ונוכיח $f(x_1) \neq f(x_2)$.

דוגמה: הוכחת חח\"ע

נוכיח ש-$f(x) = 3x - 7$ חח"ע על $\mathbb{R}$.

הוכחה: נניח $f(x_1) = f(x_2)$: $$3x_1 - 7 = 3x_2 - 7$$ $$3x_1 = 3x_2$$ $$x_1 = x_2$$

לכן $f$ חח"ע. ∎

פונקציה על (סורייקטיבית)¶

הגדרה¶

הגדרה: פונקציה על

פונקציה $f: A \to B$ נקראת על (surjective, onto) אם:

\[\forall y \in B. \exists x \in A. f(x) = y\]

או באופן שקול: $\text{Im}(f) = B$

כלומר, כל איבר בטווח מתקבל.

דוגמאות

$f(x) = 2x + 3$ מ-$\mathbb{R}$ ל-$\mathbb{R}$ - על
$f(x) = x^2$ מ-$\mathbb{R}$ ל-$\mathbb{R}$ - לא על (מספרים שליליים לא מתקבלים)
$f(x) = x^2$ מ-$\mathbb{R}$ ל-$[0, \infty)$ - על

שיטות להוכחת "על"¶

שיטה: בניית מקור

לכל $y \in B$, מוצאים $x \in A$ כך ש-$f(x) = y$.

דוגמה: הוכחת על

נוכיח ש-$f(x) = 3x - 7$ על מ-$\mathbb{R}$ ל-$\mathbb{R}$.

הוכחה: יהי $y \in \mathbb{R}$. נבחר $x = \frac{y + 7}{3}$.

אז $x \in \mathbb{R}$ ו: $$f(x) = 3 \cdot \frac{y+7}{3} - 7 = y + 7 - 7 = y$$

לכן $f$ על. ∎

פונקציית שקילות (ביאקציה)¶

הגדרה¶

הגדרה: פונקציית שקילות

פונקציה $f: A \to B$ נקראת פונקציית שקילות או ביאקציה (bijection) אם היא גם חח"ע וגם על.

במקרה זה, לכל $y \in B$ יש בדיוק מקור אחד ב-$A$.

דוגמאות

$f(x) = 2x + 3$ מ-$\mathbb{R}$ ל-$\mathbb{R}$ - ביאקציה
$f(x) = e^x$ מ-$\mathbb{R}$ ל-$(0, \infty)$ - ביאקציה
$i_A: A \to A$ - ביאקציה (פונקציית הזהות)

קשר בין חח"ע/על להרכבות¶

משפט: חח\"ע והרכבה

אם $g \circ f$ חח"ע, אז $f$ חח"ע.
אם $f$ ו-$g$ חח"ע, אז $g \circ f$ חח"ע.

הוכחה (1): נניח $g \circ f$ חח"ע. נראה ש-$f$ חח"ע.

יהיו $x_1, x_2 \in A$ כך ש-$f(x_1) = f(x_2)$.

אז $g(f(x_1)) = g(f(x_2))$, כלומר $(g \circ f)(x_1) = (g \circ f)(x_2)$.

מחח"ע של $g \circ f$ נובע $x_1 = x_2$. ∎

משפט: על והרכבה

אם $g \circ f$ על, אז $g$ על.
אם $f$ ו-$g$ על, אז $g \circ f$ על.

קשר לגודל קבוצות¶

משפט: חח\"ע, על וגדלים

עבור קבוצות סופיות $A, B$ עם $|A| = |B|$:

\[f: A \to B \text{ חח"ע} \iff f \text{ על} \iff f \text{ ביאקציה}\]

זהירות

המשפט הזה לא נכון לקבוצות אינסופיות!

דוגמה נגדית: $f: \mathbb{N} \to \mathbb{N}$, $f(n) = 2n$ - חח"ע ✓ - על ✗ (מספרים אי-זוגיים לא מתקבלים)

טבלת סיכום¶

תכונה	הגדרה	דוגמה (כן)	דוגמה (לא)
חח"ע	$f(x_1) = f(x_2) \Rightarrow x_1 = x_2$	$f(x) = 2x$	$f(x) = x^2$ על $\mathbb{R}$
על	$\text{Im}(f) = B$	$f(x) = x^3$ על $\mathbb{R}$	$f(x) = e^x$ על $\mathbb{R}$
ביאקציה	חח"ע + על	$f(x) = 2x + 1$	$f(x) = x^2$ על $\mathbb{R}$

תרגילים¶

תרגיל 1

האם $f: \mathbb{Z} \to \mathbb{Z}$ המוגדרת $f(n) = n^2 - 1$ היא חח"ע? על?

תרגיל 2

תהי $f: A \to B$ ו-$g: B \to C$. הוכיחו: אם $g \circ f$ ביאקציה אז $f$ חח"ע ו-$g$ על.

תרגיל 3

מצאו פונקציה $f: \mathbb{N} \to \mathbb{N}$ שהיא על אך לא חח"ע.

מקורות¶

מקורות היחידה

ספר הקורס (פרופ' אברון): פרק ב.4 - פונקציות
תרגול 6 - פונקציות חח"ע ועל

תכונה	הגדרה	דוגמה (כן)	דוגמה (לא)
חח"ע	\(f(x_1) = f(x_2) \Rightarrow x_1 = x_2\)	\(f(x) = 2x\)	\(f(x) = x^2\) על \(\mathbb{R}\)
על	\(\text{Im}(f) = B\)	\(f(x) = x^3\) על \(\mathbb{R}\)	\(f(x) = e^x\) על \(\mathbb{R}\)
ביאקציה	חח"ע + על	\(f(x) = 2x + 1\)	\(f(x) = x^2\) על \(\mathbb{R}\)