# Elementary set theory question regarding finiteness

We say that a set $X$ is finite if there is a bijection from $X$ to $\{0, 1, ..., m\}$, for some $m\in \mathbb{N}$.

Let $A$ and $B$ be finite sets such $A\subseteq B$ and let $\phi: A \rightarrow B$ be a bijection. Show that $A=B$.

-
What have you tried? Did you see a proof and did not understand it? –  Asaf Karagila Nov 29 '12 at 19:53
Linna, people might think your question is a bit impolite. Actually, you did not specify a question rather an assignment for us. For better response try to reformulate yourself. –  AD. Nov 29 '12 at 20:03

Suppose that $B$ is finite, $A\subseteq B$, and $\phi\colon A\to B$ is a given bijection, then in particular $\phi^{-1}\colon B\to A$ is a bijection, and therefore $\phi^{-1}\colon B\to B$ is an injection..

Using the pigeonhole principle we deduce that $\phi^{-1}\colon B\to B$ is actually surjective, and therefore $B=\operatorname{rng}(\phi^{-1})=\operatorname{dom}(\phi)=A$ as wanted.

-
Asaf, you wrote $B\to B$ instead of $B\to A$ (3ed line). –  AD. Nov 29 '12 at 20:08
@AD. Yes, I know I did. If $F\colon X\to Y$ and $Y\subseteq Z$ then $F\colon X\to Z$ as well. While surjectivity does not necessarily lift if $Y\neq Z$, injectivity does and this is what I care about. I want to have an injective function from $B$ into itself, therefore it has to be surjective, but since the range of the function is $A$ then equality follows. –  Asaf Karagila Nov 29 '12 at 20:09
:) you are right –  AD. Nov 29 '12 at 20:10
+1 for you :) $\ \$ –  AD. Nov 29 '12 at 20:12
@AD. Thanks! Now I have a palindromic reputation! :-) –  Asaf Karagila Nov 29 '12 at 20:14

HINT: Since $B$ is finite, there is a bijection $\psi:B\to\{0,\dots,m\}$ for some $m\in\Bbb N$. You’re given a bijection $\varphi:A\to B$. What can you say about the map $\psi\circ\varphi$?

-