単射、逆関数、全射、全単射

いま『関数プログラミング』という本を読んでます。


関数プログラミング

関数プログラミング


ちょっと難しくなってきたのでメモ。
間違ってたら教えてください。


関数プログラミング』ではMirandaで書かれてますが、
MirandaわからないのでHaskellで書きます。

f :: A -> B

という型の関数があり、f x == f y ならば x == y である関数を単射関数(injective function)という。
すべての単射関数には、逆関数(inverse function)が対応付けられる。
以下のような単射関数があった場合、

f :: Integer -> (Integer, Integer)
f x = (signum x, abs x)

以下の逆関数を成り立つ。

ff :: (Integer, Integer) -> Integer
ff (s, a) = s * a

単射関数 f :: A -> B が、Bのすべての値yについて以下の式

f  (ff y) == y

を満たすということは一般的に成り立つわけではない。
単射関数に限らず、この条件を満たす関数を全射である(surjective)という。
単射であり、全射でもある関数fを全単射である(bijective)という。