Порядковые обозначения

В математической логике и теории множеств , порядковое обозначение является частичной функцией из множества всех конечных последовательностей символов из конечного алфавита на счетное множество порядковых и нумерация Геделя является функцией из множества хорошо образованных формул ( Правильно построенная формула - это конечная последовательность символов, на которой определена функция порядкового обозначения) некоторого формального языка к натуральным числам. Это связывает каждую правильно построенную формулу с уникальным натуральным числом, называемым его числом Гёделя. Если гёделевская нумерация фиксирована, то отношение подмножества ординалов индуцирует порядок на правильно сформированных формулах, который, в свою очередь, индуцирует хороший порядок на подмножестве натуральных чисел. АРекурсивная порядковая запись должна удовлетворять следующим двум дополнительным свойствам:

подмножество натуральных чисел является рекурсивным множеством
индуцированный хороший порядок на подмножестве натуральных чисел является рекурсивным соотношением

Существует множество таких схем порядковых обозначений, в том числе схемы Вильгельма Аккермана , Хайнца Бахмана , Вильфрида Бухгольца, Георга Кантора , Соломона Фефермана , Герхарда Егера, Айлса, Пфайффера, Вольфрама Полерса, Курта Шютте , Гайси Такеути (называемые порядковыми диаграммами ), Освальда Веблена. . У Стивена Коула Клини есть система обозначений, называемая О Клини , которая включает порядковые обозначения, но она не так хорошо работает, как другие системы, описанные здесь.

Обычно приступают к определению нескольких функций от порядковых до порядковых и представлению каждой такой функции символом. Во многих системах, таких как хорошо известная система Веблена, функции являются нормальными функциями, то есть они строго возрастают и непрерывны по крайней мере по одному из своих аргументов и возрастают по другим аргументам. Еще одно желаемое свойство таких функций состоит в том, что значение функции больше, чем каждый из ее аргументов, так что порядковый номер всегда описывается в терминах меньших порядковых номеров. Есть несколько таких желательных свойств. К сожалению, ни одна система не может иметь их всех, поскольку они противоречат друг другу.

Упрощенный пример использования функции сопряжения [ править ]

Как обычно, мы должны начать с постоянного символа нуля, «0», который мы можем рассматривать как функцию нулевой арности . Это необходимо, потому что не существует меньших порядковых чисел, с помощью которых можно было бы описать ноль. Наиболее очевидным следующим шагом было бы определение унарной функции «S», которая переводит порядковый номер в наименьший порядковый номер, больший его; другими словами, S - функция-последователь. В сочетании с нулем преемник позволяет назвать любое натуральное число.

Третья функция может быть определена как функция, которая отображает каждый порядковый номер в наименьший порядковый номер, который еще не может быть описан с помощью двух вышеуказанных функций и предыдущих значений этой функции. Это отобразит β в ω · β, за исключением случаев, когда β является фиксированной точкой этой функции плюс конечное число, и в этом случае используется ω · (β + 1).

Четвертая функция будет карта α к ш ^ш · α кроме случаев , когда α является неподвижной точкой , что плюс конечное число в этом случае один использует ш ^ш · (α + 1).

ξ-обозначение [ править ]

Так можно было бы продолжить, но это дало бы нам бесконечное количество функций. Вместо этого давайте объединим унарные функции в двоичную функцию. Путем трансфинитной рекурсии на α мы можем использовать трансфинитную рекурсию на β, чтобы определить ξ (α, β) = наименьший ординал γ такой, что α <γ и β <γ и γ не является значением ξ для любого меньшего α или для тот же α с меньшим β.

Таким образом, определим ξ-обозначения следующим образом:

«0» - это ξ-обозначение нуля.
Если «A» и «B» заменить на ξ-обозначения для α и β в «ξAB», то результатом будет ξ-обозначение для ξ (α, β).
Других ξ-обозначений нет.

Функция ξ определена для всех пар ординалов и взаимно однозначна. Он всегда дает значения, превышающие его аргументы, а его диапазон - все порядковые номера, кроме 0 и эпсилон-чисел (ε = ω ^ε ).

Имеется ξ (α, β) <ξ (γ, δ) тогда и только тогда, когда либо (α = γ и β <δ), либо (α <γ и β <ξ (γ, δ)), либо (α> γ и ξ (α, β) ≤ δ).

В этом определении первые несколько ξ-обозначений следующие:

«0» для 0. «ξ00» для 1. «ξ0ξ00» для ξ (0,1) = 2. «ξξ000» для ξ (1,0) = ω. «ξ0ξ0ξ00» для 3. «ξ0ξξ000» для ω + 1. «ξξ00ξ00» для ω · 2. «ξξ0ξ000» для ω ^ω . «ξξξ0000» для

{\ displaystyle \ omega ^ {\ omega ^ {\ omega}}.}

В общем случае ξ (0, β) = β + 1. В то время как ξ (1 + α, β) = ω ^{ω ^α} · (β + k) для k = 0 или 1 или 2 в зависимости от особых ситуаций:
k = 2, если α - эпсилон-число, а β конечно.
В противном случае k = 1, если β делится на ω ^{ω ^{α + 1}} плюс конечное число.
В противном случае k = 0.

Ξ-нотации могут использоваться для обозначения любого ординала меньше ε ₀ с алфавитом, состоящим только из двух символов («0» и «ξ»). Если эти обозначения расширены путем добавления функций, которые перечисляют эпсилон-числа, тогда они смогут назвать любой порядковый номер, меньший, чем первое эпсилон-число, который не может быть назван добавленными функциями. Это последнее свойство, добавление символов в начальный сегмент порядковых номеров, дает имена в этом сегменте, называется полнотой (в честь Соломона Фефермана ).

