Введение

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

Свойства

1=α · 0 = 0 · α = 0, и свойство нулевого произведения выполняется: 1=α · β = 0 → α = 0 или 1=β = 0. Порядковый 1 является мультипликативным нейтральным элементом, 1=α · 1 = 1 · α = α. Умножение ассоциативно, 1=(α · β) · γ = α · (β · γ). Умножение строго возрастает и непрерывно по правому аргументу: (α < β и γ > 0) → γ·α < γ·β. Умножение не строго возрастает по левому аргументу, например, 1 < 2, но 1=1 · ω = 2 · ω = ω. Однако оно (нестрого) возрастает, то есть α ≤ β → α·γ ≤ β·γ. Умножение порядковых чисел в общем случае некоммутативно. В частности, натуральное число, большее 1, никогда не коммутирует с каким-либо бесконечным порядковым числом, а два бесконечных порядковых числа α и β коммутируют тогда и только тогда, когда 1=α^(m) = β^(n) для некоторых ненулевых натуральных чисел m и n. Отношение "α коммутирует с β" является отношением эквивалентности на порядковых числах, больших 1, и все классы эквивалентности счетно бесконечны. Распределительность выполняется слева: 1=α(β + γ) = αβ + αγ. Однако закон распределительности справа 1=(β + γ)α = βα+γα не выполняется в общем случае: 1=(1 + 1) · ω = 2 · ω = ω, в то время как 1=1 · ω + 1 · ω = ω + ω, что отличается. Существует закон левого сокращения: если α > 0 и 1=α · β = α · γ, то 1=β = γ. Правое сокращение не работает, например, 1=1 · ω = 2 · ω = ω, но 1 и 2 различны. Свойство деления с остатком слева выполняется: для всех α и β, если β > 0, то существуют единственные γ и δ такие, что 1=α = β · γ + δ и 1=δ < β. Деление справа не работает: не существует α такого, что 1=α · ω ≤ ω^(ω) ≤ (α + 1) · ω. Порядковые числа образуют левое полукольцо, но не образуют кольцо. Следовательно, порядковые числа не являются евклидовым кольцом, поскольку они даже не являются кольцом; кроме того, евклидова "норма" была бы порядковой, определяемой с помощью деления слева. Число δ (см. Мультипликативно неразложимый порядковый номер) — это порядковый номер β, больший 1, такой, что 1=αβ = β, когда 0 < α < β. Они состоят из порядкового числа 2 и порядковых чисел вида 1=β = ω^(ω^(γ)).

Свойства

1=α^(0) = 1. Если 0 < α, то 1=0^(α) = 0. 1=1^(α) = 1. 1=α^(1) = α. 1=α^(β) · α^(γ) = α^(β + γ). 1=(α^(β))^(γ) = α^(β·γ). Существуют α, β и γ, для которых 1=(α · β)^(γ) ≠ α^(γ) · β^(γ). Например, 1=(ω · 2)^(2) = ω·2·ω·2 = ω^(2) · 2 ≠ ω^(2) · 4. Порядковая экспонента строго возрастает и непрерывна относительно правого аргумента: если γ > 1 и α < β, то γ^(α) < γ^(β). Если α < β, то α^(γ) ≤ β^(γ). Обратите внимание, например, что 2 < 3, но при этом 1=2^(ω) = 3^(ω) = ω. Если α > 1 и 1=α^(β) = α^(γ), то 1=β = γ. Если 1=α = 1 или 1=α = 0, это не так. Для всех α и β, если β > 1 и α > 0, то существуют единственные γ, δ и ρ такие, что 1=α = β^(γ) · δ + ρ, где 0 < δ < β и ρ < β^(γ). Якобсталь показал, что единственные решения уравнения 1=α^(β) = β^(α) при α ≤ β имеют вид 1=α = β, или 1=α = 2 и 1=β = 4, или α – любое предельное порядковое число, и 1=β = εα, где ε – число ε, большее чем α.

За пределами экспоненциализации

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

Большие подсчитываемые порядковые числа

Как обсуждалось выше, нормальная форма Кантора ординалов меньше ε0 может быть выражена в алфавите, содержащем только символы функций для сложения, умножения и возведения в степень, а также константные символы для каждого натурального числа и для ω. Мы можем обойтись без бесконечного множества числовых обозначений, используя только константный символ 0 и операцию следования, S (например, натуральное число 4 может быть выражено как S(S(S(S(0))))). Это описывает ординальную нотацию: систему для именования ординалов с использованием конечного алфавита. Эта конкретная система ординальной нотации называется множеством арифметических ординальных выражений и может выражать все ординалы меньше ε0, но не может выражать ε0. Существуют другие ординальные нотации, способные представлять ординалы, значительно превышающие ε0, но поскольку существует лишь счетное количество строк конечной длины над любым конечным алфавитом, для любой заданной ординальной нотации найдутся ординалы меньше ω1 (первого несчётного ординала), которые не могут быть выражены. Такие ординалы известны как большие счётные ординалы. Операции сложения, умножения и возведения в степень являются примерами примитивно рекурсивных ординальных функций, и более общие примитивно рекурсивные ординальные функции могут быть использованы для описания больших ординалов.

Арифметика Нимбера

Существуют арифметические операции над порядковыми числами благодаря взаимно однозначному соответствию между порядковыми числами и числами Ним. Три распространённые операции над числами Ним — это сложение Ним, умножение Ним и минимальное исключенное значение (mex). Сложение Ним является обобщением побитовой операции исключающего ИЛИ над натуральными числами. Mex множества порядковых чисел — это наименьшее порядковое число, отсутствующее в этом множестве.