Теорема Кнастера–Тарского

В математической области порядка и теории решёток теорема Кнастера –Тарского , названная в честь Бронислава Кнастера и Альфреда Тарского , утверждает следующее:

Пусть ( L , ≤) — полная решетка и пусть f : L → L — сохраняющая порядок (монотонная) функция wrt ≤ . Тогда множество неподвижных точек f в L образует полную решетку относительно ≤ .

Именно Тарский сформулировал результат в наиболее общей форме, ^[1] и поэтому теорема часто известна как теорема Тарского о неподвижной точке . Некоторое время назад Кнастер и Тарский установили результат для особого случая, когда L — решетка подмножеств множества , решетка степенного множества . ^[2]

Теорема имеет важные приложения в формальной семантике языков программирования и абстрактной интерпретации , а также в теории игр .

Своего рода обратная теорема была доказана Энн К. Дэвис : если каждая сохраняющая порядок функция f  : L → L на решетке L имеет неподвижную точку, то L является полной решеткой. ^[3]

Поскольку полные решетки не могут быть пустыми (они должны содержать супремум и инфимум пустого множества), теорема, в частности, гарантирует существование по крайней мере одной неподвижной точки f и даже существование наименьшей неподвижной точки (или наибольшей неподвижной точки ). Во многих практических случаях это является наиболее важным следствием теоремы.

Наименьшая неподвижная точка f — это наименьший элемент x такой, что f ( x ) = x , или, что эквивалентно, такой, что f ( x ) ≤ x ; двойственное утверждение справедливо для наибольшей неподвижной точки , наибольшего элемента x такого, что f ( x ) = x .

Если f (lim x _n ) = lim f ( x _n ) для всех возрастающих последовательностей 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 — монотонная функция . Далее, предположим, что существует u в L, такое что f ( u ) ≤ u и что любая цепь в подмножестве имеет супремум. Тогда f допускает наименьшую неподвижную точку .${\displaystyle \{x\in L\mid x\leq f(x),x\leq u\}}$

Это можно применить для получения различных теорем об инвариантных множествах , например, теоремы Ока:

Для монотонного отображения F  : P ( X  ) → P ( X  ) на семействе (замкнутых) непустых подмножеств X следующие условия эквивалентны: (o) F допускает A в P ( X  ) st , (i) F допускает инвариантное множество A в P${\displaystyle A\subseteq F(A)}$ ( X  ) ie , (ii) F допускает максимальное инвариантное множество A, (iii) F допускает наибольшее инвариантное множество A.${\displaystyle А=Ф(А)}$

В частности, используя принцип Кнастера-Тарского, можно развить теорию глобальных аттракторов для неконтрактных разрывных (многозначных) итерационных систем функций . Для слабоконтрактных итерационных систем функций достаточно теоремы Канторовича (известной также как принцип неподвижной точки Тарского-Канторовича).

Другие приложения принципов неподвижной точки для упорядоченных множеств вытекают из теории дифференциальных , интегральных и операторных уравнений.

Переформулируем теорему.

