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

Lemma.

Let $A\mathrm{,}B$ be two finite sets of the same cardinality. If $f\mathrm{:}A\mathrm{\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
Canonical name	AnInjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective
Date of creation	2013-03-22 15:10:20
Last modified on	2013-03-22 15:10:20
Owner	alozano (2414)
Last modified by	alozano (2414)
Numerical id	6
Author	alozano (2414)
Entry type	Theorem
Classification	msc 03-00
Related topic	SchroederBernsteinTheorem
Related topic	ProofOfSchroederBernsteinTheorem
Related topic	OneToOneFunctionFromOntoFunction