2

全単射と日常生活での利用法

448
1
$$$$

目次
1.全射、単射、全単射の定義
2.例題
3.日常での利用

全射、単射、全単射の定義

全射

$$写像 f:X → Y $$が全射であるとは、以下の条件が成り立つときにいう
$$ \exists x \in X s.t. \forall y \in Y, y=f(x) $$

これは、「遷移先の集合のすべての要素には、写像によって遷移する前の要素が必ず存在する」
という意味です。

単射

$$写像 f:X → Y $$が単射であるとは、以下の条件が成り立つときにいう
$$ \forall x,x' \in X, f(x)=f(x') ⇒ x=x' $$

これは、「遷移先の要素が同じならば遷移する前の要素も同じ」
という意味です。

全単射

$$写像 f:X → Y$$
$$が全単射であるとは、写像fが全射かつ単射であるときをいう$$

例題

  1. $$f:\mathbb{N}×\mathbb{N}→\mathbb{N}$$
    $$  (a,b)\mapsto a+b$$
    $$例えば、1 \in \mathbb{N}, \nexists a,b \in \mathbb{N} s.t. f((a,b))=a+b=1 $$
    $$よって、fは全射でない$$
    $$また、例えば$$
    $$5=1+4,5=3+2 だから$$
    $$5 \in \mathbb{N}, 1,2,3,4 \in \mathbb{N}, (1,4) ≠ (2,3), f((1,4))=f((2,3))=5 $$
    $$よって、fは単射でない$$

  2. $$g:\mathbb{N}×\mathbb{N}→\mathbb{Z}$$
    $$  (a,b)\mapsto a-b$$
    $$a-b=c \in \mathbb{Z} とする$$
    $$b=1とするとa-1 \geq 0$$
    $$よって$$
    $$c \geq 0⇒\exists (a,b)\in \mathbb{N}×\mathbb{N}, c=a-b=g((a,b))・・・①$$
    $$ $$
    $$a=1とすると1-b \leq 0$$
    $$よって$$
    $$c \leq 0⇒\exists (a,b)\in \mathbb{N}×\mathbb{N}, c=a-b=g((a,b))・・・②$$
    $$①,②から、gは全射$$
    $$また、fと同様、gは単射でない$$

  3. $$φ:\mathbb{N}→\mathbb{Z}$$
    $$   a\mapsto a$$
    $$例えば、0 \in \mathbb{Z}, \nexists a \in \mathbb{N} s.t. a=φ(a) $$
    $$よって、φは全射でない$$
    $$また$$
    $$\forall a,a' \in \mathbb{Z}, a≠a' において$$
    $$φ(a)=a, φ(a')=a' より、 φ(a)≠φ(a') が成り立つ(定義2の対偶)$$
    $$よって、φは単射$$

  4. $$ψ:\mathbb{N}→\mathbb{Z}$$
    $$  a \mapsto (-1)^{a}・\frac {a+ \frac{(-1)^{a}-1}{2}}{2}$$
    $$数式の意味$$
    $$aが偶数⇒ψ(a)=\frac{a}{2}$$
    $$aが奇数⇒ψ(a)=-\frac{a-1}{2}$$
    $$1→0$$
    $$2→1$$
    $$3→-1$$
    $$4→2$$
    $$5→-2$$
    $$・$$
    $$・$$
    $$・$$
    $$感覚的に全単射ということがわかるが、数式でも証明する$$
    $$\forall c \in \mathbb{Z}$$
    $$ \begin{eqnarray} \left\{ \begin{array}{l} c \gt 0 ⇒ 2c    \in \mathbb{N} \\ c \le 0 ⇒ -2c+1 \in \mathbb{N} \end{array} \right. \end{eqnarray} $$
    とおくと
    $$ \exists a \in \mathbb{N} s.t. \forall c \in \mathbb{Z}, c=ψ(a) $$
    $$よって、ψは全射$$
    $$\forall a,a' \in \mathbb{N}$$
    $$a≠a'⇒ (-1)^{a}・\frac {a+ \frac{(-1)^{a}-1}{2}}{2} ≠ (-1)^{a'}・\frac {a'+ \frac{(-1)^{a'}-1}{2}}{2}$$
    $$よって、ψは単射$$
    $$ψは全射かつ単射なので全単射$$

