הצגת המקור של הדף "תורת הקבוצות/פונקציות"

{{תורת הקבוצות}}

==הגדרה==
[[תורת הקבוצות/יחסים|יחס]] <math>R\subseteq A\times B</math> ייקרא '''פונקציה''' אם מהוא מקיים שתי תכונות:
#קיום: לכל <math>a\in A</math> קיים <math>b\in B</math> כך ש- <math>aRb</math> .
#יחידות: אם <math>aRb_1</math> ו- <math>aRb_2</math> אז <math>b_1=b_2</math> .
במקרה כזה <math>A</math> ייקרא '''התחום''' של הפונקציה ואילו <math>B</math> ייקרא '''הטווח''' של הפונקציה ומסמנים זאת כך: <math>R: A\to B</math> . אם ל- <math>a\in A</math> מתקיים <math>f(a)=b</math> אז <math>b</math> ייקרא '''התמונה''' של <math>a</math> ואילו <math>a</math> ייקרא '''המקור''' של <math>b</math> .

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

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

===פונקציית זהות===
אם <math>A</math> היא קבוצה אז הפונקציה <math>\mbox{id}_A:A\to A</math> המוגדרת באמצעות <math>\mbox{id}_A(x)=x</math> לכל <math>x\in A</math> תיקרא '''פונקציית הזהות'''. נשים לב כי לא מתקיים בהכרח <math>\mbox{id}_A=\mbox{id}_B</math> : למשל הפונקציה <math>f(x)=|x|</math> היא <math>\mbox{id}_\N</math> אבל לא <math>\mbox{id}_\Z</math> .
===צמצום של פונקציה===
בהתאם להגדרת [[תורת הקבוצות/יחסים#צמצום|צמצום של יחס]], נגדיר '''צמצום של פונקציה''' באופן הבא: בהינתן <math>f:A\to B</math>, ובהינתן <math>C\subseteq A</math> כך ש, נגדיר את הצמצום של <math>f</math> ל<math>C</math> כפונקציה <math>f|_{C}:C\to B</math> המוגדרת על פי <math>f|_{C}(x)=f(x)</math>.

==סוגי פונקציות==
פונקציה חח״ע: פונקציה <math>f:A\to B</math> תיקרא '''חח״ע''' או '''חד-חד-ערכית''' אם <math>f(a_1)=f(a_2)</math> גורר <math>a_1=a_2</math> .

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

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

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

{{טענה|
מספר=|
שם=|
תוכן=היחס <math>f^{-1}</math> הוא פונקציה אם ורק אם <math>f</math> חח״ע ועל.}}
{{הוכחה| נניח תחילה כי <math>f</math> חח״ע ועל. נגדיר את <math>f^{-1}</math> להיות <math>f^{-1}(x)=y</math> , כאשר <math>y</math> הוא האבר המקיים <math>f(y)=x</math> . (האבר קיים ויחיד מהחח״ע ועל של <math>f</math>){{ש}}
נניח כעת כי <math>f</math> הפיכה. יהי שני אברים <math>a,b</math> כך ש- <math>f(a)=f(b)</math> , אז מכיון ש- <math>f</math> הפיכה אפשר להפעיל את <math>f^{-1}</math> על שני הצדדים ולקבל <math>a=b</math> . כעת, יהי <math>y</math> כלשהו. נבחר <math>x=f^{-1}(y)</math> , אז <math>f(x)=(f\circ f^{-1})(y)=y</math> .}}
אם ישנה פונקציה חח״ע ועל מ- <math>A</math> ל- <math>B</math> אז אפשר לחשוב על הפונקציה כ"משנה את השמות" של האברים ב- <math>A</math> לאברים ב- <math>B</math> , כלומר שאברי <math>B</math> הם אברי <math>A</math> עם "שמות שונים". על בסיס הגיון זה נגדיר:
{{הגדרה|
מספר=1.6|
שם=קבוצות שקולות|
תוכן=נגדיר קבוצות <math>A,B</math> כ'''שקולות''', ונסמן <math>A\sim B</math> אם קיימת פונקציה <math>f:A\to B</math> שהיא חח״ע ועל. יש לשים לב כי אם <math>A\subset B</math> אז לא בהכרח <math>A\not\sim B</math> : כך למשל <math>\mathbb{A}=\{2,4,6,\dots\}\subset\N</math> אך <math>\mathbb{A}\sim\N</math> , עם הפונקציה <math>f(n)=2n</math> .}}
קיימים סוגים נוספים של שקילות אך לא נדון בהם בפרק הזה, מכיוון שעצם הגדרתם דורש מושגים נוספים.{{ש}}
כזכור, הגדרנו פונקציות באמצעות מכפלה קרטזית של שתי קבוצות. כעת נוכל להגדיר מכפלה קרטזית כללית וחזקות של קבוצות באמצעות פונקציות:
{{הגדרה|
מספר=1.7|
שם=מכפלה קרטזית|
תוכן=תהי <math>\Lambda</math> קבוצה כלשהי ו- <math>\mathcal{F}</math> משפחה של קבוצות כך ש- <math>\Lambda\sim\mathcal{F}</math> . נסמן את הקבוצה <math>A</math> שמותאמת לאבר <math>\lambda</math> בתור <math>A_\lambda</math> . כעת המכפלה הקרטזית <math>\prod_{\lambda\in\Lambda}A_\lambda</math> מוגדרת להיות <math>\prod_{\lambda\in\Lambda}A_\lambda=\left\{f:\Lambda\to\bigcup\mathcal{F}\Big|\forall\lambda\in\Lambda:f(\lambda)\in A_\lambda\right\}</math> .}}

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

{{הגדרה|
מספר=1.8|
שם=חזקת קבוצות|
תוכן=אם <math>A,B</math> הן קבוצות אז נגדיר את <math>B^A=\{f:A\to B\}</math> . כלומר: אוסף כל הפונקציות מ- <math>A</math> ל- <math>B</math> . כעת נבהיר את הסימון מאחורי <math>2^A</math> בתור קבוצת החזקה: אפשר לחשוב על כל תת-קבוצה <math>X</math> בתור פונקציה <math>f:A\to 2</math> המוגדרת  בתור <math>f(x)=\left\{\begin{matrix}0&x\notin B\\ 1&x\in B\end{matrix}\right.</math> ולכן קבוצת החזקה היא קבוצת כל הפונקציות מ- <math>A</math> ל- <math>2</math> , וזוהי ההגדרה של <math>2^A</math> .}}
גם כאן, ההגדרה נראית "מוזרה". אך גם לה יש הגיון רב: <math>B^A</math> הוא על-פי הגדרה של חזקות <math>\prod_{a\in A}B</math> , אשר שווה על-פי הגדרה 1.7 ל- <math>\{f:A\to B|\forall a\in A:f(a)\in B\}=\{f:A\to B\}</math> , כאשר הצעד האחרון נובע מההגדרה של פונקציות.
{{הגדרה|
מספר=1.9|
שם=פונקציה מצטמצמת|
תוכן=
* נאמר כי <math>f</math> היא פונקציה '''מצטמצמת מימין''' אם ורק אם לכל שתי פונקציות <math>g,h</math>, אם <math>f\circ g=f\circ h</math> אז <math>g=h</math>.
* נאמר כי <math>f</math> היא פונקציה '''מצטמצמת משמאל''' אם ורק אם לכל שתי פונקציות <math>g,h</math>, אם <math>g\circ f=h\circ f</math>, אז <math>g=h</math>.
* נאמר כי <math>f</math> היא פונקציה '''מצטמצמת''' אם ורק אם היא מצטמצמת מימין וגם משמאל.}}

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

{{משפט|
מספר=2.1|
שם=|
תוכן=אם <math>f:A\to B</math> ו- <math>g:B\to C</math> הן פונקציות חח״ע אז גם ההרכבה <math>g\circ f: A\to C</math> היא חח״ע, ואם הפונקציות על אז ההרכבה היא על.}}
{{הוכחה|
חח״ע: יהי <math>a_1,a_2\in A</math> כך ש- <math>(g\circ f)(a_1)=(g\circ f)(a_2)</math>. מכיון ש- <math>g</math> חח״ע <math>f(a_1)=f(a_2)</math> . מכיון ש- <math>f</math> חח״ע <math>a_1=a_2</math> .

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

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

{{משפט|
מספר=2.2|
שם=|
תוכן=לכל <math>A</math> לא קיימת פונקציה על מ- <math>A</math> ל- <math>2^A</math> .}}
{{הוכחה|נניח בשלילה שקיימת פונקציה <math>f</math> שהיא על. ניצור תת-קבוצה <math>Z =\{x|x\notin f(x)\}</math> . מכיון ש- <math>f</math> על קיים <math>z</math> כך ש- <math>f(z)=Z</math> . כעת, האם <math>z\in Z</math> ? אם כן, אז על פי הגדרת <math>Z</math> מתקיים <math>z\notin Z</math> בסתירה לכך ש- <math>z\in Z</math> . אם <math>z\notin Z</math> אז <math>z\notin f(z)</math> ולכן <math>z\in Z</math> .}}

{{משפט|
מספר=2.3|
שם=|
תוכן=תהי <math>f:A\to B</math> . אם <math>f</math> חח״ע, קיימת פונקציה <math>g:A\to B</math> כך ש- <math>g\circ f=\mbox{id}_A</math> . אם <math>f</math> על, אז קיימת פונקציה <math>g</math> כך ש- <math>f\circ g=\mbox{id}_B</math> .}}
{{הוכחה|נניח כי <math>f</math> חח״ע. יהי <math>a\in A</math> (אם <math>A=\varnothing</math> המשפט טריוויאלי), כעת נגדיר את <math>g</math> בתור <math>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.</math> . נגדיר <math>f(x)=y</math> , אז <math>(g\circ f)(x)=g(f(x))=g(y)=x</math> .{{ש}}
כעת נניח כי <math>f</math> על. לכל <math>y\in B</math> קיימת קבוצה לא-ריקה <math>f_y=\{x|f(x)=y\}</math> , ולכל קבוצה כזו נבחר "נציג" <math>x_0</math> ונגדיר <math>g(y)=x_0</math> . כעת <math>(f\circ g)(y)=f(g(y))=f(x_0)=y</math> .}}

{{משפט|
מספר=2.4|
שם=|
תוכן=לכל <math>A,B</math> קיימת פונקציה חח״ע מ- <math>A</math> ל- <math>B</math> אם ורק אם קיימת פונקציה על מ- <math>B</math> ל- <math>A</math> .}}
{{הוכחה|נניח שקיימת פונקציה חח״ע <math>f:A\to B</math> . ממשפט 2.3 קיימת פונקציה <math>g:B\to A</math> כך ש- <math>g\circ f=\mbox{id}_A</math> . יהי 
<math>a\in A</math> , אז <math>g(f(a)=a</math> ולכן <math>f(a)</math> הוא מקור ל<math>a</math> .{{ש}}
כעת נניח שקיימת פונקציה על <math>f:A\to B</math> . ממשפט 2.3 קיימת <math>g:A\to B</math> כך ש- <math>f\circ g=\mbox{id}_A</math> . נניח ש- <math>g(a_1)=g(a_2)</math> , אז <math>a_1=f(g(a_1))=f(g(a_2))=a_2</math> .}}
{{משפט|
מספר=2.5|
שם=|
תוכן=
# <math>f</math> היא פונקציה מצטמצמת מימין אם ורק אם היא חח"ע.
# <math>f</math> היא פונקציה מצטמצמת משמאל אם ורק אם היא על.}}
{{הוכחה|
# נניח שf חח"ע. יהו g,h כך ש <math>f\circ g=f\circ h</math>. אז לכל <math>x</math>, <math>f(g(x))=f(h(x))</math>. מכיוון שf חח"ע, נקבל <math>g(x)=h(x)</math>, כלומר <math>g=h</math>. לכן f מצטמצמת מימין. נניח שf לא חח"ע. יהו <math>a\not=b</math> כך ש<math>f(a)=f(b)</math>. נגדיר את הפונקציות <math>g(x)=a,h(x)=b</math>. <math>g\not=h</math>, ולמרות זאת <math>f(g(x))=f(a)=f(b)=f(h(x))</math>, כלומר <math>f\circ g=f\circ h</math>. לכן f לא מצטמצמת מימין.
# נניח שf על. יהו <math>g,h</math> כך ש-<math>g\circ f=h\circ f</math>. לכל x יהי y כך ש-<math>f(y)=x</math>. אז מתקיים <math>g(x)=g(f(y))=h(f(y))=h(x)</math>, לכן <math>g=h</math>. לכן f מצטמצמת משמאל. נניח שf לא על. יהי a כך שלכל x, <math>f(x)\not=a</math>. נגדיר את הפונקציות <math>g,h</math> כך שמתקיים <math>h(x)=\begin{cases}g(x)&&x\not=a\\b&&x=a\end{cases}</math> עבור <math>b\not=g(a)</math> כלשהו. מתקיים <math>g\not=h</math>, ולמרות זאת <math>g\circ f=h\circ f</math> (כי בכל תמונת הפונקציה f, <math>g=h</math>). לכן f לא מצטמצמת משמאל.}}
{{תורת הקבוצות|מוגבל}}
[[קטגוריה:תורת הקבוצות|פונקציות]]