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.
Is this the correct way of going about this problem? Thank you!

  • 1
    $\begingroup$ LaTeX commands you might want to know: $\to$ is $\to$, $\le$ is $\le$, $\in$ is $\in$, and $x_1$ is $x_1$ $\endgroup$ – Omnomnomnom Dec 11 '14 at 23:25
  • 1
    $\begingroup$ 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? $\endgroup$ – Omnomnomnom Dec 11 '14 at 23:29
  • $\begingroup$ how would I prove for more than 3? thanks! $\endgroup$ – Zoë Soriano Dec 11 '14 at 23:42
  • $\begingroup$ @Omnomnomnom i looked into that principle and i still don't really get it... any other hints? $\endgroup$ – Zoë Soriano Dec 12 '14 at 5:17

The answer to the first part would go something like this:

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.

The conclusion follows.


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.