שינויים

יהיו תהיינה <math>A</math> ו-<math>B</math> קבוצות סופיות בעלות עוצמה זההלא ריקות. הוכיחו שכל פונקציה מ-: <math>|A|\geq |B|</math> ל-אם ורק אם קיימת <math>f:A\to B</math> הינה על אם"ם היא חח"ע.

'''====הוכחה:'''====נסמן <math>f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_nb_m\} </math> . כאשר כל האיברים ב-<math>A</math> שונים זה מזה וכנ"ל ב-<math>B</math>. נניח <math>f</math> חח"ע אזי <math>|\{f(a_1),\dots, f(a_n)\}|=n</math> כיוון ש-<math>\{f(a_1),\dots, f(a_n)\}\subseteq B </math> ובשניהם יש אותו מספר איברים, מתקיים שיוון ולכן <math>f </math> על. נניח <math>f </math> על. נניח בשלילה ש-<math>f</math> אינה חח"ע אזי <math>|\{f(a_1),\dots, f(a_n)\}|<n</math> (כי יש שני איברים שנשלחים לאותו מקום) ואז <math>f</math> אינה על, שזו סתירה.  הערה: הדבר אינו נכון אם <math>A</math> ו-<math>B</math> קבוצות אינסופיות. נסו למצוא דוגמה.