写像を集合ごと指定する
写像f:A→Bを考えるとき、Aは入力を許す定義域、Bは出力の所属先として指定する終域です。実際に出てくる値を集めた像f(A)はBの一部であり、必ずB全体になるとは限りません。式だけでなく、この二つの集合を決めてから性質を調べます。例えばf(x)=x²でも、実数全体から実数全体へ送る場合と、非負の実数から非負の実数へ送る場合では、入力の区別や出力の網羅の性質が変わります。計算式が同じだから同じ結論になると考えず、どの値を入力として認め、どの出力を要求しているのかを先に書きます。
単射は入力の区別を保つ
単射では、f(a)=f(b)ならa=bが成り立ちます。逆に言えば、違う入力が同じ出力へ衝突しません。A={1,2,3}からB={a,b,c,d}へ1→a、2→b、3→cと送る写像は単射ですが、dには届きません。未使用の出力があっても単射の条件には反しません。データの識別番号を割り当てる際には、異なる対象が同じ番号を持たないことが単射に対応します。ただし、削除した番号の再利用や対象の同一性の定義は別の規則です。ある時点の表で重複がないことと、全運用期間にわたり衝突しない保証も区別します。
全射は指定した出力を覆う
全射では、終域Bのどの要素bにも、f(a)=bとなる入力aが少なくとも一つあります。A={1,2,3}、B={a,b}で1→a、2→a、3→bなら全射です。1と2が同じaへ行っても、全射の条件には反しません。一方、終域を{a,b,c}へ広げて式を変えなければ、cへ届かないので全射ではなくなります。実際の出力を並べてから都合よく終域と呼び直すと、元の要求を満たしたか分からなくなります。どの出力を必ず作れる必要があるかを先に定め、各出力について入力の存在を説明します。
両方あれば逆写像を作れる
単射かつ全射の写像を全単射と呼びます。このとき各出力には、入力がちょうど一つ対応します。全射が存在を保証し、単射が一意性を保証するため、出力から元の入力へ戻す逆写像を定義できます。どちらか一方だけでは同じ結論にはなりません。全射だけなら戻り先が複数あり、単射だけなら終域の一部に戻り先がない場合があります。有限集合でAとBの要素数が同じなら、単射と全射は同値になりますが、この有限性と同数という前提を省いて一般化しないようにします。
無限集合では個数の直感を確かめ直す
整数から整数へのf(n)=2nは単射ですが、奇数へ届かないため全射ではありません。同じ整数集合から同じ整数集合への写像でも、単射だから全射とは言えない例です。逆に、自然数の集合を0以上の整数と定め、f(n)=⌊n/2⌋とすれば、各出力へ2nと2n+1が対応し、全射ですが単射ではありません。有限集合で有効だった個数の議論を、そのまま無限集合へ持ち込まないことが重要です。実装では型の値域が有限か、オーバーフローで折り返すかも確認します。数学上の整数の例と、固定幅整数の実装の性質は別に検証します。
合成の性質を確かめる
単射fと単射gを続けて適用すると、g(f(a))=g(f(b))から順にg、fの単射性を使いa=bを導けます。全射同士の合成も、終域の任意の値から入力の存在を二段階で追って示せます。ただし合成できるように、fの出力がgの定義域へ入ることが前提です。型の対応も含めて式を確認します。