Composition of Repeated Compositions of Injections

From ProofWiki
Jump to navigation Jump to search


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


$\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 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.


$\forall m, n \in \Z_{\ge 0}: f^n \circ f^m = f^{m + n}$