Composition of Repeated Compositions of Injections
Theorem
Let $S$ be a set.
Let $f: S \to S$ be an injection.
- $f^0, f^1, f^2, \ldots, f^n, \ldots$
be defined as:
- $\forall n \in \N: f^n \left({x}\right) = \begin{cases}
x & : n = 0 \\ f \left({x}\right) & : n = 1 \\ f \left({f^{n-1} \left({x}\right)}\right) & : n > 1 \end{cases}$
Then:
- $\forall m, n \in \Z_{\ge 0}: f^n \circ f^m = f^{m + n}$
where $f^n \circ f^m$ denotes composition of mappings.
Proof
Proof by induction:
Let $m \in \Z_{\ge 0}$ be given.
For all $n \in \Z_{\ge 0}$, let $P \left({n}\right)$ be the proposition:
- $f^n \circ f^m = f^{m + n}$
$P \left({0}\right)$ is true, as this is the case:
| \(\ds f^0 \circ f^m\) | \(=\) | \(\ds I_S \circ f^m\) | where $I_S$ is the identity mapping | |||||||||||
| \(\ds \) | \(=\) | \(\ds f^m\) | Identity Mapping is Left Identity |
Basis for the Induction
$P \left({1}\right)$ is true, as this is the case:
- $f^{m+1} \left({x}\right) = f \left({f^m \left({x}\right)}\right)$
by definition.
This is our basis for the induction.
Induction Hypothesis
Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.
So this is our induction hypothesis:
- $f^k \circ f^m = f^{m + k}$
Then we need to show:
- $f^{k+1} \circ f^m = f^{m + k + 1}$
Induction Step
This is our induction step:
| \(\ds \left({f^{k+1} \circ f^m}\right) \left({x}\right)\) | \(=\) | \(\ds \left({f \left({f^k}\right) \circ f^m}\right) \left({x}\right)\) | Definition of $f^{k+1}$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \left({\left({f \circ f^k}\right) \circ f^m}\right) \left({x}\right)\) | Definition of Composition of Mappings | |||||||||||
| \(\ds \) | \(=\) | \(\ds \left({f \circ \left({f^k \circ f^m}\right)}\right) \left({x}\right)\) | Composition of Mappings is Associative | |||||||||||
| \(\ds \) | \(=\) | \(\ds \left({f \circ f^{m+k} }\right) \left({x}\right)\) | Induction Hypothesis | |||||||||||
| \(\ds \) | \(=\) | \(\ds f^{m+k+1} \left({x}\right)\) | Basis for the Induction |
So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\forall m, n \in \Z_{\ge 0}: f^n \circ f^m = f^{m + n}$
$\blacksquare$