クナスター・タルスキーの定理

数学の秩序論と格子理論の分野では、ブロニスワフ・クナスターとアルフレッド・タルスキにちなんで名付けられたクナスター・タルスキの定理は、次のように述べている。

( L , ≤)を完全束とし、f : L → L を≤ に関して順序保存（単調）関数とする。このとき、L における f の不動点の集合は、≤ に関して完全束を形成する。 

最も一般的な形で結果を述べたのはタルスキであり、^{[ 1 ]}そのためこの定理はタルスキの不動点定理としてよく知られている。それより少し前に、クナスターとタルスキは、 Lが集合の部分集合の束、冪集合束である特殊な場合について結果を確立した。^{[ 2 ]}

この定理は、プログラミング言語の形式意味論や抽象解釈、そしてゲーム理論において重要な応用を持つ。コンピュータ科学における再帰的または反復的なプロセスの意味を定義し、ゲーム理論などの分野で均衡状態の存在を証明するための論理的な基盤となる。本質的に、システムが単純で非減少的な規則に従う場合、安定した自己矛盾のない結果が必ず存在することを証明している。

この定理の逆は、アン・C・デイビスによって証明された。格子 L 上のすべての順序保存関数f  : L → Lが不動点を持つならば、Lは完全格子である。^{[ 3 ]}

完全束は空集合であってはならない（空集合の上限と下限を含まなければならない）ため、この定理は特に、 fの少なくとも 1 つの不動点の存在、さらには最小不動点と最大不動点の存在を保証する。多くの実際的なケースにおいて、これがこの定理の最も重要な含意である。

fの最小不動点は、 f ( x ) = xとなる最小の要素x、または同等に、f ( x ) ≤ xとなる要素 x です。最大不動点については、 f ( x ) = xとなる最大の要素xに対して双対が成り立ちます。

すべての昇順列x _nに対してf (lim x _n ) = lim f ( x _n ) が成り立つ場合、 fの最小不動点はlim f ⁿ (0) であり、0 はLの最小要素であるため、定理のより「構成的な」バージョンが得られます。(クリーネの不動点定理を参照)。より一般的に、fが単調である場合、 fの最小不動点は、順序数αについてαを取るf ^α (0)の定常極限であり、f ^αは超限帰納法によって定義されます。f α ⁺¹ = f ( f ^α ) であり、極限順序数γに対するf ^γは、 γより小さいすべてのβ順序数に対するf ^βの最小上界です。^{[ 4 ]}双対定理は最大不動点に対して成り立ちます。

例えば、理論計算機科学では、単調関数の最小不動点がプログラムの意味論を定義するために用いられます（例については「最小不動点」§  「表示的意味論」を参照）。多くの場合、定理のより特殊なバージョンが用いられ、 Lはある集合のすべての部分集合を部分集合包含関係で順序付けした格子であると仮定されます。これは、多くの応用においてそのような格子のみが考慮されるという事実を反映しています。この場合、通常は関数fの不動点となる性質を持つ最小の集合を探します。抽象解釈では、クナスター・タルスキーの定理と、最小および最大の不動点を与える公式が広く利用されます。

クナスター・タルスキの定理は、カントール・ベルンシュタイン・シュレーダーの定理^{[ 5 ] [ 6 ]}の簡単な証明を与えるために使用でき、バナッハ・タルスキのパラドックスを確立するためにも使用されます。

クナスター・タルスキの定理の弱いバージョンは順序集合に対して定式化できるが、より複雑な仮定が必要となる。例えば、次のようになる。

L を最小要素(最下)を持つ半順序集合 とし、f : L → L を単調関数とする。さらに、L 内に f ( u ) ≤ uとなる u が存在し、部分集合内の任意の鎖が${\displaystyle \{x\in L\mid x\leq f(x),x\leq u\}}$上限を持つ。すると、f は最小不動点を持つ。^{[ 7 ]}

これは、不変集合に関する様々な定理を得るために応用できる。例えば、オクの定理などである。

X の (閉じた) 空でない部分集合の族上の単調写像 F  : P ( X ) → P ( X )について、以下は同値である: (o) F は、P ( X )内の A を許容し、${\displaystyle A\subseteq F(A)}$(i) F は P ( X )において不変集合 A を許容する。${\displaystyle A=F(A)}$(ii) F は最大不変集合 A を持つ、(iii) F は最大の不変集合 A を持つ。

