תורת הקבוצות/פונקציות

הגדרה

יחס $R\subseteq A\times B$ ייקרא פונקציה אם מהוא מקיים שתי תכונות:

1. קיום: לכל $a\in A$ קיים $b\in B$ כך ש- $aRb$ .
2. יחידות: אם $aRb_{1}$ ו- $aRb_{2}$ אז $b_{1}=b_{2}$ .

במקרה כזה $A$ ייקרא התחום של הפונקציה ואילו $B$ ייקרא הטווח של הפונקציה ומסמנים זאת כך: $R:A\to B$ . אם ל- $a\in A$ מתקיים $f(a)=b$ אז $b$ ייקרא התמונה של $a$ ואילו $a$ ייקרא המקור של $b$ .

דוגמאות

• היחס $f\subseteq \mathbb {R} ^{2}$ המוגדר על-ידי $f(x)=x+1$ הוא פונקציה.
• היחס $g\subseteq \{1,2\}\times \{3,5,10\}$ המוגדר על-ידי $g(1)=10\ ,\ g(2)=3$ הוא פונקציה, אף על-פי שאינה מוגדרת על-ידי שום נוסחא.
• היחס $s\subseteq \mathbb {N} \times \mathbb {R}$ המוגדר על-ידי $s(x)=\pm {\sqrt {x}}$ אינו פונקציה מכיון שלכל מספר טבעי היחס מחזיר שני מספרים (למשל $\pm 2$ ל-4).
• היחס $p\subseteq \mathbb {N} \times \mathbb {N}$ המוגדר באמצעות $p(1)=0$ אינו פונקציה מכיון שאינו מוגדר על כל הטבעיים.

הרכבה של פונקציות

אם $f:A\to B$ ו- $g:B\to C$ הן פונקציות אז ההרכבה שלהן $g\circ f:A\to C$ מוגדרת בתור $(g\circ f)(x)=g(f(x))$ .

פונקציית זהות

אם $A$ היא קבוצה אז הפונקציה ${\mbox{id}}_{A}:A\to A$ המוגדרת באמצעות ${\mbox{id}}_{A}(x)=x$ לכל $x\in A$ תיקרא פונקציית הזהות. נשים לב כי לא מתקיים בהכרח ${\mbox{id}}_{A}={\mbox{id}}_{B}$ : למשל הפונקציה $f(x)=|x|$ היא ${\mbox{id}}_{\mathbb {N} }$ אבל לא ${\mbox{id}}_{\mathbb {Z} }$ .

צמצום של פונקציה

בהתאם להגדרת צמצום של יחס, נגדיר צמצום של פונקציה באופן הבא: בהינתן $f:A\to B$, ובהינתן $C\subseteq A$ כך ש, נגדיר את הצמצום של $f$ ל$C$ כפונקציה $f|_{C}:C\to B$ המוגדרת על פי $f|_{C}(x)=f(x)$.

סוגי פונקציות

פונקציה חח״ע: פונקציה $f:A\to B$ תיקרא חח״ע או חד-חד-ערכית אם $f(a_{1})=f(a_{2})$ גורר $a_{1}=a_{2}$ .

פונקציה על: פונקציה $f:A\to B$ תיקרא על אם לכל $b\in B$ קיים $a\in A$ כך ש- $f(a)=b$ .

פונקציה חח״ע ועל: פונקציה $f:A\to B$ תיקרא חח״ע ועל או חד-חד-ערכית ועל אם היא חד-חד-ערכית וגם על.

פונקציה הופכית: אם $f:A\to B$ היא פונקציה אז הפונקציה ההופכית, אם קיימת, של $f$ , $f^{-1}:B\to A$ היא פונקציה המוגדרת בתור $f^{-1}=\{(b,a)|f(a)=b\}$ , כלומר אם $f(a)=b$ אז $f^{-1}(b)=a$ . בניסוח שקול, $f^{-1}$ היא פונקציה אשר מקיימת $f\circ f^{-1}={\mbox{id}}_{B}$ ו- $f^{-1}\circ f={\mbox{id}}_{A}$ . הגדרה זו דומה למדי ליחס ההפוך אך לפונקציה לא בהכרח קיימת הופכית שהיא גם פונקציה. למעשה לפונקציה קיימת הופכית אם ורק אם הפונקציה חח״ע ועל:

