Yanofsky流Lawvereの不動点定理とCantorの定理

最近Lawvereの不動点定理が腑に落ちたので備忘メモを記す。

Theorem(Lawvere) デカルト閉圏$\mathscr{C}$において全射$f:\Omega\rightarrow Y^\Omega$が存在するとき、任意の$\alpha : Y\rightarrow Y$は不動点を持つ。

Proof デカルト閉圏の性質から$\mathscr{C}(\Omega, Y^\Omega)\simeq \mathscr{C}(\Omega\times\Omega, Y)$なので$f$を$\hat{f}:\Omega\times\Omega\rightarrow Y$とみなすことができる。$f$は全射なので任意の$h\in Y^\Omega: \Omega\rightarrow Y$に対して$h=f(\omega_h)$あるいは同じことであるが$h(\omega)=\hat{f}(\omega, \omega_h)$を満たす$\omega_h$が（一意的ではないにせよ）存在する。いま$Y^\Omega$の元として$g(\omega)=\alpha(\hat{f}(\omega,\omega))$なるものを考える。すると$g=f(\omega_g)$($g(\omega)=\hat{f}(\omega,\omega_g)$)なる$\omega_g$について$g(\omega_g)=\alpha(f(\omega_g,\omega_g))=\hat{f}(\omega_g, \omega_g)$。(QED)

解釈
$\Omega$というのは「ラベル」の空間で、任意の$Y^\Omega$がラベルづけできる、すなわち任意の$h\in Y^\Omega$に対して対応する$\Omega$の元が存在する、言い換えれば$\Omega\rightarrow Y^\Omega$なる全射が存在することがキモとなっている。$\alpha$として不動点が存在し得ない写像を想定できればこの全射性を否定することができる。

Yanofsky流にダイアグラムを書くと次のようになる。
\[
\xymatrix{
\Omega\times\Omega \ar[r]^{\hat{f}} & Y \ar[d]^\alpha \\
\Omega \ar[u]^\Delta \ar[r]^g & Y
}\]
$\Delta$は$\Omega\times\Omega$の対角線を取る作用素である。

Lavereの不動点定理（の対偶）を用いてCantorの定理を証明しよう。いま$\mathbf{2}=\{0,1\}$, $\wp(\mathbb{N})=\mathbf{2}^\mathbb{N}$とする。

Theorem(Cantor) $\mathbb{N}\lneq\wp(\mathbb{N})$

Proof 定理は$\mathbb{N}\rightarrow\mathbf{2}^\mathbb{N}$なる全射が存在しないことを主張している。$\alpha:\mathbf{2}\rightarrow\mathbf{2}$として$\alpha:1\mapsto 0, 0\mapsto 1$なるものを考えると、この変換は不動点を持たない。したがってLawvereの定理の対偶により全射$\mathbb{N}\rightarrow\mathbf{2}^\mathbb{N}$は存在しない。(QED)

解釈
$\wp(\mathbb{N})=\mathbf{2}^\mathbb{N}$の$\mathbb{N}$は桁番号を、$\mathbf{2}$はその桁の値を表している。すなわち$\mathbf{2}^\mathbb{N}$は$[0,1)$の実数を二進法で表したものである。（写像が数になる、と言うところが冪対象の存在の所以である。）全射$\mathbb{N}\rightarrow\mathbf{2}^\mathbb{N}$が存在すると$[0,1)$の実数に自然数で通し番号をつけることができるということになるが、$g(n)=\alpha(\hat{f}(n,n))$すなわちその$n$桁目が$n$番目の数の$n$桁目ではないもの、であるような$g$を取ると、$g$の$n_g$桁目は$g$の$n_g$桁目ではないものになってしまうので矛盾するのである。

\[
\xymatrix{
\mathbb{N}\times\mathbb{N} \ar[r]^{\hat{f}} & \mathbf{2} \ar[d]^\alpha \\
\mathbb{N} \ar[u]^\Delta \ar[r]^g & \mathbf{2}
}\]

Yanofskyの論文[1]や辻本さんという人の文書[2]に興味深い例がたくさん載っている。一つ[2]から紹介しよう。

Lemma(辻本) すべての心理状態を物理状態に帰着させることはできない。

Proof 心理状態として物理状態を良し悪しで判定することを考える。すなわち物理状態の空間を$\mathcal{H}$とおくと、この心理状態の集合は$\mathbb{2}^\mathcal{H}$で表されることとなる。ここで否定的な状態を考える。すなわち$\alpha:1\mapsto 0, 0\mapsto 1$なるものを考えて$g(h)=\alpha(\hat{f}(h,h))$とする。$g$は$h$なる物理状態で指定される心理$f(h)$が$h$自身について考えた結果を否定する。$g$が$g$自身について考えれば、これは$\alpha$の不動点となり矛盾する。(QED)


[1]N. S. Yanofsky, http://arxiv.org/abs/math/0305282
[2]辻下 徹, www.ritsumei.ac.jp/se/~tjst/doc/tjst/988-st.pdf‎