日常での利用

1. トランプの代用案

区別のつく52枚のカードがあれば、4種類、13枚ずつに分けると、トランプとして代用できる。

$$f:\lbrace 0,1,2,3,・・・,51 \rbrace → \lbrace 0,1,2,・・・,12 \rbrace ×\lbrace 0,1,2,3 \rbrace$$
$$       a      \mapsto    (a \mod{13} , \lbrack \frac{a}{13} \rbrack)$$
とすると$f$は全単射

2. アルゴの代用案

Amazon アルゴ ベーシック
$$このカードは黒いカードに書かれた0~11の数字と、白いカードに書かれた0~11までの数字を並び替え、相手の手札の順番を当てた方の勝ちです。$$
$$同じ数字で比べる場合、黒 \lt 白となります。$$

アルゴは、1色24枚でも遊べる。

$$f:\lbrace 0,1 \rbrace × \lbrace 0,1,2,・・・,11 \rbrace→ \lbrace 0,1,2,・・・,23 \rbrace$$
$$       (a,b)      \mapsto  2b+a$$
$$(黒⇒a=0,白⇒a=1)$$
$$とするとfは全単射$$

$$対応表(B:黒、W:白)$$
$$B0:0   B6:12$$
$$W0:1   W6:13$$
$$B1:2   B7:14$$
$$W1:3   W7:15$$
$$B2:4   B8:16$$
$$W2:5   W8:17$$
$$B3:6   B9:18$$
$$W3:7   W9:19$$
$$B4:8   B10:20$$
$$W4:9   W10:21$$
$$B5:10  B11:22$$
$$W5:11  W11:23$$

3. ストップウォッチでランダム化計画

