פונקציה

פונקציה (או העתקה) היא כלל שמקשר כל איבר מקבוצה אחת, הנקראת תחום, לאיבר יחיד בקבוצה שנייה, הנקראת טווח. הסימון f: X → Y מורה שפונקציה f מקבוצה X ל־Y. פורמלית, פונקציה היא תת־קבוצה של המכפלה הקרטזית X×Y (קבוצת הזוגות הסדורים), כך שלכל x ב־X יש לפחות תמונה אחת y ובנוסף התמונה היא יחידה. את הקבוצה של כל הזוגות הסדורים שקובעת את f קוראים גרף הפונקציה.

מסמנים f(x)=y אם (x,y) שייך לגרף. ה־y נקרא תמונה (התוצאה) של x, ו־x נקרא מקור של y. אם לכל y יש מקור יחיד אומרים שהפונקציה חד־חד־ערכית (אינו־מכפילה). אם מוותרים על קיומה של תמונה לכל x מקבלים פונקציה חלקית. אם מאפשרים למספר תמונות עבור x מקבלים יחס מרובה.

לכל תת־קבוצה Z של X מגדירים f(Z) = {f(z) | z ∈ Z} והיא התמונה של Z. להיפך, לכל תת־קבוצה W של Y מגדירים המקור f^{-1}(W) = {x ∈ X | f(x) ∈ W}. הצמצום של f ל־Z מסומן f|_Z והוא פשוט הגבלה של התחום ל־Z.


לכל x ב־X יש תמונה יחידה. לעומת זאת איבר ב־Y יכול להיות עם כמה מקורות או בלי מקור כלל. לכן בדרך כלל f^{-1}(f(Z)) לא שווה בדיוק ל־Z, וגם f(f^{-1}(W)) לא חייבת לשחזר את W, אם כי תמיד קיימים יחסיים הכלליים שמתקיימים.


ההתאמה המתאימה לכל אדם את גילו היא פונקציה מקבוצת האנשים לקבוצת המספרים הטבעיים, כי לכל אדם יש גיל יחיד. ההתאמה המתאימה לכל מספר ממשי את ריבועו היא פונקציה על הממשיים המוגדרת על־ידי f(x)=x^2. לעומת זאת, ההתאמה המתאימה לכל אדם את המדינה שבה הוא אזרח אינה פונקציה אם לאדם יש כמה אזרחויות. גם מד הכושר בשחמט לא תמיד מהווה פונקציה אם לאדם אין דירוג.


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



פונקציית הזהות על X, I_X: X → X, מוגדרת I_X(x)=x לכל x. היא חד־חד־ערכית ועל, ולכן הפיכה ועל־ידי עצמה. היא איבר היחידה ביחס להרכבת פונקציות.


הפונקציה הריקה היא היחידה מהקבוצה הריקה ∅ אל Y. מכיוון שאין אף איבר ב־∅, הפונקציה לא קולטת ואין סתירה לתנאי ההגדרה. היא חד־חד־ערכית באופן ריק, אך בדרך כלל אינה על.


פונקציה קבועה היא כזו שמחזירה תמיד את אותו y_0 ∈ Y לכל x∈X. אם X אינה ריקה והיא לא יחידון, פונקציה קבועה אינה חד־חד־ערכית.


לרתק תת־קבוצה Z ⊂ X מגדירים את פונקציית המציין 1_Z: X → {0,1} כך ש־1_Z(x)=1 אם x∈Z ו־1_Z(x)=0 אם x∉Z. זו דרך פשוטה לייצג קבוצות באמצעות פונקציות.


פונקציה n־מקומית (פעולה n־ארית) היא כלל f: X^n → X שמקבל n קלטים ומחזיר איבר ב־X. פונקציה 1־מקומית היא פשוט פונקציה רגילה על X; פונקציה 2־מקומית נקראת פעולה בינארית, כמו חיבור וכפל על מספרים.


בהינתן f: X → Y ו־g: Y → Z מגדירים את ההרכבה g∘f: X → Z על־ידי (g∘f)(x)=g(f(x)). הרכבה אינה קומוטטיבית לרוב, כלומר g∘f שונה מ־f∘g. עם זאת היא אסוציאטיבית. פונקציית הזהות היא איבר היחידה בהרכבה.


קבוצה של כל הפונקציות מ־X ל־Y מסומנת Y^X. כאשר X ו־Y סופיות, גודל Y^X שווה |Y|^{|X|}, כלומר מספר הפונקציות שווה למספר האופציות לבחירת תמונה לכל איבר ב־X.

פונקציה היא כלל שנותן לכל כניסה תשובה אחת. כניסה מגיעה מתחום (תחום = קבוצת הקלטים). התשובות שייכות לטווח (טווח = קבוצת התשובות). כותבים f: X → Y כדי לומר שפונקציה f מקבוצה X ל־Y.

פונקציה היא אוסף של זוגות (x,y). אם (x,y) שייך לאוסף אז f(x)=y. ה־y נקרא תמונה של x. ה־x נקרא מקור של y.


הכלל שמקצה לכל אדם את גילו הוא פונקציה. הכלל שמקצה לכל מספר את הריבוע שלו הוא פונקציה: f(x)=x^2. אבל אם לאדם יש כמה אזרחויות, אז ההתאמה למדינה אינה פונקציה.


פונקציית הזהות על X מחזירה כל דבר כמו שהוא: I(x)=x. הפונקציה הריקה היא מהקבוצה הריקה ואין לה קלטים. פונקציה קבועה מחזירה תמיד את אותה תשובה עבור כל קלט.


פונקציה 2־מקומית מקבלת שני קלטים ומחזירה תשובה. דוגמה פשוטה היא חיבור של שני מספרים.


הרכבה אומרת לעשות פעולה אחת ואחריה שנייה. אם עושים קודם f ואז g, מקבלים g∘f.