このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

不動点方程式/不動点不等式と不動点オペレーター

フリーモナド 1: 自由で無料な木」において、次のように予告しました。

圏論的な不動点方程式と、不動点方程式によるフリーモナドの構成については「2」で述べます。

しかし、不動点の話はフリーモナドとは独立に語れるので、「フリーモナド」の続きではない形にします。不動点の一般論を特にフリーモナドに対して適用する話が「フリーモナド 2」になるでしょう。

不動点の話だけでもけっこうなボリュームになるので、この記事は“関数の不動点”を扱います。“関手の不動点”は続く記事にします(予定)。$`\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\In}{\text{ in } }
\newcommand{\On}{\text{ on } }
\newcommand{\Iff}{\Leftrightarrow }
\newcommand{\Imp}{\Rightarrow }
\newcommand{\id}{\mathrm{id} }
\require{color}
\newcommand{\Keyword}[1]{ \textcolor{green}{\text{#1}} }%
\newcommand{\For}{\Keyword{For } }%
\newcommand{\Condition}{\Keyword{Condition } }%
\newcommand{\Where}{\Keyword{Where } }%
%`$

内容:

ナスター/タルスキーの定理

不動点に関する有名な定理にナスター/タルスキー〈Knaster-Tarski〉の定理があります。幾つかの変種があるので、次のように分類しておきます。

  1. 不動点の存在定理: 適当な条件のもとで、不動点方程式に解が在ることを主張する。
  2. 不動点集合に関する定理: 不動点集合(不動点方程式の解集合)が、良い性質を持つことを主張する。
  3. 最小プレ不動点定理: 最小プレ不動点が最小不動点に一致することを主張する。

不動点方程式とは、おおざっぱに言えば次の形の方程式です。

$`\quad x = f(x)`$

未知数 $`x`$ は順序集合上を走る変数で、$`f`$ は単調な自己関数〈{monotonic | monotone} endofunction〉です。このことも記述すると不動点方程式は次のようになります。

$`\Condition x = f(x) \On X\\
\Where f:X \to X \In \cat{C}
`$

ここで、$`\cat{C} = {\bf Ord}`$ ($`{\bf Ord}`$ は順序集合と単調関数の圏)とすると、解の存在は保証できません。単なる順序集合/単調関数よりきびしい条件が必要です。例えば次のような条件を付けます。

  1. $`X`$ は、最小元($`\bot`$ と書く)を持つ。
  2. $`X`$ では、任意のω-鎖(自然数でインデックス付けられた上昇列)$`x_0 \le x_1 \le \cdots`$ が上限〈最小上界〉を持つ。
  3. $`f`$ は上限を保存する。

この条件を満たす順序集合/単調関数の全体は圏をなすので、それを $`\omega{\bf CPO}_\bot`$ と書きます。圏 $`\omega{\bf CPO}_\bot`$ における不動点方程式は次のように書けます。

$`\Condition x = f(x) \On X\\
\Where f:X \to X \In \omega{\bf CPO}_\bot
`$

このセッティングにおいては不動点(不動点方程式の解)の存在定理が言えます。次の過去記事で話題にしています。

不動点集合(不動点方程式の解集合)に関する定理としては、完備束〈complete lattice〉と単調関数の圏 $`{\bf CLatt}`$ における不動点方程式の結果があります。

$`\Condition x = f(x) \On X\\
\Where f:X \to X \In {\bf CLatt}
`$

このセッティングで、不動点集合は部分完備束になることが言えます。これもナスター/タルスキーの定理と呼びます(Wikipedia項目「Knaster–Tarski theorem」参照)。

不動点不等式とタルスキーの最小プレ不動点定理

順序集合では、等号以外に不等号(つまり、順序関係)も使えます。$`\cat{C}`$ は順序集合の圏 $`{\bf Ord}`$ への忘却関手を持つ圏だとして、次の形の不動点不等式を考えることができます。

$`\Condition x \ge f(x) \On X\\
\Where f:X \to X \In \cat{C}
`$

$`\Condition x \le f(x) \On X\\
\Where f:X \to X \In \cat{C}
`$

上の一番目の不等式の解を($`f`$ の)プレ不動点〈pre-fixed point〉、ニ番目の不等式の解を($`f`$ の)ポスト不動点〈post-fixed point〉と呼びます*1。ここでは主にプレ不動点を考えます。プレ不動点は、$`f`$ の作用により減少する〈下降する〉点だと言えます。

$`f`$ の不動点全体の集合を $`\mrm{FP}(f)`$ 、$`f`$ のプレ不動点全体の集合を $`\mrm{PreFP}(f)`$ と書くことにします。これらの集合が空でないことは一般的には保証できません。が、定義より $`\mrm{FP}(f) \subseteq \mrm{PreFP}(f)`$ は確実です。

