Ординалы в теории множеств и вычислимости

Введение

Порядковые числа в математике и теории множеств
В математической дисциплине теории множеств существует множество способов описания конкретных счётных порядковых чисел. Наименьшие из них могут быть полезно и нециклично выражены в терминах их нормальных форм Кантора. Помимо этого, многие порядковые числа, важные для теории доказательств, всё ещё имеют вычислимые порядковые обозначения (см. ординальный анализ). Однако невозможно эффективно определить, является ли данное предполагаемое порядковое обозначение корректным обозначением или нет (по причинам, аналогичным неразрешимости проблемы останова); доступны различные более конкретные способы определения порядковых чисел, которые гарантированно имеют обозначения. Поскольку существует лишь счётное количество обозначений, все порядковые числа с обозначениями исчерпываются значительно ниже первого несчётного порядкового числа ω1; их супремум называется ω1 Чёрча — Клини или ω (что не следует путать с первым несчётным порядковым числом ω1), описанным ниже. Порядковые числа, меньшие ω, являются рекурсивными порядковыми числами (см. ниже). Счётные порядковые числа, большие этого, всё ещё могут быть определены, но не имеют обозначений. Ввиду акцента на счётных порядковых числах, повсеместно используется порядковая арифметика, если не указано иное. Описанные здесь порядковые числа не столь велики, как те, что рассматриваются в теории больших кардиналов, но они велики среди тех, которые имеют конструктивные обозначения (описания). Можно определять всё более и более крупные порядковые числа, но их описание становится всё более сложным.

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

Вычислимые ординалы (или рекурсивные ординалы) — это определенные счетные ординалы: грубо говоря, те, которые представляются вычислимой функцией. Существует несколько эквивалентных определений: самое простое состоит в том, чтобы сказать, что вычислимый ординал является типом порядка некоторой рекурсивной (т. е. вычислимой) хорошо упорядоченной последовательности натуральных чисел; таким образом, по сути, ординал является рекурсивным, когда мы можем представить множество меньших ординалов таким образом, чтобы компьютер (машина Тьюринга, например) мог манипулировать ими (и, по сути, сравнивать их). Другое определение использует систему ординальных обозначений Клине. Вкратце, ординальное обозначение — это либо имя нуля (описывающее ординал 0), либо преемник ординального обозначения (описывающий преемник ординала, описанного этим обозначением), либо машина Тьюринга (вычислимая функция), которая производит возрастающую последовательность ординальных обозначений (описывающую ординал, являющийся пределом этой последовательности). Ординальные обозначения (частично) упорядочены таким образом, чтобы преемник *o* был больше *o*, а предел был больше любого члена последовательности (этот порядок вычислим; однако, множество *O* ординальных обозначений само по себе крайне нерекурсивно из-за невозможности определить, действительно ли данная машина Тьюринга производит последовательность обозначений). Рекурсивный ординал — это ординал, описанный некоторым ординальным обозначением. Любой ординал, меньший рекурсивного ординала, сам является рекурсивным, поэтому множество всех рекурсивных ординалов образует определенный (счетный) ординал, ординал Черча — Клине (см. ниже). Соблазнительно забыть об ординальных обозначениях и говорить только о самих рекурсивных ординалах: и некоторые утверждения, касающиеся рекурсивных ординалов, на самом деле относятся к обозначениям этих ординалов. Однако это приводит к трудностям, поскольку даже самый маленький бесконечный ординал, ω, имеет множество обозначений, некоторые из которых нельзя доказать эквивалентными очевидному обозначению (самой простой программе, перечисляющей все натуральные числа).

Отношение к системам арифметики

Существует связь между вычислимыми ординалами и определенными формальными системами (содержащими арифметику, то есть, по крайней мере, разумный фрагмент арифметики Пеано). Некоторые вычислимые ординалы настолько велики, что, хотя они могут быть заданы определенным порядковым обозначением *o*, данная формальная система может оказаться недостаточно мощной, чтобы показать, что *o* действительно является порядковым обозначением: система не доказывает трансфинитную индукцию для таких больших ординалов. Например, обычные аксиомы Пеано первого порядка не доказывают трансфинитную индукцию для (или выше) ε₀: хотя ординал ε₀ может быть легко описан арифметически (он счетен), аксиомы Пеано недостаточно сильны, чтобы показать, что это действительно ординал; фактически, трансфинитная индукция на ε₀ доказывает непротиворечивость аксиом Пеано (теорема Дженцена), поэтому, согласно второй теореме о неполноте Гёделя, аксиомы Пеано не могут формализовать это рассуждение. (Это лежит в основе теоремы Кирби — Париса о последовательностях Гудштейна.) Поскольку арифметика Пеано может доказать, что любой ординал меньше ε₀ хорошо упорядочен, мы говорим, что ε₀ измеряет доказательную силу аксиом Пеано. Но мы можем делать это и для систем, значительно превосходящих аксиомы Пеано. Например, доказательная сила теории множеств Крипке — Платека — это ординал Бахмана — Ховарда, и, фактически, достаточно просто добавить к аксиомам Пеано аксиомы, утверждающие хорошее упорядочение всех ординалов ниже ординала Бахмана — Ховарда, чтобы получить все арифметические следствия теории множеств Крипке — Платека.

