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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

הגדרה[עריכה]

יחס ייקרא פונקציה אם מהוא מקיים שתי תכונות:

  1. קיום: לכל קיים כך ש- .
  2. יחידות: אם ו- אז .

במקרה כזה ייקרא התחום של הפונקציה ואילו ייקרא הטווח של הפונקציה ומסמנים זאת כך: . אם ל- מתקיים אז ייקרא התמונה של ואילו ייקרא המקור של .

דוגמאות[עריכה]

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

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

אם ו- הן פונקציות אז ההרכבה שלהן מוגדרת בתור .

פונקציית זהות[עריכה]

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

סוגי פונקציות[עריכה]

פונקציה חח״ע: פונקציה תיקרא חח״ע או חד-חד-ערכית אם גורר .

פונקציה על: פונקציה תיקרא על אם לכל קיים כך ש- .

פונקציה חח״ע ועל: פונקציה תיקרא חח״ע ועל או חד-חד-ערכית ועל אם היא חד-חד-ערכית וגם על.

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


טענה:

היחס הוא פונקציה אם ורק אם חח״ע ועל.

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

מש"ל.PNG

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

הגדרה 1.6: קבוצות שקולות

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

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

הגדרה 1.7: מכפלה קרטזית

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

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


הגדרה 1.8: חזקת קבוצות

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

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

משפטי עזר[עריכה]

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



משפט 2.1:

אם ו- הן פונקציות חח״ע ועל אז גם ההרכבה היא חח״ע ועל.


הוכחה: חח״ע: יהי כך ש- . מכיון ש- חח״ע . מכיון ש- חח״ע .

על: יהי . מכיון ש- על קיים כך ש- . מכיון ש- על קיים כך ש- . כעת .

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

מש"ל.PNG



משפט 2.2:

לכל לא קיימת פונקציה על מ- ל- .


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

מש"ל.PNG



משפט 2.3:

תהי . אם חח״ע, קיימת פונקציה כך ש- . אם על, אז קיימת פונקציה כך ש- .


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

מש"ל.PNG



משפט 2.4:

לכל קיימת פונקציה חח״ע מ- ל- אם ורק אם קיימת פונקציה על מ- ל- .


הוכחה: נניח שקיימת פונקציה חח״ע . ממשפט 2.3 קיימת פונקציה כך ש- . יהי , אז ולכן הוא מקור ל .
כעת נניח שקיימת פונקציה על . ממשפט 2.3 קיימת כך ש- . נניח ש- , אז .

מש"ל.PNG


הפרק הקודם:
יחסים
פונקציות הפרק הבא:
יחסי שקילות