В математических областях порядка и решетки теории , то теорема Кнастера-Тарского , названный в честь Бронислав Кнастера и Тарский , говорится следующее:
- Пусть (L, ≤) - полная решетка и пусть f: L → L - функция, сохраняющая порядок (wrt ≤). Тогда множество из фиксированных точек Р в L также образует полную решетку под ≤.
Именно Тарский сформулировал результат в его наиболее общей форме [1], поэтому эту теорему часто называют теоремой Тарского о неподвижной точке . Некоторое время назад Кнастер и Тарский установили результат для частного случая, когда L - решетка подмножеств множества, решетка множества степеней. [2]
Теорема имеет важные приложения в формальной семантике языков программирования и абстрактной интерпретации .
Отчасти обратное этой теореме было доказано Энн К. Дэвис : если каждая сохраняющая порядок функция f: L → L на решетке L имеет неподвижную точку, то L является полной решеткой. [3]
Последствия: наименьшая и наибольшая фиксированные точки.
Поскольку полные решетки не могут быть пустыми (они должны содержать верхнюю / нижнюю границу пустого множества), теорема, в частности, гарантирует существование по крайней мере одной неподвижной точки f и даже существование наименьшей (или наибольшей ) неподвижной точки. Во многих практических случаях это самое важное следствие теоремы.
Мере Fixpoint из F является наименьшим элементом х таким образом, что F ( х ) = х , или, что эквивалентно, таким образом, что F ( х ) ≤ х ; двойного справедливо для наибольшей фиксированной точки , наибольший элемент х такой , что F ( х ) = х .
Если f (lim x n ) = lim f ( x n ) для всех возрастающих последовательностей x n , то наименьшая фиксированная точка f - это lim f n (0), где 0 - наименьший элемент L, что дает более "конструктивный" версия теоремы. (См .: Теорема Клини о неподвижной точке .) В более общем смысле, если f монотонна, то наименьшая неподвижная точка f является стационарным пределом f α (0), принимая α по ординалам , где f α определяется трансфинитной индукцией : е α + 1 = F ( F & alpha ; ) и F γ для предельного порядкового γ является не менее верхняя граница из ф р для всех бета порядковых меньше , чем у. Двойственная теорема верна для наибольшей неподвижной точки.
Так , например, в области теоретической информатики , хотя бы фиксированные точки из монотонных функций используются для определения семантики программы . Часто используется более специализированная версия теоремы, где L предполагается решеткой всех подмножеств определенного набора, упорядоченных по включению подмножеств. Это отражает тот факт, что во многих приложениях рассматриваются только такие решетки. Затем обычно ищут наименьшее множество, которое имеет свойство быть фиксированной точкой функции f . Абстрактная интерпретация широко использует теорему Кнастера – Тарского и формулы, дающие наименьшую и наибольшую неподвижные точки.
Теорема Кнастера – Тарского может быть использована для простого доказательства теоремы Кантора – Бернштейна – Шредера . [4] [5]
Более слабые версии теоремы
Более слабые версии теоремы Кнастера – Тарского могут быть сформулированы для упорядоченных множеств, но содержат более сложные предположения. Например:
- Пусть L - частично упорядоченное множество с наименьшим элементом (внизу) и пусть f: L → L - функция, сохраняющая порядок . Далее, предположим, что существует u в L такое, что f (u) ≤ u и что любая цепь из подмножестваимеет супремум. Тогда f имеет наименьшую неподвижную точку .
Это может быть применено для получения различных теорем об инвариантных множествах , например теоремы Ок:
- Для монотонного отображения F: P (X) → P (X) на семействе (замкнутых) непустых подмножеств X следующие условия эквивалентны: (o) F допускает A в P (X) st, (i) F допускает инвариантное множество A в P (X), т.е. , (ii) F допускает максимальное инвариантное множество A, (iii) F допускает наибольшее инвариантное множество A.
В частности, используя принцип Кнастера-Тарского, можно развить теорию глобальных аттракторов для несжимающих разрывных (многозначных) систем итерированных функций . Для слабо сжимающих систем с повторяющимися функциями достаточно теоремы Канторовича о неподвижной точке (известной также как принцип Тарского-Канторовича).
Другие приложения принципа неподвижной точки для упорядоченных множеств исходят из теории дифференциальных, интегральных и операторных уравнений.
Доказательство
Переформулируем теорему.
Для полной решетки и монотонная функция на L множество всех неподвижных точек f также является полной решеткой, с участием:
- как наибольшая фиксированная точка f
- как наименьшую неподвижную точку 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 ≤ F (U) , т.е. U ∈ D . Тогда f (u) ∈ D (поскольку f (u) ≤ f (f (u)) ) и, значит, f (u) ≤ u, откуда следует f (u) = u . Поскольку каждая фиксированная точка находится в D, мы получаем, что u является наибольшей фиксированной точкой f .
Функция f монотонна на двойственной (полной) решетке. Как мы только что доказали, существует его самая большая неподвижная точка. Это наименьшая неподвижная точка L , поэтому P имеет наименьшее и наибольшее элементы, то есть в более общем смысле каждая монотонная функция на полной решетке имеет наименьшую неподвижную точку и наибольшую неподвижную точку.
Если a ∈ L и b ∈ L , то через [ a , b ] обозначим отрезок с границами a и b : {x ∈ L | a ≤ x ≤ 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 л ]. Это позволяет нам рассматривать f как функцию на полной решетке [ w , 1 L ]. Тогда он имеет наименьшую там неподвижной опоры, что дает нам верхняя грань W . Мы показали, что произвольное подмножество P имеет супремум, то есть P является полной решеткой.
Смотрите также
Заметки
- ↑ Альфред Тарский (1955). "Теорема о неподвижной точке теории решеток и ее приложения" . Тихоокеанский математический журнал . 5: 2 : 285–309.
- ^ Б. Кнастер (1928). "Теорема сюр лесов смыслов". Аня. Soc. Полон. Математика . 6 : 133–134. С А. Тарским.
- ^ Энн С. Дэвис (1955). «Характеристика полных решеток» . Тихоокеанский математический журнал . 5 (2): 311–319. DOI : 10,2140 / pjm.1955.5.311 .
- ^ Пример 3 в R. Uhl, « Теорема Тарского о неподвижной точке », из MathWorld - веб-ресурса Wolfram, созданного Эриком В. Вайстейном.
- ^ Дэйви, Брайан А .; Пристли, Хилари А. (2002). Введение в решетки и порядок (2-е изд.). Издательство Кембриджского университета . С. 63, 4. ISBN 9780521784511.
Рекомендации
- Анджей Гранас и Джеймс Дугунджи (2003). Теория неподвижной точки . Спрингер-Верлаг , Нью-Йорк. ISBN 978-0-387-00173-9.
- Форстер, Т. (21 июля 2003 г.). Логика, индукция и множества . ISBN 978-0-521-53361-4.
дальнейшее чтение
- С. Хаяси (1985). «Самоподобные множества как неподвижные точки Тарского» . Публикации НИИ математических наук . 21 (5): 1059–1066. DOI : 10.2977 / Призмы / 1195178796 .
- Ю. Яхимский; Л. Гайек; К. Покаровски (2000). «Принцип Тарского-Канторовича и теория повторяющихся функциональных систем» . Бык. Austral. Математика. 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). «Алгоритмы для свойства фиксированной точки». Теорет. Comput. Sci . 217 (2): 301–358. DOI : 10.1016 / S0304-3975 (98) 00273-4 .
- С. Хейккиля (1990). «О неподвижных точках с помощью обобщенного итерационного метода с приложениями к дифференциальным и интегральным уравнениям с участием разрывов». Нелинейный анал . 14 (5): 413–426. DOI : 10.1016 / 0362-546X (90) 90082-R .
- Р. Уль (2003). «Наименьшая и наибольшая неподвижные точки квазимонотонных возрастающих отображений». Mathematische Nachrichten . 248–249: 204–210. DOI : 10.1002 / mana.200310016 .
Внешние ссылки
- Дж. Б. Нация, Заметки по теории решетки .
- Приложение к элементарной задаче комбинаторики : дана книга со 100 страницами и 100 леммами, докажите, что существует некоторая лемма, написанная на той же странице, что и ее индекс.