טענה: היחס $f^{-1}$ הוא פונקציה אם ורק אם $f$ חח״ע ועל.

הוכחה: נניח תחילה כי $f$ חח״ע ועל. נגדיר את $f^{-1}$ להיות $f^{-1}(x)=y$ , כאשר $y$ הוא האבר המקיים $f(y)=x$ . (האבר קיים ויחיד מהחח״ע ועל של $f$)
נניח כעת כי $f$ הפיכה. יהי שני אברים $a,b$ כך ש- $f(a)=f(b)$ , אז מכיון ש- $f$ הפיכה אפשר להפעיל את $f^{-1}$ על שני הצדדים ולקבל $a=b$ . כעת, יהי $y$ כלשהו. נבחר $x=f^{-1}(y)$ , אז $f(x)=(f\circ f^{-1})(y)=y$ .

אם ישנה פונקציה חח״ע ועל מ- $A$ ל- $B$ אז אפשר לחשוב על הפונקציה כ"משנה את השמות" של האברים ב- $A$ לאברים ב- $B$ , כלומר שאברי $B$ הם אברי $A$ עם "שמות שונים". על בסיס הגיון זה נגדיר:

הגדרה 1.6: קבוצות שקולות נגדיר קבוצות $A,B$ כשקולות, ונסמן $A\sim B$ אם קיימת פונקציה $f:A\to B$ שהיא חח״ע ועל. יש לשים לב כי אם $A\subset B$ אז לא בהכרח $A\not \sim B$ : כך למשל $\mathbb {A} =\{2,4,6,\dots \}\subset \mathbb {N}$ אך $\mathbb {A} \sim \mathbb {N}$ , עם הפונקציה $f(n)=2n$ .

קיימים סוגים נוספים של שקילות אך לא נדון בהם בפרק הזה, מכיוון שעצם הגדרתם דורש מושגים נוספים.
כזכור, הגדרנו פונקציות באמצעות מכפלה קרטזית של שתי קבוצות. כעת נוכל להגדיר מכפלה קרטזית כללית וחזקות של קבוצות באמצעות פונקציות:

הגדרה 1.7: מכפלה קרטזית תהי $\Lambda$ קבוצה כלשהי ו- ${\mathcal {F}}$ משפחה של קבוצות כך ש- $\Lambda \sim {\mathcal {F}}$ . נסמן את הקבוצה $A$ שמותאמת לאבר $\lambda$ בתור $A_{\lambda }$ . כעת המכפלה הקרטזית $\prod _{\lambda \in \Lambda }A_{\lambda }$ מוגדרת להיות $\prod _{\lambda \in \Lambda }A_{\lambda }=\left\{f:\Lambda \to \bigcup {\mathcal {F}}{\Big |}\forall \lambda \in \Lambda :f(\lambda )\in A_{\lambda }\right\}$ .

ההגיון מאחורי ההגדרה ה"מוזרה" הוא כזה: המכפלה $\prod _{\lambda \in \Lambda }A_{\lambda }$ היא על-פי ההגדרה קבוצת כל הסדרות של אברים, כך שהמקום ה- $\lambda$ בסדרה הוא אבר בקבוצה $A_{\lambda }$ . מצד שני, נחשוב על כל סדרה בתור פונקציה $f$ שמקבלת אבר $\lambda$ ומוציאה כפלט את האבר שנמצא במקום ה- $\lambda$ בסדרה (שהוא אבר ב- $A_{\lambda }$). על כן, המכפלה הקרטזית $\prod _{\lambda \in \Lambda }A_{\lambda }$ היא בעצם אוסף הפונקציות שמקבלות מספר ב- $\lambda$ ומוציאות מספר ב- $A_{\lambda }$ , אבל זה שקול להגדרה למעלה.

