自然数上の関数の随伴について
自然数上の関数について遊んだ結果を残す。
用語の定義
この記事だけの用語を定義する。
関数$f,g:\mathbb{N}\rightarrow\mathbb{N}$が随伴関係$\ f \dashv g \ $が成り立つとは
任意の自然数$c,d$について
$f(c)\leq d \iff c\leq g(d)$
が成り立つことをいう。
この時、$f$を$g$の左随伴、$g$を$f$の右随伴と呼ぶことにする。
随伴関係には元ネタがあるが(後述)、この用語自体はこの記事だけのローカルな用語としたい。
つぎに基本的な用語を定義する。
関数$f:\mathbb{N}\rightarrow \mathbb{N}$が単調であるとは任意の自然数$c,d$について、
$c\leq d \implies f(c)\leq f(d)$
単調性は広義単調関数とかの単調である。
関数$f:\mathbb{N}\rightarrow \mathbb{N}$が上に有界(下に有界)であるとは
$f$の値域に最大値(最小値)が存在することである。
関数$f$が上に有界$\iff$ $\exists m:\mathbb{N}.\forall x:\mathbb{N}.f(x)\leq m$
関数$f$が下に有界$\iff$ $\exists m:\mathbb{N}.\forall x:\mathbb{N}.m\leq f(x)$
関数$f:\mathbb{N}\rightarrow \mathbb{N}$が上に非有界(下に非有界)であるとは
関数$f$が上に非有界$\iff$ $\forall m:\mathbb{N}. \exists x:\mathbb{N}.m\leq f(x)$
関数$f$が下に非有界$\iff$ $\forall m:\mathbb{N}. \exists x:\mathbb{N}.f(x)\leq m$
ここでは有界と非有界は単純な否定の関係として定義していない。
記事内で共通する用語については以上となる。
これからは随伴関係について、その性質を紹介していく。
随伴の各性質
随伴関係は一方が定まれば、他方は一意に定まる。
- $f\dashv g$かつ$f\dashv g'$ならば、$g=g'$
- $f\dashv g$かつ$f'\dashv g$ならば、$f=f'$
関数$f,g,g':\mathbb{N}\rightarrow\mathbb{N}$について、$f\dashv g$かつ$f\dashv g'$とする。
それぞれを定義をもとに変形すると、
$f(c)\leq d \iff c\leq g(d)$かつ$f(c)\leq d \iff c\leq g'(d)$
となるから、同値性により
$c\leq g(d) \iff c\leq g'(d)$
である。
$c$に$g(d)$を代入すれば右側が常に成り立つから$g(d)\leq g'(d)$。
同様に$g'(d)$を代入すれば$g'(d)\leq g(d)$が成り立つから
任意の自然数$d$について
$g(d)= g'(d)$
であることが分かり、関数として等しいことが示された。
この議論を$f\dashv g$かつ$f'\dashv g$に適用すれば、左随伴の一意性も分かる。
この一意性から、随伴関係を満たす関数を構成すれば、それが唯一であると宣言できる。
また、右随伴については顕著な性質がある。
関数$g:\mathbb{N}\rightarrow \mathbb{N}$について以下は同値である。
- 関数$g$は右随伴(左随伴$f$を持つ)
- 関数$g$は単調かつ上に非有界
これを示すのは少し長くなるので、随伴の性質を少しずつ示していく。
関数$g$が右随伴ならば単調である。
$g$が(関数$f$の)右随伴とは、任意の自然数$c,d$について
$f(c)\leq d \iff c\leq g(d)$
となることであった。
$c$に$g(d)$を代入すると、
$f(g(d))\leq d \iff g(d)\leq g(d)$
$\implies f(g(d))\leq d\dots (1)$
次に$c$に$g(d')$を代入すると、
$f(g(d'))\leq d \iff g(d')\leq g(d)\dots (2)$
この$(1),(2)$に対して$d'\leq d$を仮定すれば、
$d'\leq d\implies f(g(d'))\leq d' \leq d \implies g(d')\leq g(d)$
これは関数$g$の単調性である。
関数$g$が右随伴ならば上に非有界である。
目標は$\forall m:\mathbb{N}. \exists x:\mathbb{N}.m\leq g(x)$を示すことにある。
左随伴$f$の存在は与えられているから、任意の自然数$m$について次は自明
$\forall m:\mathbb{N}.f(m)\leq f(m)$
$\implies \forall m:\mathbb{N}.\exists x:\mathbb{N}.f(m)\leq x$
随伴の性質より
$\iff \forall m:\mathbb{N}.\exists x:\mathbb{N}.m\leq g(x)$
これは、目標の式である。
以上の結果により、右随伴ならば単調かつ上に非有界まで言えた。
つぎは、単調かつ上に非有界ならば右随伴であることを示す。
関数$g$が単調かつ上に非有界ならば右随伴である。
関数$g$は単調かつ上に非有界だとする。また、自然数は整列していることから、次の関数$f'$が定義できる。
$f'(c):=\min\{x\mid c\leq g(x) \}$
$f'$が関数であることを確認する。集合$\{x\mid c\leq g(x) \}$の要素は不等式$c\leq g(x)$を満たす$x$であり、任意の$c$についても$g$の非有界性から不等式を満たす$x$が存在するため、集合は常に非空となる。
また、集合の要素はすべて自然数であり最小値がただ一つ存在するから、$f'$は関数となる。
話を戻す。この関数$f'$が関数$g$の左随伴であることを示す
$f'(c)\leq d \implies c\leq g(d)$ を示す。
$g$の単調性から、
$\min\{x\mid c\leq g(x) \}\leq d\implies g(\min\{x\mid c\leq g(x) \})\leq g(d) $
$c\leq g(x) $を満たす自然数$x$の内の一つを$g$に適用すれば$c$以上になるので、$c\leq g(\min\{x\mid c\leq g(x) \})$
以上より、
$f'(c)\leq d\implies c\leq g(d) $
$ c\leq g(d) \implies f'(c)\leq d$を示す。
集合$\{x\mid c\leq g(x) \}$の条件より、
$ c\leq g(d)\implies d\in\{x\mid c\leq g(x) \}$であり、集合の最小値の方が小さくなるので
$c\leq g(d)\implies f'(c)\leq d$
以上より、$f'\dashv g$が示され、$g$は右随伴である。
結果をまとめる。
関数$g$について以下は同値である。
- $g$は右随伴
- $g$は単調かつ上に非有界
証明の中で、具体的な随伴の構成を行ったので、それも明示する。
関数$f,g:\mathbb{N}\rightarrow\mathbb{N}$について$f\dashv g $が成り立つとき、$f,g$はそれぞれ$g,f$を使って次のように構成される。
$f(c):= \min\{x\mid c\leq g(x)\}$
$g(d):= \max\{x\mid f(x)\leq d\}$
右随伴は先ほど証明した。
左随伴の場合も、右随伴の場合と同様の方針で証明できる。
ただ左随伴については、右随伴かつ$f(0)=0$を満たす必要があり、非対称的となっている。
関数$f$について以下は同値である。
- $f$は左随伴
- $f$は単調かつ$f(0)=0$かつ上に非有界
右随伴と同様の議論により、$f$は左随伴ならば$f$は単調かつ下に非有界まで分かり、自然数には最小値$0$が存在するので、$f(0)=0$が分かる。
よって、上に有界であるかを議論する。
($1\implies \text{上に非有界}$を示す)
$f$が上に有界と仮定する。
$f$は左随伴なので、ある右随伴な関数$g$が存在し、
$f(c)\leq d \iff c\leq g(d)$を満たすので、
$\exists d.\forall c.f(c)\leq d $(仮定より)
$\implies \exists d.\forall c.c\leq g(d) $
しかし、後件を満たす自然数は存在しない。
その為次のようになる。
$ \lnot (\exists d.\forall c.f(c)\leq d )$
$\implies \forall d. \exists c. \lnot (f(c)\leq d) $
$\implies \forall d. \exists c. d< f(c) $
$\implies \forall d. \exists c. d\leq f(c) $
よって、$f$は上に非有界である。
($2\implies 1$を示す)
$g'(d):= \max\{x\mid f(x)\leq d \}$
が関数として定義できているか確認する。
$f$は$f(0)=0$であるので、集合$\{x\mid f(x)\leq d \} $は非空である。
また、$f$は単調かつ上に非有界であり、ある自然数以上の引数に対しては値が$d+1$以上となるため、集合は有限となり、最大値を持つ。
よって、$g' $は関数となる。
以降は右随伴の場合と同様の議論により、関数$g'$が$f$の右随伴($f$は左随伴)であることが分かる。
随伴の公式について
随伴に関する性質によれば、関数の随伴は存在すれば一意なので、存在を仮定すれば、演算子のように扱うことができる。
そこで次のような記号を導入する。
$g$が右随伴、$f$が左随伴としたとき、随伴演算子を次のように定義する。
$g^{L}(c):=\min\{x\mid c\leq g(x)\}$
$f^{R}(d):= \max\{x\mid f(x)\leq d\}$
このとき、$g^L\dashv g$,$f\dashv f^R$である。
随伴演算子についてはいくつかの公式が成り立つので右随伴に限って紹介する。
- $(g^{L})^R=g$
- $(h\circ g)^L=g^L \circ h^L$
- $(g^m)^L=(g^L)^m$
- $g^L\circ g(d)\leq d$
- $d\leq g\circ g^L(d)$
- $f\leq g \implies g^L \leq f^L$
- $g(x)+1=g^{LL}(x+1)$
これらの公式の多くは随伴の性質を活用して証明される。
ただし、最後の式(7)については自分の中で証明が固まっていない。
方針としては、関数$g$の取りうる値ごとに引数の区間を分割し、それらが左随伴演算子を適用することによりどう振る舞うかを追いかけることを考えている。
随伴関係について
定義1として随伴関係を定義した。これは圏論における随伴と同じものである。
圏論における随伴は次のように定義される。1
圏$C,D$に対して関手$F:C\rightarrow D,G:D\rightarrow C$が定義されているとき、
$F$が$G$の左随伴、$G$が$F$の右随伴であるとは、
任意の$c\in C,d\in D$について自然な全単射$\varphi _{c,d}:\text{Hom}_D(F(c),d)\Rightarrow \text{Hom}_C(c,G(d))$
が存在することである。
このとき、$F\dashv G$を書かれる。
自然数の集合$\mathbb{N}$は、自然数の大小関係$\leq$を射とすることで圏をなす。すると、$\mathbb{N}$から$\mathbb{N}$への単調関数は関手になる。
$\mathbb{N}$の射は大小関係であった。つまり$n$から$m$への射の集合$\text{Hom}_{\mathbb{N}}(n,m)$は$n\leq m$が成り立つ時は一元集合、そうでない時は空集合なので、$\text{Hom}_{\mathbb{N}}(n,m)$と論理式$n\leq m$は同一視できる。
ここまでを踏まえると、随伴関係は圏論の随伴とそっくりな形をしているのが分かるだろう。
今回は自然数上の関数についてだったが、あるいはもっと広く全順序、半順序、前順序集合間の順序を保つ関数については今回と同じように随伴の議論を行うことができる。
これらは非常に具体的な対象について話をすることになり、パズルみたいな楽しさがある。
個人的な動機
逆っぽい関数
自然数上の関数について遊んでいると、逆関数について考えたくなる。
ただ多くの場合、逆関数は存在しない。
しかし関数の大きさにしか関心がないと、逆関数でなかったとしても、逆っぽい関数であれば良かったりもして、更にそこに良い性質なんかがあれば尚更良かったりもする。
そうしていると、逆っぽい関数として次のような関数が思い浮かんだ。
関数$f:\mathbb{N}\rightarrow \mathbb{N}$の値域が非有界だとする。
このとき、逆っぽい関数$g_1$を次のように定義する。
$g_1(y):=\ \begin{eqnarray} \left\{ \begin{array}{l} \min \{x\mid y=f(x) \} \ \dots \ \ \exists x.y=f(x)\text{のとき}\\ g_1(y+1) \dots \text{上記以外のとき} \end{array} \right. \end{eqnarray}$
この関数の"逆っぽさ"は何といっても「$\min \{x\mid y=f(x) \} $」の部分だろう。
このパートにより、$g_1(f(x))=x$が成り立つ部分が存在する。
しかし全部ではない。関数$f$が単射でない限り、複数の値が同じになる部分が出てくるので、その値の部分では$g_1(f(x))=x$が成り立たない。
この逆っぽい関数は変形していく内にまとまった形になっていた。
逆っぽい関数を自分で作っておいて奇妙に感じたのは、「$g_1(y+1)$」の部分だ。
関数を自然数の再帰で定義するとき、引数よりも小さい値を再帰に使用するものだと考えているから、この定義はそれに反している。しかし関数$f$の値域が非有界であると仮定しているから、引数を大きくしていけば、いつかは上の場合分けにぶつかり、事なきを得る。
個人的な利用方法
個人的な利用方法としては、関数同士の支配関係を分析するときに使用している。
支配関係とは次のような関係だった。
（ここでは独自の記号$\leq _ \exists$を使っている。）
支配関係$f\leq_\exists g \iff \exists p.\forall x.p\leq x \implies f(x)\leq g(x)$
関数を合成した先でも成り立つかどうかを考えたいときや、あるいは引数の回数だけ反復合成を行うことを考えるとき、$p$の部分が変更される場合がある。
つまり、$g$が$f$を引き離す引数$p$が後ろにずれていった場合には、それを安易に一般化すると、いつまで経っても$f$が$g$より大きいままになる可能性がある。
そこで$p$を定量的に評価するために左随伴演算子を使う。
一旦、$g$が$f$より大きくなる引数$p$を明示した大小関係を定義する。
$f\leq_p g\iff \forall x.p\leq x\implies f(x)\leq g(x)$
すると、次が成り立つ。
関数$h$が右随伴とする。
- $f\leq_p g\implies f\circ h\leq_{h^L(p)}g\circ h$
$f\leq_p g$
$\iff (\forall x.p\leq x\implies f(x)\leq g(x))$
$\implies (\forall y.p\leq h(y)\implies f(h(y))\leq g(h(y)))$
$\iff (\forall y.h^L(p)\leq y\implies f(h(y))\leq g(h(y)))$
$\iff f\circ h\leq_{h^L(p)} g\circ h$
この公式によれば、有限個の関数合成においては支配関係を保つことが分かる。
使用する関数が恒等関数より強ければ、任意回の関数合成に対しても支配する定数が頭打ちになることもわかる。
また、支配関係をさらに弱くしたいと考えたときにも、これらの議論は有用であったので、これからも使っていきたい。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
