Оглавление
Теорема Бурбаки–Витта
-
Теорема Бурбаки–Витта
- Основная теорема о фиксированной точке для частично упорядоченных множеств
- Утверждает, что если X является непустой цепочкой и f: X → X удовлетворяет условию f(x) ≥ x для всех x, то f имеет фиксированную точку
-
Частный случай конечного множества
- Если X конечно, то утверждение теоремы имеет четкую интерпретацию
- Последовательность последовательных итераций стабилизируется, что приводит к неподвижной точке f
-
Доказательство теоремы
- Выберите y ∈ X и определите функцию K рекурсивно по ординалам
- Функция K должна быть возрастающей и в конечном счете постоянной
- Пусть x = K(α), где α – предельный порядковый номер, тогда x является фиксированной точкой f
-
Приложения теоремы
- Доказательство леммы Цорна для полных цепочек без максимального элемента
- Использование в информатике для теории вычислимых функций и определения рекурсивных типов данных
-
Другие области применения
- Теорема Клини о неподвижной точке для непрерывных функций Скотта
- Теорема Кнастера–Тарского для полных решеток