Теорема Бурбаки – Витта

В математике теорема Бурбаки -Витта в теории порядка , названная в честь Николаса Бурбаки и Эрнста Витта , является основной теоремой о неподвижной точке для частично упорядоченных множеств . В нем говорится, что если X — непустая цепочка, полная частично упорядоченное множество , и $f:X\to X$ такой, что $f(x)\geq x$ для всех $x,$ тогда f имеет неподвижную точку . Такая функция f называется инфляционной или прогрессивной .

Особый случай конечного частично упорядоченного множества [ править ]

Если ЧУ-множество X конечно, то утверждение теоремы имеет ясную интерпретацию, которая приводит к доказательству. Последовательность последовательных итераций,

x_{n+1}=f(x_{n}),n=0,1,2,\ldots ,

где x ₀ — любой элемент X , монотонно возрастает. В силу конечности X он стабилизируется:

x_{n}=x_{\infty },

для n достаточно большого.

Отсюда следует, что x _∞ является неподвижной точкой f .

Доказательство теоремы [ править ]

Выберите несколько $y\in X$ . Определите функцию K рекурсивно по порядковым номерам следующим образом:

\,K(0)=y

\,K(\alpha +1)=f(K(\alpha )).

Если $\beta$ является предельным ординалом , то по построению $\{K(\alpha )\ :\ \alpha <\beta \}$ является цепью X. в Определять $K(\beta )=\sup\{K(\alpha )\ :\ \alpha <\beta \}.$

Теперь это возрастающая функция от ординалов X. до Оно не может быть строго возрастающим, как если бы у нас была бы инъективная функция из порядковых чисел в множество, что нарушает лемму Хартогса . Следовательно, функция в конечном итоге должна быть постоянной, поэтому для некоторых $\alpha ,\ \ K(\alpha +1)=K(\alpha );$ то есть, $\,f(K(\alpha ))=K(\alpha ).$

Так что позвольте $\,x=K(\alpha ),$ у нас есть желаемая фиксированная точка. КЭД

Приложения [ править ]

Теорема Бурбаки–Витта имеет множество важных приложений. Один из наиболее распространенных — в доказательстве того, что из аксиомы выбора следует лемма Цорна . Сначала мы докажем это для случая, когда X цепно полно и не имеет максимального элемента. Пусть g — функция выбора на $P(X)-\{\varnothing \}.$ Определить функцию $f:X\to X$ к $f(x)=g(\{y\ :\ y>x\}).$

Это допустимо, поскольку по предположению множество непусто. Тогда f ( x ) > x , поэтому f — инфляционная функция без неподвижной точки, что противоречит теореме.

Этот частный случай леммы Цорна затем используется для доказательства принципа максимальности Хаусдорфа , согласно которому каждое ЧУ-множество имеет максимальную цепь, что, как легко видеть, эквивалентно лемме Цорна.

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

Ссылки [ править ]

Николя Бурбаки (1949). «О теореме Цорна». Архив математики . 2 (6): 434–437. дои : 10.1007/bf02036949 . S2CID 117826806 .
Эрнст Витт (1951). «Доказательства теоремы М. Цорна». Математические новости . 4 : 434–438. дои : 10.1002/мана.3210040138 .