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

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

( 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 ^α+1 = f ( f ^α ) であり、極限順序数 γ に対するf ^{γ は}、 γ より小さいすべての β 順序数に対するf ^βの最小の上限です。 ^[4]双対定理は最大不動点に対しても成り立ちます。 

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

クナスター・タルスキーの定理はカントール・ベルンシュタイン・シュレーダーの定理 ^{[5] [6]}の簡単な証明に利用され、バナッハ・タルスキーのパラドックスの証明にも利用されている。

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

L を最小元（底）を持つ半順序集合とし、 f ​​ : L → L を単調関数とする。さらに、 L に u が存在し、 f ( u ) ≤ u であり、サブセット内の任意のチェーンに上限があるとする。このとき、 f は最小の不動点を許容する。${\displaystyle \{x\in L\mid x\leq f(x),x\leq u\}}$

これを応用すると、不変集合に関するさまざまな定理が得られます。たとえば、Ok の定理です。

X の (閉じた) 空でない部分集合の族上の単調写像 F  : P ( X  ) → P ( X  )に対して、次のものは同値です: (o) F は P ( X  ) stに A を許容します、(i) F は P ( X  ) ieに不変集合 A を許容します、(ii) F は最大不変集合 A を許容します、(iii) F は最大不変集合 A を許容します。${\displaystyle A\subseteq F(A)}$${\displaystyle A=F(A)}$

特に、クナスター・タルスキ原理を使用すると、非収縮不連続（多値）反復関数システムのグローバルアトラクターの理論を展開できます。弱収縮反復関数システムの場合、カントロビッチ定理（タルスキ・カントロビッチ不動点原理としても知られています）で十分です。

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

定理をもう一度述べてみましょう。

L上の完全格子と単調関数に対して、 fのすべての不動点の集合も完全格子であり、次のようになります。 ${\displaystyle \langle L,\leq \rangle }$${\displaystyle f\colon L\rightarrow L}$${\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となります。

ここで、 ( D ⊆ LかつLが完全格子であるため、u が存在する)とします。すると、すべての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の最大の不動点となります。 ${\displaystyle u=\bigvee D}$

関数f は、双対（完全）格子上で単調です。先ほど証明したように、その最大不動点が存在します。これはLの最小不動点なので、P には最小元と最大元があり、より一般的には、完全格子上のすべての単調関数には最小不動点と最大不動点があります。 ${\displaystyle \langle L^{op},\geq \rangle }$

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

P が完全格子であることを証明する必要があります。 、W ⊆ P、 とします。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 ]上の関数として見ることができます。するとそこに最小の不動点があり、 Wの最小上限が得られます。Pの任意の部分集合には上限があること、つまりP が完全格子であること を示しました。${\displaystyle 1_{L}=\bigvee L}$${\displaystyle w=\bigvee W}$

Chang、Lyuu、Ti ^[7]は、順序保存関数が値オラクルによって与えられた場合に、完全に順序付けられた格子内のTarski不動点を見つけるアルゴリズムを提示している。彼らのアルゴリズムはクエリを必要とし、ここでLは格子内の要素の数である。対照的に、一般的な格子（オラクルとして与えられた）の場合、彼らはクエリの下限を証明している。 ${\displaystyle O(\log L)}$${\displaystyle \オメガ (L)}$

Deng、Qi、Ye ^[8]は、Tarski不動点を見つけるためのいくつかのアルゴリズムを提示している。彼らは、成分順と辞書式順序の2種類の格子を考慮している。彼らは、関数fに対する2種類の入力、すなわち値オラクル、または多項式関数を考慮している。彼らのアルゴリズムの実行時複雑度は次のようになる（dは次元数、N _iは次元iの要素数）。

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

d =2の場合、成分ごとの格子と値オラクルの計算量は最適です。^[9]しかし、 d >2の場合、より高速なアルゴリズムがあります。 ${\displaystyle O(\log ^{2}L)}$

• Fearnley、Palvolgyi、Savani ^[10]はクエリのみを使用するアルゴリズムを提示した。特にd =3の場合、クエリのみが必要となる。${\displaystyle O(\log ^{2\lceil d/3\rceil }L)}$${\displaystyle O(\log ^{2}L)}$
• ChenとLi ^[11]はクエリのみを使用するアルゴリズムを提示した。${\displaystyle O(\log ^{\lceil (d+1)/2\rceil }L)}$

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

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

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

• 様相μ計算

• Andrzej Granas とJames Dugundji (2003)。『固定点理論』。Springer -Verlag、ニューヨーク。ISBN 978-0-387-00173-9。
• フォースター、T. (2003-07-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)。「タルスキ＝カントロビッチ原理と反復関数システムの理論」Bull. Austral. Math. Soc . 61 (2): 247–261. doi : 10.1017/S0004972700022243。
• EA Ok (2004). 「自己相似性とゲームへの応用を伴う閉対応の固定集合論」.非線形アナル. 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). 「一般化反復法による不動点について、および不連続性を含む微分および積分方程式への応用」。非線形分析。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個の補題がある本が与えられたとき、その索引と同じページにいくつかの補題が書かれていることを証明してください。