Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

Detailed proof, please.

share|improve this question
    
What have you tried? Did you see a proof and did not understand it? –  Asaf Karagila Nov 29 '12 at 19:53
5  
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

2 Answers 2

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.

share|improve this answer
    
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$?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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