情報統合思念体への手紙

16号廃墟へ向かう道

写像・全射・単射

集合論

$A,B,C,......：1つの集合$

$a,b,c,......：1つの束縛変項$

$a_1,a_2,...,b_1,b_2,......：1つの自由変項$

とする．

写像

$A⊆X$

$B⊆Y$

記号 $f(A)$ について

$f(A):=\{f(x)|x∈A\}$

$=\{y|f(x)=y∈B\}$

$=\{y|∀y∃x［y∈f(A)→［f(x)=y∈B］］\}⊆Y$

と定める．このとき

$f:X→Y$

$x\mapsto f(x)$

$∀x∈X∃!y∈Y$ 　s.t.　 $f(x)=y$

i.e.　 $∀x∃!y［x∈X→［f(x)=y∈Y］］$

となるような $f$ を $X$ から $Y$ への写像といい， $f(A)$ を写像の像と呼んで

$\mathrm{Im} f:=f(A)$

と書く．

全射

$\mathrm{Im} f=Y$

単射

$∀x=［x_1,x_2］_X$

$x_1≠x_2　→　f(x_1)≠f(x_2)$

例

$A⊆\mathbb{N}$

$B⊆\mathbb{Z}$

$\mathrm{Im} f:=\{y|∀y∃x［y∈\mathrm{Im}f→［f(x)=y∈B］］\}⊆\mathbb{Z}$

$f:\mathbb{N}→\mathbb{Z}$ 　関数

$x\mapsto f(x)$

$f(x)=y$

i.e.　 $∀x∈\mathbb{N}∃!y∈\mathbb{Z}$ 　s.t.　 $f(x)=y$

i.e.　 $∀x∃!y［x∈\mathbb{N}→［f(x)=y∈\mathbb{Z}］］$

$f(x):=x$ 　関数のかたち

$B:=\mathbb{N}$

$∵$ 　 $f(x):=x∈\mathbb{N}$ による　

とする．このような関数は全射・単射かを調べる．

①　 $f$ は全射か？

　まず， $\mathrm{Im} f$ $⊆\mathbb{Z}$ であるから

$\mathbb{Z}⊆\mathrm{Im}f$

を示せば十分である．そのために

$∀y［y∈\mathbb{Z}］\vdash ∀y［y∈\mathbb{Z}→y∈\mathrm{Im}f ］$

を考える．

1　(1)　 $∀y［y∈\mathbb{Z}］$ 　　前提

1　(2)　 $y_1∈\mathbb{Z}$ 　　1. ∀-除去

3　(3)　 $y_1∈\mathrm{Im}f$ 　　仮定

ここで(3)の仮定の妥当性を考える．たとえば負の整数は $\mathrm{Im}f$ に属することができない．これは前提に反する．したがって，この仮定は妥当でないので $f$ は全射ではない．

②　 $f$ は単射か？

　 $a_1≠a_2$ を仮定する．このとき関数のかたちは $f(x):=x$ であり， $f(x)=y$ から $∃y=［b_1,b_2］_{\mathbb{Z}}$ ， $a_1=b_1,a_2=b_2$ と成る $b_1≠b_2$ を選べば

$f(a_1)=a_1=b_1$ 　☆

$f(a_2)=a_2=b_2$

と表示できる．写像の一意性と仮定により $f(a_1)≠f(a_2)$ を得る．したがって $f$ は単射である．

☆の必要性

　この逆 $g: \mathbb{Z}→\mathbb{N}$ ， $g(x):=x$ で単射が成立しないため．