Confusion with a function being "onto" and 1-1 correspondence.
If we are given an onto function $f : A \to B$, then this ensures that every element of $B$ corresponds to something in $A$.
But does this necessarily mean that the number of elements in set $B$ equates to that of the number of elements in set $A$?
My understanding is the answer to this is "no".
If my understanding is correct, then given a 1-1 correspondence between two sets $A$ and $B$ (i.e 1-1 and onto) does THIS then imply that the number of elements in sets $A$ and $B$ are equal?
Also, assume that $A$ and $B$ are finite sets. I do not want to necessarily talk about cardinality of infinite domains.
$\endgroup$ 13 Answers
$\begingroup$Yes, it means that $f$ is a bijection ("1-1" means injective, "onto" means surjective), and this is one of the definitions of "equal in size".
In my opinion, these notions are confusing beyond usability, but the consensus is that:
"1-1" or "1-1 mapping" means injective, i.e., no element of $B$ has more than one pre-image;
"1-1 correspondance" means injective both ways, i.e., bijective.
I prefer to use:
- "onto" for surjective;
- "injective" for injective;
- "bijective" for bijective.
However, in many real cases, there are more proper names as "factors", "homo/endo/auto/iso-morphisms", "conjugations" etc., so you then don't meet the basic notions so often.
$\endgroup$ 1 $\begingroup$For your first question, the answer is "no". For example, the function $[x]$ (integer part) maps the reals onto the integers.
For the second, the existence of a 1-1 correspondence is the usual definitionof having the same number of elements for infinite sets.
$\endgroup$ $\begingroup$If f:A→B is a surjective (onto) function then |A|≥|B| and f is a bijection iff the cardinality of A and B are equal (even if they are infinite sets)
$\endgroup$ 2
