A surjective map $S \to T$ implies $|S| \geq |T|$

Question

Problem: Suppose that there is a function mapping $S$ onto $T$.

Show that $\operatorname{Card}(S)\ge\operatorname{Card}(T)$

Issue: I can't seem to find a reason why this follows. If $S$ maps $T$ then this guarantees that for any element in $T$ there is at least one element in $S$. Therefore, I keep coming up with the fact that $\operatorname{Card}(S)\le\operatorname{Card}(T)$. Am I missing something, or is there a typo on my study guide?

Thanks in advance.

Answer 1

You appear to be misunderstanding the meaning of "surjective (or onto) function."

A function from $A$ to $B$ is onto if, for every element $b\in B$, there is some $a\in A$ such that $f(a)=b$. So, for example, the map $0\mapsto 5, 1\mapsto 5$ is a surjection from $\{0, 1\}$ onto $\{5\}$.

Meanwhile there is no surjection from $\{5\}$ to $\{0, 1\}$ - we can send $5$ to $0$, or we can send $5$ to $1$, but we can't do both (functions are single-valued), and whichever of $0$ or $1$ we send $5$ to, the other will be "missed."

Answer 2

If for each element in $T$ there is at least one element in $S$ that maps onto it, doesn't that mean there are at least as many elements in $S$ as in $T$ (don't forget an element in $S$ can map onto only one element in $T$)?

Answer 3

If, for every element in $T$, there's at least one element in $S$, surely that means that there are at least as many elements in $S$ than in $T$; in other words, the size of $S$ is at least as big as $T$.

To prove a statement like this, there's a standard result for finite sets (sometimes its given as a definition) that $|A|\leq|B|$ if and only if there is an injection (a one-to-one function) from $A$ to $B$. This makes sense because it says there are at least enough elements in $B$ such that every element in $A$ can be sent to a different element; you don't need to double up where any of the elements go.

Once you know that there is a surjection $S\rightarrow T$, you can define a really straightforward injection in the other direction. (Technically this requires the axiom of choice). In other words, as there is a surjection, for any element $t\in T$, there is at least one element $s\in S$ such $f(s)=t$. Then define $g(t)=s$ for one of those $s$'s. This is definitely an injection $T\rightarrow S$ (because $f$ was well-defined) and so you can conclude $|S|\geq|T|$.