Теорема Кнастера – Тарского - Википедия - Knaster–Tarski theorem

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

Пусть L - полная решетка и пусть f: L → L - функция сохранения порядка. Затем набор из фиксированные точки f в L также является полной решеткой.

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

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

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

Последствия: наименьшая и наибольшая фиксированные точки.

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

В наименьшая фиксированная точка из ж наименьший элемент Икс такой, что ж(Икс) = Икс, или, что то же самое, такое, что ж(Икс) ≤ Икс; в двойной относится к самая большая точка фиксации, величайший элемент Икс такой, что ж(Икс) = Икс.

Если ж(лим Икс_п) = lim ж(Икс_п) для всех возрастающих последовательностей Икс_п, то наименьшая фиксированная точка ж Лим ж^п(0) где 0 - наименьший элемент L, что дает более «конструктивную» версию теоремы. (Видеть: Теорема Клини о неподвижной точке.) В общем, если ж монотонна, то наименьшая неподвижная точка ж стационарный предел ж^α(0), взяв α по порядковые, куда ж^α определяется трансфинитная индукция: ж^{α + 1} = ж ( ж^α) и ж^γ для предельного ординала γ - это наименьшая верхняя граница из ж^β для всех β ординалов меньше γ. Двойственная теорема верна для наибольшей неподвижной точки.

Например, в теоретической Информатика, наименьшие фиксированные точки из монотонные функции используются для определения семантика программы. Часто используется более специализированный вариант теоремы, где L считается решеткой всех подмножества некоторого множества, упорядоченного по включению подмножества. Это отражает тот факт, что во многих приложениях рассматриваются только такие решетки. Затем обычно ищут наименьшее множество, которое имеет свойство быть фиксированной точкой функции ж. Абстрактная интерпретация широко использует теорему Кнастера – Тарского и формулы, определяющие наименьшие и наибольшие неподвижные точки.

Теорема Кнастера – Тарского может быть использована для простого доказательства Теорема Кантора – Бернштейна – Шредера..^[4]^[5]

Более слабые версии теоремы

Более слабые версии теоремы Кнастера – Тарского могут быть сформулированы для упорядоченных множеств, но содержат более сложные предположения. Например:

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

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

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

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

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

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

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

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

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

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

Теперь позвольте ${ displaystyle u = bigvee D}$ (ты существует, потому что D ⊆ L и L полная решетка). Тогда для всех Икс ∈ D правда, что Икс ≤ ты и f (x) ≤ f (u), так Икс ≤ f (x) ≤ f (u). Следовательно, f (u) является верхней границей D, но ты наименьшая верхняя граница, поэтому ты ≤ f (u), т.е. ты ∈ D. потом f (u) ∈ D (потому что f (u) ≤ f (f (u))) и так f (u) ≤ ты из чего следует f (u) = ты. Потому что каждая фиксированная точка находится в D у нас есть это ты это самая большая точка опоры ж.

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

Если а ∈ L и б ∈ L, Ну пиши [а, б] для отрезка с оценками а и б: {x ∈ L | а ≤ х ≤ б }. Если а ≤ б, тогда ${ displaystyle langle}$ [а, б], ${ displaystyle leq rangle}$ является полной решеткой.

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

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

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

Примечания

^ Альфред Тарский (1955). "Теорема о неподвижной точке в теории решеток и ее приложения". Тихоокеанский математический журнал. 5:2: 285–309.
^ Б. Кнастер (1928). "Теорема сюр лесов смыслов". Анна. Soc. Полон. Математика. 6: 133–134. С А. Тарским.
^ Энн С. Дэвис (1955). «Характеристика полных решеток». Pacific J. Math. 5 (2): 311–319. Дои:10.2140 / pjm.1955.5.311.
^ Пример 3 в R. Uhl, "Теорема Тарского о неподвижной точке ", из MathWorld- Интернет-ресурс Wolfram, созданный Эриком В. Вайстейном.
^ Дэйви, Брайан А .; Пристли, Хилари А. (2002). Введение в решетки и порядок (2-е изд.). Издательство Кембриджского университета. С. 63, 4. ISBN 9780521784511.

дальнейшее чтение

С. Хаяси (1985). «Самоподобные множества как неподвижные точки Тарского». Публикации НИИ математических наук. 21 (5): 1059–1066. Дои:10.2977 / prims / 1195178796.
Я. Яхимский; Л. Гайек; К. Покаровски (2000). «Принцип Тарского-Канторовича и теория повторяющихся функциональных систем». Бык. Austral. Математика. Soc. 61 (2): 247–261. Дои:10.1017 / S0004972700022243.
E.A. Хорошо (2004). «Теория фиксированных множеств для закрытых соответствий с приложениями к самоподобию и играм». Нелинейный анал. 56 (3): 309–330. CiteSeerX 10.1.1.561.4581. Дои:10.1016 / j.na.2003.08.001.
B.S.W. Шредер (1999). «Алгоритмы для свойства фиксированной точки». Теорет. Comput. Наука. 217 (2): 301–358. Дои:10.1016 / S0304-3975 (98) 00273-4.
С. Хейккиля (1990). «О неподвижных точках с помощью обобщенного итерационного метода с приложениями к дифференциальным и интегральным уравнениям с участием разрывов». Нелинейный анал. 14 (5): 413–426. Дои:10.1016 / 0362-546X (90) 90082-R.
Р. Уль (2003). «Наименьшая и наибольшая неподвижные точки квазимонотонных возрастающих отображений». Mathematische Nachrichten. 248–249: 204–210. Дои:10.1002 / мана.200310016.

внешняя ссылка

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

[1] Альфред Тарский (1955). "Теорема о неподвижной точке в теории решеток и ее приложения". Тихоокеанский математический журнал. 5:2: 285–309.

[2] Б. Кнастер (1928). "Теорема сюр лесов смыслов". Анна. Soc. Полон. Математика. 6: 133–134. С А. Тарским.

[3] Энн С. Дэвис (1955). «Характеристика полных решеток». Pacific J. Math. 5 (2): 311–319. Дои:10.2140 / pjm.1955.5.311.

[4] Пример 3 в R. Uhl, "Теорема Тарского о неподвижной точке ", из MathWorld- Интернет-ресурс Wolfram, созданный Эриком В. Вайстейном.

[5] Дэйви, Брайан А .; Пристли, Хилари А. (2002). Введение в решетки и порядок (2-е изд.). Издательство Кембриджского университета. С. 63, 4. ISBN 9780521784511.

[1]

[2]

[3]

[4]

[5]