写像・単射・全射と逆写像
入力と出力の対応から、元の入力を一意に求められる条件を学びます。
説明
写像は、入力の集合に含まれる各要素へ、出力の集合の要素を一つずつ対応させる規則です。入力の集合を定義域、出力先として指定した集合を終域と呼びます。実際に出力される値の集合は像です。
このモジュールでは、四つの入力と四つの出力候補からなる小さな対応表を使います。出力の重複や使われない候補を調べ、単射・全射・全単射の違いを説明します。最後に、出力から入力へ戻す逆写像を作り、元の対応を復元します。
1各入力に一つの出力を割り当てる
入力をa〜d、出力候補を0〜3とします。まず、異なる入力が同じ出力になる対応を作ります。
domain = ['a', 'b', 'c', 'd']定義域; codomain = {0, 1, 2, 3}終域; f = {'a': 0, 'b': 1, 'c': 1, 'd': 2}対応表; [(x, f[x]) for x in domain]入力と出力を列挙bとcはともに1へ対応します。それでも各入力の出力が一つに決まっているので、この対応は写像です。
2実際に出力される値の集合
対応表の出力を集合にすると、同じ値の重複がなくなります。
image = set(f.values())出力値の集合; sorted(image)像, sorted(codomain - image)出力されない終域の要素像は0、1、2で、終域の3は出力に使われていません。終域と像は、必ず同じ集合になるわけではありません。
3単射でないことを示す組
単射とは、異なる入力が同じ出力にならない写像です。出力が重複する入力の組を探します。
[(x, y, f[x]) for i, x in enumerate(domain) for y in domain[i+1:]異なる入力の組を一度ずつ作る if f[x] == f[y]出力が同じ組だけを抽出]bとcが同じ1へ対応する組が見つかりました。出力1だけを受け取っても、元がbかcかを決められません。
4出力を一つずつ使う対応に変える
dを3、cを2へ対応させ、入力ごとに異なる出力を使います。
f = {'a': 0, 'b': 1, 'c': 2, 'd': 3}対応を変更; len(set(f.values())) == len(domain)出力の重複がないか, set(f.values()) == codomain終域の全要素を使うか出力の重複がないという判定も、終域の全要素を使うという判定もTrueです。前者が単射、後者が全射で、両方を満たす写像を全単射と呼びます。
5全射かどうかは終域の指定にも依存する
対応表を変えず、終域に4を加えます。
larger_codomain = codomain | {4}終域を拡張; set(f.values()) == larger_codomain新しい終域への全射か, sorted(larger_codomain - set(f.values()))使われない出力候補全射の判定はFalseとなり、使われない値4が見つかりました。同じ対応表でも、終域を何とするかによって全射かどうかは変わります。
6出力から入力へ戻す対応表
元の終域0〜3に対しては全単射なので、入力と出力を交換した対応表を作れます。
inverse = {value: key for key, value in f.items()}入力と出力を交換; sorted(inverse.items())逆写像の対応表0→a、1→b、2→c、3→dです。出力ごとに元の入力が一つに決まり、終域内で戻せない値もありません。これが逆写像です。
7写像と逆写像を続けて使う
各入力をfで変換し、inverseで戻します。
[(x, f[x], inverse[f[x]]入力・変換後・逆変換後) for x in domain定義域の全要素]すべての行で、最初の入力と最後の値が一致します。fの後に逆写像を使うと、定義域の各要素が元へ戻ります。
8出力が重複する対応表を逆引きした結果
最初のようにbとcをともに1へ対応させます。辞書で機械的にキーと値を交換した結果を確認します。
many = {'a': 0, 'b': 1, 'c': 1, 'd': 2}重複する出力を持つ写像; reversed_map = {v: k for k, v in many.items()}辞書のキーと値を交換; sorted(reversed_map.items()), len(reversed_map)残った対応と件数1に対応する入力はcだけ残り、bが失われました。Pythonの辞書では同じキーへの後の代入が上書きされるためです。この表は元の写像の逆写像にはなっていません。
まとめ
単射は出力に重複がないこと、全射は終域の全要素が出力に現れることです。両方を満たす全単射には、終域から定義域へ戻す逆写像があります。
終域の指定や出力の重複を確認せずに対応表を逆にすると、戻せない値や失われる入力が生じます。
操作履歴と解説を振り返れます。
Python 3
domain = ['a', 'b', 'c', 'd']; codomain = {0, 1, 2, 3}; f = {'a': 0, 'b': 1, 'c': 1, 'd': 2}; [(x, f[x]) for x in domain][('a', 0), ('b', 1), ('c', 1), ('d', 2)]image = set(f.values()); sorted(image), sorted(codomain - image)([0, 1, 2], [3])
[(x, y, f[x]) for i, x in enumerate(domain) for y in domain[i+1:] if f[x] == f[y]][('b', 'c', 1)]f = {'a': 0, 'b': 1, 'c': 2, 'd': 3}; len(set(f.values())) == len(domain), set(f.values()) == codomain(True, True)
larger_codomain = codomain | {4}; set(f.values()) == larger_codomain, sorted(larger_codomain - set(f.values()))(False, [4])
inverse = {value: key for key, value in f.items()}; sorted(inverse.items())[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]
[(x, f[x], inverse[f[x]]) for x in domain][('a', 0, 'a'), ('b', 1, 'b'), ('c', 2, 'c'), ('d', 3, 'd')]many = {'a': 0, 'b': 1, 'c': 1, 'd': 2}; reversed_map = {v: k for k, v in many.items()}; sorted(reversed_map.items()), len(reversed_map)([(0, 'a'), (1, 'c'), (2, 'd')], 3)
演習完了