# an injection between two finite sets of the same cardinality is bijective

###### Lemma.

Let $A,B$ be two finite sets of the same cardinality. If $f\colon A\to B$ is an injective function then $f$ is bijective.

###### Proof.

In order to prove the lemma, it suffices to show that if $f$ is an injection then the cardinality of $f(A)$ and $A$ are equal. We prove this by induction on $n=\text{card}(A)$. The case $n=1$ is trivial. Assume that the lemma is true for sets of cardinality $n$ and let $A$ be a set of cardinality $n+1$. Let $a\in A$ so that $A_{1}=A-\{a\}$ has cardinality $n$. Thus, $f(A_{1})$ has cardinality $n$ by the induction hypothesis. Moreover, $f(a)\notin f(A_{1})$ because $a\notin A_{1}$ and $f$ is injective. Therefore:

 $f(A)=f(\{a\}\cup A_{1})=\{f(a)\}\cup f(A_{1})$

and the set $\{f(a)\}\cup f(A_{1})$ has cardinality $1+n$, as desired. ∎

Title an injection between two finite sets of the same cardinality is bijective AnInjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective 2013-03-22 15:10:20 2013-03-22 15:10:20 alozano (2414) alozano (2414) 6 alozano (2414) Theorem msc 03-00 SchroederBernsteinTheorem ProofOfSchroederBernsteinTheorem OneToOneFunctionFromOntoFunction