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

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

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

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

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

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

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

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

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

ξ-нотация [ править ]

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

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

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

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

Имеем ξ(α, β) < ξ(γ, δ) тогда и только тогда, когда либо (α = γ и β < δ), либо (α < γ и β < ξ(γ, δ)) или (α > γ и ξ(a, b) ⩽ d).

Согласно этому определению, первые несколько ξ-нотаций таковы:

«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» для

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

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

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

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

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

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

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

Veblen [ edit ]

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

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

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

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

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

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

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

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

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

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

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

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

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

ψ _v (α) — наименьший ординал, не принадлежащий C _v (α)

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

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

Эта система имеет примерно такую же силу, как и система Фефермана, поскольку $\theta \varepsilon _{\Omega _{v}+1}0=\psi _{0}(\varepsilon _{\Omega _{v}+1})$ для v ≤ ω. Тем не менее, хотя эта система эффективна, ее нельзя назвать порядковой системой записи. Бухгольц действительно создал соответствующую порядковую запись, но она сложна: определение есть в основной статье.

Клини О [ править ]

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

Список ограничений различных порядковых обозначений и функций свертывания [ править ]

Таблица пределов различных обозначений и функций
Обозначения	Супремум выразимых счетных ординалов
Канторова нормальная форма	Эпсилон-ноль $\varepsilon _{0}$
Бинарная функция Веблена	Порядковый номер Фефермана-Шхютте $\Gamma _{0}$
Финитарная функция Веблена	Малый порядковый номер Веблена
Птица $\theta$ функция	Малый порядковый номер Веблена $\theta (\Omega ^{\omega })$
Расширенная функция Веблена	Большой порядковый номер Веблена
Бахмана $\psi$ функция	Порядковый номер Бахмана – Говарда $\psi _{\Omega }(\varepsilon _{\Omega +1})$
Мадора $\psi$ функция	Порядковый номер Бахмана – Говарда $\psi (\varepsilon _{\Omega +1})$
Вейермана $\vartheta$ функция	Порядковый номер Бахмана – Говарда $\vartheta (\varepsilon _{\Omega +1})$
Фефермана $\theta$ функция	Порядковый номер Такеути – Фефермана – Бухгольца $\theta _{\varepsilon _{\Omega _{\omega }+1}}(0)$
Бухгольца $\psi$ функция	Порядковый номер Такеути – Фефермана – Бухгольца $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$
Ратьен'с $\psi$ функция	$\psi _{\Omega }(\chi _{\varepsilon _{M}+1}(0))$
Ратьен'с $\Psi$ функция	> $\Psi (\varepsilon _{K+1})$
Первый Стегерта $\Psi$ функция	> $\Psi _{(\omega ^{+};{\mathsf {P}}_{0};\epsilon ;\epsilon ;0)}^{\varepsilon _{\Xi }+1}$ ^[1]
Второй Стегерта $\Psi$ функция	> Большой порядковый номер Стегерта $\Psi _{(\omega ^{+};{\mathsf {P}}_{0};\epsilon ;\epsilon ;0)}^{\varepsilon _{Y}+1}$ ^[1]
Тарановского $C$ функция	Существование неизвестно, но рекурсивно и очень велико.
Клини ${\mathcal {O}}$ функция	Порядковый номер Чёрча-Клин $\omega _{1}^{\mathsf {CK}}$
Клев ${\mathcal {O}}^{+}$ функция	Супремум записываемых ординалов $\lambda$
Клев ${\mathcal {O}}^{++}$ функция	Супремум записываемых порядковых номеров $\zeta$

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

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

^ Перейти обратно: ^а ^б Д. Мадор, Зоопарк ординалов (с. 2). По состоянию на 25 октября 2021 г.

, Вильгельм (1951) Математика , Кантора второго сечения класса чисел структура " " , Конструктивная Акерманн
Бахманн, Хайнц (1950), «Нормальные функции и проблема выделенных последовательностей порядковых чисел» (PDF) , Ежеквартальный журнал Общества естественных исследований в Цюрихе (на немецком языке), 95 : 115–147, MR 0036806 ; Английский перевод Мартина Дауда (2019), arXiv : 1903.04609
Бухгольц, В. (1986), «Новая система теоретико-доказательных порядковых функций», Ann. Чистое приложение. Логика , 32 (3): 195–207, doi : 10.1016/0168-0072(86)90052-7 , MR 0865989
«Конструктивные системы порядковых обозначений» Фредрика Гасса.
Клини, SC (1938), «Об обозначениях порядковых чисел», Журнал символической логики , 3 (4): 150–155, doi : 10.2307/2267778 , JSTOR 2267778 , S2CID 34314018
«Гиперарифметические индексные множества в теории рекурсии», Штеффен Лемпп
Гильберт Левиц, Трансфинитные ординалы и их обозначения: для непосвященных , пояснительная статья, 1999 г. (8 страниц, в PostScript )
Миллер, Ларри В. (1976), «Нормальные функции и конструктивные порядковые обозначения», Журнал символической логики , 41 (2): 439–459, doi : 10.2307/2272243 , JSTOR 2272243
Полерс, Вольфрам (1989), Теория доказательств , Конспекты лекций по математике, том. 1407, Берлин: Springer-Verlag, номер номера : 10.1007/978-3-540-46825-7 , ISBN. 978-3-540-51842-6 , МР 1026933
Роджерс, Хартли (1987) [1967], Теория рекурсивных функций и эффективная вычислимость , Первое издание MIT в мягкой обложке, ISBN 978-0-262-68052-3
Шютте, Курт (1977), Теория доказательств , Основы математических наук, том. 225, Берлин-Нью-Йорк: Springer-Verlag, стр. xii+299, ISBN. 978-3-540-07911-8 , МР 0505313
Такеути, Гаиси (1987), Теория доказательств , Исследования по логике и основам математики, том. 81 (второе изд.), Амстердам: North-Holland Publishing Co., ISBN 978-0-444-87943-1 , МР 0882549
Веблен, Освальд (1908), «Непрерывно растущие функции конечных и трансфинитных ординалов», Труды Американского математического общества , 9 (3): 280–292, doi : 10.2307/1988605 , JSTOR 1988605

[stegertzoo-1] Перейти обратно: ^а ^б Д. Мадор, Зоопарк ординалов (с. 2). По состоянию на 25 октября 2021 г.

[1]