# 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 |