Предсказательные определения и иерархия Веблена

Мы уже упоминали (см. нормальную форму Кантора) порядковый номер ε₀, который является наименьшим, удовлетворяющим уравнению , поэтому он является пределом последовательности 0, 1, ω, ω², ω³, … Следующий порядковый номер, удовлетворяющий этому уравнению, называется ε₁: это предел последовательности … В более общем случае, n-й порядковый номер, такой что ψ(α) = α, называется εₙ. Мы могли бы определить εₙ как наименьший порядковый номер, такой что ψ(α) = α, но поскольку в греческом алфавите нет трансфинитно многих букв, лучше использовать более устойчивую нотацию: определим порядковые числа с помощью трансфинитной индукции следующим образом: пусть ε₀ = 0 и пусть εₙ₊₁ будет (n+1)-й неподвижной точкой функции ψ (т.е., (n+1)-й порядковый номер, такой что ψ(α) = α; так, например, ε₁ = ω). А когда n является пределом, определим εₙ как (n)-ю общую неподвижную точку функции ψ для всех m < n. Это семейство функций известно как иерархия Веблена (существуют несущественные вариации в определении, например, допустим, для предельного n, εₙ является пределом εₘ для m < n: это по существу лишь сдвигает индексы на 1, что не имеет значения). Функция εₙ называется функцией Веблена (с основанием ω). Порядок: εₙ < εₘ тогда и только тогда, когда либо (n < m и εₙ < εₘ) либо (n = m и ψ(εₙ) < ψ(εₘ)) либо (n < m и ψ(εₙ) < εₘ).

Ординал FefermanSchütte и далее

Самый маленький порядковый номер, известный как ординал Фефермана — Шютте, обычно записывается как Γ₀. Его можно описать как множество всех порядковых номеров, которые могут быть записаны в виде конечных выражений, начиная с нуля, с использованием только иерархии Веблена и сложения. Ординал Фефермана — Шютте важен, поскольку, в некотором сложно точном смысле, это наименьший (бесконечный) ординал, который нельзя ("предикативно") описать, используя меньшие ординалы. Он измеряет силу систем, таких как "арифметическая трансфинитная рекурсия". В более общем виде, Γα перечисляет ординалы, которые нельзя получить из меньших ординалов, используя сложение и функции Веблена. Разумеется, можно описать ординалы, превосходящие ординал Фефермана — Шютте. Можно продолжать искать фиксированные точки всё более и более сложным образом: перечислить фиксированные точки φ₀, затем перечислить фиксированные точки этого, и так далее, а затем искать первый ординал α, такой что α получается за α шагов этого процесса, и продолжать диагонализацию таким ad hoc образом. Это приводит к определению "малых" и "больших" ординалов Веблена.

Непредсказуемые порядковые числа

Чтобы выйти далеко за пределы ординала Фефермана — Шутте, необходимо ввести новые методы. К сожалению, пока не существует стандартного способа это сделать: кажется, что каждый автор в этой области изобрел свою собственную систему обозначений, и довольно сложно переводить между различными системами. Первая такая система была введена Бахманом в 1950 году (в порядке ad hoc), а различные её расширения и вариации были описаны Бухгольцем, Такеути (ординарные диаграммы), Феферманом (θ-системы), Ацзелем, Бриджем, Шутте и Полерсом. Однако большинство систем используют одну и ту же основную идею — построение новых счётных ординалов с использованием существования определённых несчётных ординалов. Вот пример такого определения, описанного гораздо подробнее в статье о функции коллапса ординалов: ψ(α) определяется как наименьший ординал, который нельзя построить, начиная с 0, 1, ω и Ω, и последовательно применяя сложение, умножение и возведение в степень, а также ψ к ранее построенным ординалам (с оговоркой, что ψ можно применять только к аргументам, меньшим α, чтобы обеспечить его корректность). Здесь Ω = ω1 — первый несчётный ординал. Он вводится, потому что в противном случае функция ψ «застревала» бы на наименьшем ординале σ, таком что εσ = σ: в частности, ψ(α) = σ для любого ординала α, удовлетворяющего σ ≤ α ≤ Ω. Однако тот факт, что мы включили Ω, позволяет нам преодолеть эту точку: ψ(Ω+1) больше σ. Ключевым свойством Ω, которое мы использовали, является то, что оно больше любого ординала, порождённого ψ. Чтобы построить ещё большие ординалы, мы можем расширить определение ψ, добавив больше способов построения несчётных ординалов. Существует несколько способов это сделать, описанных в некоторой степени в статье о функции коллапса ординалов. Ординал Бахмана — Говарда (иногда просто называемый ординалом Говарда, ψ0(εΩ+1) в указанных обозначениях) является важным, поскольку он описывает доказательную силу теории множеств Крипке — Платека. Действительно, основная важность этих больших ординалов и причина их описания заключается в их связи с определёнными формальными системами, как было объяснено выше. Однако такие мощные формальные системы, как полная арифметика второго порядка, не говоря уже о теории множеств Цермело — Френкеля, пока представляются недостижимыми.