特に、クナスター・タルスキ原理を用いることで、非縮小不連続（多値）反復関数系のグローバルアトラクターの理論を構築することができる。弱縮小反復関数系については、カントロビッチ定理（タルスキ・カントロビッチ不動点原理としても知られる）で十分である。

順序集合に対する不動点原理の他の応用例は、微分方程式、積分方程式、および作用素方程式の理論から得られる。

定理を改めて述べましょう。

完全な格子の場合${\displaystyle \langle L,\leq \rangle }$単調関数${\displaystyle f\colon L\rightarrow L}$L上では、 fのすべての不動点の集合も完全束である。${\displaystyle \langle P,\leq \rangle }$、 と：

• ${\displaystyle \bigvee P=\bigvee \{x\in L\mid x\leq f(x)\}}$fの最大の固定点として
• ${\displaystyle \bigwedge P=\bigwedge \{x\in L\mid x\geq f(x)\}}$fの最小不動点として。

証明。まず、 P が最小元と最大元の両方を持つことを示すことから始めます。D = { x | x ≤ f ( x )}とし、 x ∈ Dとします(少なくとも 0 _LがDに属することはわかっています)。すると、 fは単調であるため、f ( x ) ≤ f ( f ( x ))となり、つまりf ( x ) ∈ Dとなります。

さあ${\displaystyle u=\bigvee D}$( u が存在するのは、D ⊆ Lであり、 L が完全束であるためです。) 次に、すべてのx ∈ Dに対して、 x ≤ uおよびf ( x ) ≤ f ( u )が成り立つので、x ≤ f ( x ) ≤ f ( u )となります。したがって、f ( u ) はDの上限ですが、u は最小上限なので、u ≤ f ( u )、つまりu ∈ Dとなります。次に、f ( u ) ∈ D ( f ( u ) ≤ f ( f ( u )))となり、 f ( u ) ≤ uとなり、これからf ( u ) = uが導かれます。すべての不動点がDにあるので、uはfの最大不動点となります。

関数fは双対 (完全) 格子上で単調である${\displaystyle \langle L^{op},\geq \rangle }$先ほど証明したように、その最大不動点は存在します。それはLの最小不動点であるため、Pは最小要素と最大要素を持ちます。つまり、より一般的に言えば、完全束上のすべての単調関数は最小不動点と最大不動点を持ちます。

Lのa、bに対して、境界aとbを持つ閉区間を [ a、b ] と表記します。 : { x ∈ L | a ≤ x ≤ b }。a ≤ bの場合、⟨ [ a、b ], ≤ ⟩は完全束です。

Pが完全束であることはまだ証明されていない。${\displaystyle 1_{L}=\bigvee L}$、W ⊆ Pおよび${\displaystyle w=\bigvee W}$。 f ([ w , 1 _L ]) ⊆ [ w , 1 _L ]であることを示します。実際、すべてのx ∈ Wに対してx = f ( x )であり、 w はWの最小上界であるため、x ≤ f ( w )です。特に、w ≤ f ( w )です。次に、y ∈ [ w , 1 _L ]から、 w ≤ f ( w ) ≤ f ( y )が成り立ち、f ( y ) ∈ [ w , 1 _L ]または単にf ([ w , 1 _L ]) ⊆ [ w , 1 _L ]となります。これにより、 f を完全束 [ w , 1 _L ]上の関数として見ることができます。すると、f はそこに最小不動点を持ち、 Wの最小上界が得られます。我々は、 Pの任意の部分集合が上限を持つこと、すなわちPが完全束であることを示した。

Chang、Lyuu、Ti ^{[ 8 ]}は、順序保存関数が値オラクルによって与えられる場合、全順序格子におけるタルスキー不動点を見つけるアルゴリズムを提示している。彼らのアルゴリズムは、${\displaystyle O(\log L)}$クエリ、ここでLは格子内の要素の数です。対照的に、一般的な格子 (オラクルとして与えられる) については、下限が証明されています。${\displaystyle \Omega (L)}$クエリ。

Deng、Qi、Ye ^{[ 9 ]}は、タルスキー不動点を見つけるためのいくつかのアルゴリズムを提示しています。彼らは、要素ごとの順序付けと辞書式順序付けという 2 種類の格子を考慮しています。彼らは、関数fへの入力として、値オラクルまたは多項式関数という 2 種類を考慮しています。彼らのアルゴリズムの実行時間計算量は次のようになります (ここで、dは次元の数、N _iは次元iの要素の数です)。

