Порядок Клини – Брауэра

В дескриптивной теории множеств порядок Клини -Брауэра или порядок Лусина-Серпинского. ^{[ 1 ]} является линейным порядком на конечных последовательностях над некоторым линейно упорядоченным множеством $(X,<)$ , который отличается от более часто используемого лексикографического порядка тем, как он обрабатывает случай, когда одна последовательность является префиксом другой. В порядке Клини-Брауэра префикс находится позже, чем более длинная последовательность, содержащая его, а не раньше.

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

Определение

Если $t$ и $s$ являются конечными последовательностями элементов из $X$ , мы говорим, что $t<_{KB}s$ когда есть $n$ такое, что либо:

$t\upharpoonright n=s\upharpoonright n$ и $t(n)$ определено, но $s(n)$ не определено (т.е. $t$ правильно расширяет $s$ ), или
оба $s(n)$ и $t(n)$ определены, $t(n)<s(n)$ , и $t\upharpoonright n=s\upharpoonright n$ .

Здесь обозначение $t\upharpoonright n$ к префиксу относится $t$ до, но не включая $t(n)$ . Проще говоря, $t<_{KB}s$ в любое время $s$ является префиксом $t$ (т.е. $s$ заканчивается раньше $t$ , и до этого момента они равны) или $t$ находится «слева» от $s$ во-первых, они различаются. ^{[ 1 ]}

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

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

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

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

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

История

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

Ссылки

^ Jump up to: ^а ^б ^с Мошовакис, Яннис (2009), Описательная теория множеств (2-е изд.), Род-Айленд: Американское математическое общество, стр. 148–149, 203–204, ISBN 978-0-8218-4813-5
^ Швихтенберг, Хельмут ; Вайнер, Стэнли С. (2012), «2.8 Рекурсивные функционалы типа 2 и обоснованность», Доказательства и вычисления , Перспективы логики, Кембридж: Cambridge University Press, стр. 98–101, ISBN 978-0-521-51769-0 , МР 2893891 .
^ Лусин, Николас ; Серпинский, Вацлав (1923), «О неизмеримом множестве B» , Журнал чистой и прикладной математики , 9 (2): 53–72, заархивировано из оригинала 14 апреля 2013 г.
^ Брауэр, Л.Э. (1924), «Доказательство того, что каждая полная функция одинаково постоянна», Королевская голландская академия наук, Proc. Раздел наук , 27 : 189–193 . Цитируется Клини (1955) .
^ Клини, SC (1955), «О формах предикатов в теории конструктивных ординалов. II», American Journal of Mathematics , 77 : 405–428, doi : 10.2307/2372632 , JSTOR 2372632 , MR 0070595 . См., в частности, раздел 26 «Отступление относительно рекурсивного линейного упорядочения», стр. 419–422.

[moschovakis-1] Jump up to: ^а ^б ^с Мошовакис, Яннис (2009), Описательная теория множеств (2-е изд.), Род-Айленд: Американское математическое общество, стр. 148–149, 203–204, ISBN 978-0-8218-4813-5

[2] Швихтенберг, Хельмут ; Вайнер, Стэнли С. (2012), «2.8 Рекурсивные функционалы типа 2 и обоснованность», Доказательства и вычисления , Перспективы логики, Кембридж: Cambridge University Press, стр. 98–101, ISBN 978-0-521-51769-0 , МР 2893891 .

[3] Лусин, Николас ; Серпинский, Вацлав (1923), «О неизмеримом множестве B» , Журнал чистой и прикладной математики , 9 (2): 53–72, заархивировано из оригинала 14 апреля 2013 г.

[4] Брауэр, Л.Э. (1924), «Доказательство того, что каждая полная функция одинаково постоянна», Королевская голландская академия наук, Proc. Раздел наук , 27 : 189–193 . Цитируется Клини (1955) .

[5] Клини, SC (1955), «О формах предикатов в теории конструктивных ординалов. II», American Journal of Mathematics , 77 : 405–428, doi : 10.2307/2372632 , JSTOR 2372632 , MR 0070595 . См., в частности, раздел 26 «Отступление относительно рекурсивного линейного упорядочения», стр. 419–422.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]