Given pigeonhole principle: for any natural numbers n and m, there's no bijective function between the set {1,...,n+m} and the set {1,...,n}. ($n,m\ge 1$)

A set $S$ is finite if there a bijective function between $s$ and $\{1,...,n\}$ for some natural number $n$.

From Royden's Real Analysis, let $A\subset B,\ A\ne \emptyset $ and $B$ is finite. There is a bijective function $f$ between $B$ and $\{1,...n\}$. We can define $g(1)$ to be the smallest natural number such that $f(g(1))\in A$ and $g(k)$ equals the smallest natural number such that $$f(g(k))\in A-\{f(g(1)),...,f(g(k-1))\}$$ Now he claims that according to pigeonhole principle, this process has to end after at most $N$ selections, where $N\le n$.

I am wondering how pigeonhole principle implies this process has to end?

  • $\begingroup$ If $f$ is the bijective function from $B$ to $\{1,\cdots,n\}$, could you edit the question to say this, please? Otherwise readers are left guessing what $f$ is! :-) $\endgroup$ – Frentos Jan 19 '16 at 1:32

Assuming that you meant that $f$ is a bijective function from $\{1,...n\}$ to $B$...

First, observe that if there is no bijective function from $\{1,...,n+m\}$ to $\{1,...,n\}$ then there is no injective function, since if there was, we could throw out any elements we missed in the range and have a bijective function to a smaller set.

Assume to the contrary that this process continues for at least $n+1$ iterations. Then you have a map $$g:\{1,...,n,n+1\}\to A.$$ By how $g$ is defined, $g$ is injective, then $$f^{-1}\circ g:\{1,...,n+1\}\to\{1,...,n\}$$ is injective. This contradicts our earlier statement derived from the pigeonhole principle.

  • $\begingroup$ Thank you. But $f^{-1}$ doesn't map $A$ to $\{1,...,n\}$. $\endgroup$ – Allitee Jan 19 '16 at 17:00
  • $\begingroup$ Do you want to say that $f^{-1}$ maps $\{1,...,n+1\}$ to $\{1,...,k\}$ for some $k\le n$. However, that is what I am trying to prove: there's bijective function from a subset of $\{1,...,n\}$ to $\{1,...,k\}$ for $k\le n$. $\endgroup$ – Allitee Jan 19 '16 at 17:06
  • $\begingroup$ @Allitee $f^{-1}$ maps $B$ to $\{1,...,n\}$. Since $A\subseteq B$, the composition is defined and maps between the two sets indicated. $\endgroup$ – Sean English Jan 19 '16 at 17:57
  • $\begingroup$ Thank you. Also, about the claim that there is no injective $f$ from $\{1,...,n+m\}$ to $\{1,...n\}$, is it a simple consequence of the pigeonhole principle stated in the question? I only can prove it using induction. $\endgroup$ – Allitee Jan 19 '16 at 18:54
  • $\begingroup$ @Allitee I have actually never heard the pigeonhole principle stated in terms of bijections. Usually it is stated "if n>m and only one pigeon fits in a pigeonhole, then n pigeons can't fit in m pigeonholes"(or some equivalent statement) which is a statement about injective functions. To prove the result concretely from the definition in your post, I think you would have to use induction as you suggested. $\endgroup$ – Sean English Jan 19 '16 at 19:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.