Клинес О - Kleenes O

В теория множеств и теория вычислимости, Клини с ${\displaystyle {\mathcal {O}}}$ является каноническим подмножеством натуральные числа когда рассматривается как порядковые обозначения. Это содержит порядковые обозначения для каждого рекурсивный порядковый, то есть порядковые числа ниже Чёрч – Клини ординал, ${\displaystyle \omega _{1}^{CK}}$. С ${\displaystyle \omega _{1}^{CK}}$ является первым ординалом, не представимым в вычислимой системе порядковых обозначений, элементы ${\displaystyle {\mathcal {O}}}$ можно рассматривать как канонические порядковые обозначения.

Клини (1938) описал систему обозначений для всех рекурсивных ординалов (тех, которые меньше Чёрч – Клини ординал ). Он использует подмножество натуральные числа вместо конечных строк символов. К сожалению, в целом нет эффективный способ узнать, представляет ли некоторое натуральное число порядковый номер или два числа представляют один и тот же порядковый номер. Однако можно эффективно найти обозначения, которые представляют порядковую сумму, произведение и степень (см. порядковая арифметика ) любых двух обозначений в терминах Клини ${\displaystyle {\mathcal {O}}}$; и учитывая любые обозначения для порядкового номера, существует рекурсивно перечислимый набор обозначений, которые содержат один элемент для каждого меньшего порядкового номера и эффективно упорядочены.

Клини ${\displaystyle {\mathcal {O}}}$

Основная идея системы порядковых обозначений Клини заключается в эффективном построении порядковых номеров. Членам ${\displaystyle p}$ из ${\displaystyle {\mathcal {O}}}$, порядковый номер, для которого ${\displaystyle p}$ это обозначение ${\displaystyle |p|}$. ${\displaystyle {\mathcal {O}}}$ и ${\displaystyle <_{\mathcal {O}}}$ (а частичный заказ Клини ${\displaystyle {\mathcal {O}}}$) - наименьшие множества, для которых выполняется следующее.

• Натуральное число 0 принадлежит Клини ${\displaystyle {\mathcal {O}}}$ и ${\displaystyle |0|=0}$.
• Если ${\displaystyle i}$ принадлежит Клини ${\displaystyle {\mathcal {O}}}$ и ${\displaystyle |i|=\alpha }$, тогда ${\displaystyle 2^{i}}$ принадлежит Клини ${\displaystyle {\mathcal {O}}}$ и ${\displaystyle |2^{i}|=\alpha +1}$ и ${\displaystyle i<_{\mathcal {O}}2^{i}}$.
• Предполагать ${\displaystyle \{e\}}$ это ${\displaystyle e}$-я частичная рекурсивная функция. Если ${\displaystyle e}$ всего, с диапазоном, содержащимся в ${\displaystyle {\mathcal {O}}}$, и для каждого натурального числа ${\displaystyle n}$, у нас есть ${\displaystyle \{e\}(n)<_{\mathcal {O}}\{e\}(n+1)}$, тогда ${\displaystyle 3\cdot 5^{e}}$ принадлежит Клини ${\displaystyle {\mathcal {O}}}$, ${\displaystyle \{e\}(n)<_{\mathcal {O}}3\cdot 5^{e}}$ для каждого ${\displaystyle n}$ и ${\displaystyle |3\cdot 5^{e}|=\lim _{k}|\{e\}(k)|}$, т.е. ${\displaystyle 3\cdot 5^{e}}$ обозначение предела порядковых чисел ${\displaystyle \gamma _{k}}$ куда ${\displaystyle |\{e\}(k)|=\gamma _{k}}$ для каждого натурального числа ${\displaystyle k}$.
• ${\displaystyle p<_{\mathcal {O}}q}$ и ${\displaystyle q<_{\mathcal {O}}r}$ подразумевать ${\displaystyle p<_{\mathcal {O}}r}$ (это гарантирует, что ${\displaystyle <_{\mathcal {O}}}$ транзитивен.)

Это определение имеет то преимущество, что можно рекурсивно перечислять предшественников данного порядкового номера (но не в ${\displaystyle <_{\mathcal {O}}}$ упорядочение) и что обозначения закрыты вниз, т. е. если есть обозначение для ${\displaystyle \gamma }$ и ${\displaystyle \alpha <\gamma }$ то есть обозначение для ${\displaystyle \alpha }$.

