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