תורת הקבוצות - פונקציות חד-חד-ערכיות, על והפיכות

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

ראשית, בואו נגדיר את שתי התכונות הללו. ניקח פונקציה \( f:A\to B \). אינטואיטיבית - זה משהו שלוקח קלט מתוך \( A \) ומחזיר פלט מתוך \( B \). כעת, התכונה “\( f \) חד-חד-ערכית” פירושה שקלטים שונים מחזירים פלטים שונים או במילים אחרות, אין שני קלטים שונים שנותנים את אותו פלט. פורמלית: אם \( a_{1}\ne a_{2}\in A \) אז \( f\left(a_{1}\right)\ne f\left(a_{2}\right) \), או בניסוח אחר, שימושי אולי אפילו יותר: אם \( f\left(a_{1}\right)=f\left(a_{2}\right) \) אז \( a_{1}=a_{2} \).

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

בואו נראה דוגמאות מקרב הפונקציות הממשיות, \( f:\mathbb{R}\to\mathbb{R} \). הפונקציה \( f\left(x\right)=x \) היא חד-חד-ערכית, באופן די מובן מאליו כי אם \( f\left(a_{1}\right)=f\left(a_{2}\right) \) אז מההגדרה של \( f \) נקבל \( a_{1}=f\left(a_{1}\right)=f\left(a_{2}\right)=a_{2} \). הנה משהו קצת יותר מחוכם: הפונקציה הלינארית \( f\left(x\right)=3x-7 \) היא חד-חד-ערכית כי אם \( f\left(a_{1}\right)=f\left(a_{2}\right) \) אז \( 3a_{1}-7=3a_{2}-7 \) ואם נחבר 7 לשני האגפים ונחלק ב-3 נקבל \( a_{1}=a_{2} \).

לעומת זאת הפונקציה \( f\left(x\right)=x^{2} \) איננה חד-חד-ערכית כי \( f\left(1\right)=f\left(-1\right)=1 \). מה השתבש? למה אי אפשר להגיד \( a_{1}^{2}=a_{2}^{2} \) ואז להוציא שורש משני האגפים? בדיוק בגלל שפעולת הוצאת השורש דורשת מאיתנו לאבד מידע. אם תזכרו, בפוסט הקודם אמרתי משהו על כך שהוצאת שורש היא משהו מוזר שנקרא פונקציה רב ערכית ומה שאנחנו עובדים איתו בדרך כלל הוא רק ענף של הפונקציה. לא חייבים להיכנס לדקות הזו; רק להיות מודעים לכך שלא כל פעולה שאנחנו מפעילים על שני אגפי משוואה מבטיחה שפתרונות אפשריים לא ילכו לאיבוד.

באופן שאולי קצת מפתיע, \( f\left(x\right)=x^{3} \) היא דווקא כן פונקציה חד-חד-ערכית כשמדובר על פונקציה במספרים ממשיים; זאת מכיוון של-\( a^{3} \) יש שלושה שורשים אפשריים ש-\( a \) הוא רק אחד מהם, אבל שני השורשים האחרים הם מספרים מרוכבים שאינם ממשיים. אם כן, השאלה מתי פונקציה היא חד-חד-ערכית או לא עשויה להיות טריקית למדי; צריך להיזהר עם זה.

בשביל האינטואיציה שלנו, הנה קריטריון פשוט שמאפשר “לראות” מתי פונקציה ממשית היא חד-חד-ערכית. נסתכל על הגרף שלה ונשאל את עצמנו את השאלה הבאה: האם קיים קו אופקי שחותך את גרף הפונקציה בשתי נקודות או יותר? שתי נקודות חיתוך כאלו שהן באותו גובה הן זוגות \( \left(x_{1},y\right),\left(x_{2},y\right) \) - כלומר שני קלטים של הפונקציה שנותנים את אותו פלט. אם מסתכלים על הגרף של \( f\left(x\right)=x^{2} \) (“פרבולה מחייכת”) רואים בקלות שהיא לא חד-חד-ערכית כי כל קו שגבוה מ-\( y=0 \) חותך אותה בשני מקומות; לעומת זאת הגרף של \( f\left(x\right)=x^{3} \) (“אין לי מושג איך לקרוא לזה אבל זה פיתול מוזר שכזה”) מקיים את תכונת החיתוך הזו יפה.

