עקרון שובך היונים

[raviosa]

עקרון שובך היונים

הוכח ע"פ עקרון שובך היונים שאם n מספר טבעי וגם פונקציה f שהולכת מהטבעיים (עד ל-n לא כולל) ל->טבעיים (עד ל-n לא כולל) היא חח"ע, אז f היא גם על.

עכשיו, מה עקרון שובך היונים אומר? שלא קיימת העתקה f מהטבעיים עד n לטבעיים עד m, כאשר n>m שהיא חח"ע.
אני מנסה להבין איך אני יכול להשתמש בזה פה, בעצם במקרה המדובר בתרגיל n=m ואז זה מסתדר ואומר שהיא חח"ע.
אבל איך העל נכנס פה לתמונה? נתון לי שהיא כבר חח"ע. שובך היונים לא מדבר בכלל על על - או לא-על. הוא מדבר רק על חד חד ערכיות.
אפשר עזרה?

 

[1ca1]

תשובה

מדובר על פונקציה מקבוצה סופית {1,...,n} לעצמה.
למרות שזאת אותה קבוצה, נחשוב על f:A->B כאשר A,B אותה קבוצה, ו-A זה יונים ו-B זה שובכים ו-f זה ההשמה של יונה לשובך.
נניח ש-f לא על.
אז התמונה של f היא תת-קבוצה ממש של B, בפרט מגודל קטן ממש מ-n.
משובך היונים, אנחנו מכניסים n יונים לפחות מ-n שובכים ולכן יש שובך עם יותר מיונה אחת, בסתירה לחח"ע של f.
&nbsp