入力ごとに出力が1つの対応
写像とは、入力ごとに出力をちょうど1つ決める対応のことです。関数とも呼びます。学籍番号から名前を引く、バーコードから値段を引くなど、プログラムの中でも毎日使っています。
対応には、「同じ出力を2人が使う」「使われない出力が残る」といった性質があります。それを単射や全射という言葉で整理します。
このレッスンのゴール
メモ
対応を見て、写像かどうかと、単射か全射かを判断することができる。
キーワード
| ことば | いみ |
|---|---|
| 写像 | 入力ごとに出力がちょうど1つ決まる対応 |
| 定義域 | 入力にできるものの集合 |
| 値域 | 実際に出力として現れるものの集合 |
| 単射 | 異なる入力が、異なる出力になる写像 |
| 全射 | 終域のすべてが、出力として使われる写像 |
| 全単射 | 単射であり、全射でもある写像 |
学生が入力するセルは、このプレビューでは空白です。
入力ごとに出力が1つなら写像
写像は、入力ごとに出力をちょうど1つ決める対応です。入力にできるものの集合を定義域、出力の候補として決めた集合を終域と呼びます。
実際に出力として現れるものの集合が値域です。値域は、終域の一部になります。
例: 学籍番号と部活の対応
| 対応 | 入力から出力へ | 写像か | 理由 |
|---|---|---|---|
| A | 101→サッカー、102→茶道、103→サッカー | 写像 | どの入力にも出力が1つ |
| B | 101→サッカー、101→茶道、102→茶道 | 写像ではない | 101 に出力が2つある |
| C | 101→サッカー、102→茶道(定義域は101から103) | 写像ではない | 103 に出力がない |
学生が入力するセルは、このプレビューでは空白です。
Python の辞書は写像そのもの
python3 -c "m = {101: 'soccer', 102: 'tea', 103: 'soccer'}; print(m[101], len(m), sorted(set(m.values())))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
単射、全射、全単射
単射は、異なる入力が必ず異なる出力になる写像です。出力が重なりません。全射は、終域のすべてが、どれかの入力の出力になる写像です。使われない出力が残りません。
両方を満たすと全単射です。入力と出力が、1対1でぴったり対応します。
例: 4つの写像を比べる
| 写像 | 入力から出力へ | 終域 | 単射 | 全射 |
|---|---|---|---|---|
| f | 1→a、2→b、3→c | {a, b, c} | はい | はい |
| g | 1→a、2→b、3→c | {a, b, c, d} | はい | いいえ |
| h | 1→a、2→a、3→b | {a, b} | いいえ | はい |
| k | 1→a、2→a、3→b | {a, b, c} | いいえ | いいえ |
学生が入力するセルは、このプレビューでは空白です。
写像 h を調べる
python3 -c "m = {1: 'a', 2: 'a', 3: 'b'}; print(len(set(m.values())) == len(m), set(m.values()) == {'a', 'b'})"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
for で単射と全射を調べる
# 写像を辞書で表し、出力が重なるか、終域が残らず使われるかを調べます。
mapping = {1: "a", 2: "a", 3: "b"}
codomain = ["a", "b"]
seen = []
one_to_one = True
for x in mapping:
y = mapping[x]
if y in seen:
one_to_one = False
seen.append(y)
onto = True
for y in codomain:
if y not in seen:
onto = False
print("単射:", one_to_one, "全射:", onto)
# codomain に "c" を足して、もう一度実行しましょう。
よくある間違い
注意
「全射なら、単射でもある」と考える人が多くいます。h は全射ですが、1と2が同じ出力なので単射ではありません。入力と出力が同じ個数の有限集合のときだけ、一方が成り立てば他方も成り立ちます。
関係と、同値関係
関係は、2つのものが結びついているかを決める規則です。「同じ学年である」「より背が高い」は関係です。写像とちがい、1つの入力に結びつく相手が何人いても構いません。
次の3つを満たす関係を同値関係と呼びます。自分自身と結びつく(反射)。a が b と結びつけば、b も a と結びつく(対称)。a が b と、b が c と結びつけば、a は c と結びつく(推移)。
例: 3 で割った余りが同じ
| 数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 3 で割った余り | 0 | 1 | 2 | 0 | 1 | 2 | 0 |
| グループ | A | B | C | A | B | C | A |
学生が入力するセルは、このプレビューでは空白です。
0 から 9 を3で割った余り
python3 -c "print([n % 3 for n in range(10)])"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
さらに挑戦
5人の学生を4つの部屋に入れます。どう入れても、2人以上入る部屋が必ずできます。入力が終域より多い写像は、単射になれないということです。
学籍番号の下2桁は100通りです。101人の学生がいると、下2桁が同じ人が必ずいます。その理由を、言葉で説明しましょう。