If m > n then a function [m] rightarrow [n] cannot be injective. Proposition 13.

Question

If m > n then a function [m] rightarrow [n] cannot be injective. Proposition 13.5 implies that if m > n and we label n objects with numbers from 1 to m then there exist two objects that have the same label. The Pigeonhole Principle appears in many different areas in mathematics and beyond. It asserts that if there are/t pigeonholes and m pigeons, there are at least two pigeons who must share a hole; or if there are n people in an elevator and m buttons are pressed, someone is playing a practical joke.

Explanation / Answer

In the Pigeonhole Principle. if n are the pigeons and m are the pigeon holes, (given n > m), then there will be atleast one hole which will have 2 pigeons

In our problem, the number of holes are more than the number of pigeons

Domain has more elements than Range

Now trating m has pigeon and n has holes, there will be atleast one hole or range element with ceil(m/n) eleemnts, hence there will atleast 2 elements that will be mapped to same element in N

Hence the system won't be injective since there is no on-one mapping

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.