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