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

הגדרה

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

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

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

דוגמאות

• היחס $f\subseteq {ℝ}^2$ המוגדר על-ידי $f(x)=x+1$ הוא פונקציה.
• היחס $g\subseteq \{1,2\}\times \{3,5,10\}$ המוגדר על-ידי $g(1)=10,g(2)=3$ הוא פונקציה, אף על-פי שאינה מוגדרת על-ידי שום נוסחא.
• היחס $s\subseteq \mathbb{N}\times ℝ$ המוגדר על-ידי $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$ היא קבוצה אז הפונקציה ${\text{id}}_A:A\to A$ המוגדרת באמצעות ${\text{id}}_A(x)=x$ לכל $x\in A$ תיקרא פונקציית הזהות. נשים לב כי לא מתקיים בהכרח ${\text{id}}_A={\text{id}}_B$ : למשל הפונקציה $f(x)=|x|$ היא ${\text{id}}_{\mathbb{N}}$ אבל לא ${\text{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}={\text{id}}_B$ ו- $f^{-1}\circ f={\text{id}}_A$ . הגדרה זו דומה למדי ליחס ההפוך אך לפונקציה לא בהכרח קיימת הופכית שהיא גם פונקציה. למעשה לפונקציה קיימת הופכית אם ורק אם הפונקציה חח״ע ועל:

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

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

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

משפטי עזר

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