I'm trying to get an early start on my discrete structures subject next semester (trying to get a head start :D) and trying to understand key parts of it. I was doing some online research about combinatorics when I found this interesting question. I figured this has something to do with set theory but I'm not sure which sub-topic this falls under.

You're given a positive natural number, $a \in \mathbb N^+$, two finite sets $X,Y$ such that $|X| > a|Y|$, and $f: X \to Y$. Show that there exists a $y \in Y$ such that $|f^{-1}(y)| ≥ a+1$.

Before actually answering this question, I would be grateful for any tips on what I should search to get a better understanding of how to solve this kind of a question and how I should go about answering such a question.

PS - This is my first time using this forum so any suggestions of how to better make a question or what kind of further information I should put in the question, would be great!

  • 3
    $\begingroup$ Have you encountered the pigeonhole principle before? $\endgroup$ Jun 24 '19 at 16:07
  • $\begingroup$ "Show that there exists a $y∈Y$ such that...." < nothing to do with y > ..... "$|f^{-1}(b)|$" (a reference to an undefined variable $b$). Was this a typo? Was that supposed to be a $y \in Y$ and $|f^{-1}(y)|$ or equivalently a $b\in Y$ and $|f^{-1}(y)|$. $\endgroup$
    – fleablood
    Jun 24 '19 at 16:11
  • $\begingroup$ @GregMartin We briefly touched up on it in my analysis class last semester and something to remember for our DS class next semester, so long answer short, yes but just the very basic idea. $\endgroup$
    – user684504
    Jun 24 '19 at 16:12
  • $\begingroup$ @fleablood I'm sorry it was a typo I meant to say $f^{-1}(\{y\})$ $\endgroup$
    – user684504
    Jun 24 '19 at 16:13

There are some tips :

  • It looks natural to reason by contraposition : i.e to suppose $|f^{-1}(\{y\})| \leq a$ and to show $|X| \leq a|Y|$ (there is no more $a+1$).

  • Some intuitive idea : the $|f^{-1}(\{y\})|$ are called fibers of $f$. The application $f$ from $X$ to $Y$ is in a certain way giving some structure on the set $X$. Mentally, you can put the different $y$ horizontally, and the elements of a same fiber $f^{-1}(\{y\})$ vertically over $y$. f can be thought as a projection on the horizontal axis.

  • It is linked to the previous point : the sets $f^{-1}(\{y\})$, for $y$ in $Y$, constitutes a partition of the set A, i.e the sets $f^{-1}(\{y\})$ are disjoint and their union is A. This implies something for the cardinal of the sum...

  • $\begingroup$ So one can use "Proof by Contradiction" to show that $|f^{-1}(\{y\})| \leq a$ is false, therefore the opposite must be true. But how do I begin with proof after I've stated that? $\endgroup$
    – user684504
    Jun 25 '19 at 12:18
  • $\begingroup$ It's not that $|f^{-1}(\{y\})| \le a$ is false. It's that $f^{-1}(\{y\}) \le a$ for every $y\in Y$. If that were true then $\sum_{y\in Y} |f^{-1}(\{y\})|\le \sum_{y\in Y} a = a|Y|$. But $|X| \le \sum_{y\in Y} |f^{-1}(\{y\})|$. So we have $a|Y| < |X| \le \sum_{y\in Y} |f^{-1}(\{y\})| \le a|Y|$. That's a contradiction. $\endgroup$
    – fleablood
    Jun 25 '19 at 15:19

The sets are finite so....

Think it out... Let $|Y| = n$ and $Y = \{y_1, ......, y_n\}$ and

ANd each $f^{-1}(y_i) \subset X$ must be finite so let $|f^{-1}(y_i)| = K_i$

Now $f: X\to Y$ so $f^{-1}(Y) = X$ and $f^{-1}(Y) = \cup_{i=1....n}f^{-1}(y_i)$.

Now the basic inclusion exclusion property of finite sets says that $|A \cup B| = |A| + |B| - |A\cap B|$ so $|X| = |f^{-1}(Y)| = |\cup_{i=1....n}f^{-1}(y_i)| \le \sum_{i=1}^n |K_i|$.

Now $|X| > a|Y|= an$.