Основные свойства ${\displaystyle <_{\mathcal {O}}}$

• Если ${\displaystyle |i|=\alpha }$ и ${\displaystyle |j|=\beta }$ и ${\displaystyle i<_{\mathcal {O}}j\,,}$ тогда ${\displaystyle \alpha <\beta }$; но обратное может оказаться неверным.
• ${\displaystyle <_{\mathcal {O}}}$ индуцирует древовидную структуру на ${\displaystyle {\mathcal {O}}}$, так ${\displaystyle {\mathcal {O}}}$ является обоснованный.
• ${\displaystyle {\mathcal {O}}}$ только ветви в предельных ординалах; и при каждом обозначении предельного ординала, ${\displaystyle {\mathcal {O}}}$ бесконечно ветвится.
• Поскольку каждая рекурсивная функция имеет счетное число индексов, каждый бесконечный порядковый номер получает счетное число обозначений; конечные ординалы имеют уникальные обозначения, ${\displaystyle n}$ обычно обозначается ${\displaystyle n_{\mathcal {O}}}$.
• Первый порядковый номер, не получивший обозначения, называется Чёрч – Клини ординал и обозначается ${\displaystyle \omega _{1}^{CK}}$. Поскольку существует только счетное число рекурсивных функций, порядковый номер ${\displaystyle \omega _{1}^{CK}}$ очевидно, счетно.
• Ординалы с обозначениями Клини ${\displaystyle {\mathcal {O}}}$ точно рекурсивные ординалы. (Тот факт, что каждый рекурсивный ординал имеет обозначение, следует из замыкания этой системы порядковых обозначений относительно преемников и эффективных ограничений.)
• ${\displaystyle <_{\mathcal {O}}}$ не является рекурсивно перечислимый, но существует рекурсивно перечислимое отношение, которое согласуется с ${\displaystyle <_{\mathcal {O}}}$ именно на членов ${\displaystyle {\mathcal {O}}}$.
• Для любых обозначений ${\displaystyle p}$, набор ${\displaystyle \lbrace q\mid q<_{\mathcal {O}}p\rbrace }$ обозначений ниже ${\displaystyle p}$ рекурсивно перечислимо. Однако Клини ${\displaystyle {\mathcal {O}}}$в целом ${\displaystyle \Pi _{1}^{1}}$ (видеть аналитическая иерархия ).
• Фактически, ${\displaystyle {\mathcal {O}}}$ является ${\displaystyle \Pi _{1}^{1}}$-полный и каждый ${\displaystyle \Sigma _{1}^{1}}$ подмножество ${\displaystyle {\mathcal {O}}}$ эффективно ограничено в ${\displaystyle {\mathcal {O}}}$ (результат Спектора).
• ${\displaystyle {\mathcal {O}}}$ это универсальная система порядковых обозначений в том смысле, что любой конкретный набор порядковых обозначений может быть отображен в нее прямым способом. Точнее есть рекурсивная функция ${\displaystyle f}$ так что если ${\displaystyle e}$ является индексом для рекурсивного упорядочивания, тогда ${\displaystyle f(e)}$ является членом ${\displaystyle {\mathcal {O}}}$ и ${\displaystyle <_{e}}$ изоморфна по порядку начальному отрезку множества ${\displaystyle \{p\mid p<_{\mathcal {O}}f(e)\}}$.
• Есть рекурсивная функция ${\displaystyle +_{\mathcal {O}}}$, что для членов ${\displaystyle {\mathcal {O}}}$имитирует порядковое сложение и обладает свойством ${\displaystyle \max\{p,q\}\leq p+_{\mathcal {O}}q}$. (Джокуш)

Свойства путей в ${\displaystyle {\mathcal {O}}}$

Путь в ${\displaystyle {\mathcal {O}}}$ это подмножество ${\displaystyle {\mathcal {P}}}$ из ${\displaystyle {\mathcal {O}}}$ который полностью заказан ${\displaystyle <_{\mathcal {O}}}$ и закрывается по предшественникам, т.е. если ${\displaystyle p}$ является участником пути ${\displaystyle {\mathcal {P}}}$ и ${\displaystyle q<_{\mathcal {O}}p}$ тогда ${\displaystyle q}$ также является членом ${\displaystyle {\mathcal {P}}}$. Тропинка ${\displaystyle {\mathcal {P}}}$ максимальна, если нет элемента ${\displaystyle {\mathcal {O}}}$ что выше (в смысле ${\displaystyle <_{\mathcal {O}}}$) каждый член ${\displaystyle {\mathcal {P}}}$, иначе ${\displaystyle {\mathcal {P}}}$ не является максимальным.