$`\mrm{FP}(f)`$ 、$`\mrm{PreFP}(f)`$ に最小元〈least elemnet〉があれば、それを最小不動点〈least fixed point〉、最小プレ不動点〈least pre-fixed point〉と呼びます。

  • $`a`$ が $`f`$ の最小不動点である ⇔ $`\forall x\in \mrm{FP}(f). a \le x`$
  • $`b`$ が $`f`$ の最小プレ不動点である ⇔ $`\forall x\in \mrm{PreFP}(f). b \le x`$

$`a`$ が $`f`$ の最小不動点であることは次の2つの条件に分けて書くことができます。

  1. $`a = f(a)`$ (不動点である)
  2. $`\forall x\in X.\, x = f(x) \Imp a \le x`$ (不動点のなかで最小である)

$`b`$ が $`f`$ の最小プレ不動点であることも2つの条件に分けて書くことができます。

  1. $`f(b) \le b`$ (プレ不動点である)
  2. $`\forall x\in X.\, f(x) \le x \Imp b \le x`$ (プレ不動点のなかで最小である)

タルスキーの最小プレ不動点定理は、$`\cat{C} = {\bf Ord}`$ のセッティング(追加条件なし)において次の命題を主張しています。

  • 最小プレ不動点は最小不動点に一致する。

もう少し詳しくいうと:

パラメータ付き不動点方程式

次の形の方程式をパラメータ付き不動点方程式〈parameterized fixed point equation〉と呼びます。

$`\Condition x = g(a, x) \On X\\
\Where g:A\times X \to X \In \cat{C}
`$

ここで $`\times`$ はデカルト積〈直積〉なので、圏 $`\cat{C}`$ はデカルト圏である必要があります。

パラメータ付き不動点方程式の記述において、パラメータ変数 $`a`$ や未知数変数 $`x`$ を使っていますが、変数無し〈ポイントフリー〉スタイルで書くこともできます。下の可換図式はパラメータ付き不動点方程式と同値です。

$`\require{AMScd}
u:A \to X \in \cat{C}\\
\:\\
\begin{CD}
A @>{\langle \id_A, u\rangle}>> A\times X \\
@| @VV{g}V \\
A @>{ u}>> A\times X
\end{CD}\\
\text{commutative in }\cat{C}
`$

ここで、$`u`$ が求めるべき未知射で、可換図式が条件です。このような $`u`$ が存在する保証は(一般には)ないし、存在したとしても一意とは限りません。仮に存在して、なんらかの方法でひとつを選び出せるという想定のもとで、$`g`$ に対して決まる不動点射(不動点方程式のパラメータ付き解を与える射)を $`g^\dagger`$ と書きます。

変数を使って書くなら、パラメータ $`a`$ を決めるごとに $`g^\dagger(a)`$ が不動点方程式の解を与えるので次が成立します。

$`\quad g^\dagger(a) = g(a, g^\dagger(a))`$

パラメータ $`a`$ の値により不動点が在ったり無かったりするかも知れません。その意味で、不動点射 $`g^\dagger`$ はかなりアヤフヤな存在です。

事例を出します。圏 $`{\bf Ord}`$ で考えます。$`{\bf R}_{\ge 0}`$ は非負の実数の集合で、普通の順序を考えます。$`({\bf R}_{\ge 0})^2`$ には直積順序を入れます。$`g`$ を次のように定義します。

$`\For a = (a_1, a_2) \in ({\bf R}_{\ge 0})^2\\
\For x \in {\bf R}_{\ge 0}\\
\quad g(a, x ) = g( (a_1, a_2), x ) := a_1 x + a_2
`$

パラメータ $`a = (a_1, a_2)`$ の値により不動点が在ったり無かったりします。$`a_1 = 1, a_2 = 0`$ のときは無限個の不動点があります。

不動点オペレーター

デカルト圏 $`\cat{C}`$ がパラメータ付き不動点方程式に関して理想的に良い環境を提供するとします。具体的には次が成立しているとします。

  • 任意の $`A, X\in |\cat{C}|`$ と任意の $`g:A\times X \to X \in \cat{C}`$ に対して、不動点射が存在する。
  • 複数の不動点射が存在したとしても、なんらかの方法でひとつの不動点射を選び出すことが出来る。

このような理想的な状況ならば、$`g \mapsto g^\dagger`$ は圏論的オペレーターになります。$`\mrm{Fix}(g) := g^\dagger`$ と置くと、$`\mrm{Fix}`$ は次のようなオペレーターです。

$`\For A, X \in |\cat{C}|\\
\quad \mrm{Fix}_{A, X}: \cat{C}(A\times X , X) \to \cat{C}(A , X) \In {\bf Set}
%`$

$`\mrm{Fix}(g) = \mrm{Fix}_{A, X}(g)`$ が不動点射〈パラメータ付き不動点〉を与えることから次は成立します。

$`\quad \langle \id_A, \mrm{Fix}_{A, X}(g)\rangle ; g = \mrm{Fix}_{A, X}(g) \In \cat{C}`$

