ベルンシュタインの定理とfunctional graph
初めに
ベルンシュタインの定理($|A|\leq |B|$かつ$|B|\leq |A|$ならば$|A|=|B|$)は, ステートメントが素直な割に, 証明で集合をガチャガチャしていて気持ちがわかりづらく見えやすいと思います.
昔, もう少しいい証明はないかとこねくり回していたときに, functional graphを用いることである程度再現性を持った(そらで書きやすい)証明が書けることに気づいたので, 備忘録として残しておきます. (本質的にしている証明は同じです;
英語版wikipedia
に乗っているものと近いと思います. まあみんな暗黙知として知っているような内容な気もしますが...)
functional graph
$X$を集合, $f:X\to X$を関数とする. $f$のfunctional graphとは, 次のように定まる有向グラフを指す:
頂点集合: $X$
辺集合: $x\in X$に対して, $x$から$f(x)$に辺を張る.
functional graph の弱連結成分として, どのようなグラフが現れるかを調べる. 今回の目的では$f$が単射なときのみに調べれば十分.
$f:X\to X$が単射とし, $C$を$f$のfunctional graphの弱連結成分とする. このとき, $C$は以下のいずれかと同型:
(1) 頂点数$n$のcycleグラフ($n\geq 1$)
(2) 両方向に無限に伸びるpathグラフ(i.e, 台集合を$\Z$とし, $i$から$i+1$に辺を張ったグラフと同型なもの)
(3) 始点から片方向に無限に伸びるpathグラフ(i.e, 台集合を$\N$とし, $i$から$i+1$に辺を張ったグラフと同型なもの)
特に, $|C\setminus f(C)|\leq 1$が成立する.
$X$の弱連結成分$C$を任意にとる. 辺の張り方から, $f(C)\subset C$および$f^{-1}(C)\subset C$が成り立つことに注意せよ.
- $f(C)\neq C$のとき
このとき, $x\in C\setminus f(C)$を一つとり, 固定する. $C$の連結性より, $x\not\in \mathrm{Im}(f)$に注意せよ.
もし, $f^i(x)=f^j(x) (i< j)$となったら, $f$の単射性より$x=f^{j-i}(x)\in \mathrm{Im}(f)$となり, 矛盾. ゆえに, $f^i(x) (i\in \Z_{\geq 0})$は相異なる.
$D=\{f^i(x)|i\in\Z_{\geq 0}\}$と置く. $f$の単射性と$x\not\in \mathrm{Im}(f)$より $f(D)\subset D, f^{-1}(D)\subset D$がわかるので, $D$は弱連結成分となり, $D=C$. よって, $C$は$\N$とgraphとして同型になる. - $C=f(C)$のとき
(この部分はベルンシュタインの定理の証明で使わないので読みとばしてもよい. )
このとき, $f$の単射性より, $f|_C$は全単射になる. この逆写像を単に$f^{-1}$と書く. (以下では$C$の元しか出てこないので混乱は起こらない.)
$D=\{f^i(x)|i\in\Z\}$とすると, $f(D)=f^{-1}(D)=D$. よって, $D$は弱連結成分となり, $D=C$.
もし, $f^n(x)\neq x(\forall n\in \Z_{>0})$なら, $i\neq j\implies f^i(x)\neq f^j(x)$となるので, $C$は$\Z$と同型なgraphになる.
もし, $f^n(x)=x$となる$n\in \Z_{>0}$があるなら, その中で最小のものを$n_0$とすると, $f^i(x)=f^j(x)\iff x = f^{j-i}(x)\iff n_0 \mid j-i$がわかる[1]. よって, $C=D=\{x,f(x),\cdots,f^{n_0-1}(x)\}$となり, これらの元は相異なるので, $C$は大きさ$n$のcycleとなる.
ベルンシュタインの定理の証明
$X,Y$を集合とし, $f:X\to Y$, $g:Y\to X$を共に単射とする. このとき, $X$と$Y$の間に全単射が存在する.
まず, 簡単な帰着を行う. $f$によって, $Y$を$X$の部分集合と思うことにより, 次の命題を示せば十分: (より詳細には以下の証明を参照)
$h:X\to X$を単射とし, $W$を$h(X)\subset W\subset X$を満たす集合とする. このとき, $X$と$W$の間に全単射が存在する.
$X,Y,f,g$を定理2のようにとる. $h:= g\circ f: X\to X$と置く. このとき, $f,g$の単射性より, $h$は単射であり, また$h(X)=g(f(X))\subset g(Y) \subset X$. よって, 命題3より, $X$と$g(Y)$の間に全単射$\phi:g(Y)\to X$が存在する. すると, $\phi\circ g:Y\to X$が欲しい全単射となる.
$h$のfunctional graphを$G$と置く. $G$の弱連結成分ごとに考えればよいので, 結局$G$は弱連結であるとしてよい. このとき, 命題1より, $|X\setminus h(X)|\leq 1$であり, 仮定より$h(X)\subset W\subset X$. よって, $W=h(X)$か$W=X$の少なくとも一方が成立する. $W=X$なら$\mathrm{id}$が求める全単射であり, $W=h(X)$なら$h$が求める全単射となる.
上の書き方だと少しラフなので, 一応作っている全単射を具体的に書きます:
$x\in X$に対して$x$を含む弱連結成分を$C_x$と表す. このとき, $\phi:X\to W$を,
$\phi(x)= \begin{cases}
x && C_x \subset W \\
h(x) && otherwise
\end{cases}
$
と定めると, これは求める全単射.
この証明を展開する(補題を使わずにまとめて書く)と, 結局よくみる$X_n,Y_n$を帰納的に定めて頑張る証明になるわけです.
