Введение
В математических областях теории порядка и решёток теорема Кнастера — Тарского, названная в честь Бронислава Кнастера и Альфреда Тарского, утверждает следующее:
Пусть (L, ≤) — полная решётка и пусть f : L → L — функция, сохраняющая порядок (монотонная) относительно ≤. Тогда множество неподвижных точек f в L образует полную решётку относительно ≤. Именно Тарский сформулировал результат в наиболее общей форме, поэтому теорема часто известна как теорема Тарского о неподвижной точке. Ранее Кнастер и Тарский установили этот результат для частного случая, когда L является решёткой подмножеств множества, решёткой булеана. Теорема имеет важное применение в формальной семантике языков программирования и абстрактной интерпретации, а также в теории игр. Обобщение, близкое к обратной теореме, было доказано Энн С. Дэвис: если каждая сохраняющая порядок функция f : L → L на решётке L имеет неподвижную точку, то L является полной решёткой.
Последствия: наименьшие и наибольшие фиксированные точки
Поскольку полные решетки не могут быть пустыми (они должны содержать супремум и инфимум пустого множества), теорема в частности гарантирует существование как минимум одной неподвижной точки функции f, и даже существование наименьшей неподвижной точки (или наибольшей неподвижной точки). Во многих практических случаях это наиболее важное следствие теоремы. Наименьшая неподвижная точка f – это наименьший элемент x, такой что f(x) = x, или, эквивалентно, такой что f(x) ≤ x; двойственное утверждение верно для наибольшей неподвижной точки, которая является наибольшим элементом x, таким что f(x) = x. Если f(lim xn) = lim f(xn) для всех возрастающих последовательностей xn, то наименьшая неподвижная точка f равна lim f n(0), где 0 – наименьший элемент L, что дает более "конструктивную" версию теоремы. (См.: Теорема о неподвижной точке Клини.) В более общем случае, если f монотонна, то наименьшая неподвижная точка f является стационарным пределом f α(0), рассматривая α как порядковые числа, где f α определяется трансфинитной индукцией: f α+1 = f(f α), а f γ для предельного порядкового числа γ является наименьшей верхней гранью f β для всех порядковых чисел β, меньших γ. Двойственная теорема справедлива для наибольшей неподвижной точки. Например, в теоретической информатике наименьшие неподвижные точки монотонных функций используются для определения семантики программ, см. пример. Часто используется более специализированная версия теоремы, в которой L предполагается решеткой всех подмножеств определенного множества, упорядоченной включением подмножеств. Это отражает тот факт, что во многих приложениях рассматриваются только такие решетки. В этом случае обычно ищут наименьшее множество, обладающее свойством быть неподвижной точкой функции f. Абстрактная интерпретация широко использует теорему Кнастера — Тарского и формулы для вычисления наименьших и наибольших неподвижных точек. Теорему Кнастера — Тарского можно использовать для получения простого доказательства теоремы Кантора — Бернштейна — Шредера.
Более слабые версии теоремы
Более слабые версии теоремы Кнастера — Тарского могут быть сформулированы для упорядоченных множеств, но требуют более сложных предположений. Например:
Пусть L — частично упорядоченное множество с наименьшим элементом (нижней гранью) и пусть f : L → L — монотонная функция. Кроме того, предположим, что существует элемент u в L, такой что f(u) ≤ u, и что любая цепь в подмножестве имеет супремум. Тогда f имеет наименьшую неподвижную точку. Это можно применить для получения различных теорем об инвариантных множествах, например, теоремы Ока:
Для монотонного отображения F : P(X) → P(X) на семействе (замкнутых) непустых подмножеств X, следующие утверждения эквивалентны: (o) F имеет A в P(X) такое, что, (i) F имеет инвариантное множество A в P(X), то есть, (ii) F имеет максимальное инвариантное множество A, (iii) F имеет наибольшее инвариантное множество A. В частности, используя принцип Кнастера — Тарского, можно разработать теорию глобальных аттракторов для неконтрактных разрывных (многозначных) итерационных функциональных систем. Для слабоконтрактных итерационных функциональных систем достаточно теоремы Канторовича (известной также как принцип неподвижной точки Тарского — Канторовича). Другие применения принципов неподвижной точки для упорядоченных множеств исходят из теории дифференциальных, интегральных и операторных уравнений.
Применение в теории игр
Теорема о фиксированной точке Тарского находит применение в супермодульных играх. Супермодульная игра (также называемая игрой стратегических взаимодополнений) – это игра, в которой функция полезности каждого игрока обладает возрастающими разностями, вследствие чего наилучший ответ игрока является слабо возрастающей функцией стратегий других игроков. Например, рассмотрим игру конкуренции между двумя фирмами. Каждая фирма должна решить, какую сумму потратить на исследования. В общем случае, если одна фирма увеличивает расходы на исследования, наилучшим ответом другой фирмы будет также увеличить расходы на исследования. Некоторые распространенные игры можно моделировать как супермодульные игры, например, конкуренция Курно, конкуренция Бертрана и игры на инвестиции. Поскольку функции наилучшего ответа монотонны, теорема о фиксированной точке Тарского может быть использована для доказательства существования равновесия Нэша в чистых стратегиях (PNE) в супермодульной игре. Более того, Топкис показал, что множество PNE супермодульной игры является полной решеткой, поэтому игра имеет "наименьшую" PNE и "наибольшую" PNE. Эхеник представляет алгоритм для нахождения всех PNE в супермодульной игре. Его алгоритм сначала использует последовательности наилучших ответов для определения наименьшей и наибольшей PNE, затем исключает некоторые стратегии и повторяет процесс, пока не будут найдены все PNE. В худшем случае алгоритм имеет экспоненциальную сложность, но на практике работает быстро. Дэн, Ци и Е показывают, что PNE можно эффективно вычислить, найдя фиксированную точку Тарского для отображения, сохраняющего порядок, связанного с игрой.