how to prove: If A and B are finite sets with the same number of elements, then f: A --> B is bijective iff f is injective iff f is surjective.

Printable View

- Sep 6th 2008, 02:03 PMdori1123cardinality
how to prove: If A and B are finite sets with the same number of elements, then f: A --> B is bijective iff f is injective iff f is surjective.

- Sep 6th 2008, 02:44 PMPlato
That is a bit confused I think. Because a function is bijective iff it is both injective and surjective. So that is by definition.

Now if $\displaystyle \left| A \right| = \left| B \right| < \infty $ then any function from A to B is injective if and only if it is also surjective.

I will help you one way. Suppose that $\displaystyle f:A \mapsto B$ is bijective.

From subjectivity, $\displaystyle \left( {\forall b \in B} \right)\left( {\exists a \in A} \right)\left[ {f(a) = b} \right] \Rightarrow \left| A \right| \ge \left| B \right|$.

From injectivity, $\displaystyle \left( {\forall p \in A} \right)\left( {\exists !q \in B} \right)\left[ {f(p) = q} \right] \Rightarrow \left| B \right| \ge \left| A \right|$.

Therefore $\displaystyle \left| B \right| = \left| A \right|$.