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

В математике, теорема Бурбаки – Витта в теории порядка, названная в честь Николаса Бурбаки и Эрнст Витт, является базовой теоремой о неподвижной точке для частично упорядоченных множеств. В нем указано, что если X - это непустая цепочка , полная poset и

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

такая, что

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

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

• 1 Частный случай конечного чугуна
• 2 Доказательство теоремы
• 3 Приложения
• 4 Ссылки

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

$xn\; +\; 1\; =\; f\; (xn),\; n\; =\; 0,\; 1,\; 2,\dots ,\; \{\backslash \; displaystyle\; x\_\; \{n\; +\; 1\}\; =\; f\; (x\_\; \{n\}),\; n\; =\; 0,\; 1,2,\; \backslash \; ldots,\}$

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

$xn\; =\; x\; \infty ,\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; x\; \_\; \{\backslash \; infty\},\}$для достаточно большого n.

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

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

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

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

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

- цепь в X. Определим

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

$\alpha ,\; K\; (\alpha \; +\; 1)\; =\; K\; (\alpha );\; \{\backslash \; Displaystyle\; \backslash \; альфа,\; \backslash \; \backslash \; К\; (\backslash \; альфа\; +1)\; =\; К\; (\backslash \; альфа);\}$

то есть

$f\; (K\; (\alpha ))\; =\; K\; (\alpha ).\; \{\backslash \; Displaystyle\; \backslash ,\; е\; (К\; (\backslash \; альфа))\; =\; К\; (\backslash \; альфа).\}$

Итак, если

$х\; =\; К\; (\alpha ),\; \{\backslash \; Displaystyle\; \backslash ,\; х\; =\; K\; (\backslash \; альфа),\}$

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

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

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

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

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

с помощью

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

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

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

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

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