Úloha 2.3.4. $\varphi^{n+m}=\varphi^n\circ\varphi^m$, $\varphi^{nm}=(\varphi^n)^m$

[alex.diko]

$\textbf{Úloha 2.3.4.}$
Matematickou indukciou dokážte, že $\varphi^{n+m}=\varphi^n\circ\varphi^m$, $\varphi^{nm}=(\varphi^n)^m$

$\textbf{a.)}$ $\varphi^{n+m}=\varphi^n\circ\varphi^m$ dokážeme indukciou na $n$, pre ľubovoľné $m\geq 0$.

1.) pre $n=0$ máme $\varphi^{0+m}=\varphi^{m}$ a $\varphi^{0}\circ\varphi^{m} =
id\circ\varphi^{m} = \varphi^{m}$

2.) Predpokladajme, že pre $n\geq 1$ platí $\varphi^{n-1+m}=\varphi^{n-1}\circ\varphi^{m}$

3.) Prenásobme obidve strany predpokladu zľava $\varphi$
$\varphi\circ\varphi^{n-1+m} = \varphi^{n+m}$ (definícia 2.3.1. JG: technicky to nie je 2.3.1)
$\varphi\circ(\varphi^{n-1}\circ\varphi^{m}) = (\varphi\circ\varphi^{n-1})\circ\varphi^{m}
=\varphi^n\circ\varphi^m$ (skladanie permutácii je podľa tvrdenia 2.2.10 asociatívne)
Teda $\varphi^{n-1+m}=\varphi^{n-1}\circ\varphi^{m}\;\Rightarrow\;
\varphi\circ\varphi^{n-1+m}=\varphi\circ(\varphi^{n-1}\circ\varphi^{m})\;\Rightarrow\;
\varphi^{n+m}=\varphi^n\circ\varphi^m$

b.) $\varphi^{nm}=(\varphi^n)^m$ spravíme indukciou na $m$ pre ľubovoľné $n\geq 0$

1.) pre $m=0$ máme $\varphi^{n\times 0} = \varphi^0=id$ a $(\varphi^n)^0 = id$ (lebo $\varphi^n$ je stále len nejaká permutácia)

2.) predpokladajme, že pre $m\geq 1$ platí $\varphi^{n(m-1)}=(\varphi^n)^{m-1}$

3.) vynásobme obidve strany predpokladu sprava $\varphi^n$
$\varphi^{n(m-1)}\circ\varphi^{n} = \varphi^{nm}$ (súčet exponentov ako dôsledok $\textbf{a.)}$ )
$(\varphi^n)^{m-1}\circ\varphi^{n} = (\varphi^n)^{m-1}\circ(\varphi^{n})^{1}=(\varphi^n)^m$ (kedže $\varphi^n$ je permutácia, opäť ako dôsledok súčtu exponentov)
Teda $\varphi^{n(m-1)}=(\varphi^n)^{m-1}\;\Rightarrow\;
\varphi^{n(m-1)}\circ\varphi^{n}=(\varphi^n)^{m-1}\circ\varphi^{n}\;\Rightarrow\;
\varphi^{nm}=(\varphi^n)^m$

[jaroslav.gurican]

OK, 1 bod