В математической логике и теории множеств порядковая нотация — это частичная функция, отображающая множество всех конечных последовательностей символов, которые сами являются членами конечного алфавита, в счетное множество порядковых чисел . Геделева нумерация — это функция, отображающая множество правильно построенных формул (конечную последовательность символов, на которой определена функция порядковой нотации) некоторого формального языка в натуральные числа. Это связывает каждую правильно построенную формулу с уникальным натуральным числом, называемым ее числом Геделя. Если гедева нумерация фиксирована, то отношение подмножества на ординалах индуцирует упорядочение на правильно построенных формулах, которое, в свою очередь, индуцирует правильное упорядочение на подмножестве натуральных чисел. Рекурсивная порядковая нотация должна удовлетворять следующим двум дополнительным свойствам:
Существует много таких схем порядковых обозначений, включая схемы Вильгельма Аккермана , Хайнца Бахмана , Вильфрида Бухгольца, Георга Кантора , Соломона Фефермана , Герхарда Йегера, Айлза, Пфайффера, Вольфрама Полерса, Курта Шютте , Гайси Такеути (называемые порядковыми диаграммами ), Освальда Веблена . У Стивена Коула Клини есть система обозначений, называемая O Клини , которая включает порядковые обозначения, но она не так хорошо себя ведет, как другие системы, описанные здесь.
Обычно приступают к определению нескольких функций от ординалов к ординалам и представлению каждой такой функции символом. Во многих системах, таких как известная система Веблена, функции являются нормальными функциями, то есть они строго возрастают и непрерывны по крайней мере по одному из своих аргументов и возрастают по другим аргументам. Другим желательным свойством для таких функций является то, что значение функции больше, чем каждый из ее аргументов, так что ординал всегда описывается в терминах меньших ординалов. Существует несколько таких желательных свойств. К сожалению, ни одна система не может обладать всеми из них, поскольку они противоречат друг другу.
Как обычно, мы должны начать с постоянного символа для нуля, "0", который мы можем рассматривать как функцию арности ноль. Это необходимо, поскольку нет меньших ординалов, в терминах которых можно описать ноль. Самым очевидным следующим шагом было бы определение унарной функции, "S", которая переводит ординал в наименьший ординал, больший его; другими словами, S является функцией-последователем. В сочетании с нулем, функция-последователь позволяет назвать любое натуральное число.
Третья функция может быть определена как функция, которая отображает каждый ординал в наименьший ординал, который пока не может быть описан с помощью двух вышеуказанных функций и предыдущих значений этой функции. Это отображало бы β в ω·β, за исключением случая, когда β является фиксированной точкой этой функции плюс конечное число, в этом случае используется ω·(β+1).
Четвертая функция отображает α в ω ω ·α, за исключением случая, когда α является фиксированной точкой этого множества плюс конечное число; в этом случае используется ω ω ·(α+1).
Можно было бы продолжать в том же духе, но это дало бы нам бесконечное число функций. Поэтому вместо этого давайте объединим унарные функции в бинарную функцию. С помощью трансфинитной рекурсии по α мы можем использовать трансфинитную рекурсию по β, чтобы определить ξ(α,β) = наименьшее порядковое число γ такое, что α < γ и β < γ и γ не является значением ξ для любого меньшего α или для того же α с меньшим β.
Таким образом, определим ξ-обозначения следующим образом:
Функция ξ определена для всех пар ординалов и является взаимно-однозначной. Она всегда дает значения, большие, чем ее аргументы, и ее областью действия являются все ординалы, отличные от 0 и чисел эпсилон (ε=ω ε ) .
Имеем ξ(α, β) < ξ(γ, δ) тогда и только тогда, когда либо (α = γ и β < δ), либо (α < γ и β < ξ(γ, δ)) или (α > γ и ξ(α, β) ≤ δ).
При таком определении первые несколько ξ-обозначений таковы:
В общем случае ξ(0,β) = β+1. В то время как ξ(1+α,β) = ω ω α ·(β+k) для k = 0, 1 или 2 в зависимости от особых ситуаций:
k = 2, если α — эпсилон-число и β конечно.
В противном случае k = 1, если β кратно ω ω α+1 плюс конечное число.
В противном случае к = 0.
ξ-нотации могут использоваться для наименования любого порядкового числа, меньшего ε 0, с алфавитом всего из двух символов («0» и «ξ»). Если эти нотации расширить, добавив функции, которые перечисляют эпсилон-числа, то они смогут наименования любого порядкового числа, меньшего первого эпсилон-числа, которое не может быть наименовано добавленными функциями. Это последнее свойство, добавление символов в начальный сегмент порядкового числа дает имена в пределах этого сегмента, называется полнотой (в честь Соломона Фефермана ).
Существует много различных систем порядковой записи, введенных разными авторами. Часто бывает довольно сложно конвертировать между различными системами.
«Экспоненциальные многочлены» от 0 и ω дают систему порядковых обозначений для порядковых чисел, меньших ε 0 . Существует много эквивалентных способов их записи; вместо экспоненциальных многочленов можно использовать корневые деревья, или вложенные скобки, или систему, описанную выше.
Функции Веблена с двумя переменными (Веблен 1908) можно использовать для создания системы порядковых обозначений для ординалов, меньших ординала Фефермана-Шютте . Функции Веблена с конечным или трансфинитным числом переменных дают системы порядковых обозначений для ординалов, меньших малого и большого ординалов Веблена .
Аккерман (1951) описал систему порядковой нотации, которая была слабее, чем система, описанная ранее Вебленом. Предел его системы иногда называют порядковой записью Аккермана .
Бахман (1950) ввел ключевую идею использования несчетных ординалов для получения новых счетных ординалов. Его первоначальная система была довольно громоздкой в использовании, поскольку требовала выбора специальной последовательности, сходящейся к каждому ординалу. Более поздние системы обозначений, введенные Феферманом и другими, избежали этого усложнения.
Такеути (1987) описал очень мощную систему порядковой записи, называемую «порядковыми диаграммами», которая сложна для понимания, но позднее была упрощена Феферманом.
Феферман ввел тета-функции, описанные в работе Бухгольца (1986) следующим образом. Для ординала α, θ α является функцией, отображающей ординалы в ординалы. Часто θ α (β) записывается как θαβ. Множество C (α, β) определяется индукцией по α как множество ординалов, которые могут быть получены из 0, ω 1 , ω 2 , ..., ω ω , вместе с ординалами, меньшими β, с помощью операций сложения ординалов и функций θ ξ для ξ < α. А функция θ γ определяется как функция, перечисляющая ординалы δ с δ ∉ C (γ,δ). Проблема этой системы в том, что порядковые обозначения и функции свертывания не идентичны, и поэтому эта функция не может считаться порядковой записью. Связанная с ней порядковая запись неизвестна.
Бухгольц (1986) описал следующую систему порядковой записи как упрощение тета-функций Фефермана. Определите:
Функции ψ v (α) для α — ординала, v — ординала не выше ω, определяются индукцией по α следующим образом:
где C v (α) — наименьшее множество, такое что
Эта система имеет примерно такую же силу, как и система Фефермана, как и для v ≤ ω. Тем не менее, хотя эта система и мощна, она не может считаться порядковой нотацией. Бухгольц создал связанную порядковую нотацию, но она сложна: определение приведено в основной статье.
Клини (1938) описал систему обозначений для всех рекурсивных ординалов (меньше ординала Чёрча-Клини ). К сожалению, в отличие от других систем, описанных выше, в общем случае не существует эффективного способа определить, представляет ли некоторое натуральное число ординал или два числа представляют один и тот же ординал. Однако можно эффективно найти обозначения, которые представляют ординальную сумму, произведение и степень (см. ординальную арифметику ) любых двух данных обозначений в Клини ; и для любого обозначения для ординала существует рекурсивно перечислимое множество обозначений, которое содержит один элемент для каждого меньшего ординала и эффективно упорядочено. Клини обозначает каноническое (и очень невычислимое) множество обозначений. Оно использует подмножество натуральных чисел вместо конечных строк символов и не является рекурсивным, поэтому, опять же, не подпадает под определение ординальной нотации.