これらのアルゴリズムは二分探索に基づいている。一方、与えられた不動点が一意であるかどうかを判断することは計算上困難である。

d = 2の場合、コンポーネントごとの格子と値オラクルの場合、複雑さは${\displaystyle O(\log ^{2}L)}$が最適である。^{[ 10 ]}しかし、d > 2 の場合、より高速なアルゴリズムが存在する。

• Fearnley、Palvolgyi、Savani ^{[ 11 ]}は、${\displaystyle O(\log ^{2\lceil d/3\rceil }L)}$クエリ。特に、d = 3 の場合、${\displaystyle O(\log ^{2}L)}$問い合わせが必要です。
• ChenとLi ^{[ 12 ]}は、${\displaystyle O(\log ^{\lceil (d+1)/2\rceil }L)}$クエリ。

タルスキの不動点定理は、スーパーモジュラーゲームに応用できる。^{[ 9 ]}スーパーモジュラーゲーム（戦略的補完ゲームとも呼ばれる^{[ 13 ]}）は、各プレイヤーの効用関数の差が増加するゲームであり、プレイヤーの最適反応は、他のプレイヤーの戦略の弱増加関数となる。例えば、2つの企業間の競争ゲームを考えてみよう。各企業は、研究にどれだけの資金を費やすかを決定する必要がある。一般に、一方の企業が研究に多く費やす場合、もう一方の企業の最適反応は、研究に多く費やすことである。クールノー競争、ベルトラン競争、投資ゲームなど、いくつかの一般的なゲームはスーパーモジュラーゲームとしてモデル化できる。

最適応答関数は単調であるため、タルスキーの不動点定理を用いて、スーパーモジュラーゲームにおける純粋戦略ナッシュ均衡（PNE）の存在を証明することができる。さらに、トプキス^{[ 14 ]}は、スーパーモジュラーゲームのPNEの集合が完全束であることを示し、したがって、このゲームには「最小」PNEと「最大」PNEが存在することを示した。

Echenique ^{[ 15 ] は}、スーパーモジュラーゲームですべての PNE を見つけるアルゴリズムを提示しています。彼のアルゴリズムは、まず最良応答シーケンスを使用して最小および最大の PNE を見つけ、次にいくつかの戦略を削除して、すべての PNE が見つかるまで繰り返します。彼のアルゴリズムは最悪の場合指数関数的ですが、実際には高速に実行されます。Deng、Qi、Ye ^{[ 9 ] は}、ゲームに関連付けられた順序保存写像の Tarski 不動点を見つけることで、PNE を効率的に計算できることを示しました。

• モーダルμ計算

• Andrzej Granas およびJames Dugundji (2003).不動点理論. Springer-Verlag、ニューヨーク。ISBN 978-0-387-00173-9。
• フォースター、T. (2003年7月21日).論理、帰納法、集合. ケンブリッジ大学出版局. ISBN 978-0-521-53361-4。

• S. Hayashi (1985). 「タルスキーの不動点としての自己相似集合」 .数理科学研究所紀要. 21 (5): 1059–1066 . doi : 10.2977/prims/1195178796 .
• J. Jachymski; L. Gajek; K. Pokarowski (2000). "The Tarski-Kantorovitch principle and the theory of iterated function systems" . Bull. Austral. Math. Soc. 61 (2): 247– 261. doi : 10.1017/S0004972700022243 .
• EA Ok (2004). 「自己相似性とゲームへの応用を伴う閉じた対応の固定集合理論」Nonlinear Anal . 56 (3): 309–330 . CiteSeerX 10.1.1.561.4581 . doi : 10.1016/j.na.2003.08.001 . 
• BSW Schröder (1999). 「不動点性質のアルゴリズム」 . Theoret. Comput. Sci . 217 (2): 301– 358. doi : 10.1016/S0304-3975(98)00273-4 .
• S. Heikkilä (1990). 「不連続性を含む微分方程式および積分方程式への応用を伴う一般化反復法による不動点について」Nonlinear Anal . 14 (5): 413–426 . doi : 10.1016/0362-546X(90)90082-R .
• R. ウール (2003)。 「準単調増加マッピングの最小および最大の不動点」。数学的表現。248–249 : 204–210 .土井: 10.1002/mana.200310016。S2CID 120679842。 

• JB Nation、「格子理論に関するノート」。
• 初等的な組み合わせ論の問題への応用：100ページ、100個の補題がある本が与えられたとき、索引と同じページに書かれた補題が存在することを証明せよ。