# Thread: Help with injective, surjective proof

1. ## Help with injective, surjective proof

Please help me with this, I'm not sure I understand it and don't know where to start

Let A and B be finite sets with |A| = |B|. Suppose that f: A--->B. Prove that f is injective if and only if f is surjective

2. Originally Posted by Dax
Let A and B be finite sets with |A| = |B|. Suppose that f: A--->B. Prove that f is injective if and only if f is surjective
Suppose that $f:A \mapsto B$ is injective but not surjective.
Notation: $f^{ - 1} (b) = \left\{ {x \in A:f(x) = b} \right\}$
$\mathbb{F} = \left\{ {f^{ - 1} (b):b \in B} \right\}\;\& \,\left| \bigcup\mathbb{F} \right| = \left| A \right|$
But $f$ is not surjective so $\left( {\exists c \in B} \right)\left[ {f^{ - 1} (c) = \emptyset } \right]$.

3. is there an easier way to explain that, none of that looks familiar, i'm only a few weeks into the class and that doesn't make sense to me at all

4. Originally Posted by Dax
is there an easier way to explain that, none of that looks familiar, i'm only a few weeks into the class and that doesn't make sense to me at all
Look, this is not a trivial problem. It usually makes use of the pigeon-hole principle.
You are not going to find a trivial proof. Any proof is equivalent to proving a form of the pigeon-hole principle.

That said, try this.
Suppose that $f:A \mapsto B$ is injective.
$\left( {\forall a \in A} \right)\left\{ {\{ f(a)\} } \right\}$ is collection of pair-wise disjoint subsets of $B$.
But by the nature if functions $\left| {\left\{ {\{ f(a)\} } \right\}} \right| = \left| A \right| = \left| B \right|$.
From that how can conclude that $f$ is surjective?