88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 5
תוכן עניינים
המשך פונקציות - פונקציות על תת-קבוצות
תמונות חלקיות
הגדרה. תהי פונקציה, ויהיו תת קבוצות
. אזי התמונה החלקית של A תחת f היא התת-קבוצה
, והתמונה החלקית ההפוכה של B תחת f היא התת-קבוצה
.
שימו לב להבדל בין התמונה ההפוכה לבין הפונקציה ההופכית
. התמונה ההפוכה איננה מניחה כי הפונקציה f הפיכה. הדרך להבחין בין פונקציה הפיכה לתמונה ההפוכה היא לבדוק האם בין הסוגריים נמצא איבר של התמונה (בדוגמאות לעיל זהו
) או שנמצאת תת-קבוצה של התמונה (בדוגמאות לעיל זו
).
תרגיל.
הוכח/הפרך: תהיינה ותהי f פונקציה
. אזי
פתרון.
נפריך על ידי דוגמא נגדית. נניח וf אינה חח"ע, כלומר קיימים כך ש
. ניקח
אזי:
תרגיל.
תהי ותהי
. הוכח
. וקיים שיוויון אם
חח"ע
פתרון.
יהא אזי
ולכן
.
נראה את ההכלה בכיוון השני אם חח"ע:
יהא לכן
לכן
. כיוון ש
חח"ע נובע כי
תרגיל.
תהי ותהי
. הוכח
. וקיים שיוויון אם
על
פתרון.
יהא כאשר
ולכן
.
נראה את ההכלה בכיוון השני אם על:
יהא כיוון ש f על
לכן
. ואז
תרגיל ממבחן (קצת משודרג).
יהיו שתי קבוצות, ותהי
פונקציה כלשהי. נגדיר את הפונקציה
על ידי
.
בדוק את הקשר בין החח"ע/על של f לבין אלה של g. (כלומר, מה גורר את מה בהכרח).
פתרון.
1. f על אמ"מ g חח"ע
בכיוון אחד- נתון ש f על. נניח נפעיל את f על שני הצדדים ונקבל (בגלל ש f על)
בכיוון השני- נתון כי g חח"ע. נניח בשלילה כי f אינה על אזי לכן
בסתירה לחח"ע של g.
2. f חח"ע אמ"מ g על
בכיוון אחד- נתון f חח"ע. אזי ולכן g על ( עבור A המקור שלה יהיה
)
בכיוון השני- נתון g על. נניח בשלילה ש f אינה חח"ע אזי קיימים שונים כך ש
. נביט בנקודון
כיוון ש g על קיימת כך ש
לכן
ולכן
לכן כלומר
. סתירה.
מכאן ניתן להסיק כי שאר הגרירות אינן מוכרחות:
- ייתכן ו-f חח"ע אך g אינה כזו (ניקח f חח"ע שאינה על אזי g אינה חח"ע לפי 1)
- יתכן ו-g חח"ע אך f אינה כזו. (ניקח g חח"ע שאינה על אזי f אינה חח"ע לפי 2)
- ייתכן ו-f על אך g אינה כזו (ניקח f על שאינה חח"ע אזי g אינה על לפי 2)
- ייתכן ו-g על אך f אינה כזו (ניקח g על שאינה חח"ע אזי f אינה על לפי 1)
אתם מוזמנים לתת דוגמאות למסקנות לעיל
למשל:
יהיו . אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן
ואלה הקבוצות היחידות בקבוצת החזקה של Y.
פונקציה מצומצמת
הגדרה.
תהי ותהי
. הפונקציה f מצומצמת לA מוגדרת על ידי:
כך ש
.
דוגמא.
נביט ב המוגדרת על ידי
ואינה חח"ע. נכון לומר שהפונקציה המצומצמת
כן חח"ע.
תרגיל.
תהי פונקציה, הוכח שקיימת קבוצה A כך ש
חח"ע עם אותה התמונה כמו הפונקציה המקורית (כלומר
פתרון.
נגדיר לכל את הקבוצה של המקורות שלו
כעת נבחר מכל
איבר יחיד
. נגדיר
. כיוון שבחרנו מקור לכל תמונה ובחרנו מקור אחד אזי
חח"ע עם אותו טווח של
.
אזהרה! ההוכחה מתבססת על אקסיומת הבחירה (נפגש איתה בהמשך)
פונקציות המכבדות יחס שקילות
הגדרה. תהי , ויהי R יחס שקילויות על A. אומרים כי f מוגדרת היטב על
אם
כלומר אם a שקול ל b אזי .
למה זה טוב?
כדי שנוכל להגדיר פונקציה על קבוצת המנה ע"י
באופן מפורש .
טענה: g אכן פונקציה
הוכחה:
1. g שלמה - "לפי העיניים". כלל ההתאמה מנוסח כך שהיחס הוא שלם.
2. g חד ערכית- נניח , ואז
. צ"ל
, וזה אכן מתקיים כי f מוגדרת היטב על קבוצת המנה.
דוגמא לחידוד
האם f על הרציונאליים המוגדרת על ידי מוגדרת היטב?
פתרון
לא! כזכור הרציונאליים הם קבוצת מנה של . לפי היחס שהגדרנו מתקיים
אבל לא מתקיים
במילים: לא ברור לאן f שולחת את השבר שליש!
הערה: בכוונה ניסחנו את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורש. זו הדרך בה נתקל במושג 'מוגדר היטב' במהלך התואר - יחס השקילויות יהיה מרומז בלבד.