MHB One-to-one & Onto Function: $f$ from $A$ to $B$

[alexmahone]

Suppose that $f$ is a function from $A$ to $B$, where $A$ and $B$ are finite sets with
$|A|=|B|$. Show that $f$ is one-to-one if and only if it is onto.

(Hints only as this is an assignment problem.)

 

[Amer]

If $f$ is a function then if $f(a) = x$ and $f(a) = y$ then $x=y$ function definition
If $f$ is one to one then if $f(a) = f(b)$ then $a = b$. And we have $|A| = |B|$ and each are finite

You begin with the right implication suppose $f$ is one to one want to prove it is onto. You can prove by contradiction suppose not so we have ... What does it mean to be onto ?

If $f$ is onto suppose it is not one to one then there exit $a \not = b$ and $f(a) = f(b)$

 

[Deveno]

Do you know the pigeonhole principle? Imagine $A$ is a set of $n$ balls, and $f$ is a function that tells you where to put them in $m$ holes ($B$ is the set of holes).

Then "onto" tells you every hole is filled, and "1-1" tells you any hole has only one ball (at most).

See what you can do with this idea, when $n = m$.

 

[alexmahone]

I think I have a counterexample:
Let $A=\{a, b, c, d\}$ and $B=\{1, 2, 3, 4\}$. Let $f$ be a function from $A$ to $B$ defined by $f(a)=1$, $f(b)=2$, $f(c)=3$.
$f$ is surely one-to-one but not onto?

 

[I like Serena]

I think I have a counterexample:
Let $A=\{a, b, c, d\}$ and $B=\{1, 2, 3, 4\}$. Let $f$ be a function from $A$ to $B$ defined by $f(a)=1$, $f(b)=2$, $f(c)=3$.
$f$ is surely one-to-one but not onto?

Hi Alexmahone,

Part of the definition of a function is (usually) that every element in its domain gets mapped.
In your example $d$ does not get mapped.

 

[alexmahone]

I think I got it. I'd be glad if someone could go through this proof for me. I used the pigeonhole principle as Deveno suggested.

Assume that $f$ is not onto. Then there is at least one element in $B$ that does not have a preimage in $A$. Let $m$ be the number of elements in $B$ that have preimages. $m<|B|$
Let the elements in $A$ be the pigeons and the elements in $B$ that have preimages be the pigeonholes.
Number of pigeons $=|A|$
Number of pigeonholes $=m<|B|=|A|$
Since we have more pigeons than pigeonholes, by the pigeonhole principle, at least one of the pigeonholes contains more than one pigeon. That is, there is at least one element in $B$ that has more than one preimage in $A$. So, $f$ is not one-to-one.

Assume that $f$ is not one-to-one. Then there is at least one element in $B$ that has more than one preimage in $A$. Let $b_1$ be one such element in $B$ that has $m$ preimages in $A$ where $m>1$. Number of remaining elements in $A=|A|-m$. These elements can have at most $|A|-m$ images in $B$.
So, total images in $B\le 1+|A|-m=1+|B|-m<|B|$ $(\because m>1)$
So, $f$ is not onto.