Knaster–Tarskiの定理
概要
Knaster–Tarski の定理（Knaster–Tarski theorem）とは、完備束 $L$ 上の単調写像 $\varphi$ が最小不動点と最大不動点を持ち、最小不動点は前不動点 $\{x\mid\varphi(x)\le x\}$ 全体の下限、最大不動点は後不動点 $\{x\mid x\le\varphi(x)\}$ 全体の上限で与えられるという定理である。証明は完備性と単調性だけを用い、位相や連続性を使わない。さらに不動点全体はそれ自身完備束をなし、前不動点は最小不動点以上であるという性質が、冪集合上の帰納的定義とその帰納法の原理を支える。整数上の $x\mapsto x+1$ や $[0,1]$ 上の単調でない写像は不動点を持たず、完備性と単調性のどちらも落とせない。
定義
半順序集合 $(L,\le)$ の部分集合 $S$ に対し、$u\in L$ が $S$ の上界であるとは、すべての $s\in S$ について $s\le u$ となることをいい、$S$ の上界のうち最小のもの（存在すれば一意）を $S$ の上限といい $\bigvee S$ と書く。双対に、すべての $s\in S$ について $l\le s$ となる $l$ を下界、最大の下界を下限といい $\bigwedge S$ と書く。$S=\emptyset$ のとき、$L$ のすべての元が上界かつ下界なので、$\bigvee\emptyset$ は $L$ の最小元、$\bigwedge\emptyset$ は $L$ の最大元である（存在すれば）。
半順序集合 $(L,\le)$ が完備束（complete lattice）であるとは、$L$ の任意の部分集合 $S$（空集合と $L$ 自身を含む）が上限 $\bigvee S$ と下限 $\bigwedge S$ を持つことをいう。特に完備束は最小元 $\bot=\bigvee\emptyset$ と最大元 $\top=\bigwedge\emptyset$ を持ち、二元の上限・下限を持つので束である。
半順序集合 $L$ 上の写像 $\varphi\colon L\to L$ が単調（monotone、順序を保つ）であるとは、$x\le y$ ならば $\varphi(x)\le\varphi(y)$ となることをいう。$x\in L$ が $\varphi$ の不動点であるとは $\varphi(x)=x$ となることをいい、$\varphi(x)\le x$ となる $x$ を前不動点（prefixed point）、$x\le\varphi(x)$ となる $x$ を後不動点（postfixed point）という。不動点全体の集合を $\operatorname{Fix}(\varphi)$ と書く。$\operatorname{Fix}(\varphi)$ の最小元（存在すれば）を最小不動点 $\operatorname{lfp}(\varphi)$、最大元を最大不動点 $\operatorname{gfp}(\varphi)$ という。
半順序集合 $L$ の任意の部分集合が上限を持つならば、任意の部分集合は下限も持ち、$L$ は完備束である。双対に、任意の部分集合が下限を持つならば $L$ は完備束である。
$S\subset L$ とし、$S$ の下界全体の集合を $D$ とする。$l:=\bigvee D$ が $S$ の下限であることを示す。$s\in S$ は $D$ の各元以上なので $D$ の上界であり、上限の最小性から $l\le s$ である。よって $l$ は $S$ の下界である。$D$ の各元は $l$ 以下なので、$l$ は最大の下界である。双対も同様である。$\square$
直感
完備束では「どんなに多くの元をとっても、それらをまとめる最小の元と最大の元がある」。Knaster–Tarski の定理は、この性質と写像の単調性だけから不動点の存在を導く。最小不動点は「$\varphi$ を施しても大きくならない元（前不動点、$\varphi(x)\le x$）」すべての下限として、最大不動点は「$\varphi$ を施しても小さくならない元（後不動点、$x\le\varphi(x)$）」すべての上限として与えられる。冪集合の場合、これは「与えられた操作で閉じた最小の集合」（閉包・帰納的定義）を作る操作にほかならない。連続性や位相は一切使わない。
例と反例
集合 $X$ の冪集合 $\mathcal{P}(X)$ は包含関係について完備束である（部分集合の族 $\mathcal{S}\subset\mathcal{P}(X)$ の上限は合併 $\bigcup\mathcal{S}$、下限は共通部分 $\bigcap\mathcal{S}$。空族については $\bigcup\emptyset=\emptyset$、$\bigcap\emptyset=X$ と約束する）。$A\subset X$ と写像 $f\colon X\to X$ に対し、$\varphi(S):=A\cup f[S]$（$f[S]$ は像）は単調である。thm-knaster-tarski により $\operatorname{lfp}(\varphi)=\bigcap\{S\subset X\mid A\cup f[S]\subset S\}$、すなわち $A$ を含み $f$ で閉じた最小の部分集合 $M$ が存在する。$M$ は $A$ から $f$ を繰り返して得られる元全体 $M':=\bigcup_{n\ge0}M_n$（$M_0=A$、$M_{n+1}=M_n\cup f[M_n]$）に等しい。実際、$M'$ は $A$ を含み $f$ で閉じている（$x\in M_n$ なら $f(x)\in M_{n+1}$）ので $M\subset M'$ であり、$M$ は $A$ を含み $f$ で閉じているので帰納法により各 $M_n\subset M$、よって $M'\subset M$ である。
$f\colon A\to B$、$g\colon B\to A$ を単射とする。$\mathcal{P}(A)$ 上の写像 $\Phi(S):=A\setminus g[B\setminus f[S]]$ は単調である。実際、$S\subset S'$ なら $f[S]\subset f[S']$、$B\setminus f[S]\supset B\setminus f[S']$、$g[B\setminus f[S]]\supset g[B\setminus f[S']]$、よって $\Phi(S)\subset\Phi(S')$ である。thm-knaster-tarski により不動点 $S=\Phi(S)$ があり、$A\setminus S=g[B\setminus f[S]]$ が成り立つ。$h\colon A\to B$ を、$S$ 上では $f$、$A\setminus S$ 上では $g$ の逆写像（$g$ は単射なので $g[B\setminus f[S]]$ 上で定まる）と定める。$h$ は全単射である：$h[S]=f[S]$ と $h[A\setminus S]=B\setminus f[S]$ は互いに交わらず合併は $B$ であり、$h$ は $S$ 上でも $A\setminus S$ 上でも単射だから $h$ は単射かつ全射である。よって $A$ と $B$ の間に全単射が存在する。
次の例は、thm-knaster-tarski の仮定「完備束」「単調」のどちらも落とせないことを示す。
- 整数全体 $\mathbb{Z}$ は通常の順序で束だが完備束でない（$\mathbb{Z}$ 自身に上限がない）。写像 $x\mapsto x+1$ は単調だが不動点を持たない。よって「束上の単調写像 ⇒ 不動点あり」は成り立たない。
- 閉区間 $[0,1]$ は完備束である（任意の部分集合が実数の上限・下限を持ち、空集合の上限は $0$、下限は $1$）。写像 $\varphi(x)=1$（$x<1/2$）、$\varphi(x)=0$（$x\ge1/2$）は単調でなく、不動点を持たない（$x<1/2$ なら $\varphi(x)=1\neq x$、$x\ge1/2$ なら $\varphi(x)=0\neq x$）。よって「完備束上の写像 ⇒ 不動点あり」は成り立たない。
定理
$(L,\le)$ を完備束、$\varphi\colon L\to L$ を単調写像とする。このとき $\varphi$ の最小不動点と最大不動点が存在し、
$$\operatorname{lfp}(\varphi)=\bigwedge\{x\in L\mid\varphi(x)\le x\},\qquad\operatorname{gfp}(\varphi)=\bigvee\{x\in L\mid x\le\varphi(x)\}$$
が成り立つ。すなわち、最小不動点は前不動点全体の下限、最大不動点は後不動点全体の上限である。
$P:=\{x\in L\mid\varphi(x)\le x\}$ とおき、$p:=\bigwedge P$ とする（完備性により存在する）。
まず $\varphi(p)$ が $P$ の下界であることを示す。$x\in P$ をとると、$p$ は $P$ の下界なので $p\le x$ であり、単調性により $\varphi(p)\le\varphi(x)$、また $x\in P$ より $\varphi(x)\le x$ である。よって $\varphi(p)\le x$ である。$p$ は $P$ の最大の下界なので $\varphi(p)\le p$、すなわち $p\in P$ である。
次に、$\varphi(p)\le p$ と単調性から $\varphi(\varphi(p))\le\varphi(p)$、すなわち $\varphi(p)\in P$ である。$p$ は $P$ の下界なので $p\le\varphi(p)$ であり、反対称律から $\varphi(p)=p$ である。よって $p$ は不動点である。任意の不動点 $x$ は $\varphi(x)=x\le x$ を満たすので $P$ に属し、$p\le x$ である。ゆえに $p$ は最小不動点である。
最大不動点については、$Q:=\{x\in L\mid x\le\varphi(x)\}$、$q:=\bigvee Q$ とおく。$x\in Q$ に対し $x\le q$ から $x\le\varphi(x)\le\varphi(q)$ なので $\varphi(q)$ は $Q$ の上界であり、$q\le\varphi(q)$、すなわち $q\in Q$ である。単調性により $\varphi(q)\le\varphi(\varphi(q))$ なので $\varphi(q)\in Q$ であり、$\varphi(q)\le q$ である。よって $\varphi(q)=q$ であり、任意の不動点は $Q$ に属するので $q$ は最大不動点である。$\square$
$(L,\le)$ を完備束、$\varphi\colon L\to L$ を単調写像とする。このとき不動点全体 $\operatorname{Fix}(\varphi)$ は、$L$ から誘導される順序について完備束である。
prop-knaster-tarski-sup-suffices により、$\operatorname{Fix}(\varphi)$ の任意の部分集合 $S$ が $\operatorname{Fix}(\varphi)$ の中で上限を持つことを示せばよい。$s:=\bigvee S$（$L$ における上限）とおき、区間 $I:=\{x\in L\mid s\le x\}$ を考える。
$I$ は誘導順序について完備束である。実際、$T\subset I$ に対し、$L$ における上限 $\bigvee T$ は $T\neq\emptyset$ なら $I$ に属し、$T=\emptyset$ なら $s\in I$ が $I$ における上限である。$I$ に属する上界のうち最小のものが $I$ における上限なので、いずれの場合も $T$ は $I$ の中で上限を持つ。よって prop-knaster-tarski-sup-suffices を $I$ に適用すると、$I$ は完備束である。
$\varphi$ は $I$ を $I$ に写す。実際、各 $y\in S$ について $y=\varphi(y)\le\varphi(s)$（$y\le s$ と単調性）なので $\varphi(s)$ は $S$ の上界であり $s\le\varphi(s)$ である。よって $x\in I$ なら $s\le\varphi(s)\le\varphi(x)$ である。
したがって $\varphi$ の $I$ への制限は完備束 $I$ 上の単調写像であり、thm-knaster-tarski により最小不動点 $p\in I$ を持つ。$p$ は $\varphi$ の不動点で $S$ の上界（$s\le p$）であり、$S$ の上界である任意の不動点 $x$ は $I$ に属する $\varphi|_I$ の不動点なので $p\le x$ である。ゆえに $p$ は $\operatorname{Fix}(\varphi)$ における $S$ の上限である。$\square$
完備束 $L$ 上の単調写像 $\varphi$ と $x\in L$ について、$\varphi(x)\le x$ ならば $\operatorname{lfp}(\varphi)\le x$ である。特に、冪集合 $\mathcal{P}(X)$ 上の単調写像 $\varphi$ の最小不動点 $M$ について、$\varphi(S)\subset S$ を満たす任意の $S\subset X$ は $M$ を含む。
$\operatorname{lfp}(\varphi)$ は前不動点全体の下限なので（thm-knaster-tarski）、前不動点 $x$ について $\operatorname{lfp}(\varphi)\le x$ である。$\square$
補足：用途と関連する定理
- 帰納的定義：ex-knaster-tarski-powerset のように、生成規則に対応する単調写像の最小不動点として「規則で生成される最小の集合」が得られる。cor-knaster-tarski-induction は、その集合に関する帰納法の原理（規則で閉じた性質は生成されるすべての元が持つ）に対応する。
- 最大不動点：後不動点全体の上限である最大不動点は、余帰納的な定義（双模倣など）に用いられる。
- 他の不動点定理との比較：Knaster–Tarski の定理は位相も連続性も使わない。単調写像が可算な鎖の上限を保つときは、$\bot,\varphi(\bot),\varphi(\varphi(\bot)),\dots$ の上限が最小不動点になる（Kleene の不動点定理。DP02 第 8 章を引用し、本記事では扱わない）。完備束を仮定しない不動点定理として、空でない完備距離空間上の縮小写像に関する Banach の不動点定理や、Euclid 空間の空でない凸コンパクト集合上の連続写像に関する Brouwer の不動点定理がある。
- 本定理は Knaster（1928、冪集合の場合。Kna28）と Tarski（1955、Tar55）による。完備束の基礎は DP02 第 2 章を参照。
関連項目
- 前提: 半順序集合, 束
- 比較: 完備束, 不動点, 閉包作用素
- 発展: Kleeneの不動点定理, Brouwerの不動点定理, Cantor–Schröder–Bernsteinの定理, 帰納的定義
