1
$\begingroup$

Prove that a nonempty set ${T_1}$ is finite if and only if there is a bijection from ${T_1}$ onto a finite set ${T_2}$.

Now,I think my proof is correct but I want the opinion of other people because I have started analysis. Please help me perfect my thought process and proof writing by checking my solution.

${{Proof : }}$ Since ${T_2}$ is a finite set, so there is a bijection from ${T_2}$ onto ${\mathbb{N}_m}$ for some ${m\in\mathbb{N}}$. Let,

${f : T_2\rightarrow{N}_m}$ _(1)

be a bijection from ${T_2}$ to ${\mathbb{N}_m}$. Now, if ${T_1}$ is a bijection onto ${T_2}$, then

${g : T_1{\rightarrow}T_2}$. _(2)

Now, from ${(1)}$ & ${(2)}$,

${f(g(T_1)) = {\mathbb{N}_m}}$.

So, ${f.o.g : T_1\rightarrow\mathbb{N}_m}$ is a bijection from ${T_1}$ onto ${{\mathbb{N}_m}}$. Therefore ${T_1}$ is a finite set.

Please correct me if my proof is wrong or if it needs some more argument. Thank you! :))

$\endgroup$
1
$\begingroup$

When you see a 'if and only if', you have two directions to prove (the if, and the only if). What you have is about the point that if $T_1$ has a bijection onto some finite set $T_2$, then $T_1$ is also finite. But you must also show the converse, that if $T_1$ is finite then there is some finite set $T_2$ for which $T_1$ has a bijection onto $T_2$. This direction is trivial, as you can take $T_2 = T_1$ and there certainly is a bijection between $T_1$ and $T_1$. But it needs to be stated.

As for your proof, what you end up with is that $T_1$ has a bijection onto some finite set $\mathbb{N}_m$. But we already knew that, since there is a bijection between $T_1$ and finite $T_2$. So we gained no new information. Actually, you could set $\mathbb{N}_m = T_2$ and nothing new was deduced. What you can look into is the condition on the cardinalities of $T_1$ and $T_2$ for them to admit a bijection.

$\endgroup$
  • $\begingroup$ Thank you! Can you please show me the correct proof so that I can understand how to proceed in similar situations? Thank you... :) $\endgroup$ – Abir Mukherjee Apr 25 '14 at 19:47
  • 1
    $\begingroup$ Well, maybe you should try first :) Can you find an argument using the cardinalities of $T_1$ and $T_2$ if they admit a bijection ? $\endgroup$ – Manuel Lafond Apr 25 '14 at 19:52
  • $\begingroup$ I think the cardinalities of ${T_1}$ and ${T_2}$ must be same since they are in bijection. If ${T_1}$ is not a finite set then ${|T_1|>|T_2|}$, which contradicts the fact that they are in bijection. Thus ${T_1}$ is a finite set.Am I right? :-) $\endgroup$ – Abir Mukherjee Apr 25 '14 at 21:54
  • 1
    $\begingroup$ That is correct and convincing enough for me :) Now, you might want to convince yourself that the cardinalities must be the same. Essentially, a bijection between $X$ and $Y$ maps each element of $X$ to a distinct element of $Y$, such that every element of $Y$ got mapped to some element - which is impossible if $|X| \neq |Y|$. This can be formalized using the definition of a bijection : it is a surjective and injective function. $\endgroup$ – Manuel Lafond Apr 26 '14 at 4:51

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.