... Pigeon hole.... if each $|K_i| \le a$ then $\sum_{i=1}^n|K_i| \le \sum_{i=1}^n a = an < |X| \le \sum_{i=1}^n |K_i|$. A contradiction.


In plainer english:

Suppose $Y$ has $n$ elements and $Y = \{y_1, ...., y_2\}$. And $X$ has more than $an$ elements.

$K_i= f^{-1}(\{y_i\}$ is the set of all elements of $Y$ that get mapped into $y_i$. The are $n$ of these sets: $K_1 = f^{-1}(\{y_1\}), K_2=f^{-1}(\{y_2\}), ..... etc.$

If each of these sets have at most $a$ elements then in total these sets have at the very most $an$ elements.

But every element of $X$ gets mapped to some element of $Y$ (that's what a "function" means) so every element of $X$ is in one of these sets. So at the absolute very most $X$ has $an$ elements.

Which contradicts our assumption that $X$ had more than $an$ elements.


Maybe to get an intuition we can do a physical example:

Let $Y = \{1,2,3,4\}$ so $|Y| = 4$ and $a = 3$ and $X= \{1,2,3,4,......, 13\}$ and $|X| = 13 > 3*4$.

Let say for $x \in \{1,2,3,4,.......,13\}=X$ then $f(x) \in \{1,2,3,4\} = Y$.

Consider $\{f(1), f(2), f(3),....., f(13)\}$. As there are only $4$ possible values these can be there must be some repeats. How many repeats? Well let's suppose $f(x) = 1$ has $3$ repeats. There are there $x_1,x_2,x_3 \in X$ so that $f(x_1)=f(x_2) =f(x_3) = 1$. And $f^{-1}(\{1\} ) = \{x_1, x_2, x_3\}$.

Okay, that's fine. Now how many repeats does $f(x) =2$ have? Let's say it has $3$. So there are $x_4,x_5,x_6$ so that $f(x_4) = f(x_5)=f(x_6) = 2$.

And how many repeats does $f(x) = 3$ have? and $f(x) =4$? Assume those have $3$ each too.

So how many $x \in X$ have we accounted for $x_1,x_2, x_3$ all map to $1$. And $x_4,x_5, x_6$ all map to $2$. And $x_7,x_8, x_9$ all map to $3$. And $x_{10}, x_{11}$ and $x_{12}$ map to $4$.

But... there are $13$ $x \in X$. Which one did we not account for? If $13$ elements are mapped into $4$ options there must be at least one option with more than $3$ elements mapped to it.

Another way of looking at it is if $|X|> na$ elements are mapped to $|Y|=n$ options, each option has on average $\frac {|X|}{|Y|} > \frac {na}{n} = a$ elements mapped to it. Now it's not possible for every option to have fewer than average mapped to it. So only must have at least the average mapped to it. And the average is at least $a + 1$.

  • $\begingroup$ So what you're saying is: Because |Y| is finite, we can make it equal an arbitrary but fixed $n$. Then we have that $f^{-1}(y_n) \subset X$ because its values come from the set $X$ and since it's finite, we can make it equal $K_i$. I'm not sure I understand the part where $f^{-1}(Y) = \cup_{i=1....n}f^{-1}(y_i)$. Are you saying that the inverse of $Y$ is the is the union set of the inverse of $y_n$, since $|Y|=n$? From here on I'm not sure what happened. You used the inclusion-exclusion property of finite sets, and got $|X| = |f^{-1}(Y)| = |\cup_{i=1....n}f^{-1}(y_i)| \le \sum_{i=1}^n |K_i|$. $\endgroup$
    – user684504
    Jun 25 '19 at 12:10
  • $\begingroup$ If you could explain the last steps here or make it clearer in the answer, I can accept it as the official answer and others can also see what happened more clearly. Thanks. $\endgroup$
    – user684504
    Jun 25 '19 at 12:11
  • $\begingroup$ If saying that every element of $x$ gets mapped to an element of $Y$ (that's what a function is) so every element of $x$ is in some $K_i$. If you add up all the elements of each $K_i$ you get at most the elements of $x$. (If the function is one to one then the $K_i$ are disjoint and the number of elements is exactly equal to the sum; if the function is not one to one the number of elements is less than the sum). If the most any $K_i$ has is $a$ the the most the can add to is $a|Y|$. $\endgroup$
    – fleablood
    Jun 25 '19 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy