Ординал ε₀

Ординал ε₀ (эпсилон-ноль) — это наименьший эпсилон-число, то есть наименьший ординал, удовлетворяющий уравнению ε = ω^ε, где ω — наименьший бесконечный ординал. В теории множеств и теории доказательств ε₀ является ключевым объектом, обозначающим доказательную силу арифметики Пеано первого порядка (PA). Он представляет собой предельный ординал, который не может быть достигнут путём конечного применения операций сложения, умножения и возведения в степень, начиная с ω, и является первым ординалом, для которого не существует конечной системы обозначений в рамках обычной канторовской нормальной формы.

Определение и формальное построение

Ординал ε₀ определяется как наименьшая неподвижная точка функции f(α) = ω^α. Иными словами, ε₀ = sup{ω, ω^ω, ω^(ω^ω), ω^(ω^(ω^ω)), …}. Эта последовательность, известная как «башня из степеней ω», не имеет предела в пределах счётных ординалов, получаемых с помощью конечного числа операций, и её предел и есть ε₀.

Формально, ε₀ = ω↑↑ω, где ↑↑ обозначает тетрацию (повторное возведение в степень). В терминах ординальной арифметики это означает, что ε₀ = ω^ε₀. Другие эпсилон-числа (ε₁, ε₂, …) определяются аналогично как неподвижные точки, большие ε₀, но ε₀ является наименьшим из них.

Свойства

Порядковый тип и мощность

Ординал ε₀ является счётным ординалом, то есть его мощность равна алеф-нулю (ℵ₀). Несмотря на свою бесконечную сложность, он остаётся счётным, так как является объединением счётного числа счётных ординалов. Порядковый тип ε₀ — это тип вполне упорядоченного множества, которое не может быть представлено в виде конечного выражения с использованием только ω и операций сложения, умножения и возведения в степень.

Недостижимость в канторовской нормальной форме

Канторовская нормальная форма для ординалов вида α = ω^β₁·n₁ + ω^β₂·n₂ + … + ω^βₖ·nₖ, где β₁ > β₂ > … > βₖ, не может быть применена к ε₀ непосредственно, так как ε₀ = ω^ε₀, что приводит к бесконечной рекурсии. Это свойство делает ε₀ первым ординалом, который не может быть записан в конечной канторовской нормальной форме без использования эпсилон-чисел.

Ординальная арифметика

Для ε₀ выполняются следующие соотношения:

• ε₀ = ω^ε₀.
• ε₀ + 1 > ε₀, но ε₀ + 1 < ε₀·2, ε₀·2 < ε₀·ω, и так далее, вплоть до ε₀·ω, которое всё ещё меньше ε₀^2.
• ε₀^ω = ω^(ε₀·ω) = ω^(ω^(ε₀+1)) = ε₀^ω, что также меньше ε₀^ε₀.

История и происхождение

Понятие эпсилон-чисел было введено Георгом Кантором в конце XIX века в рамках его теории трансфинитных чисел. Кантор искал способы описания ординалов, которые не могут быть получены с помощью конечного числа операций, и определил ε₀ как наименьший ординал, удовлетворяющий уравнению ε = ω^ε. Впоследствии это понятие стало фундаментальным в теории доказательств, особенно в работах Герхарда Генцена (1936 год), который показал, что непротиворечивость арифметики Пеано может быть доказана с помощью трансфинитной индукции вплоть до ε₀.

Применение в теории доказательств

Доказательная сила арифметики Пеано

Ординал ε₀ играет центральную роль в теории доказательств как ординал, соответствующий доказательной силе арифметики Пеано первого порядка (PA). Генцен доказал, что если предположить трансфинитную индукцию вплоть до ε₀, то можно доказать непротиворечивость PA. При этом сама PA не может доказать непротиворечивость трансфинитной индукции до ε₀, что делает этот ординал точной мерой её доказательной силы.

Ординальный анализ

В теории доказательств ординал ε₀ используется для классификации формальных систем. Системы, доказательная сила которых не превышает ε₀, считаются «слабыми» по сравнению с системами, такими как арифметика второго порядка или теория множеств Цермело — Френкеля. Ординальный анализ позволяет определить, до какого ординала может быть проведена трансфинитная индукция в рамках данной системы.

Связь с другими математическими объектами

Функция Веблена

Ординал ε₀ является первым элементом иерархии эпсилон-чисел, которая обобщается с помощью функции Веблена φ(α, β). В этой иерархии ε₀ = φ(1, 0), где φ(0, β) = ω^β, а φ(1, β) — это β-е эпсилон-число. Функция Веблена позволяет строить ещё более крупные ординалы, такие как φ(2, 0) (критический ординал для функции φ(1, β)), φ(ω, 0) и так далее.

Тетрация и башни степеней

В терминах гиперопераций ε₀ = ω↑↑ω, где ↑↑ обозначает тетрацию. Это означает, что ε₀ — это результат бесконечного повторения возведения в степень. В отличие от конечных тетраций, таких как ω↑↑3 = ω^(ω^ω), бесконечная тетрация не имеет конечного выражения и требует введения эпсилон-чисел.

Примеры и иллюстрации

Последовательность, сходящаяся к ε₀

Последовательность ординалов, предел которой равен ε₀, выглядит следующим образом:

• α₀ = ω,
• α₁ = ω^ω,
• α₂ = ω^(ω^ω),
• α₃ = ω^(ω^(ω^ω)),
• …
• αₙ = ω↑↑(n+1),
• sup{αₙ | n < ω} = ε₀.

Сравнение с другими ординалами

• ε₀ > ω, ω^ω, ω^(ω^ω) и так далее.
• ε₀ < ω₁ (первый несчётный ординал).
• ε₀ < ω₁^CK (первый нерекурсивный ординал).
• ε₀ < ω_ω (предел последовательности ω, ω₁, ω₂, …).

Интересные факты

• Ординал ε₀ является наименьшим ординалом, для которого не существует конечной системы обозначений в рамках обычной канторовской нормальной формы. Это делает его важным примером в теории рекурсивных ординалов.
• В теории вычислимости ε₀ является рекурсивным ординалом, то есть существует вычислимое вполне упорядочение натуральных чисел с типом порядка ε₀.
• В некоторых контекстах ε₀ обозначается как ω↑↑ω, что подчёркивает его связь с тетрацией.
• Ординал ε₀ используется в анализе систем, основанных на арифметике Пеано, и является границей, после которой начинаются более сильные теории, такие как арифметика второго порядка.

Критика и ограничения

Несмотря на свою важность, ординал ε₀ не является максимальным в иерархии эпсилон-чисел. Существуют ординалы ε₁, ε₂, …, ε_ω, …, ε_ε₀, …, которые ещё больше. Кроме того, ε₀ не является недостижимым или компактным ординалом в смысле теории множеств; он лишь первый из эпсилон-чисел. В более широком контексте, например, в теории множеств Цермело — Френкеля, существуют ординалы, значительно превосходящие ε₀, такие как ординалы Фефермана — Шютте (Γ₀) или ординалы, связанные с аксиомой недостижимости.

Источники

• Кантор, Г. «Основы общего учения о многообразиях» (1883).
• Генцен, Г. «Непротиворечивость арифметики» (1936).
• Такеути, Г. «Теория доказательств» (1975).
• Джех, Т. «Теория множеств» (2003).
• Погорельский, В. «Ординалы и их применение в теории доказательств» (2010).