計算機科学のブログ

関数の基礎 全単射の合成写像

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第6章(関数の基礎)、章末問題の6.7の解答を求めてみる。

zをZの任意の元とする。

gは全射なので、 あるYの元yが存在して、

z = g ( y )

fは全射なので、あるXの元xが存在して、

f ( x ) = y

よって、

( g ∘ f ) ( x ) = g ( f ( x ) ) = g ( y ) = z

ゆえに、合成写像は全射である。

a、 bを X の任意の元とする。

( g ∘ f ) ( a ) = ( g ∘ f ) ( b )

ならば、

g ( f ( a ) ) = g ( f ( b ) )

gは単射なので、

f ( a ) = f ( b )

fは単射なので、

a = b

よって、 合成写像 は単射である。

ゆえに合成写像は全単射である。

（証明終）