В описательной теории множеств , то порядок Клини-Брауэр или Лузин-Серпинский порядок [1] является линейным порядком на конечных последовательностях над некоторым линейно упорядоченным множеством, который отличается от более часто используемого лексикографического порядка тем, как он обрабатывает случай, когда одна последовательность является префиксом другой. В порядке Клини – Брауэра префикс является более поздним, чем более длинная последовательность, содержащая его, а не более ранним.
Порядок Клини – Брауэра обобщает понятие постпорядкового обхода с конечных деревьев на деревья, которые не обязательно являются конечными. Для деревьев над хорошо упорядоченным множеством порядок Клини – Брауэра сам по себе является хорошо упорядоченным тогда и только тогда, когда дерево не имеет бесконечной ветви. Он назван в честь Стивена Коула Клини , Луитцена Эгбертуса, Яна Брауэра , Николая Лузина и Вацлава Серпинского .
Определение
Если а также конечные последовательности элементов из мы говорим, что когда есть такое, что либо:
- а также определено, но не определено (т.е. правильно расширяет ), или же
- оба а также определены, , а также .
Здесь обозначение относится к префиксу из до, но не включая . Проще говоря, в любое время является префиксом (т.е. заканчивается раньше , и до этого момента они равны) или находится "слева" от в первую очередь они различаются. [1]
Интерпретация дерева
В описательной теории множеств дерево определяется как набор конечных последовательностей, замкнутый при выполнении операций с префиксом. Родителем в дереве любой последовательности является более короткая последовательность, образованная удалением ее последнего элемента. Таким образом, любой набор конечных последовательностей может быть расширен, чтобы сформировать дерево, и порядок Клини – Брауэра является естественным порядком, который может быть задан этому дереву. Это обобщение на потенциально-бесконечные деревья обхода конечного дерева после порядка : в каждом узле дерева дочерние поддеревья упорядочиваются слева направо, а сам узел идет после всех своих дочерних элементов. Тот факт, что порядок Клини – Брауэра является линейным порядком (то есть, что он транзитивен, а также является полным), немедленно следует из этого, поскольку любые три последовательности, на которых должна быть проверена транзитивность, образуют (со своими префиксами) дерево, на котором порядок Клини – Брауэра совпадает с постпорядком.
Значение порядка Клини – Брауэра проистекает из того факта, что если является вполне упорядоченным , то дерево надявляется хорошо обоснованным (не имеющим бесконечно длинных ветвей) тогда и только тогда, когда порядок Клини – Брауэра является хорошим упорядочением элементов дерева. [1]
Теория рекурсии
В теории рекурсии порядок Клини – Брауэра может применяться к деревьям вычислений реализаций полных рекурсивных функционалов . Дерево вычислений является хорошо обоснованным тогда и только тогда, когда выполняемые им вычисления полностью рекурсивны. Каждое государствов дереве вычислений может быть присвоен порядковый номер , верхняя грань порядковых чисел где колеблется над детьми в дереве. Таким образом, сами полные рекурсивные функционалы могут быть классифицированы в иерархию в соответствии с минимальным значением порядкового номера в корне дерева вычислений, минимизированным по всем деревьям вычислений, реализующим функционал. Порядок Клини – Брауэра хорошо обоснованного дерева вычислений сам по себе является рекурсивным хорошо упорядоченным и по крайней мере такой же большой, как порядковый номер, присвоенный дереву, из чего следует, что уровни этой иерархии индексируются рекурсивными порядковыми числами . [2]
История
Этот порядок использовался Люсином и Серпински (1923) , [3], а затем снова Брауэром (1924) . [4] Брауэр не цитирует никаких ссылок, но Moschovakis утверждает, что он, возможно, либо видел Lusin & Sierpinski (1923) , либо находился под влиянием более ранних работ тех же авторов, которые привели к этой работе. Намного позже Клини (1955) изучил такое же упорядочение и приписал его Брауэру. [5]
Рекомендации
- ^ a b c Moschovakis, Yiannis (2009), Descriptive Set Theory (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), "Об одной ансамбль не измерима Б" , Журнал де Mathématiques Pures и др Appliquées , 9 (2): 53-72, заархивированы с оригинала на 2013-04-14.
- ^ Брауэр, LEJ (1924), "Beweis, dass jede volle Funktion gleichmässig stetig ist", Koninklijke Nederlandse Akademie van Wetenschappen, Proc. Секция наук , 27 : 189–193.. Цитируется Клини (1955) .
- ^ Клини, SC (1955), "О формах предикатов в теории конструктивных ординалов II.", Американский журнал математика , 77 : 405-428, DOI : 10,2307 / 2372632 , JSTOR 2372632 , MR 0070595. См., В частности, раздел 26, «Отступление о рекурсивном линейном порядке», стр. 419–422.