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$
Sources
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): $\S 22.2$: Injections; bijections; inverse of a bijection