נעבור לתכונה השניה. פונקציה \( f:A\to B \) היא על \( B \) אם לכל פלט אפשרי אכן קיים קלט שמחזיר אותו: כלומר, לכל \( b\in B \) קיים \( a\in A \) כך ש-\( f\left(a\right)=b \). למשל, אם לכל מילה בשפה העברית \( f \) מתאימה את האות הראשונה שלה, אז זו פונקציה על כי לכל אות בעברית קיימת מילה אחת לפחות שמתחילה באות הזו. לעומת זאת, הפונקציה שמחזירה לכל אדם בישראל את מספר תעודת הזהות שלו איננה על כי קיימים מספרים שאינם מספרי תעודת זהות. אבל רגע, הניסוח שלי קצת בעייתי - לא אמרתי על מה הפונקציה הזו אמורה להיות. האם על קבוצת כל המספרים הטבעיים? או אולי רק המספרים הטבעיים בני 9 ספרות בדיוק? או אולי הקבוצה “כל המספרים הטבעיים שהם מספר זהות של מישהו”, מה שיגרום לפונקציה כן להיות על?

בואו נחזור אל שתי הפונקציות החביבות \( f\left(x\right)=x^{2} \) ו-\( f\left(x\right)=x^{3} \) ונשאל את עצמנו - האם הן על? אם חושבים עליהן בתור פונקציות \( f:\mathbb{R}\to\mathbb{R} \), אז \( f\left(x\right)=x^{2} \) בוודאי איננה על, כי \( -1 \) אינו הפלט של אף קלט. לעומת זאת \( f\left(x\right)=x^{3} \) היא כן על. אפשר לראות את זה בתמונה: פונקציה היא על אם כל קו אופקי חותך אותה לפחות פעם אחת.

