# Help with injective, surjective proof

• Sep 20th 2009, 01:06 PM
Dax
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
• Sep 20th 2009, 01:29 PM
Plato
Quote:

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 $\displaystyle f:A \mapsto B$ is injective but not surjective.
Notation: $\displaystyle f^{ - 1} (b) = \left\{ {x \in A:f(x) = b} \right\}$
$\displaystyle \mathbb{F} = \left\{ {f^{ - 1} (b):b \in B} \right\}\;\& \,\left| \bigcup\mathbb{F} \right| = \left| A \right|$
But $\displaystyle f$ is not surjective so $\displaystyle \left( {\exists c \in B} \right)\left[ {f^{ - 1} (c) = \emptyset } \right]$.
• Sep 20th 2009, 02:32 PM
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
• Sep 20th 2009, 03:07 PM
Plato
Quote:

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 $\displaystyle f:A \mapsto B$ is injective.
$\displaystyle \left( {\forall a \in A} \right)\left\{ {\{ f(a)\} } \right\}$ is collection of pair-wise disjoint subsets of $\displaystyle B$.
But by the nature if functions $\displaystyle \left| {\left\{ {\{ f(a)\} } \right\}} \right| = \left| A \right| = \left| B \right|$.
From that how can conclude that $\displaystyle f$ is surjective?