Proof. It will first be proven that, if a
bijection exists between two
finite sets, then the two sets have the same
number of elements. Let

and

be finite sets and

be a bijection. The claim will be proven by
induction on

.
If
, then
, and
can only be surjective if
.
Assume the statement holds for any set
with
. Let
. Let
with
. Let
. Then
.
Define
by
. Since
,
for all
. Thus, to show that
is well-defined, it only needs to be verified that
for all
. This follows immediately from the facts that
and
is injective. Therefore,
is well-defined.
Now it need to be proven that
is a bijection. The fact that
is injective follows immediately from the fact that
is injective. To verify that
is surjective, let
. Since
is surjective, there exists
with
. Since
and
is injective,
. Thus,
. Hence,
. It follows that
is a bijection.
By the induction hypothesis,
. Thus,
. Therefore,
. 