על פניו, נראה שאם פונקציה אינה על קל “לתקן” את זה - פשוט נצמצם את הטווח שלה. למשל, עבור \( f\left(x\right)=x^{2} \) אם נסתכל עליה בתור פונקציה \( f:\mathbb{R}\to[0,\infty( \) אז היא בהחלט פונקציה על. אבל מה זה אומר, לצמצם את הטווח? זה אומר להחליף את הפונקציה שלנו בפונקציה אחרת, שה”כלל” שמגדיר אותה זהה. זה אומר שעברנו לסיטואציה אחרת, שהיא אולי מועילה יותר בהקשר הנוכחי שלנו אבל לפעמים היא לא מועילה בכלל, ואני מקווה שזה יתברר בקרוב מעצמו. עדיין, כדאי לדבר במפורש על ה”תיקון” הזה: אם \( f:A\to B \) היא פונקציה כלשהי, התמונה של \( f \) על \( A \) היא הקבוצה \( f\left(A\right)\triangleq\left\{ f\left(a\right)\ |\ a\in A\right\} \) - זה אוסף האיברים ב-\( B \) שמתקבלים בעזרת \( f \). עכשיו, אפשר תמיד לומר ש-\( f:A\to f\left(A\right) \) היא על; ואפשר גם לומר שהתכונה “להיות על” היא פשוט הטענה \( B=f\left(A\right) \).

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

עכשיו, אחרי שראינו קצת את התכונות הללו, בואו ונראה מאיפה הן מגיעות. ראשית, בואו נזכיר את שתי התכונות שמגדירות מה זו פונקציה. יחס \( f\subseteq A\times B \) הוא פונקציה אם מתקיים:

1. "קיום": לכל \( a\in A \) קיים \( b\in B \) כך ש-\( \left(a,b\right)\in f \).
2. "יחידות": אם \( \left(a,b_{1}\right)\in f \) וגם \( \left(a,b_{2}\right)\in f \) עבור \( a\in A \) ו-\( b_{1},b_{2}\in B \) אז \( b_{1}=b_{2} \).

עכשיו אני אנסח את תכונות ה”על” וה”חד-חד-ערכית” באמצעות יחסים:

1. "על": לכל \( b\in B \) קיים \( a\in A \) כך ש-\( \left(a,b\right)\in f \)
2. "חד-חד-ערכית": אם \( \left(a_{1},b\right)\in f \) וגם \( \left(a_{2},b\right)\in f \) עבור \( a_{1},a_{2}\in A \) ו-\( b\in B \) אז \( a_{1}=a_{2} \).

הדמיון בין תכונות הקיום/יחידות ותכונות העל/חח”ע בולט מאוד, כמובן. נראה שההגדרות כמעט זהות עד כדי החלפת תפקידים בין \( A \) ו-\( B \). ויש דרך לחדד את הדמיון עוד יותר אם נהפוך את \( f \). בואו נדבר על זה שניה.

\( f \) היא פונקציה, ומעבר למשמעות האינטואיטיבית של “משהו שהופך קלט לפלט” פונקציה היא קודם כל יחס - אוסף של זוגות סדורים. אפשר פשוט לקחת כל זוג כזה ולהפוך את הסדר בין האיברים שלו, והתוצאה נקראת היחס ההפוך. פורמלית, אם \( R\subseteq A\times B \) הוא יחס כלשהו, מגדירים \( R^{-1}\triangleq\left\{ \left(b,a\right)\ |\ \left(a,b\right)\in R\right\} \). עכשיו עבור המקרה הפרטי של פונקציה \( f \) אפשר לעשות את אותו הדבר בדיוק: להגדיר \( f^{-1}\triangleq\left\{ \left(b,a\right)\ |\ \left(a,b\right)\in f\right\} \), ובסימון קצת יותר “פונקצייתי”: \( f^{-1}\triangleq\left\{ \left(b,a\right)\ |\ f\left(a\right)=b\right\} \).

מתי \( f^{-1} \) היא פונקציה? שימו לב לכך שהיחס \( f^{-1} \) תמיד קיים אבל בהחלט לא מובטח שהוא יהיה פונקציה; פונקציה היא יחס שמקיים שני תנאים ספציפיים, “קיום” ו”יחידות”, שפירושם עבור היחס \( f^{-1}\subseteq B\times A \) הוא

1. "קיום": לכל \( b\in B \) קיים \( a\in A \) כך ש-\( \left(b,a\right)\in f^{-1} \).
2. "יחידות": אם \( \left(b,a_{1}\right)\in f^{-1} \) וגם \( \left(b,a_{2}\right)\in f^{-1} \) עבור \( a_{1},a_{2}\in A \) ו-\( b\in B \) אז \( a_{1}=a_{2} \).

עכשיו, במקום לכתוב \( \left(b,a\right)\in f^{-1} \) אני יכול לכתוב \( \left(a,b\right)\in f \): זו בדיוק ההגדרה של \( f^{-1} \). וכעת שתי השורות למעלה הופכות להיות:

1. "קיום": לכל \( b\in B \) קיים \( a\in A \) כך ש-\( \left(a,b\right)\in f \).
2. "יחידות": אם \( \left(a_{1},b\right)\in f \) וגם \( \left(a_{2},b\right)\in f \) עבור \( a_{1},a_{2}\in A \) ו-\( b\in B \) אז \( a_{1}=a_{2} \).

ואלו בדיוק, אבל בדיוק, התכונות של “על” ו”חד-חד-ערכיות” של \( f \). אז אפשר לסכם את מה שראינו במשפט אחד קצר וקולע: \( f \) היא חח”ע ועל אם ורק אם \( f^{-1} \) היא פונקציה. במקרה הזה נהוג להגיד ש-\( f \) היא הפיכה. למה? כי אפשר לחשוב על \( f^{-1} \) בתור “אותה הפונקציה כמו \( f \) רק בכיוון ההפוך”. אם יש לנו \( a\in A \) ואנחנו מפעילים את \( f \) על \( a \) ומקבלים \( f\left(a\right)=b \) ואז מפעילים את \( f^{-1} \) על \( b \) אנחנו מקבלים \( f^{-1}\left(b\right)=a \), כלומר \( f^{-1}\left(f\left(a\right)\right)=a \) - הפונקציה \( f^{-1} \) “ביטלה” את הפעולה של \( f \).

פונקציות הפיכות הן כלי מרכזי בתורת הקבוצות - עליהן מתבססת ההגדרה שלנו לשוויון עוצמות של קבוצות, שבאה לתת גישה אפשרית אחת לשאלה מתי שתי קבוצות (גם אינסופיות) הן מאותו גודל (ההגדרה פשוטה: \( A \) שוות עוצמה ל-\( B \) אם קיימת \( f:A\to B \) הפיכה). נדבר על זה עוד בהמשך, אבל לפני כן אני ארצה לתת גישה מסודרת יותר לעניין ה”מפעילים את \( f \) על קלט ואז מפעילים משהו אחר על הפלט” - זה יוביל אותנו למושג ההרכבה שעליו אדבר בפוסט הבא.