הגדרה 1.8: חזקת קבוצות אם $A,B$ הן קבוצות אז נגדיר את $B^{A}=\{f:A\to B\}$ . כלומר: אוסף כל הפונקציות מ- $A$ ל- $B$ . כעת נבהיר את הסימון מאחורי $2^{A}$ בתור קבוצת החזקה: אפשר לחשוב על כל תת-קבוצה $X$ בתור פונקציה $f:A\to 2$ המוגדרת בתור $f(x)=\left\{{\begin{matrix}0&x\notin B\\1&x\in B\end{matrix}}\right.$ ולכן קבוצת החזקה היא קבוצת כל הפונקציות מ- $A$ ל- $2$ , וזוהי ההגדרה של $2^{A}$ .

גם כאן, ההגדרה נראית "מוזרה". אך גם לה יש הגיון רב: $B^{A}$ הוא על-פי הגדרה של חזקות $\prod _{a\in A}B$ , אשר שווה על-פי הגדרה 1.7 ל- $\{f:A\to B|\forall a\in A:f(a)\in B\}=\{f:A\to B\}$ , כאשר הצעד האחרון נובע מההגדרה של פונקציות.

הגדרה 1.9: פונקציה מצטמצמת נאמר כי $f$ היא פונקציה מצטמצמת מימין אם ורק אם לכל שתי פונקציות $g,h$, אם $f\circ g=f\circ h$ אז $g=h$. נאמר כי $f$ היא פונקציה מצטמצמת משמאל אם ורק אם לכל שתי פונקציות $g,h$, אם $g\circ f=h\circ f$, אז $g=h$. נאמר כי $f$ היא פונקציה מצטמצמת אם ורק אם היא מצטמצמת מימין וגם משמאל.

משפטי עזר

למשפטים אלה אין חשיבות רבה בפני עצמם, אך הם יעזרו לנו בשאר פרקי הספר.

משפט 2.1: אם $f:A\to B$ ו- $g:B\to C$ הן פונקציות חח״ע אז גם ההרכבה $g\circ f:A\to C$ היא חח״ע, ואם הפונקציות על אז ההרכבה היא על.

הוכחה: חח״ע: יהי $a_{1},a_{2}\in A$ כך ש- $(g\circ f)(a_{1})=(g\circ f)(a_{2})$. מכיון ש- $g$ חח״ע $f(a_{1})=f(a_{2})$ . מכיון ש- $f$ חח״ע $a_{1}=a_{2}$ .

על: יהי $c\in C$ . מכיון ש- $g$ על קיים $b\in B$ כך ש- $g(b)=c$ . מכיון ש- $f$ על קיים $a\in A$ כך ש-$f(a)=b$ . כעת $(g\circ f)(a)=g(f(a))=g(b)=c$ .

הערה: שימו לב שכיוון שהפונקציות חד-חד ערכיות ועל הן הפיכות, ומהמשפט שהוכחנו נובע שגם ההרכבה שלהן חח"ע ועל ולכן גם ההרכבה הפיכה. לפיכך הוכחנו שגם הרכבה של פונקציות הפיכות היא הפיכה.

משפט 2.2: לכל $A$ לא קיימת פונקציה על מ- $A$ ל- $2^{A}$ .

הוכחה: נניח בשלילה שקיימת פונקציה $f$ שהיא על. ניצור תת-קבוצה $Z=\{x|x\notin f(x)\}$ . מכיון ש- $f$ על קיים $z$ כך ש- $f(z)=Z$ . כעת, האם $z\in Z$ ? אם כן, אז על פי הגדרת $Z$ מתקיים $z\notin Z$ בסתירה לכך ש- $z\in Z$ . אם $z\notin Z$ אז $z\notin f(z)$ ולכן $z\in Z$ .

משפט 2.3: תהי $f:A\to B$ . אם $f$ חח״ע, קיימת פונקציה $g:A\to B$ כך ש- $g\circ f={\mbox{id}}_{A}$ . אם $f$ על, אז קיימת פונקציה $g$ כך ש- $f\circ g={\mbox{id}}_{B}$ .

הוכחה: נניח כי $f$ חח״ע. יהי $a\in A$ (אם $A=\varnothing$ המשפט טריוויאלי), כעת נגדיר את $g$ בתור $g(x)=\left\{{\begin{matrix}x&\exists y\in A:f(y)=x\\a&\forall y\in A:f(y)\not =x\end{matrix}}\right.$ . נגדיר $f(x)=y$ , אז $(g\circ f)(x)=g(f(x))=g(y)=x$ .
כעת נניח כי $f$ על. לכל $y\in B$ קיימת קבוצה לא-ריקה $f_{y}=\{x|f(x)=y\}$ , ולכל קבוצה כזו נבחר "נציג" $x_{0}$ ונגדיר $g(y)=x_{0}$ . כעת $(f\circ g)(y)=f(g(y))=f(x_{0})=y$ .

משפט 2.4: לכל $A,B$ קיימת פונקציה חח״ע מ- $A$ ל- $B$ אם ורק אם קיימת פונקציה על מ- $B$ ל- $A$ .

הוכחה: נניח שקיימת פונקציה חח״ע $f:A\to B$ . ממשפט 2.3 קיימת פונקציה $g:B\to A$ כך ש- $g\circ f={\mbox{id}}_{A}$ . יהי $a\in A$ , אז $g(f(a)=a$ ולכן $f(a)$ הוא מקור ל$a$ .
כעת נניח שקיימת פונקציה על $f:A\to B$ . ממשפט 2.3 קיימת $g:A\to B$ כך ש- $f\circ g={\mbox{id}}_{A}$ . נניח ש- $g(a_{1})=g(a_{2})$ , אז $a_{1}=f(g(a_{1}))=f(g(a_{2}))=a_{2}$ .

משפט 2.5: $f$ היא פונקציה מצטמצמת מימין אם ורק אם היא חח"ע. $f$ היא פונקציה מצטמצמת משמאל אם ורק אם היא על.

הוכחה:

1. נניח שf חח"ע. יהו g,h כך ש $f\circ g=f\circ h$. אז לכל $x$, $f(g(x))=f(h(x))$. מכיוון שf חח"ע, נקבל $g(x)=h(x)$, כלומר $g=h$. לכן f מצטמצמת מימין. נניח שf לא חח"ע. יהו $a\not =b$ כך ש$f(a)=f(b)$. נגדיר את הפונקציות $g(x)=a,h(x)=b$. $g\not =h$, ולמרות זאת $f(g(x))=f(a)=f(b)=f(h(x))$, כלומר $f\circ g=f\circ h$. לכן f לא מצטמצמת מימין.
2. נניח שf על. יהו $g,h$ כך ש-$g\circ f=h\circ f$. לכל x יהי y כך ש-$f(y)=x$. אז מתקיים $g(x)=g(f(y))=h(f(y))=h(x)$, לכן $g=h$. לכן f מצטמצמת משמאל. נניח שf לא על. יהי a כך שלכל x, $f(x)\not =a$. נגדיר את הפונקציות $g,h$ כך שמתקיים $h(x)={\begin{cases}g(x)&&x\not =a\\b&&x=a\end{cases}}$ עבור $b\not =g(a)$ כלשהו. מתקיים $g\not =h$, ולמרות זאת $g\circ f=h\circ f$ (כי בכל תמונת הפונקציה f, $g=h$). לכן f לא מצטמצמת משמאל.

הפרק הקודם: יחסים

פונקציות

הפרק הבא: יחסי שקילות