問1.1 h:Σ*→Γ* が準同型写像のとき
h(xy)=h(x)h(y) (x,y∈Σ*)
であることをyの長さに関する帰納法で証明せよ。
解
● |y|=0のとき、左辺は
h(xy)=h(xε)=h(x).
右辺は
h(x)h(y)=h(x)h(ε)=h(x). ∵準同型写像の定義による
したがって
h(xy)=h(x)h(y). (*)
● |y|=n (n∈N)のときh(xy)=h(x)h(y)が成り立つとする。yz=w∈Σ*,z∈Σとおく。|w|=n+1である。h(x・w)=h(x)h(w)を示せばよい。
連接は交換法則を満たすから、左辺は
h(x・w)=h(xyz)=h(xy・z)
=h(xy)h(z) ∵準同型写像の定義による
=h(x)h(y)h(z). ∵|y|=nのときの仮定による
右辺は
h(x)h(w)=h(x)h(yz)
=h(x)h(y)h(z) ∵準同型写像の定義によりyzを分解。
したがって
h(xy)=h(x)h(y). (**)
(*)(**)により、常にh(xy)=h(x)h(y)が成り立つ。
Q.E.D.