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]$ 上の単調でない写像は不動点を持たず、完備性と単調性のどちらも落とせない。
Knaster–Tarski の定理とは、完備束 $L$ 上の単調写像 $\varphi$ がつねに最小不動点と最大不動点をもち、最小不動点は $\varphi(x)\le x$ を満たす元全体の下限として得られる、という定理である。位相も連続性も使わずに不動点の存在が言えるので、「与えられた規則で閉じた最小の集合」を作るときに使われる。典型例は、集合 $X$ の冪集合 $\mathcal{P}(X)$ 上で、$A$ を含み写像 $f$ で閉じた最小の部分集合を構成することである。
半順序集合 $(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$ が存在すれば、$A$ と $B$ の間には全単射が存在する。この主張は 基数 の定理「Cantor–Bernstein の定理:単射の往復から全単射」を参照。不動点定理との関係は、$\mathcal P(A)$ 上の単調写像
$$
\Phi(S)=A\setminus g[B\setminus f[S]\!]
$$
を考えることで見える。二回の補集合が包含の向きを二回反転するので、$\Phi$ は単調となる。thm-knaster-tarski は、この対応に不動点が存在することを保証する。その不動点を用いて、$f$ を使う部分と $g$ の逆を使う部分を分けることができる。
次の例は、thm-knaster-tarski の仮定「完備束」「単調」のどちらも落とせないことを示す。
$(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)\}$$
が成り立つ。すなわち、最小不動点は前不動点全体の下限、最大不動点は後不動点全体の上限である。Tar55 §1 Theorem 1(pp. 286–287)。
$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$
不動点全体が完備束になるという結論は、不動点全体が $L$ の完全部分束になるという結論ではない。順序は $L$ からそのまま引き継ぐが、ある族の上限を不動点全体の中で取ると、外側での上限より大きくなることがある。外側の上限がすでに不動点であれば一致するが、単調性だけではそれを保証できない。
$L=\mathcal P(\{a,b,c\})$ とし
$$
\varphi(S)=
\begin{cases}
S\cup\{c\}&a,b\in S,\\
S&\text{それ以外}
\end{cases}
$$
と定める。$S\subseteq T$ のとき、$S$ が $a,b$ の両方を含めば $T$ も含み、追加する $c$ は両方の像に入る。含まない場合も $\varphi(S)=S\subseteq T\subseteq\varphi(T)$。よって $\varphi$ は単調である。
$\{a\}$ と $\{b\}$ は不動点だが、$L$ 内の上限 $\{a,b\}$ は不動点でない。不動点であって両者を含む集合には $c$ も入らなければならないので、不動点全体の内部での上限は $\{a,b,c\}$ となる。完備性と単調性はすべて満たしており、「不動点全体は外側の上限に閉じる」という強すぎる結論が成り立たないことを示す反例である。
上の例での不動点全体は、$\mathcal P(\{a,b,c\})$ から $\{a,b\}$ 一つを除いた集合である。不動点全体の完備性の証明では、まず外側の上限 $s$ を取り、その上の区間に制限した写像の最小不動点を探した。この第二段階が、外側の上限を不動点になるまで引き上げる役割を果たしている。したがって第一段階だけで計算を終えることはできない。
生成規則を増やすと最小不動点は大きくなる。順序論的には、写像を点ごとに比較することでこの事実を示せる。
完備束 $L$ 上の単調写像 $\varphi,\psi$ が、すべての $x\in L$ について $\varphi(x)\le\psi(x)$ を満たすとする。このとき
$$
\operatorname{lfp}(\varphi)\le\operatorname{lfp}(\psi),
\qquad\operatorname{gfp}(\varphi)\le\operatorname{gfp}(\psi)
$$
である。
$p=\operatorname{lfp}(\psi)$ とすれば $\varphi(p)\le\psi(p)=p$。よって $p$ は $\varphi$ の前不動点であり、cor-knaster-tarski-induction により $\operatorname{lfp}(\varphi)\le p$ となる。$q=\operatorname{gfp}(\varphi)$ とすれば $q=\varphi(q)\le\psi(q)$ なので、$q$ は $\psi$ の後不動点である。後不動点全体の上限である $\operatorname{gfp}(\psi)$ は $q$ 以上になる。$\square$
この比較では、不動点の集合そのものが包含されるとは主張していない。たとえば $\{0,1\}$ の鎖で $\varphi$ を恒等写像、$\psi$ を定数 $1$ とすれば、点ごとに $\varphi\le\psi$ だが $0$ は $\varphi$ の不動点であり $\psi$ の不動点でない。保存されるのは最小・最大不動点の大小関係であり、個々の不動点の帰属ではない。
有限な完備束では、最小元から $x_0=\bot$、$x_{n+1}=\varphi(x_n)$ と反復すると最小不動点に到達する。最初は $\bot\le\varphi(\bot)$、その後は単調性によって $x_n\le x_{n+1}$ が続く。有限集合の中で真に増加し続けることはできないので、ある段で $x_n=x_{n+1}$ となる。そこで $x_n$ は不動点である。任意の前不動点 $p$ に対して $x_0\le p$ であり、$x_n\le p$ なら $x_{n+1}=\varphi(x_n)\le\varphi(p)\le p$。帰納法で停止した値も $p$ 以下となるため、最小不動点である。
しかし無限束では、有限回の反復の合併が不動点になるとは限らない。$L=\mathcal P(\mathbb N\cup\{\infty\})$ とし
$$
\varphi(S)=\{0\}\cup\{n+1\mid n\in S\cap\mathbb N\}
\cup\{\infty\mid\mathbb N\subseteq S\}
$$
と定める。この写像は単調である。空集合からの有限反復では $0,1,\ldots$ が順に加わり、その合併は $\mathbb N$ だが、$\varphi(\mathbb N)=\mathbb N\cup\{\infty\}$ なので合併は不動点でない。さらに一段進めた全体は不動点であり、各前不動点は $0$ とすべての後者を含むため $\mathbb N$ を含み、続いて $\infty$ も含む。したがって最小不動点は全体となる。
この例で欠いているのは、増加する可算族の上限と $\varphi$ の交換である。$\bigcup_n\varphi(x_n)=\mathbb N$ だが $\varphi(\bigcup_n x_n)=\mathbb N\cup\{\infty\}$ となる。Knaster–Tarskiの存在定理はそのような交換条件を必要としないため、有限反復や可算反復による計算法よりも適用範囲が広い。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 完備性 | 整数の $x\mapsto x+1$ | 不動点の存在 |
| 単調性 | $[0,1]$ 上で上下を入れ替える写像 | 不動点の存在 |
| 外側上限への閉性 | $a,b$ が揃うと $c$ を加える写像 | 不動点の族の外側上限が不動点であること |
| 可算増加族の上限保存 | 自然数が揃うと $\infty$ を加える写像 | 可算反復の上限が不動点であること |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する