אם m > n ומשבצים m יונים ל-n תאים אז קיים תא אחד עם לפחות 2 יונים.הוכחה: נניח בשלילה ששיבצנו את כל היונים ובכל תא קיימת לכל היותר יונה אחת. יש לנו n תאים ולכן n >= m בסתירה לנתון.
אם אתה רוצה להרחיב אתה את ההוכחה למקרה הסופי הכללי (דהיינו 2 קבוצות A ו-B בגדלים m ו-n בהתאמה), אז אתה יכול ליצור פונקציות איזומורפיות מ-A ל{1,...,m} ומ-B ל-{1,...,n} ולעשות רדוקציה להוכחה שנתתי.
המקרה האינסופי הוא יותר מעניין, גם שם אפשר להימנע מאינדוקציה (או להשתמש באינדוקציה טרנספיניטית).
לשאלתך השנייה:
בהרבה מקומות מסמנים ב-f-1(B) את קבוצת המקורות של B ובאופן כללי אפשר לקחת איבר מ-B ולשאול מהו f-1({b}) ולקבל קבוצה עם יותר מאיבר אחד.
כדי לא להתבלבל, אני בד"כ מסמן ב-f-1[B] את קבוצת המקורות של B וב-f-1[b] את קבוצת כל האיברים שנשלחים לאיבר b.
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
