集合論の単射と全射に関する練習問題
話題になっていた集合論の単射と全射の練習問題
先日、$\mathbb{X}$で集合論の初歩の問題が話題になっていた。
→
https://x.com/HirokazuOHSAWA/status/1939898520879997306
集合論の初歩で登場する写像の単射と全射という概念の定義が分かればできる練習問題。
定義は後述。
この問題見て、面白いと思って、かつ「単射」と「全射」とが「ある種の双対的な概念」だと分かる問題だと思ったので、頭の体操に自分も解いてみていくつか
ツイートした
。ツイートだと流れてしまうので、改めてツイートしてない内容も含めてMathLogに残そうと思う。
問題をこちらにも書くと、
$X,Y:$集合、$f:X \rightarrow Y$ 写像とする。
"任意の集合$Z$と任意の写像$g,h:Z \rightarrow X;f \circ g=f\circ h \Rightarrow g=h$"$\Longleftrightarrow$"$f$は単射"
を証明せよ
$X,Y:$集合、$f:X \rightarrow Y$ 写像とする。
"任意の集合$Z$と任意の写像$g,h:Y \rightarrow Z;g \circ f=h\circ f \Rightarrow g=h$"$\Longleftrightarrow$"$f$は全射"
を証明せよ
定義の確認
$X,Y:$集合、$f:X \rightarrow Y$ 写像とする。
$f:X \rightarrow Y$が単射であるとは、
$\forall x,x'\in X;(f(x)=f(x')\Longrightarrow x=x')$
となることである。
[Link]「 単射 - Wikipedia 」
$f:X \rightarrow Y$が全射であるとは、
$\forall y \in Y,\exists x\in X;f(x)=y $
となることである。
[Link]「
全射 - Wikipedia
」
「単射」と「全射」の定義は似ていない。しかし、今回の問題の命題でわかるようにある種の互いに双対的な概念である。
にもかかわらず定義からはそう感じないのも不思議だと思う。それを
以前呟いた。
$f:X \rightarrow Y$が全単射であるとは、
$f$が単射でかつ全射であることである。
例えば、$ X$を日本の県全体の集合$Y$を日本の県庁所在地全体の集合、$f$を県庁所在地を指定する写像とする（ただし、県のところは都道府の場合も県庁所在地ということにする。東京都の都庁所在地は東京都区部とする）と、
都道府県庁所在地-Wikipedia
でわかるように、県を指定すると、県庁所在地が定まり$f$は写像で、
異なる県の県庁所在地は異なるので、$f$は単射。
どの県庁所在地を指定しても、都道府県が定まるので、$f$は全射。
$f$は全単射である。
$Y$を都市全体の集合とした場合には、県庁所在地でない都市も含まれるので、$f$が全射ではなくなる。$Y$を日本の島全体として、$f$を県庁がある島を指定する写像とすると、東京都と埼玉県は同じ本州（普通本州を島とは認識しないが）という島にあるので、$f$は単射ではない。もちろんこの場合全射でもない。
集合$ X,Y,Z$と写像$f:X \rightarrow Y,g:Y \rightarrow Z$があるとき、
写像$h:X \rightarrow Z$を$x \in X;h(x):=g(f(x))\in Z$で定義して$g$と$f$の合成写像という。
$h$を$g \circ f$で表す。
自分なりに考えてみた証明
問題1の($\Longleftarrow$)
$X,Y:$集合、$f:X \rightarrow Y$ 写像とする。
"任意の集合$Z$と任意の写像$g,h:Z \rightarrow X;f \circ g=f\circ h \Rightarrow g=h$"$\Longleftarrow$"$f$は単射"
$f \circ g=f\circ h$とする。
$\forall z\in Z;f(g(z))=f \circ g(z)=f\circ h(z)=f(h(z))$
なので、$f$が単射であることにより、$g(z)=h(z)$
$\forall z\in Z;g(z)=h(z) $なので、$g=h$∎
問題1の($\Longrightarrow$)
$X,Y:$集合、$f:X \rightarrow Y$ 写像とする。
"任意の集合$Z$と任意の写像$g,h:Z \rightarrow X;f \circ g=f\circ h \Rightarrow g=h$"$\Longrightarrow$"$f$は単射"
$f(x)=f(x')$を仮定する
$Z \neq \varnothing $とする
$\forall z \in Z$に対して、
$g_x(z):=x$（定値写像）
$h_{x'}(z):=x'$（定値写像）
$f \circ g_x(z)=f(g_x(z))=f(x)=f(x')=f(h_{x'}(z))=f \circ h_{x'}(z)$
つまり、$f \circ g_x=f \circ h_{x'} $なので、$g_x=h_{x'}$
$x=g_x(z)=h_{x'}(z)=x'$
$f(x)=f(x') \Longrightarrow x=x' $を示せたので、$f$は単射∎
問題2の($\Longleftarrow$)
$X,Y:$集合、$f:X \rightarrow Y$ 写像とする。
"任意の集合$Z$と任意の写像$g,h:Y \rightarrow Z;g \circ f=h\circ f \Rightarrow g=h$"$\Longleftarrow$"$f$は全射"
$g \circ f=h\circ f$とする
$f$が全射なので、$\forall y\in Y; \exists x \in X;f(x)=y$
この$x$を使って、
$\forall y\in Y;g(y)=g(f(x))=g \circ f(x)=h\circ f(x)=h(f(x))=h(y)$
つまり、$g=h$∎
問題2の($\Longrightarrow$)
$X,Y:$集合、$f:X \rightarrow Y$ 写像とする。
"任意の集合$Z$と任意の写像$g,h:Y \rightarrow Z;g \circ f=h\circ f \Rightarrow g=h$"$\Longrightarrow$"$f$は全射"
$y∊Y$とする
$Z:=\{0,1\}$
$y’∊Y$に対して
$g(y’):=0$ （定値写像）
$h_y(y'):=\begin{eqnarray}
\left\{
\begin{array}{l}
0 \hspace{ 10pt } (y≠y')\\
1 \hspace{ 10pt } (y=y')
\end{array}
\right.
\end{eqnarray}$
と定義する。
$g≠h_y$なので$g\circ f≠h_y\circ f$
$∃x∊X;g\circ f(x)≠h_y\circ f(x)$
$g\circ f(x)=g(f(x))=0$より、$h_y\circ f(x)=h_y(f(x))=1$
$h_y$の定義より、$f(x)=y$
$y$の任意性より$f$が全射∎
特殊な場合、マグマ（代数系）の言葉では
写像が同じ集合の中にある特殊な場合では、単なる言葉の言い換えにすぎないが、代数系（集合と演算の組）の言葉で簡潔に表すことができる。
集合に演算結果がまたその要素になる二項演算を入れた代数系をマグマという。
$M$をマグマ、$*$をその演算とする。
$f\in M;\forall g,h \in M; f*g=f*h \Longrightarrow g=h$
のとき$f$は左簡約可能という。
$M$をマグマ、$*$をその演算とする。
$f\in M;\forall g,h \in M; g*f=h*f \Longrightarrow g=h$
のとき$f$は右簡約可能という。
$M$をマグマ、$*$をその演算とする。
$f\in M$が左簡約可能でかつ右簡約可能のとき、
$f$は(両側)簡約可能という
詳しくは
[Link]「
簡約律 - Wikipedia
」 参照
ある一つの集合$X$の自己写像$X \rightarrow X$からなる集合を、合成を演算として、マグマとして考えると、以下のように表せる。
"$f$が左簡約可能"$\Longleftrightarrow$"$f$は単射"
"$f$が右簡約可能"$\Longleftrightarrow$"$f$は全射"
任意の写像の集合では、$f$の値域が$g$の定義域と一致しなければ合成$g\circ f$を定義できないため、マグマにはならない。
元の問題の命題は、集合の写像全体でも成り立つが、このマグマの言葉による言いかえはできない。
余談
今回の問題とは別の話だが、単射と全射に関して、有限集合では、面白い命題が成り立つ。
無限集合では成り立たないので、有限集合ならではの性質ともいえる。
$X,Y$:有限集合で要素数が同じとき、写像$f:X \rightarrow Y$について、
"$f$が単射"$\Longleftrightarrow$"$f$が全射"
$X,Y$の要素数を$n$とする。
$Y$の部分集合$\{y\in Y|\exists x\in X,f(x)=y\}$を$f(X)$で表す。
$f$は単射
$\Longleftrightarrow$$f(X) (\subseteq Y) $の要素数が$n$$ \quad $(
鳩の巣原理 - Wikipedia
より)
$\Longleftrightarrow$$f(X)=Y$
$\Longleftrightarrow$$f$は全射
∎
終わりに
集合論の初歩的な問題だがとても楽しめた。
考えてみた感想として、元の問題の4つの命題のうち、問題2の($\Longrightarrow$)「$g \circ f=h\circ f \Rightarrow g=h$」⇒「全射であること」を示すのが最も難しいと感じた。どうしても証明のどこかで、「対偶」か「背理法」を使用しなければならない（と思う）。
双対的（対称的）に感じる命題なのに、難易度に差異があるのが不思議に感じた。
そもそも命題「P$\Rightarrow$Q」とその対偶「$\lnot$Q$\Rightarrow$$\lnot$P」は真偽は一致するのに、何故、証明において対偶（もしくは背理法）を使用しないと煩雑、困難や不可能に感じるものがあるのだろう。一体、この命題論理では説明できない差異はどこからやってくるのだろう。
考えだすと、気になって夜しか眠れない()
