7.8 写像の演習問題
from 論理と集合から始める数学の基礎 読書会
注：f^\leftarrow[A]:=\{x\in U|f(x)\subseteq A\}
ただし、Uはfの定義域とした
7.1 U=\{1,2,3,4,5\},f:U\to U;1\mapsto3,2\mapsto5,3\mapsto5,4\mapsto2,5\mapsto3のとき
(1) fの値域は
f[U]=\{y\in U|\exist x\in U.y=f(x)\}
= \{2,3,5\}
(2) 像を求める
f[\{2,3,5\}]=\sout{\{5\}}\{3,5\}
そんな聞き方してる？
\{2,3,5\}の像って言ってない？
しまったミスった
f(2)=f(3)=5だけど、f(5)=3でした
(3) 逆像を求める
f^\leftarrow[\{3\}]=\{x\in U|f(x)\subseteq\{3\}\}
= \{1,5\}
7.2 f:U\to V,g:U\to Uのとき、以下を論理式で書き下す
(1) fは全射でない
\lnot(\forall y\in V\exist x\in U.y=f(x))
\iff\exist y\in V\forall x\in U.y\neq f(x)
(2)gは恒等写像ではない
\lnot(\forall x\in U.x=g(x)
\iff\exist x\in U.x\neq g(x)
7.3 f:\N\ni x\mapsto\frac12(x+3\llbracket x\%2=1\rrbracket)\in\N(\llbracket\bullet\rrbracketはIverson Bracket)が全射だが単射で無いことを示す
全射性：
\top
\iff\forall y\in\N.2y\in\N
\iff\forall y\in\N\exist x\in\N.2y=x
\iff\forall y\in\N\exist x\in\N.y=\frac12x
\implies\forall y\in\N\exist x\in\N.y=f(x)
単射でない：
f(3)=\frac12(3+3)=3=\frac12\cdot 6=f(6)だから単射でない
7.4 f:\Z\ni x\mapsto 2x\llbracket x>0\rrbracket+(-2x+1)\llbracket x\le0\rrbracket\in\Nが全単射であることを示せ
全射性：
\top
\iff\forall y\in\N.\frac12y\in\N
\iff\forall y\in\N\exist x\in\N.y=2x
\implies\forall y\in\N\exist x\in\N.y=f(x)
\implies\forall y\in\N\exist x\in\Z.y=f(x)
単射性：
\forall x,x'\in\Z.
f(x)=f(x')
\iff2x\llbracket x>0\rrbracket+(-2x+1)\llbracket x\le0\rrbracket=2x'\llbracket x'>0\rrbracket+(-2x'+1)\llbracket x'\le0\rrbracket
\iff\begin{dcases}2x=2x'&\text{if }x>0\land x'>0\\2x=-2x'+1&\text{if }x>0\land x'\le0\\-2x+1=2x'&\text{if }x\le0\land x'>0\\-2x+1=-2x'+1&\text{if }x\le0\land x'\le0\end{dcases}
\iff\begin{dcases}2x=-2x'+1&\text{if }x>0\land x'\le0\\-2x+1=2x'&\text{if }x\le0\land x'>0\\x=x'&\text{otherwise}\end{dcases}
\iff\begin{dcases}x+x'=\frac12\notin\Z&\text{if }x>0\land x'\le0\\x+x'=\frac12\notin\Z&\text{if }x\le0\land x'>0\\x=x'&\text{otherwise}\end{dcases}
\implies\begin{dcases}\bot&\text{if }x>0\land x'\le0\\\bot&\text{if }x\le0\land x'>0\\x=x'&\text{otherwise}\end{dcases}
\implies x=x'
\therefore\forall x,x'\in\Z.f(x)=f(x')\implies x=x'
7.6 f:U\to V,A\subseteq U,B\subseteq Vのとき、以下を示せ
これなにげに証明したことなかったので示したい
(1) A\subseteq f^\leftarrow[f[A]]
A\subseteq f^\leftarrow[f[A]]
\iff \forall x\in A.x\in f^\leftarrow[f[A]]
\iff \forall x\in A.f(x)\in f[A]
\iff \forall x\in A\exist x'\in A.f(x)=f(x')
\underline{\iff\top\quad}_\blacksquare
矢印で考えるとよくわかる
TODO:図を書く
(2) (\forall x,x'\in U.f(x)=f(x')\implies x=x')\implies A= f^\leftarrow[f[A]]
f^\leftarrow[f[A]]\subseteq A
\iff\forall x\in f^\leftarrow[f[A]].x\in A
\iff (\forall x\in U.f(x)\in f[A]\implies x\in A)
\iff (\forall x\in U.(\exist x'\in A.f(x)=f(x'))\implies x\in A)
なるほど。単射の性質から逆算できそうだ
証明
\forall x\in U.
\exist x'\in A.f(x)=f(x')
\implies \exist x'\in A.x=x'
\because\forall x,x'\in U.f(x)=f(x')\implies x=x'
\implies x\in A
\iff(\forall x\in U.(\exist x'\in A.f(x)=f(x'))\implies x\in A
\iff f^\leftarrow[f[A]]\subseteq A
\iff A= f^\leftarrow[f[A]]
\because(1)
(3) f[f^\leftarrow[B]]\subseteq B
f[f^\leftarrow[B]]\subseteq B
\iff\forall y\in f[f^\leftarrow[B]].y\in B
\iff(\forall y\in V.(\exist x\in f^\leftarrow[B].y=f(x))\implies y\in B)
\iff(\forall y\in V.(\exist x\in U.y=f(x)\in B)\implies y\in B)
\iff(\forall y\in V.(\exist x\in U.y=f(x))\land y\in B\implies y\in B)
\iff\top
(4) (\forall y\in V\exist x\in U.y=f(x))\implies f[f^\leftarrow[B]]= B
\forall y\in V\exist x\in U.y=f(x)
\implies \forall y\in B\exist x\in U.y=f(x)
\iff \forall y\in B\exist x\in U.f(x)\in B\land y=f(x)
\iff \forall y\in B\exist x\in f^\leftarrow[B].y=f(x)
\iff B\subseteq f[f^\leftarrow[B]]
7.7 f:U\to V,g:V\to Wのとき、以下を示せ
(1) f,gが単射\implies g\circ fは単射
\forall x,x'\in U.
g(f(x))=g(f(x'))
\implies f(x)=f(x')
\because gは単射
\implies x=x'
\because fは単射
\therefore g\circ fは単射
(2) f,gが全射\implies g\circ fは全射
f,gが全射
\iff\begin{dcases}\forall y\in V\exist x\in U.y=f(x)\\\forall y\in W\exist x\in V.y=g(x)\end{dcases}
\implies\forall y\in W\exist y'\in V\exist x\in U.\begin{dcases}y'=f(x)\\y=g(y')\end{dcases}
\iff\forall y\in W\exist x\in U.y=g(f(x))
\iff g\circ fは全射
(3)g\circ fは単射\implies fは単射
g\circ fは単射
\iff\forall x,x'\in U.(g(f(x))=g(f(x'))\implies x=x')
\implies\forall x,x'\in U.
f(x)=f(x')
\implies g(f(x))=g(f(x'))
\implies x=x'
\implies fは単射
(3)については、(3')「g\circ fは単射\implies \left.g\right|_{f[U]}は単射」が成り立つ
(4)g\circ fは全射\implies gは全射
g\circ fは全射
\iff\forall y\in W\exist x\in U.y=g(f(x))
\iff\forall y\in W\exist x\in V\exist x'\in U.y=g(x)\land x=f(x')
\implies\forall y\in W\exist x\in V.y=g(x)
\iff gは全射
図解するとよくわかるので図解したい
図解すると、「g\circ fは単射\implies \left.g\right|_{f[U]}は単射」という予想が立つ
論理式で書き下すと\forall x,x'\in U.(g(f(x))=g(f(x'))\implies x=x')\implies\forall x,x'\in f[U].(g(x)=g(x')\implies x=x')になる
論理式で書き出してみると、図解とはまた別の視点で当たり前な式に見える
これを(3')としておく
証明
\forall x,x'\in U.(g(f(x))=g(f(x'))\implies x=x')
\implies\forall y,y'\in V.
\exist x,x'\in U.y=f(x)\land y'=f(x')\land g(y)=g(y')
\implies\exist x,x'\in U.y=f(x)\land y'=f(x')\land g(f(x))=g(f(x'))
\implies\exist x,x'\in U.y=f(x)\land y'=f(x')\land x=x'
\implies\exist x,x'\in U.y=f(x)=f(x')=y'
\implies y=y'
\implies\forall y,y'\in V.(y,y'\in f[U]\land g(x)=g(x')\implies x=x')
\iff\forall x,x'\in f[U].(g(x)=g(x')\implies x=x')
(4)については、(4')「g\circ fは全射\implies \left.g\right|_{f[U]}は全射」が成り立つ
(5)g\circ fは単射\land fは全射\implies gは単射
g\circ fは単射\land fは全射
\implies \left.g\right|_{f[U]}は単射\land f[U] =V
\because(3')
\implies \left.g\right|_Vは単射
\iff gは単射
(6)g\circ fは全射\land gは単射\implies fは全射
2024-03-08 19:28:27 2024-03-05に脳内で図解しようとしたら、よくわからなくなって眠ってしまった
イメージを言葉で表すと
gが全単射なので、Uから矢印が出ていないVの要素があると全射でなくなり矛盾するということ
うーん、やっぱ図で書いたほうがわかりやすいな……
論理式に変換
\begin{dcases}\forall w\in W\exist u\in U.w=g(f(u))\\\forall v,v'\in V.g(v)=g(v')\implies v=v'\end{dcases}\implies\forall v\in V\exist u\in U.v=f(u)
いろいろ代入したらいけそう
証明
\begin{dcases}\forall w\in W\exist u\in U.w=g(f(u))\\\forall v,v'\in V.g(v)=g(v')\implies v=v'\end{dcases}
\iff\forall v\in V\forall w\in W\exist u\in U\begin{dcases}w=g(f(u))\\\forall v'\in V.g(v)=g(v')\implies v=v'\end{dcases}
\implies\forall v\in V\forall w\in W\exist u\in U\begin{dcases}w=g(f(u))\\g(v)=w\implies v=f(u)\end{dcases}
\implies\forall v\in V\forall w\in W\exist u\in U.(g(v)=w\implies v=f(u))
\implies\forall v\in V\forall w\in W\exist u\in U.v=f(u)
\iff\forall v\in V\exist u\in U.v=f(u)
うーん、ごちゃごちゃしてる
\exist x\in U.(g(v)=w\implies v=f(u))からg(v)=w\impliesを削っているところが冗長
ゆる募: もっとスッキリした証明
もっときれいな証明思いついた！
\begin{dcases}\forall w\in W\exist u\in U.w=g(f(u))\\\forall v,v'\in V.g(v)=g(v')\implies v=v'\end{dcases}
\implies\begin{dcases}\forall v\in V\exist u\in U.g(v)=g(f(u))\\\forall v,v'\in V.g(v)=g(v')\implies v=v'\end{dcases}
vを導入したあと、wにg(v)を代入した
\iff\forall v\in V\exist u\in U\begin{dcases}g(v)=g(f(u))\\\forall v',v''\in V.g(v')=g(v'')\implies v'=v''\end{dcases}
量化子の位置移動 & 束縛変数のリネーム
\implies\forall v\in V\exist u\in U\begin{dcases}g(v)=g(f(u))\\g(v)=g(f(u))\implies v=f(u)\end{dcases}
v'にvを、v''にf(u)を代入した
\implies\forall v\in V\exist u\in U.v=f(u)
>f:U\to V,g:V\to Wのとき、以下を示せ
>g\circ fは全射\land gは単射\implies fは全射
対偶を示す: fは全射でない \implies (g\circ fは全射\land gは単射)でない
もしf が全射でないならある要素a があって a\notin f[U]
gは単射であるときb := g(a)についてb := g(x)となるx\in V はaだけ
a \notin f[U]なのでg(f(x)) = bとなるx \in Uは存在しない、よってg\circ fは全射でない Q.E.D.
修正✅
>a \notin V
ここ「ある要素aがあってa\notin f[U]」かな？
「ある要素aがあってa \notin V」だと\exist a.a\notin Vだから、任意の場合で成立してしまう
そうだ
7.8 \exist U\neq\varnothing\exist V\neq\varnothing\exist f:U\to V\exist g:V\to U.g\circ f={\rm id}_U\land f\circ g\neq{\rm id}_Vが正しいかどうか調べよ
{\rm id}_\bulletは全単射だから、7.7よりgが単射でfが全射となる
つまり、7.8は正しくて、その具体例は全射でない単射gと単射でない全射fの組み合わせで表せる
具体例を1個示せば証明したことになる
証明
f:\{1\}\ni n\mapsto n\in\{1,2\}
g:\{1,2\}\ni n\mapsto 1\in\{1\}
とすると、以下が成り立つ
g\circ f={\rm id}_{\{1\}}
\because\forall n\in\{1\}.g(f(n))=g(n)=1=n
f\circ g\neq{\rm id}_{\{1,2\}}
\because f(g(2))=f(1)=1\neq2
\therefore\exist U\neq\varnothing\exist V\neq\varnothing\exist f:U\to V\exist g:V\to U.g\circ f={\rm id}_U\land f\circ g\neq{\rm id}_V
巻末の答え見たら、まったく同じ構成方法だった
まあ一番単純なのはこれくらいしかないよね
対合律を満たす写像のこと
(1) S=\{1,2,3,4,5,6\},g:S\to S;1\mapsto1,2\mapsto4,6\mapsto3でgが対合変換のとき、g(3),g(4),g(5)を求めよ
2=g^2(2)=g(4)
6=g^2(6)=g(3)
これで5以外は写す先が決まったので、自動的に5=g(5)だとわかる
(2)\forall U\forall f: U\to Uにてfが対合変換ならfが全単射であることを示せ
\forall U\forall f:U\to U.
\forall u,u'\in U.
f(u)=f(u')
\implies f(f(u))=f(f(u'))
\implies u=u'
\because対合変換
\therefore fは単射
\forall U\forall f:U\to U.
\top
\implies\forall u\in U. u=f(f(u))
\because対合変換
\implies\forall u\in U\exist u'\in U.u=f(u')
\because f(u)\in U
\implies fは全射
以上より、fは全単射である
(3)\forall U\forall f: U\to Uにてfが対合変換ならf=f^{-1}であることを示せ
fは全単射
\implies f\circ f^{-1}={\rm id}_U
\implies f\circ f\circ f^{-1}=f\circ{\rm id}_U=f
\iff{\rm id}_U\circ f^{-1}=f
\because fは対合変換
\underline{\iff f^{-1}=f\quad}_\blacksquare