Теорема Бурбаки – Витта
В математике теорема Бурбаки -Витта в теории порядка , названная в честь Николаса Бурбаки и Эрнста Витта , является основной теоремой о неподвижной точке для частично упорядоченных множеств . В нем говорится, что если X — непустая цепочка, полная частично упорядоченное множество , и такой, что для всех тогда f имеет неподвижную точку . Такая функция f называется инфляционной или прогрессивной .
Особый случай конечного частично упорядоченного множества [ править ]
Если ЧУ-множество X конечно, то утверждение теоремы имеет ясную интерпретацию, которая приводит к доказательству. Последовательность последовательных итераций,
где x 0 — любой элемент X , монотонно возрастает. В силу конечности X он стабилизируется:
- для n достаточно большого.
Отсюда следует, что x ∞ является неподвижной точкой f .
Доказательство теоремы [ править ]
Выберите несколько . Определите функцию K рекурсивно по порядковым номерам следующим образом:
Если является предельным ординалом , то по построению является цепью X. в Определять
Теперь это возрастающая функция от ординалов X. до Оно не может быть строго возрастающим, как если бы у нас была бы инъективная функция из порядковых чисел в множество, что нарушает лемму Хартогса . Следовательно, функция в конечном итоге должна быть постоянной, поэтому для некоторых то есть,
Так что позвольте у нас есть желаемая фиксированная точка. КЭД
Приложения [ править ]
Теорема Бурбаки–Витта имеет множество важных приложений. Один из наиболее распространенных — в доказательстве того, что из аксиомы выбора следует лемма Цорна . Сначала мы докажем это для случая, когда X цепно полно и не имеет максимального элемента. Пусть g — функция выбора на Определить функцию к
Это допустимо, поскольку по предположению множество непусто. Тогда f ( x ) > x , поэтому f — инфляционная функция без неподвижной точки, что противоречит теореме.
Этот частный случай леммы Цорна затем используется для доказательства принципа максимальности Хаусдорфа , согласно которому каждое ЧУ-множество имеет максимальную цепь, что, как легко видеть, эквивалентно лемме Цорна.
У Бурбаки-Витта есть и другие приложения. В частности, в информатике он используется в теории вычислимых функций . Он также используется для определения рекурсивных типов данных, например связанных списков, в теории предметной области .
Ссылки [ править ]
- Николя Бурбаки (1949). «О теореме Цорна». Архив математики . 2 (6): 434–437. дои : 10.1007/bf02036949 . S2CID 117826806 .
- Эрнст Витт (1951). «Доказательства теоремы М. Цорна». Математические новости . 4 : 434–438. дои : 10.1002/мана.3210040138 .