# Maps and the number of elements in a map

So here's the question:
Suppose $f: S \to T$ is a map of sets.
a. If T is finite & the map is one-to-one, show that $|S|$ is finite and that $|S| \le |T|$.
b. If S is finite & the map is onto, show that $|T|$ is finite and that $|T| ≤ |S|.$
So here's what I understand: (or think I understand)

for a: Suppose $x_1,x_2,x_3 \in S$.
Suppose $|S| > |T|$.
Then $f: S \to T$ would be $x_1 = f(x_1)$, $x_2 = f(x_2)$, $x_3 = f(x_2).$
This is a contradiction because $f$ is not one-to-one.
Therefore, $|S| \le |T|$.

And my guess would be b. would be the same thing but for proving onto.

• LaTeX commands you might want to know: $\to$ is $\to$, $\le$ is $\le$, $\in$ is $\in$, and $x_1$ is $x_1$ – Omnomnomnom Dec 11 '14 at 23:25
• You have the right general idea. Your proof as written only works if $S$ has exactly $3$ elements, though. Can we use the pigeonhole principle? – Omnomnomnom Dec 11 '14 at 23:29
• how would I prove for more than 3? thanks! – Zoë Soriano Dec 11 '14 at 23:42
• @Omnomnomnom i looked into that principle and i still don't really get it... any other hints? – Zoë Soriano Dec 12 '14 at 5:17

Let $T$ be finite and the map one to one. Suppose that $n=|S|> |T|=m$. Let $x_1,\dots,x_n$ be an enumeration of the elements of $S$ and $y_1,\dots, y_m$ an enumeration of the elements of $T$.
We note that each of the $n$ elements $f(x_i)$ is an element of the set $T=\{y_1,\dots,y_m\}$. By the pigeonhole principle, there exist two such elements that are equal. That is, there exist integers $i\neq j$ between $1$ and $n$ for which $f(x_i)=f(x_j)$. This is a contradiction of the map being one to one.