Системы порядкового обозначения [ править ]

Существует множество различных систем для порядковых обозначений, введенных разными авторами. Часто бывает довольно сложно переходить от одной системы к другой.

Кантор [ править ]

«Экспоненциальные многочлены» от 0 и ω дают систему порядковых обозначений для порядковых чисел меньше нуля эпсилон . Есть много эквивалентных способов их написания; вместо экспоненциальных полиномов можно использовать корневые деревья, вложенные скобки или систему, описанную выше.

Веблен [ править ]

Функции Веблена с двумя переменными ( Veblen 1908 ) можно использовать для получения системы порядковых обозначений для порядковых чисел, меньших, чем порядковый номер Фефермана-Шютте . Функции Веблена от конечного или трансфинитного числа переменных дают системы порядковых обозначений для ординалов, меньших, чем маленькие и большие ординалы Веблена .

Акерманн [ править ]

Акерманн (1951) описал систему порядковых обозначений более слабую, чем система, описанная ранее Вебленом. Предел его системы иногда называют порядковым номером Аккермана .

Бахманн [ править ]

Бахманн (1950) представил ключевую идею использования несчетных ординалов для создания новых счетных ординалов. Его первоначальная система была довольно громоздкой в использовании, поскольку требовала выбора специальной последовательности, сходящейся к каждому порядковому номеру. Более поздние системы обозначений, введенные Феферманом и другими, позволили избежать этого усложнения.

Такеути (порядковые диаграммы) [ править ]

Такеути (1987) описал очень мощную систему порядковых обозначений, называемую «порядковые диаграммы», которую трудно понять, но позже Феферман упростил.

Θ-функции Фефермана [ править ]

Феферман ввел тета-функции, описанные в Buchholz (1986) следующим образом. Функция для ординала α, θ _α - это функция от ординалов к ординалам. Часто θ _α (β) записывается как θαβ. Множество C (α, β) определяется индукцией по α как набор ординалов, которые могут быть сгенерированы из 0, ω 1 , ω ₂ , ..., ω _ω вместе с ординалами, меньшими чем β, с помощью операций порядкового сложения и функций θ _ξ при ξ <α. А функция θ _γ определяется как функция, перечисляющая ординалы δ с δ∉ C (γ, δ).

Бухгольц [ править ]

Бухгольц (1986) описал следующую систему порядковых обозначений как упрощение тета-функций Фефермана. Определять:

Ω _ξ = ω _ξ, если ξ> 0, Ω ₀ = 1

Функции ψ _v (α) для α - ординала, v - ординала, не превосходящего ω, определяются индукцией по α следующим образом:

ψ _v (α) наименьший ординал не в C _v (α)

где C _v (α) - наименьшее множество такое, что

C _v (α) содержит все ординалы, меньшие, чем Ω _v
C _v (α) замкнута относительно порядкового сложения
C _v (α) замкнута относительно функций ψ _u (при u ≤ω), примененных к аргументам меньше α.

Эта система имеет примерно такую же силу, что и система Феферманса, что и для v ≤ ω. ${\ displaystyle \ theta \ epsilon _ {\ Omega _ {v} +1} 0 = \ psi _ {0} (\ epsilon _ {\ Omega _ {v} +1})}$

Клини ${\ displaystyle {\ mathcal {O}}}$ [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Акерманн, Вильгельм (1951), "Konstruktiver Aufbau eines Abschnitts der zweiten Cantorschen Zahlenklasse", Math. З. , 53 (5): 403-413, DOI : 10.1007 / BF01175640 , МР 0039669
Бухгольц, W. (1986), "Новая система теоретико-доказательственных ординальных функций", Ann. Pure Appl. Логика , 32 (3): 195-207, DOI : 10,1016 / 0168-0072 (86) 90052-7 , МР 0865989
"Конструктивные системы порядковых обозначений" Фредрика Гасса
Клини, SC (1938), "О Notation для порядковых чисел", Журнал символической логики , 3 (4): 150-155, DOI : 10,2307 / 2267778 , JSTOR 2267778
"Гиперарифметические индексные множества в теории рекурсии" Штеффен Лемпп
Гильберт Левитц, Трансфинитные порядковые числа и их обозначения: для непосвященных , пояснительная статья, 1999 г. (8 страниц, в PostScript )
Миллер, Ларри W. (1976), "Нормальные функции и конструктивные Порядковые нотации", журнал символической логики , 41 (2): 439-459, DOI : 10,2307 / 2272243 , JSTOR 2272243
Pohlers, Вольфрам (1989), теория доказательств , конспект лекций по математике, 1407 , Берлин: Springer-Verlag, doi : 10.1007 / 978-3-540-46825-7 , ISBN 978-3-540-51842-6, MR 1026933
Роджерс, Хартли (1987) [1967], Теория рекурсивных функций и эффективной вычислимости , первое издание MIT в мягкой обложке, ISBN 978-0-262-68052-3
Шютте, Курт (1977), Теория доказательств , Grundlehren der Mathematischen Wissenschaften, 225 , Берлин-Нью-Йорк: Springer-Verlag, стр. Xii + 299, ISBN 978-3-540-07911-8, Руководство по ремонту 0505313
Такеути, Гайси (1987), Теория доказательства , Исследования в области логики и основ математики, 81 (второе издание), Амстердам: North-Holland Publishing Co., ISBN 978-0-444-87943-1, MR 0882549
Веблен, Освальд (1908), "Непрерывные возрастающие функции конечных и трансфинитов", Труды Американского математического общества , 9 (3): 280-292, DOI : 10,2307 / 1988605 , JSTOR 1988605