За пределы допустимых порядковых чисел

является наименьшим пределом допустимых ординалов (упомянутых далее), однако сам ординал допустимым не является. Это также наименьший ординал, являющийся моделью полноты. Ординал, который одновременно допустим и является пределом допустимых ординалов, или, эквивалентно, такой, что является -м допустимым ординалом, называется рекурсивно недоступным, а наименьший рекурсивно недоступный ординал может быть обозначен как . Ординал, который одновременно рекурсивно недоступен и является пределом рекурсивно недоступных ординалов, называется рекурсивно гипери недоступным. С.171

Но следует отметить, что мы по-прежнему говорим о, возможно, счетных ординалах. (Хотя существование недоступных или кардиналов Мало не может быть доказано в теории множеств Цермело — Френкеля, существование рекурсивно недоступных или рекурсивно Мало ординалов является теоремой ZFC: фактически, любой регулярный кардинал является рекурсивно Мало и даже больше, но даже если мы ограничимся счетными ординалами, ZFC доказывает существование рекурсивно Мало ординалов. Однако они недостижимы для теории множеств Крипке — Платека.)

Отражение

Для множества формул предельный ординал называется отражающим, если его ранг удовлетворяет определенному свойству отражения для каждой формулы. Эти ординалы возникают при порядковом анализе теорий, таких как KP+Π3 ref, теории, расширяющей теорию множеств Крипке-Платека схемой отражения. Их также можно рассматривать как "рекурсивные аналоги" некоторых несчётных кардиналов, таких как слабо компактные и неизобразимые кардиналы. Например, ординал, который является отражающим, называется рекурсивно слабо компактным. Для конечных ординалов наименьший отражающий ординал также является супремумом замыкающих ординалов монотонных индуктивных определений, графы которых являются Πm+10.

Непроектируемость

Допустимый ординал называется непроектируемым, если не существует тотальной рекурсивной инъективной функции, отображающей его в меньший ординал. (Это тривиально верно для регулярных кардиналов; однако нас в основном интересуют счетные ординалы.) Непроектируемость – гораздо более сильное условие, чем допустимость, рекурсивная недоступность или даже рекурсивная Мало. Это утверждение эквивалентно утверждению о том, что Вселенная Гёделя L до стадии α порождает модель KP + разделения. Однако само по себе разделение (без KP) недостаточно сильная схема аксиом, чтобы подразумевать непроектируемость; на самом деле существуют транзитивные модели ZFC + разделения любой счетной допустимой высоты.
Непроектируемые ординалы связаны с работой Дженсена над проектами. Наименьшие ординалы, непроектируемые относительно данного множества, связаны с построением Харрингтоном наименьшего отражающего класса Спектора 2.

Стабильные порядковые числа

Даже более крупные счетные ординалы, называемые стабильными ординалами, могут быть определены условиями неописуемости или как такие, что является Σ1-элементарной подмоделью L. Существование этих ординалов может быть доказано в ZFC, и они тесно связаны с непроектируемыми ординалами с точки зрения теории моделей. Счетный ординал α называется стабильным, если α является наименьшим допустимым ординалом, большим допустимого ординала, большего α.

Псевдо-хороший порядок

В рамках схемы обозначений Клине некоторые представляют порядковые числа, а некоторые – нет. Можно определить рекурсивное линейное упорядочение, являющееся подмножеством обозначений Клине и имеющее начальный сегмент, который хорошо упорядочен с типом порядка ω. Любое рекурсивно перечислимое (или даже гиперарифметическое) непустое подмножество этого линейного упорядочения имеет наименьший элемент. Таким образом, оно в некотором смысле напоминает хорошее упорядочение. Например, на нем можно определить арифметические операции. Однако эффективно определить, где заканчивается начальная хорошо упорядоченная часть и начинается часть, не имеющая наименьшего элемента, невозможно. В качестве примера рекурсивного псевдо-хорошего упорядочения пусть S будет ATR0 или другой рекурсивно аксиоматизируемой теорией, имеющей ω-модель, но не имеющей гиперарифметических ω-моделей, и (при необходимости) консервативно расширим S функциями Сколема. Пусть T – дерево (по существу) конечных частичных ω-моделей S: последовательность натуральных чисел принадлежит T, если S вместе с ∃m φ(m) ⇒ φ(x⌈φ⌉) (для первых n формул φ с одной числовой свободной переменной; ⌈φ⌉ – число Гёделя) не имеет доказательства противоречивости длиной менее n. Тогда порядок Клине — Брауэра на T является рекурсивным псевдо-хорошим упорядочением. Любая такая конструкция должна иметь тип порядка ω^α, где α – тип порядка ω, а ω^α – рекурсивное порядковое число.

Как рекурсивные, так и нерекурсивные порядковые числа

Майкл Ратхен, "Область ординального анализа". В С. Б. Купер и Дж. Трасс (ред.): Множества и доказательства. (Кембриджский университетский пресс, 1999) 219–279. В виде PostScript-файла.