Теорема Бурбаки – Витта. - Bourbaki–Witt theorem

В математика, то Теорема Бурбаки – Витта. в теория порядка, названный в честь Николя Бурбаки и Эрнст Витт, является основным теорема о неподвижной точке для частично упорядоченные наборы. В нем говорится, что если Икс непустой цепь завершена посеть, и

${\displaystyle f:X\to X}$

такой, что

${\displaystyle f(x)\geq x}$ для всех ${\displaystyle x,}$

тогда ж имеет фиксированная точка. Такая функция ж называется инфляционный или прогрессивный.

Частный случай конечного чугуна

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

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

где Икс₀ любой элемент Икс, монотонно возрастает. Конечностью Икс, стабилизирует:

${\displaystyle x_{n}=x_{\infty },}$ для п достаточно большой.

Это следует из того Икс_∞ неподвижная точка ж.

Доказательство теоремы

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

${\displaystyle \,K(0)=y}$

${\displaystyle \,K(\alpha +1)=f(K(\alpha )).}$

Если ${\displaystyle \beta }$ это предельный порядковый номер, то по построению

${\displaystyle \{K(\alpha )\ :\ \alpha <\beta \}}$

это цепь в Икс. Определить

${\displaystyle K(\beta )=\sup\{K(\alpha )\ :\ \alpha <\beta \}.}$

Теперь это возрастающая функция от порядковых чисел к Икс. Его нельзя строго увеличивать, как если бы мы имели инъективная функция из ординалов в набор, нарушая Лемма Хартогса. Следовательно, функция должна быть в конечном итоге постоянной, поэтому для некоторых

${\displaystyle \alpha ,\ \ K(\alpha +1)=K(\alpha );}$

это,

${\displaystyle \,f(K(\alpha ))=K(\alpha ).}$

Так что позволяя

${\displaystyle \,x=K(\alpha ),}$

у нас есть желаемая фиксированная точка. Q.E.D.

Приложения

Теорема Бурбаки – Витта имеет различные важные приложения. Один из наиболее распространенных - доказательство того, что аксиома выбора подразумевает Лемма Цорна. Сначала докажем это для случая, когда Икс полна по цепочке и не имеет максимального элемента. Позволять г быть функцией выбора на

${\displaystyle P(X)-\{\varnothing \}.}$

Определите функцию

${\displaystyle f:X\to X}$

от

${\displaystyle f(x)=g(\{y\ :\ y>x\}).}$

Это разрешено, поскольку, по предположению, набор не пустой. потом ж(Икс) > Икс, так ж является инфляционной функцией без фиксированной точки, что противоречит теореме.

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

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

использованная литература

• Николя Бурбаки (1949). "Sur le théorème de Zorn". Archiv der Mathematik. 2: 434–437. Дои:10.1007 / bf02036949.
• Эрнст Витт (1951). "Beweisstudien zum Satz von M. Zorn". Mathematische Nachrichten. 4: 434–438. Дои:10.1002 / мана.3210040138.