• Тропинка ${\displaystyle {\mathcal {P}}}$ не является максимальным тогда и только тогда, когда ${\displaystyle {\mathcal {P}}}$ рекурсивно перечислимо (т. е.). Из замечаний выше следует, что каждый элемент ${\displaystyle p}$ из ${\displaystyle {\mathcal {O}}}$ определяет немаксимальный путь ${\displaystyle {\mathcal {P}}}$; и так определяется каждый немаксимальный путь.
• Есть ${\displaystyle 2^{\aleph _{0}}}$ максимальные пути через ${\displaystyle {\mathcal {O}}}$; поскольку они максимальны, они не r.e.
• На самом деле есть ${\displaystyle 2^{\aleph _{0}}}$ максимальные пути в ${\displaystyle {\mathcal {O}}}$ длины ${\displaystyle \omega ^{2}}$. (Кроссли, Шютте)
• Для каждого ненулевого порядкового номера ${\displaystyle \lambda <\omega _{1}^{CK}}$, Существуют ${\displaystyle 2^{\aleph _{0}}}$ максимальные пути внутри ${\displaystyle {\mathcal {O}}}$ длины ${\displaystyle \omega ^{2}\cdot \lambda }$. (Aczel)
• Далее, если ${\displaystyle {\mathcal {P}}}$ это путь, длина которого нет кратный ${\displaystyle \omega ^{2}}$ тогда ${\displaystyle {\mathcal {P}}}$ не является максимальным. (Aczel)
• Для каждого р.э. степень ${\displaystyle d}$, есть участник ${\displaystyle e_{d}}$ из ${\displaystyle {\mathcal {O}}}$ так что путь ${\displaystyle {\mathcal {P}}=\lbrace p\mid p<_{\mathcal {O}}e_{d}\rbrace }$ имеет много-одну степень ${\displaystyle d}$. Фактически, для каждого рекурсивного порядкового номера ${\displaystyle \alpha \geq \omega ^{2}}$, обозначение ${\displaystyle e_{d}}$ существует с ${\displaystyle |e_{d}|=\alpha }$. (Джокуш)
• Существуют ${\displaystyle \aleph _{0}}$ пути через ${\displaystyle {\mathcal {O}}}$ которые ${\displaystyle \Pi _{1}^{1}}$. Учитывая прогрессию рекурсивно перечислимых теорий, основанных на итерации Uniform Reflection, каждый такой путь является неполным по отношению к множеству истинных ${\displaystyle \Pi _{1}^{0}}$ фразы. (Феферман и Спектор)
• Существуют ${\displaystyle \Pi _{1}^{1}}$ пути через ${\displaystyle {\mathcal {O}}}$ каждый начальный сегмент не просто r.e., но рекурсивен. (Джокуш)
• Различные другие пути в ${\displaystyle {\mathcal {O}}}$ было показано, что каждый из них обладает определенными свойствами сводимости. (См. Ссылки ниже)

Смотрите также

• Рекурсивный порядковый номер
• Большой счетный порядковый номер
• Порядковые обозначения

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

• Церковь, Алонсо (1938), «Конструктивный второй номер класса», Бык. Амер. Математика. Soc., 44 (4): 224–232, Дои:10.1090 / S0002-9904-1938-06720-1
• Клини, С. К. (1938), "Об обозначении порядковых чисел", Журнал символической логики, Ассоциация символической логики, 3 (4): 150–155, Дои:10.2307/2267778, JSTOR  2267778
• Роджерс, Хартли (1987) [1967], Теория рекурсивных функций и эффективной вычислимости, Первое издание MIT в мягкой обложке, ISBN  978-0-262-68052-3
• Феферман, Соломон; Спектор, Клиффорд (1962), "Неполнота на путях развития теорий", Журнал символической логики, 27 (4): 383–390, Дои:10.2307/2964544