В теории множеств и вычислимости теории , Клини «sявляется каноническим подмножеством натуральных чисел, рассматриваемых как порядковые обозначения . Он содержит порядковые обозначения для каждого вычислимого ординала , то есть ординалы ниже ординала Черча – Клини ,. С является первым порядковым номером, не представимым в вычислимой системе порядковых обозначений, элементы можно рассматривать как канонические порядковые обозначения.
Клини (1938) описал систему обозначений для всех вычислимых ординалов (меньших, чем ординал Черча-Клини ). Он использует подмножество натуральных чисел вместо конечных строк символов. К сожалению, в целом нет эффективного способа определить, представляет ли какое-то натуральное число порядковый номер или два числа представляют один и тот же порядковый номер. Однако можно эффективно найти обозначения, которые представляют порядковую сумму, произведение и мощность (см. Порядковая арифметика ) любых двух данных обозначений в системе Клини.; и учитывая любую нотацию для ординала, существует вычислимо перечислимый набор нотаций, который содержит один элемент для каждого меньшего ординала и эффективно упорядочен.
Клини
Основная идея системы порядковых обозначений Клини заключается в эффективном построении порядковых номеров. Членам из , порядковый номер, для которого это обозначение . а также ( частичное упорядочение Клини) - наименьшие множества, для которых выполняется следующее.
- Натуральное число 0 принадлежит Клини а также .
- Если принадлежит Клини а также , тогда принадлежит Клини а также а также .
- Предполагать это -я частично вычислимая функция. Если всего, с диапазоном, содержащимся в , и для каждого натурального числа , у нас есть , тогда принадлежит Клини , для каждого а также , т.е. обозначение предела порядковых чисел где для каждого натурального числа .
- а также подразумевать (это гарантирует, что транзитивен.)
Это определение имеет то преимущество, что можно вычислимо перечислить предшественников данного порядкового номера (хотя и не в порядок) и что обозначения закрыты вниз, т. е. если есть обозначения для а также то есть обозначение для .
Основные свойства
- Если а также а также тогда ; но обратное может оказаться неверным.
- индуцирует древовидную структуру на , так является вполне обоснованным .
- только ветви в предельных ординалах; и при каждом обозначении предельного ординала, бесконечно ветвится.
- Поскольку каждая вычислимая функция имеет счетное число индексов, каждый бесконечный ординал получает счетное число обозначений; конечные ординалы имеют уникальные обозначения, обычно обозначается .
- Первый ординал, не получивший обозначений, называется ординалом Черча – Клини и обозначается. Поскольку существует только счетное число вычислимых функций, порядковый номер очевидно, счетно.
- Ординалы с обозначениями Клини в точности вычислимые ординалы . (Тот факт, что каждый вычислимый ординал имеет обозначение, следует из замыкания этой системы порядковых обозначений относительно преемников и эффективных ограничений.)
- не является вычислимо перечислимым , но существует вычислимо перечислимое отношение, которое согласуется с именно на членов .
- Для любых обозначений , набор обозначений ниже вычислимо перечислимо. Однако Клинив целом (см. аналитическую иерархию ).
- По факту, является -полный и каждый подмножество эффективно ограничено в (результат Спектора).
- является универсальной системой порядковых обозначений в том смысле, что любой конкретный набор порядковых обозначений может быть напрямую отображен в нее. Точнее, существует вычислимая функция так что если является индексом вычислимой хорошей упорядоченности, то является членом а также изоморфна по порядку начальному отрезку множества .
- Есть вычислимая функция , что для членов , имитирует порядковое сложение и обладает тем свойством, что . (Джокуш)
Свойства путей в
Путь в это подмножество из который полностью заказан и закрывается при предшественниках, т. е. если является участником пути а также тогда также является членом . Путь максимальна, если нет элемента что выше (в смысле ) каждый член , иначе не является максимальным.
- Путь не является максимальным тогда и только тогда, когда вычислимо перечислимо (ce). Из замечаний выше следует, что каждый элемент из определяет немаксимальный путь ; и так определяется любой немаксимальный путь.
- Есть максимальные пути через ; так как они максимальны, они не в.
- На самом деле есть максимальные пути внутри длины . (Кроссли, Шютте)
- Для каждого ненулевого порядкового номера , Существуют максимальные пути внутри длины . (Aczel)
- Далее, если это путь, длина которого не кратна тогда не является максимальным. (Aczel)
- Для каждой степени CE , есть участник из так что путь имеет много-одну степень . Фактически, для каждого вычислимого ординала, обозначение существует с . (Джокуш)
- Существуют пути через которые . Учитывая прогрессию вычислимо перечислимых теорий, основанных на итерации равномерного отражения, каждый такой путь является неполным по отношению к множеству истинныхпредложения. (Феферман и Спектор)
- Существуют пути через каждый начальный сегмент не просто в.п., но вычислим. (Джокуш)
- Различные другие пути в было показано, что каждый из них обладает определенными свойствами сводимости. (См. Ссылки ниже)
Смотрите также
Рекомендации
- Чёрч, Алонзо (1938), «Конструктивное второе число класса» , Bull. Амер. Математика. Soc. , 44 (4): 224–232, DOI : 10.1090 / S0002-9904-1938-06720-1
- Клини, SC (1938), "О Notation для порядковых чисел", Журнал символической логики , Ассоциация символической логики, 3 (4): 150-155, DOI : 10,2307 / 2267778 , JSTOR 2267778
- Роджерс, Хартли (1987) [1967], Теория рекурсивных функций и эффективной вычислимости , первое издание MIT в мягкой обложке, ISBN 978-0-262-68052-3
- Феферман, Соломон; Spector, Clifford (1962), "Неполнота по путям в прогрессиях теорий", журнал символической логики , 27 (4): 383-390, DOI : 10,2307 / 2964544 , JSTOR 2964544