この等式だけではなくて、不動点オペレーターとして要求される性質があり、それらは公理化されています。次のような公理が要求されます。

  1. 自然性〈naturality〉
  2. パラメータ付き不動点性〈parameterized fixed-point property〉(上記の等式)
  3. パラメータ付き対角自然性〈parameterized dinaturality〉
  4. 対角性〈diagonal property〉

詳細は次の論文に書いてあります。

対角自然性の図式が五角形か六角形かで悩んだことが以下の過去記事に書いてあります。

なお、デカルト圏にける不動点オペレーターとトレース・オペレーターは同値な概念です。そのことを主張するのがカザネスク/ステファネスク/ハイランド/長谷川〈Cazanescu-Stefanescu-Hyland-Hasegawa〉の定理です。これについては以下の過去記事で触れています。

アフィン型不動点方程式

圏 $`\cat{C}`$ の対象 $`X`$ は、順序だけでなくて足し算も備えているとします。つまり
$`\quad (+):X\times X \to X \In \cat{C}\\ \quad 0:{\bf 1}\to X \In \cat{C}`$ があり、可換モノイドになっているとします。

この状況で、パラメータ付き不動点方程式の $`g`$ を次のように置くことができます。

$`\quad g(a, x) := a + f(x)\\
\Where f:X \to X \In \cat{C}
`$

変数無しスタイルで書くなら:

$`\quad g := (\id_X \times f) ; (+) : X\times X \to X \In \cat{C}\\
\Where f:X \to X \In \cat{C}
`$

パラメータ付き不動点方程式は次のようになります。

$`\Condition x = a + f(x) \On X\\
\Where f:X \to X \In \cat{C}
`$

この形のパラメータ付き不動点方程式をアフィン型不動点方程式〈affine-type fixed point equation〉と呼ぶことにします。

$`f`$ で決まるアフィン型不動点方程式の不動点射〈パラメータ付き不動点〉を $`\mrm{AffFix}(f)`$ と書くことにします。$`g(a, x) = a + f(x)`$ という仮定のもとで:

$`\quad \mrm{AffFix}(f) = \mrm{Fix}(g)`$

なので、アフィン型不動点オペレーターは、一般の不動点オペレーターの特別なケースに過ぎません。アフィン型不動点方程式/アフィン型不動点オペレーターを定義する理由は、この形のパラメータ付き不動点方程式が頻繁に登場するからです。

不動点の繰り返し構成法

パラメータ付き不動点方程式が与えられたとき、不動点を求める手順として繰り返し構成法〈iterative construction〉があります。ナスター/タルスキーの存在定理においても、繰り返し構成法で解を構成しています。

アフィン型不動点方程式の場合に、繰り返し構成法(下からの逐次近似法とも言える)を説明します。パラメータ $`a\in X`$ を固定して、次のような列 $`x_0, x_1, x_2, \cdots`$ を作ります。$`\bot`$ は $`X`$ の最小元です(在ると仮定)。

$`\quad x_0 := \bot\\
\quad x_1 := a + f(x_0) \\
\quad x_2 := a + f(x_1) \\
\quad \cdots\\
\quad x_{n + 1} := a + f(x_n) \\
\quad \cdots
`$

$`x_0, x_1, x_2, \cdots`$ がω-鎖(可算無限上昇列)であることはすぐ分かります。$`X`$ で「ω-鎖は上限を持つ」ならばその上限が不動点を与えます。

繰り返し構成法の手順は広い範囲に適用可能です。しかし、この手順が“停止”して、不動点に“収束”することが一般には保証できません。どのような圏なら/どのような対象なら/どのような射なら、繰り返し構成法が機能〈work〉するか? うまい条件を探すことが課題となります。

関数の不動点と関手の不動点

今までの話は関数の不動点でした。圏の対象は順序集合、または順序集合に何らかの構造(例:足し算)を付け加えたものです。単調関数 $`g:A\times X \to X`$ がパラメータ付き不動点方程式を定義します。方程式の解である不動点射も単調関数です。

公理的に定義される不動点オペレーターの場合は、ベースの圏の対象・射が集合上の構造と準同型写像とは限りませんが、パラメータ付き不動点方程式の素材である $`g`$ は(関数ではないにしろ)圏 $`\cat{C}`$ 内部の存在物です。

それに対して、関手の不動点は次のようなパラメータ付き不動点方程式で規定されます。

$`\Condition X \cong G(A, X)\On \cat{C}\\
\Where G:\cat{A}\times \cat{C} \to \cat{C} \In \cat{K}
`$

ここで、$`\cat{K}`$ は圏の2-圏 $`{\bf CAT}`$ への忘却関手を持つような2-圏です。不動点方程式を考える舞台の規模と次元が拡大します。一般論はちょっと手に負えないので、限定的状況を設定して考えます。その話はまたいずれ。

*1:プレ/ポストが逆になった定義を見たことがあります。おそらくは多数派だと思われる定義を書きました