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