Use pigeonhole principle to show that a nonempty subset of a finite set is finite

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?

• 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! :-) – 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.
• Thank you. But $f^{-1}$ doesn't map $A$ to $\{1,...,n\}$. – Allitee Jan 19 '16 at 17:00
• 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$. – Allitee Jan 19 '16 at 17:06
• @Allitee $f^{-1}$ maps $B$ to $\{1,...,n\}$. Since $A\subseteq B$, the composition is defined and maps between the two sets indicated. – Sean English Jan 19 '16 at 17:57
• 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. – Allitee Jan 19 '16 at 18:54