If a function $A\to B$ where $A$ and $B$ are two sets, is a bijection then $A$ and $B$ must have same number of elements. Is the converse true?

I know that if $A$ and $B$ are two sets with equal number of elements, and if we prove a function $A\to B$ to be either one one or onto, we also prove it a bijection. But if we haven't proved it either one one or onto, can we still believe it to be a bijection because of the fact that the two sets have same number of elements.

  • $\begingroup$ It will be true for finite sets that a function from a set to another that has the same cardinality that is one-to-one or onto must be both one-to-one and onto, but it need not be true for infinite sets. Consider the function $f~:~\Bbb N\to \Bbb N$ given by $f(n)=2n$. Clearly both the domain and codomain have the same cardinality (they are equal sets after all), but $f$ in this case is one-to-one but not onto. $\endgroup$ – JMoravitz Sep 9 '18 at 17:54
  • $\begingroup$ As for the possible interpretation of your question I'm hoping you aren't asking... there do exist functions between two finite sets of the same cardinality which are not bijections. Consider a constant function for example... IF we know literally nothing about the function other than it goes between two sets of same size, then there is the possibility of it being a bijection, but no reason for us to think it will be. $\endgroup$ – JMoravitz Sep 9 '18 at 18:01
  • $\begingroup$ Thanks sir for clearing my doubts $\endgroup$ – user64501 Sep 10 '18 at 9:15
  • $\begingroup$ Sir, can you give an example of a function which is between two finite sets of same size but not a bijection $\endgroup$ – user64501 Sep 10 '18 at 9:18

Having a bijection between two sets is equivalent to the sets having the same "size". (In the case of infinite sets, the situation might be considered a little less "obvious"; but it is the generally agreed upon notion. Cantor is probably the biggest name that should be mentioned. Without this notion, we wouldn't have his "infinite paradise"...)

For finite sets, the situation is somewhat simpler. If the domain and range have the same size (cardinality), then an injective map is bijective. Similarly, a surjective map is bijective (as you observe; actually, you forgot to specify that the sets must be finite).

For infinite sets, on the other hand, an injective map is still a bijection (onto its image). But we can have injections and surjections which aren't bijections (between infinite sets of the same cardinality). In fact, an infinite set can be characterized as a set which is in bijective correspondence with a proper subset of itself... You can use the familiar $\tan$ function (in the case of the reals), or map any interval to any other, bijectively; or more generally, a shift function ($x\to x+k$), etc... to do this sort of thing.

However, as to your question, not every function between two sets of the same "size" is a bijection, trivially. Not just in the infinite case, but also in the finite. That is, for instance, send all the elements in the domain to the same element of the range (for any set with more than $1$ element).

  • $\begingroup$ Thanks sir for clearing my doubts. $\endgroup$ – user64501 Sep 10 '18 at 9:15
  • $\begingroup$ Sir, can you give an example of a function which is between two finite sets of same size but not a bijection $\endgroup$ – user64501 Sep 10 '18 at 9:18
  • $\begingroup$ As pointed out, a constant function: $f:\{1,2\}\to\{1,2\}$ by $f(1)=f(2)=1$ would be an example. $\endgroup$ – Chris Custer Sep 10 '18 at 10:50
  • $\begingroup$ Oh yes, thanks a lot for the example $\endgroup$ – user64501 Sep 10 '18 at 11:55

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.