$$ストップウォッチをスタートさせ、ストップしたときの1/10の位と1/100の位をそれぞれ10の位、1の位とする。$$
$$例えば$$
$$7.59⇒59$$
$$8.63⇒63$$
$$例外として、00となった場合は100とする。$$
$$\frac{1}{n}(1≦n≦100)を再現したい場合$$
$$ \begin{eqnarray} \left\{ \begin{array}{l} 1~n   ⇒ 出た数を使用する \\ n+1~100 ⇒ やり直し \end{array} \right. \end{eqnarray} $$
$$とすると\frac{1}{n}が再現できる。$$

$$f:\lbrace 0,1,2,・・・,9 \rbrace × \lbrace 0,1,2,・・・,9 \rbrace→ \lbrace 1,2,・・・,100 \rbrace$$
$$         (a,b)         \mapsto   \begin{eqnarray} \left\{ \begin{array}{l} 10a+b (a≠0 or b≠0) \\ 100   (a=b=0) \end{array} \right. \end{eqnarray} $$
$$とするとfは全単射$$

手元にコインがない時、手元にサイコロがない時、出席番号順を日付で当てると32番以降の人が有利になる時・・・。
そんな時は、スマホのストップウォッチアプリを起動し、スタートボタンをプッシュ!!

$$※スタートした後にすぐストップするとイカサマができるので、スタート直後の何秒かは放置するとよい$$

4.間違えない語呂合わせ

語呂合わせとは、例えば
野菜⇒831
鳴くよ⇒794
893⇒ヤクザ、薬味
810⇒野獣、野党
と、読み方を数字に置き換えたり、数字を日本語の読み方に変えたりすることを言います。
ここでは、数字を一度日本語に変換し、正確に数字に復元する操作を考えます。
例えば、$ \sqrt{2} $
$$1.41421356→一夜一夜に人見ごろ$$
と覚えた後
$$一夜一夜に人見ごろ→1.41421356$$
と正確に復元する方法を考えます。

別の記事参照
間違えない語呂合わせ

5.自分で書いた字が読めない!どうすれば?

文字の区別をしなければ、解読は不可能です。
例えば、$I,l,1$をすべて縦棒にすると区別がつかないです。(文脈からとらえることが可能かもしれないですが、労力が必要です)
自分で書くときは、自分なりの判別方法を施すとよいでしょう。
(僕は以下のように区別しています。
$1$:数学で使う時は縦棒、英語で使う時は左右に空白を入れる
$I$:上下に横棒をつける
$l$:数学で使う時は$\ell$、英語で使う時は縦棒)

$$写像 f:L → R (L:letter 文字、R:read 読み)$$
$$    l \mapsto r$$
$$fが全単射 ⇔ 文字と読みで1対1対応(もし、違う文字で同じ読みをするものがあれば、単射でなくなる)$$

6.ニックネームの区別

本人とニックネーム、呼び方を区別する方法です。
同じ名前で呼ばれて混乱することが無くなります。
例えば、僕の場合、堀という人が身近に3人いるので、それぞれ
「堀くん」「堀さん」「堀ちゃん」で分けています。
ちなみに全員男です。
これ以上増えたらどうしよう・・・。

$$写像 f:P → C (P:parson 個人、C:call 呼び方)$$
$$    p \mapsto c$$
$$fが全単射 ⇔ 個人と呼び方で1対1対応$$

7.RPGの地図は球ではなくドーナツ型

全単射を利用した証明です。
RPGの世界は球ではなく………

8.暗号

原文と、暗号文は全単射である必要があります。

$$写像 f:O → E (O:Origin 原文、E:Encoded 暗号文)$$
$$    o \mapsto e$$
$$fが全単射 ⇔ 原文と暗号文で1対1対応$$

別途記載
RSA暗号を作ってみよう

9.誰の歯ブラシ?

5人家族で、歯磨きをするとします。
今のままだと歯ブラシに区別がつかず、別の人の歯ブラシを使う可能性があります。(それでもいいぜ!というご家庭は飛ばしてください。)
こんな時は、歯ブラシに名前を書いたり、歯ブラシを色ごとに分けたりして、誰の歯ブラシか区別をつけるとよいでしょう。

$$写像 f:P → T (P:parson 個人、T:Tooth brush 歯ブラシ)$$
$$    p \mapsto t$$
$$fが全単射 ⇔ 個人と歯ブラシで1対1対応$$

・・・と、日常で使われている全単射を上げるときりがないです。
それほど日常にあふれているということです。
あなたも探してみてください。

2023/1/25追記

申し訳ないのですが、全射の定義についてアライグマ様から指摘がありました。
お詫び申し上げます。

全射

$$写像 f:X → Y $$が全射であるとは、以下の条件が成り立つときにいう
$$ \forall y \in Y, \exists x \in X s.t. y=f(x) $$

ここで間違っていたのは順番なのですが、順番が違うと意味も違ってきます。
$1.\forall y \in Y, \exists x \in X s.t. y=f(x)$ (正)
$2.\exists x \in X s.t. \forall y \in Y, y=f(x)$ (誤)
$1.$は「$y$を一つ決めると、それに対応した$y=f(x)$となる$x \in X$が存在する」ということです。
$2.$は、「どんな$y$にでも対応できる$y=f(x)$となる$x \in X$が存在する」ということです。
$2.$は分かりにくいと思いますが、例えば
$y_1,y_2,y_3 \in Y のとき y_1=f(x)かつy_2=f(x)かつy_3=f(x)となるxが存在する。$
という意味になってしまいます。
$f(x)=y_1=y_2=y_3$のときしか成り立たんやんけ……

投稿日:202141

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

あーく
あーく
104
138089
使える数学、面白い数学の分かりやすい解説を心がけています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中