I have seen a lot of definitions for surjectivity stating that every element in the codomain must be mapped to something in the domain. But does the opposite also have to hold true for a function to maintain its surjectivity?

The definition of a function $f$ from $A$ to $B$, regardless to injectivity or surjectivity, is that the domain of $f$ is $A$, in its entirety.

This means that if $fcolon Ato B$, then for every $ain A$, there is a unique $bin B$ such that the pair $(a,b)in f$.

So the converse holds just for it to be a function from $A$ to $B$.

No (to your title question), a function $f : A to B$, by definition, gives each $x in A$ a value $f(x) in B$.

To be precise, you should have said that "for every element in the codomain, there is (at least) one element which is mapped to it by $f$" for your definition of surjectivity.

I know exactly why that is confusing, and I will try to explain this step by step. The definition of surjectivity does not mention the domain being overfull. That throws some people off when learning this the first time. The reason for your confusion is likely that you skipped over the Cartesian product and function definition topics without understanding their significance (like I did). In short, the fact that every element of a domain maps to a codomain is implied by the definition of a function (it must be well-defined...read more if you're interested).

Long-winded explanation

So what is a function $f$? Well in set theory, it is a set whose elements are from a relation set, which is called a Cartesian product of sets.

What's that? So given sets $A := 1,2,3$ and $B := a,b $, we could define a relation set between them, but first we have to understand what a relation set is. It is every possible ordered combination (tuples) of elements from each set where the first element corresponds to the first set and the second corresponds to the second set (and so on with $>2$ sets). For example, $C := (1,a), (1,b), (2,a), (2,b), (3,a), (3,b)$ (but not including $(a,1), (a,2), (b,1), (b,2), (a,3), (b,3)$, because $anotin A, bnotin A$). Books explain this with a conditional statement like “$A times B := (x,y)$, where the $x$'s are from A and the $y$'s are from B”.

So now the critical thing to understand is that a function called $f$ that maps sets $A$ to $B$ ($f : A to B$) takes its elements not directly from $A$, but rather from $C$ above. Now the question is, which elements of $C$ may I use in $f$ such that we can still call $f$ a function?

The answer you've been waiting for is here. Your function only exists out of elements of set $C$ (a subset of $C$).

So we could make our $f: (1,a), (2,a), (3,a)$, which is well-defined, because all elements of the domain are accounted for (i.e. our functions knows how to handle any input)—not injective, because $a$ is mapped to by multiple elements of the domain.

The real question

Your question is really, what if I define $f: (1,a), (2,b)$ and leave out $(3,a), (3,b)$. Your function can not handle all domain inputs, therefore is not well defined, and is also not a valid function as most authors would advocate. While you could program a "function" like this, the mathematical definition assumes "well-definedness"—not to mention that your program would be prone to error!

It is possible that your function does not map the domain to all elements in the codomain, but it is impossible that your function could "ignore" an element from the domain side of the tuple.

Furthermore, there is a rule of correspondence that says the for any one element on the domain side of the tuple, it may only map it to one element of the codomain side of the tuple; in other words, I cannot use both of these tuples: $(1,a),(1,b)$. My domain element $1$ may not map to both $a$ and $b$ (different elements) of the codomain.

Conclusion

If a function is surjective, then you know two things for certain:

1. All of the elements of the codomain correspond to elements of the domain.




2. Because of the definition of a function being well defined, the function must know how to handle all elements of the domain.

See also

• Injective? Surjective? Bijective? None?




• Can surjective functions map an element from the domain...