5
$\begingroup$

To me, it seems logical that if I have two finite sets of equal size, and there is an injection between them, then that injection must be a bijection.

However, of course, we cannot just claim these things as various tricky counter examples have demonstrated in the past.

However, I am unable to prove the above claim. What would a proof of such a claim look like? I can see that we now need to prove that the mapping is also surjective, but I am not completely sure how to go about doing this.

Also, the condition above has that the sets are finite. What happens if we drop this condition? Does the claim no longer necessarily hold?

$\endgroup$
1
  • 1
    $\begingroup$ With the answers already sketched out, I would advise you to post your answer fully laid out so that the community also feels good that they have helped someone, and if you miss something in rigour, it can be pointed out. $\endgroup$
    – Shailesh
    Aug 21, 2015 at 6:05

2 Answers 2

3
$\begingroup$

Hint: for two finite sets A and B, what would happen if an injection from A to B were not a surjection?

If $A,B$ are both infinite, let $A=B=\Bbb N$, then $f(x)=x+1$ is an injection from $A$ to $B$, but...

$\endgroup$
4
  • $\begingroup$ I'm guessing the answer would be "Then the two sets can not be of the same size"? However this feels like something I just pulled out from a visual understanding of things, which could perhaps fail sometimes? $\endgroup$
    – Trogdor
    Aug 21, 2015 at 6:04
  • 1
    $\begingroup$ @Trogdor Your understanding is perfectly right. Just imagine if $A$ contains $k$ distinct elements, then the image of an injection $f:A\to B$ must contain exactly $k$ distinct elements in $B$ (why?), and due to equal sizes $B$ cannot contain more than $k$ elements, thus $B$ is precisely the image, and hence the surjection. $\endgroup$
    – Vim
    Aug 21, 2015 at 6:09
  • $\begingroup$ @Trogdor also note that visualisation is a powerful tool, don't underestimate how much it can help you. $\endgroup$
    – Vim
    Aug 21, 2015 at 6:11
  • 1
    $\begingroup$ I understand your explanation perfectly well. Thank you. I just wish to be careful because visualisation has, in the past, fooled me before. For example, the unit interval having the same cardinality as the reals was something I formerly thought to be impossible (visually), until I saw the stereographic projection from the unit interval to the real line. $\endgroup$
    – Trogdor
    Aug 21, 2015 at 6:13
2
$\begingroup$

The proof is essentially just an exercise in definition chasing, it is good to just do it for yourself. Write out the definition of surjectivity, think of what could go wrong, and show that that cannot happen because of injectivity. Maybe drawing some diagrams with two sets points and arrows between them describing a function will help you. It's a good exercise. An appropriate exercise that follows the same idea is that if $\phi: V \to V$ is an injective linear automorphism of a finite dimensional vector space.

Obviously this is not true if the sets are not finite, $f: \mathbb{Z} \to \mathbb{Z}$ given by $f(x) = 2x$ is a counterexample, and there are many more.

Edit: Really I guess I should point out that one of the definitions of an infinite set is a set $A$ such that there exists an injective $f: A \to A$ that is not surjective. So this definitively fails for infinite sets.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .