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

В математике теорема Бурбаки -Витта в теории порядка , названная в честь Николя Бурбаки и Эрнста Витта , является основной теоремой о неподвижной точке для частично упорядоченных множеств . В нем говорится, что если 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 .