Теорема Клини о неподвижной точке - Kleene fixed-point theorem

Вычисление наименьшей фиксированной точки ж(Икс) = 1/10Икс2+загар (Икс) +1, используя теорему Клини в вещественной интервал [0,7] при обычном порядке

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

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

В восходящая цепь Клини из ж это цепь

получено повторение ж на наименьший элемент ⊥ из L. Выраженная формулой, теорема утверждает, что

куда обозначает наименьшую неподвижную точку.

Несмотря на то что Теорема Тарского о неподвижной точке не учитывает, как фиксированные точки могут быть вычислены путем повторения ж из какого-то семени (также это относится к монотонные функции на полные решетки ) этот результат часто приписывают Альфред Тарский кто доказывает это для аддитивных функций [1] Более того, теорема Клини о неподвижной точке может быть расширена на монотонные функции с использованием трансфинитных итераций.[2]

Доказательство[3]

Сначала мы должны показать, что восходящая цепочка Клини существует в . Чтобы показать это, мы докажем следующее:

Лемма. Если является DCPO с наименьшим элементом, и непрерывно по Скотту, то
Доказательство. Воспользуемся индукцией:
  • Предположим, что n = 0. Тогда поскольку наименьший элемент.
  • Предположим, что n> 0. Тогда мы должны показать, что . Переставляя, мы получаем . По предположению индукции мы знаем, что справедливо, и поскольку f монотонна (свойство непрерывных по Скотту функций), результат также верен.

Следствием леммы является следующая направленная ω-цепь:

Из определения DCPO следует, что есть супремум, назовите это Теперь остается показать, что наименьшая неподвижная точка.

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

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

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

Рекомендации

  1. ^ Альфред Тарский (1955). "Теорема о неподвижной точке в теории решеток и ее приложения". Тихоокеанский математический журнал. 5:2: 285–309., стр.305.
  2. ^ Патрик Кузо и Радия Кузо (1979). «Конструктивные версии теорем Тарского о неподвижной точке». Тихоокеанский математический журнал. 82:1: 43–57.
  3. ^ Stoltenberg-Hansen, V .; Lindstrom, I .; Гриффор, Э. Р. (1994). Математическая теория областей В. Столтенберг-Хансен. Издательство Кембриджского университета. стр.24. Дои:10.1017 / cbo9781139166386. ISBN  0521383447.