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

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

Пусть ( 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 допускает наименьшую неподвижную точку . $\{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 $A\subseteq F(A)$ ( X ) ie , (ii) F допускает максимальное инвариантное множество A, (iii) F допускает наибольшее инвариантное множество A. $А=Ф(А)$

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

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

Доказательство

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

Для полной решетки и монотонной функции на L множество всех неподвижных точек f также является полной решеткой , причем: $\langle L,\leq \rangle$ $f\двоеточие L\rightarrow L$ $\langle P,\leq \rangle$

$\bigvee P=\bigvee \{x\in L\mid x\leq f(x)\}$ как наибольшая неподвижная точка f
$\bigwedge P=\bigwedge \{x\in L\mid x\geq f(x)\}$ как наименьшая неподвижная точка f .

Доказательство. Начнем с того, что покажем, что P имеет как наименьший, так и наибольший элемент. Пусть $D = {x | x \leq f (x)}$ и $x \in D$ (мы знаем, что по крайней мере 0 _L принадлежит D ). Тогда, поскольку f монотонна, мы имеем $f (x) \leq f (f (x))$ , то есть $f (x) \in D$ .

Теперь пусть ( u существует, потому что $D$ $\subseteq$ $L$ и L — полная решетка). Тогда для всех $x$ $\in$ $D$ верно, что $x$ $\leq$ $u$ и $f$ $($ $x$ $) \leq$ $f$ $($ $u$ $)$ , поэтому $x$ $\leq$ $f$ $($ $x$ $) \leq$ $f$ $($ $u$ $)$ . Следовательно, f ( u ) является верхней границей D , но u является точной верхней границей, поэтому $u$ $\leq$ $f$ $($ $u$ $)$ , т. е. $u$ $\in$ $D$ . Тогда $f$ $($ $u$ $) \in$ $D$ (потому что $f$ $($ $u$ $) \leq$ $f$ $($ $f$ $($ $u$ $)))$ и поэтому $f$ $($ $u$ $) \leq$ $u$ , из чего следует f ( u ) = u . Поскольку каждая неподвижная точка принадлежит D , мы получаем, что u является наибольшей неподвижной точкой f . $u=\bigvee D$

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

Для a , b в L мы пишем [ a , b ] для замкнутого интервала с границами a и $b : {x \in L | a \leq x \leq b}$ . Если a ≤ b , то ⟨[ a , b ], ≤⟩ является полной решеткой.

Осталось доказать, что P — полная решетка. Пусть , $W$ $\subseteq$ $P$ и . Покажем, что $f$ $([$ $w$ $, 1$ $L$ $]) \subseteq [$ $w$ $, 1$ $L$ $]$ . Действительно, для любого $x$ $\in$ $W$ имеем x = f ( x ) и поскольку w — точная верхняя граница W , $x$ $\leq$ $f$ $($ $w$ $)$ . В частности, $w$ $\leq$ $f$ $($ $w$ $)$ . Тогда из $y$ $\in [$ $w$ $, 1$ $L$ $]$ следует, что $w$ $\leq$ $f$ $($ $w$ $) \leq$ $f$ $($ $y$ $)$ , что дает $f$ $($ $y$ $) \in [$ $w$ $, 1$ $L$ $]$ или просто $f$ $([$ $w$ $, 1$ $L$ $]) \subseteq [$ $w$ $, 1$ $L$ $]$ . Это позволяет нам рассматривать f как функцию на полной решетке [ w , 1 _L ]. Тогда она имеет там наименьшую неподвижную точку, что дает нам точную верхнюю границу W . Мы показали, что произвольное подмножество P имеет супремум, то есть P является полной решеткой. $1_{L}=\bigvee L$ $w=\bigvee W$

Вычисление фиксированной точки Тарского

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

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

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

При d = 2 для покомпонентной решетки и оракула значений сложность оптимальна. ^[9] Но при d > 2 существуют более быстрые алгоритмы: $O(\log ^{2}L)$

Fearnley, Palvolgyi и Savani ^[10] представили алгоритм, использующий только запросы. В частности, для d =3 нужны только запросы. $O(\log ^{2\lceil d/3\rceil }L)$ $O(\log ^{2}L)$
Чэнь и Ли ^[11] представили алгоритм, использующий только запросы. $O(\log ^{\lceil (d+1)/2\rceil }L)$

Применение в теории игр

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

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

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

Смотрите также

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

Примечания

^ Альфред Тарский (1955). «Теорема о неподвижной точке в теории решеток и ее приложения». Pacific Journal of Mathematics . 5 (2): 285–309. doi : 10.2140/pjm.1955.5.285 .
^ Б. Кнастер (1928). «Теорема о функциях ансамблей». Энн. Соц. Полон. Математика. 6 : 133–134. Совместно с А. Тарским.
^ Энн К. Дэвис (1955). «Характеристика полных решеток». Pacific Journal of Mathematics . 5 (2): 311–319. doi : 10.2140/pjm.1955.5.311 .
^ Кусо, Патрик; Кусо, Радхия (1979). «Конструктивные версии теорем Тарского о неподвижной точке». Pacific Journal of Mathematics . 82 : 43–57. doi : 10.2140/pjm.1979.82.43 .
^ Уль, Роланд. «Теорема Тарского о неподвижной точке». MathWorld .Пример 3.
^ Дэйви, Брайан А.; Пристли, Хилари А. (2002). Введение в решетки и порядок (2-е изд.). Cambridge University Press . стр. 63, 4. ISBN 9780521784511.
^ Чанг, Чинг-Лю; Люу, Ю-Дау; Ти, Йен-У (2008-07-23). «Сложность теоремы Тарского о неподвижной точке». Теоретическая информатика . 401 (1): 228–235. doi :10.1016/j.tcs.2008.05.005. ISSN 0304-3975.
^ abc Dang, Chuangyin; Qi, Qi; Ye, Yinyu (2020-05-01). Вычисления и сложности неподвижных точек Тарского и супермодулярных игр (отчет). arXiv.org.
^ Этессами, Куша; Пападимитриу, Христос; Рубинштейн, Авиад; Яннакакис, Михалис (2020). Видик, Томас (ред.). «Теорема Тарского, супермодулярные игры и сложность равновесий». 11-я конференция по инновациям в теоретической информатике (ITCS 2020) . Международные труды Лейбница по информатике (LIPIcs). 151. Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 18:1–18:19. doi : 10.4230/LIPIcs.ITCS.2020.18 . ISBN 978-3-95977-134-4. S2CID 202538977.
^ Фернли, Джон; Палвёлдьи, Дёмётёр; Савани, Рахул (11 октября 2022 г.). «Более быстрый алгоритм поиска фиксированных точек Тарского». Транзакции ACM на алгоритмах . 18 (3): 23:1–23:23. arXiv : 2010.02618 . дои : 10.1145/3524044. ISSN 1549-6325. S2CID 222141645.
^ Чэнь, Си; Ли, Юхао (2022-07-13). «Улучшенные верхние границы для поиска неподвижных точек Тарского». Труды 23-й конференции ACM по экономике и вычислениям . EC '22. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 1108–1118. arXiv : 2202.05913 . doi :10.1145/3490486.3538297. ISBN 978-1-4503-9150-4. S2CID 246823965.
^ Vives, Xavier (1990-01-01). «Равновесие Нэша со стратегическими взаимодополняемостями». Журнал математической экономики . 19 (3): 305–321. doi :10.1016/0304-4068(90)90005-T. ISSN 0304-4068.
^ Топкис, Дональд М. (1 ноября 1979 г.). «Точки равновесия в субмодулярных играх с ненулевой суммой n лиц». Журнал SIAM по управлению и оптимизации . 17 (6): 773–787. doi :10.1137/0317054. ISSN 0363-0129.
^ Эченик, Федерико (2007-07-01). «Нахождение всех равновесий в играх стратегических дополнений». Журнал экономической теории . 135 (1): 514–532. doi :10.1016/j.jet.2006.06.001. ISSN 0022-0531.

Ссылки

Анджей Гранас и Джеймс Дугунджи (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. дои : 10.1002/мана.200310016. S2CID 120679842.

Внешние ссылки

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