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:

$\left|{f \left({A}\right)}\right| = \left|{A}\right|$

where $\left|{A}\right|$ denotes the cardinality of $A$.

Proof

Proof by induction:

For all $n \in \N^*$, let $P_n$ be the proposition:

$\left|{f \left({A}\right)}\right| = \left|{A}\right|$ when $\left|{A}\right| = n$

Suppose $\left|{A}\right| = 0$.

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left\vert {A}\right\vert\)	\(=\)	\(\displaystyle 0\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle A\)	\(=\)	\(\displaystyle \varnothing\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Cardinality of Empty Set
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle f \left({A}\right)\)	\(=\)	\(\displaystyle \varnothing\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Image of Null is Null
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left\vert{f \left({A}\right)}\right\vert\)	\(=\)	\(\displaystyle 0\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Cardinality of Empty Set

So $P_0$ holds.

Basis for the Induction

Suppose $\left|{A}\right| = 1$.

Then let $A = \left\{{a}\right\}$.

So $f \left({A}\right) = \left\{{f \left({a}\right)}\right\}$ and so $\left|{f \left({A}\right)}\right| = 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:

$\left|{f \left({A}\right)}\right| = \left|{A}\right|$ when $\left|{A}\right| = k$

Then we need to show:

$\left|{f \left({A}\right)}\right| = \left|{A}\right|$ when $\left|{A}\right| = k+1$

Induction Step

This is our induction step:

Consider $A$ where $\left|{A}\right| = k+1$.

Let $s \in A$ and consider $A' = A \setminus \left\{{s}\right\}$.

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:

$\left|{f \restriction_{A'} \left({A'}\right)}\right| = \left|{A'}\right|$, because $\left|{A'}\right| = k$

Now consider $f \left({s}\right)$.

Suppose $f \left({s}\right) \in f \restriction_{A'} \left({A'}\right)$.

Then $\exists t \in A': f \left({t}\right) = f \left({s}\right)$ and so $f$ would not be an injection.

So $f \left({s}\right) \notin f \restriction_{A'} \left({A'}\right)$ and so:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle f \left({A}\right)\)	\(=\)	\(\displaystyle f \left({A' \cup \left\{ {s}\right\} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle f \left({A'}\right) \cup f \left({\left\{ {s}\right\} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Mapping Image of Union
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left\vert{f \left({A}\right)}\right\vert\)	\(=\)	\(\displaystyle \left\vert{f \left({A'}\right)}\right\vert + \left\vert{f \left({\left\{ {s}\right\} }\right)}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Cardinality of Set Union, as $f \left({A'}\right)$ and $f \left({\left\{ {s}\right\} }\right)$ are disjoint
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle k + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

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

Sources

• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 22.2$