# Cardinality of Image of Injection

## Theorem

Let $f: S \rightarrowtail T$ be an injection.

Let $A \subseteq S$ be a finite subset of $S$.

Then:

$\card {f \paren A} = \card A$

where $\card A$ denotes the cardinality of $A$.

## Proof

Proof by induction:

For all $n \in \N_{>0}$, let $P_n$ be the proposition:

$\card {f \paren A} = \card A$ when $\card A = n$

Suppose $\card A = 0$.

 $\ds \card A$ $=$ $\ds 0$ $\ds \leadsto \ \$ $\ds A$ $=$ $\ds \O$ Cardinality of Empty Set $\ds \leadsto \ \$ $\ds f \paren A$ $=$ $\ds \O$ Image of Empty Set is Empty Set $\ds \leadsto \ \$ $\ds \card {f \paren A}$ $=$ $\ds 0$ Cardinality of Empty Set

So $P_0$ holds.

### Basis for the Induction

Suppose $\card A = 1$.

Then let $A = \set a$.

So:

$f \paren A = \set {f \paren a}$

and so:

$\card {f \paren A} = 1$

So $P_1$ is true.

This is our basis for the induction.

### Induction Hypothesis

Now we need to show that, if $P_k$ is true, where $k \ge 1$, then it logically follows that $P_{k + 1}$ is true.

So this is our induction hypothesis:

$\card {f \paren A} = \card A$ when $\card A = k$

Then we need to show:

$\card {f \paren A} = \card A$ when $\card A = k + 1$

### Induction Step

This is our induction step:

Consider $A$ where $\card A = k+1$.

Let $s \in A$ and consider $A' = A \setminus \set s$.

Let $f {\restriction_{A'} }$ be the restriction of $f$ to $A'$.

By Restriction of Injection is Injection we have that $f {\restriction_{A'} }$ is also an injection.

Then by the induction hypothesis:

$\card {f {\restriction_{A'} } \paren {A'} } = \card {A'}$

because $\card {A'} = k$.

Now consider $f \paren s$.

Suppose $f \paren s \in f {\restriction_{A'} } \paren {A'}$.

Then:

$\exists t \in A': f \paren t = f \paren s$

and so $f$ would not be an injection.

So:

$f \paren s \notin f {\restriction_{A'} } \paren {A'}$ and so:
 $\ds f \paren A$ $=$ $\ds f \paren {A' \cup \set s}$ $\ds$ $=$ $\ds f \paren {A'} \cup f \paren {\set s}$ Image of Union under Mapping $\ds \leadsto \ \$ $\ds \card {f \paren A}$ $=$ $\ds \card {f \paren {A'} } + \card {f \paren {\set s} }$ Cardinality of Set Union, as $f \paren {A'}$ and $f \paren {\set s}$ are disjoint $\ds$ $=$ $\ds k + 1$

So $P_k \implies P_{k + 1}$ and the result follows by the Principle of Mathematical Induction.

$\blacksquare$