Composition of Repeated Compositions of Injections

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be a set.

Let $f: S \to S$ be an injection.

Let the sequence of mappings:

$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:

\(\displaystyle f^0 \circ f^m\) \(=\) \(\displaystyle I_S \circ f^m\) $\quad$ where $I_S$ is the identity mapping $\quad$
\(\displaystyle \) \(=\) \(\displaystyle f^m\) $\quad$ Identity Mapping is Left Identity $\quad$


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:

\(\displaystyle \left({f^{k+1} \circ f^m}\right) \left({x}\right)\) \(=\) \(\displaystyle \left({f \left({f^k}\right) \circ f^m}\right) \left({x}\right)\) $\quad$ Definition of $f^{k+1}$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({f \circ f^k}\right) \circ f^m}\right) \left({x}\right)\) $\quad$ Definition of Composition of Mappings $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({f \circ \left({f^k \circ f^m}\right)}\right) \left({x}\right)\) $\quad$ Composition of Mappings is Associative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({f \circ f^{m+k} }\right) \left({x}\right)\) $\quad$ Induction Hypothesis $\quad$
\(\displaystyle \) \(=\) \(\displaystyle f^{m+k+1} \left({x}\right)\) $\quad$ Basis for the Induction $\quad$

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$