Для полной решетки и монотонной функции на L множество всех неподвижных точек f также является полной решеткой , причем:${\displaystyle \langle L,\leq \rangle}$${\displaystyle f\двоеточие 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 .

Теперь пусть ( 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 .${\displaystyle u=\bigvee D}$

Функция f монотонна на двойственной (полной) решетке . Как мы только что доказали, существует ее наибольшая неподвижная точка. Это наименьшая неподвижная точка L , поэтому P имеет наименьший и наибольший элементы, то есть, в более общем смысле, каждая монотонная функция на полной решетке имеет наименьшую неподвижную точку и наибольшую неподвижную точку.${\displaystyle \langle L^{op},\geq \rangle}$

Для a , b в L мы пишем [ 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}$

Чанг, Люу и Ти ^[7] представляют алгоритм для поиска неподвижной точки Тарского в полностью упорядоченной решетке, когда функция сохранения порядка задана значением оракула . Их алгоритм требует запросов, где L — число элементов в решетке. Напротив, для общей решетки (заданной как оракул) они доказывают нижнюю границу запросов.${\displaystyle O(\log L)}$${\displaystyle \Омега (L)}$

Дэн, Ци и Йе ^[8] представляют несколько алгоритмов для поиска неподвижной точки Тарского. Они рассматривают два вида решеток: покомпонентное упорядочение и лексикографическое упорядочение . Они рассматривают два вида входных данных для функции f : значение оракула или полиномиальная функция. Их алгоритмы имеют следующую сложность выполнения (где d — число измерений, а N _i — число элементов в измерении i ):

Вход Решетка	Полиномиальная функция	Значение оракула
Покомпонентно	${\displaystyle O(\operatorname {poly} (\log L)\cdot \log N_{1}\cdots \log N_{d})}$	${\displaystyle O(\log N_{1}\cdots \log N_{d})\approx O(\log ^{d}L)}$
Лексикографический	${\displaystyle O(\operatorname {poly} (\log L)\cdot \log L)}$	${\displaystyle O(\log L)}$

Алгоритмы основаны на бинарном поиске . С другой стороны, определение того, является ли заданная фиксированная точка уникальной, является вычислительно сложным:

Вход Решетка	Полиномиальная функция	Значение оракула
Покомпонентно	coNP-полный	${\displaystyle \Theta (N_{1}+\cdots +N_{d})}$
Лексикографический	coNP-полный	${\displaystyle \Theta (L)}$

При 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)}$
• Чэнь и Ли ^[11] представили алгоритм, использующий только запросы.${\displaystyle O(\log ^{\lceil (d+1)/2\rceil }L)}$

Теорема Тарского о неподвижной точке имеет приложения к супермодулярным играм . ^[8] Супермодулярная игра (также называемая игрой стратегических дополнений ^[12] ) — это игра , в которой функция полезности каждого игрока имеет возрастающие различия , поэтому наилучшим ответом игрока является слабо возрастающая функция стратегий других игроков. Например, рассмотрим игру конкуренции между двумя фирмами. Каждая фирма должна решить, сколько денег потратить на исследования. В общем, если одна фирма тратит больше на исследования, лучшим ответом другой фирмы будет также потратить больше на исследования. Некоторые общие игры можно смоделировать как супермодулярные игры, например, соревнование Курно , соревнование Бертрана и инвестиционные игры .

Поскольку функции наилучшего ответа монотонны, теорема Тарского о неподвижной точке может быть использована для доказательства существования равновесия Нэша в чистой стратегии (PNE) в супермодулярной игре. Более того, Топкис ^[13] показал, что множество PNE супермодулярной игры представляет собой полную решетку, поэтому игра имеет «наименьшее» PNE и «наибольшее» PNE.

Эченик ^[14] представляет алгоритм для поиска всех PNE в супермодулярной игре. Его алгоритм сначала использует последовательности наилучших ответов для поиска наименьшего и наибольшего PNE; затем он удаляет некоторые стратегии и повторяет, пока не будут найдены все PNE. Его алгоритм является экспоненциальным в худшем случае, но быстро работает на практике. Дэн, Ци и Йе ^[8] показывают, что PNE можно эффективно вычислить, найдя неподвижную точку Тарского отображения, сохраняющего порядок, связанного с игрой.

• Модальное μ-исчисление

• Анджей Гранас и Джеймс Дугунджи (2003). Теория неподвижной точки . Springer-Verlag , Нью-Йорк. ISBN 978-0-387-00173-9.
• Форстер, Т. (2003-07-21). Логика, индукция и множества . Cambridge University Press. 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). «Теория фиксированных множеств для замкнутых соответствий с приложениями к самоподобию и играм». 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.
• Р. Уль (2003). «Наименьшие и наибольшие неподвижные точки квазимонотонно возрастающих отображений». Mathematische Nachrichten . 248–249 : 204–210 . doi :10.1002/mana.200310016. S2CID  120679842.

• Дж. Б. Нейшн, Заметки по теории решеток.
• Приложение к элементарной комбинаторной задаче: дана книга со 100 страницами и 100 леммами. Докажите, что на той же странице, что и ее индекс, написана некоторая лемма.