WikiDer > Заказ Клини – Брауэра

Kleene–Brouwer order

В описательная теория множеств, то Заказ Клини – Брауэра или же Орден Лусина – Серпинского[1] это линейный порядок на конечных последовательностях над некоторым линейно упорядоченным множеством , который отличается от более часто используемых лексикографический порядок в том, как он обрабатывает случай, когда одна последовательность является префикс другого. В порядке Клини – Брауэра префикс стоит позже, чем более длинная последовательность, содержащая его, а не раньше.

Порядок Клини – Брауэра обобщает понятие обход послепорядка от конечных деревьев к деревьям, которые не обязательно являются конечными. Для деревьев над хорошо упорядоченным множеством порядок Клини – Брауэра сам по себе является хорошо упорядочивающим тогда и только тогда, когда дерево не имеет бесконечной ветви. Он назван в честь Стивен Коул Клини, Луитцен Эгбертус Ян Брауэр, Николай Лузин, и Вацлав Серпинский.

Определение

Если и конечные последовательности элементов из мы говорим, что когда есть так что либо:

  • и определено, но не определено (т.е. правильно расширяет ), или же
  • обе и определены, , и .

Здесь обозначение относится к префикс из до, но не включая .Проще говоря, в любое время является префиксом (т.е. заканчивается раньше , и они равны до этого момента) или находится "слева" от в первую очередь они отличаются.[1]

Интерпретация дерева

А деревов дескриптивной теории множеств определяется как набор конечных последовательностей, замкнутый относительно префиксных операций. Родителем в дереве любой последовательности является более короткая последовательность, образованная путем удаления ее последнего элемента. Таким образом, любой набор конечных последовательностей может быть расширен, чтобы сформировать дерево, и порядок Клини – Брауэра является естественным порядком, который может быть задан этому дереву. Это обобщение потенциально бесконечных деревьев обход послепорядка конечного дерева: в каждом узле дерева дочерние поддеревья упорядочиваются слева направо, а сам узел идет после всех своих дочерних элементов. Тот факт, что порядок Клини – Брауэра является линейным (то есть, что он транзитивен, а также является тотальным), немедленно следует из этого, поскольку любые три последовательности, на которых должна быть проверена транзитивность, образуют (со своими префиксами) конечную дерево, на котором порядок Клини – Брауэра совпадает с постпорядком.

Значение порядка Клини – Брауэра проистекает из того факта, что если является хорошо организованный, затем дерево над является обоснованный (не имеющий бесконечно длинных ветвей) тогда и только тогда, когда порядок Клини – Брауэра является хорошим упорядочением элементов дерева.[1]

Теория рекурсии

В теория рекурсии, порядок Клини – Брауэра может быть применен к деревья вычислений реализации тотально рекурсивный функционалы. Дерево вычислений является хорошо обоснованным тогда и только тогда, когда выполняемые им вычисления полностью рекурсивны. Каждое государство в дереве вычислений может быть назначен порядковый номер , верхняя грань порядковых чисел куда колеблется над детьми в дереве. Таким образом, сами полные рекурсивные функционалы могут быть классифицированы в иерархию в соответствии с минимальным значением порядкового номера в корне дерева вычислений, минимизированным по всем деревьям вычислений, реализующим функционал. Порядок Клини-Брауэра хорошо обоснованного дерева вычислений сам по себе является рекурсивным хорошо упорядоченным и по крайней мере такой же большой, как порядковый номер, присвоенный дереву, из чего следует, что уровни этой иерархии индексируются рекурсивные ординалы.[2]

История

Этот порядок использовался Лусин и Серпинский (1923),[3] а затем снова Брауэр (1924).[4] Брауэр не приводит никаких ссылок, но Moschovakis утверждает, что он, возможно, видел Лусин и Серпинский (1923), или находились под влиянием более ранних работ тех же авторов, которые привели к этой работе. Много позже, Клини (1955) изучил тот же порядок и приписал его Брауэру.[5]

Рекомендации

  1. ^ а б c Мощовакис, Яннис (2009), Описательная теория множеств (2-е изд.), Род-Айленд: Американское математическое общество, стр. 148–149, 203–204, ISBN 978-0-8218-4813-5
  2. ^ Швихтенберг, Гельмут; Уэйнер, Стэнли С. (2012), «2.8 Рекурсивные функционалы типа 2 и обоснованность», Доказательства и вычисления, Перспективы в логике, Кембридж: Издательство Кембриджского университета, стр. 98–101, ISBN 978-0-521-51769-0, МИСТЕР 2893891.
  3. ^ Лусин, Николас; Серпинский, Вацлав (1923), "Sur un ensemble неизмеримый B", Journal de Mathématiques Pures et Appliquées, 9 (2): 53–72, архивировано с оригинал на 2013-04-14.
  4. ^ Брауэр, Л. Э. Дж. (1924), "Beweis, dass jede volle Funktion gleichmässig stetig ist", Koninklijke Nederlandse Akademie van Wetenschappen, Proc. Секция наук, 27: 189–193. Как цитирует Клини (1955).
  5. ^ Клини, С. (1955), «О формах предикатов в теории конструктивных ординалов. II», Американский журнал математики, 77: 405–428, Дои:10.2307/2372632, JSTOR 2372632, МИСТЕР 0070595. См., В частности, раздел 26, «Отступление о рекурсивном линейном порядке», стр. 419–422.