4. Prove the following infinite version of the pigeon-hole principle: Suppose that X is an infinite...

Transcribed Image Text:

4. Prove the following infinite version of the pigeon-hole principle: Suppose that X is an infinite subset, and Y is a finite subset. Then for any function f : X →Y, there is a y E Y such that |f¹(y)| > ∞. (Hint: By contradiction: Assume that f-¹(y)| <∞ for all y E Y and use the fact that Y is finite to obtain a contradiction using the generalized pigeonhole principle) 4. Prove the following infinite version of the pigeon-hole principle: Suppose that X is an infinite subset, and Y is a finite subset. Then for any function f : X →Y, there is a y E Y such that |f¹(y)| > ∞. (Hint: By contradiction: Assume that f-¹(y)| <∞ for all y E Y and use the fact that Y is finite to obtain a contradiction using the generalized pigeonhole principle)

Answer rating: 100% (QA)

We will prove a principle called the infinite pigeonhole principle using a method called contradiction Imagine we have a function called f that takes ... View the full answer