Порядковая арифметика

Операции над ординалами, расширяющие классическую арифметику

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

Добавление

Сумма двух вполне упорядоченных множеств S и T — это порядковый номер, представляющий вариант лексикографического порядка с наименее значимой позицией первой, на объединении декартовых произведений S × {0} и T × {1} . Таким образом, каждый элемент S меньше каждого элемента T , сравнения внутри S сохраняют тот порядок, который у них уже есть, и то же самое касается сравнений внутри T.

Определение сложения α + β также может быть дано трансфинитной рекурсией по β . Когда правое слагаемое β = 0 , обычное сложение дает α + 0 = α для любого α . Для β > 0 значение α + β является наименьшим ординалом, строго большим суммы α и δ для всех δ < β . Записываем случаи последовательных и предельных ординалов отдельно:

• α + 0 = α
• α + S ( β ) = S ( α + β ) , где S обозначает функцию- преемник .
• ${\displaystyle \alpha +\beta =\bigcup _{\delta <\beta }(\alpha +\delta )}$когда β — предельный ординал .

Порядковое сложение натуральных чисел такое же, как и стандартное сложение. Первый трансфинитный ординал — это ω , множество всех натуральных чисел, за которым следуют ω + 1 , ω + 2 и т. д. Порядковый ω + ω получается из двух копий натуральных чисел, упорядоченных обычным образом, и второй копии полностью справа от первой. Записывая 0' < 1' < 2' < ... для второй копии, ω + ω выглядит как

0 < 1 < 2 < 3 < ... < 0' < 1' < 2' < ...

Это отличается от ω , поскольку в ω только 0 не имеет прямого предшественника, тогда как в ω + ω два элемента 0 и 0' не имеют прямых предшественников.

Характеристики

Порядковое сложение, в общем случае, не коммутативно . Например, 3 + ω = ω, поскольку отношение порядка для 3 + ω равно 0 < 1 < 2 < 0' < 1' < 2' < ... , что можно переобозначить как ω . Напротив, ω + 3 не равно ω, поскольку отношение порядка 0 < 1 < 2 < ... < 0' < 1' < 2' имеет наибольший элемент (а именно, 2' ), а ω — нет ( ω и ω + 3 равномощны , но не изоморфны по порядку).

Порядковое сложение по-прежнему ассоциативно ; можно увидеть, например, что ( ω + 4) + ω = ω + (4 + ω ) = ω + ω .

Сложение строго возрастает и непрерывно в правом аргументе:

${\displaystyle \alpha <\beta \Rightarrow \gamma +\alpha <\gamma +\beta }$

но аналогичное соотношение не выполняется для левого аргумента; вместо этого мы имеем только:

${\displaystyle \alpha <\beta \Rightarrow \alpha +\gamma \leq \beta +\gamma }$

Порядковое сложение является левосокращающим : если α + β = α + γ , то β = γ . Более того, можно определить левое вычитание для ординалов β ≤ α : существует единственный γ такой, что α = β + γ . С другой стороны, правое сокращение не работает:

${\displaystyle 3+\omega =0+\omega =\omega }$но ${\displaystyle 3\neq 0}$

То же самое касается и правого вычитания, даже если β ≤ α : например, не существует такого γ , что γ + 42 = ω .

Если ординалы, меньшие α, замкнуты относительно сложения и содержат 0, то α иногда называют γ -числом (см. аддитивно неразложимый ординал ). Это в точности ординалы вида ω ^β .

Умножение

Несвязное объединение { ( n ,0) : n ∈ N } ∪ { ( n ,1) : n ∈ N } , использующее лексикографический порядок с наименее значимой позицией первой, имеет тип порядка ω • 2. Это отличается от ω .

Множество { (0, n ) , (1, n )  : n ∈ N } в лексикографическом порядке с наименее значимой позицией первой имеет тип порядка 2 • ω , который равен ω .

Декартово произведение , S × T , двух вполне упорядоченных множеств S и T может быть вполне упорядочено с помощью варианта лексикографического порядка , который ставит наименее значимую позицию первой. Фактически, каждый элемент T заменяется непересекающейся копией S. Тип порядка декартового произведения — это порядковый номер, который получается в результате умножения типов порядка S и T.

Определение умножения также может быть дано с помощью трансфинитной рекурсии по β . Когда правый множитель β = 0 , обычное умножение дает α · 0 = 0 для любого α . Для β > 0 значение α · β является наименьшим ординалом, большим или равным ( α · δ ) + α для всех δ < β . Записываем случаи последовательных и предельных ординалов отдельно:

• α · 0 = 0.
• α · S ( β ) знак равно ( α · β ) + α , для порядкового номера преемника S ( β ) .
• ${\displaystyle \alpha \cdot \beta =\bigcup _{\delta <\beta }(\alpha \cdot \delta )}$, когда β — предельный ординал.

В качестве примера приведем соотношение порядка для ω · 2 :

0 ₀ < 1 ₀ < 2 ₀ < 3 ₀ < ... < 0 ₁ < 1 ₁ < 2 ₁ < 3 ₁ < ...,

который имеет тот же тип порядка, что и ω + ω . Напротив, 2 · ω выглядит так:

0 ₀ < 1 ₀ < 0 ₁ < 1 ₁ < 0 ₂ < 1 ₂ < 0 ₃ < 1 ₃ < ...

и после переименования это выглядит как ω . Таким образом, ω · 2 = ω + ω ≠ ω = 2 · ω , показывая, что умножение ординалов в общем случае не является коммутативным, см. рисунки.

Как и в случае со сложением, порядковое умножение натуральных чисел аналогично стандартному умножению.

Характеристики

α · 0 = 0 · α = 0 , и имеет место свойство нулевого произведения : α · β = 0 → α = 0 или β = 0 . Порядковый номер 1 является мультипликативным тождеством, α · 1 = 1 · α = α . Умножение ассоциативно, ( α · β ) · γ = α · ( β · γ ) . Умножение строго возрастающее и непрерывное по правому аргументу: ( α < β и γ > 0 ) → γ · α < γ · β . Умножение не является строго возрастающим по левому аргументу, например, 1 < 2, а 1 · ω = 2 · ω = ω . Однако он (нестрого) возрастает, т.е. α ≤ β → α · γ ≤ β · γ .

Умножение ординалов в общем случае не коммутативно. В частности, натуральное число больше 1 никогда не коммутирует ни с каким бесконечным ординалом, а два бесконечных ординала α и β коммутируют тогда и только тогда, когда α ^m = β ⁿ для некоторых ненулевых натуральных чисел m и n . Отношение « α коммутирует с β » является отношением эквивалентности на ординалах больше 1, и все классы эквивалентности счетно бесконечны.

Слева имеет место дистрибутивность : α ( β + γ ) = αβ + αγ . Однако закон распределения справа ( β + γ ) α = βα + γα в общем случае не верен : (1 + 1) · ω = 2 · ω = ω, в то время как 1 · ω + 1 · ω = ω + ω , что отличается. Существует закон левого сокращения : если α > 0 и α · β = α · γ , то β = γ . Правое сокращение не работает, например 1 · ω = 2 · ω = ω , но 1 и 2 различны. Левое деление с остатком выполняется: для всех α и β , если β > 0 , то существуют уникальные γ и δ, такие, что α = β · γ + δ и δ < β . Правое деление не работает: нет α такой, что α · ω ≤ ω ^ω ≤ ( α + 1) · ω .

Порядковые числа образуют левое почти-полукольцо , но не образуют кольцо . Следовательно, порядковые числа не являются евклидовой областью , поскольку они даже не являются кольцом; более того, евклидова «норма» была бы порядковозначной с использованием левого деления здесь.

δ - число (см. Мультипликативно неразложимый ординал ) — это ординал β, больший 1, такой, что αβ = β, когда 0 < α < β . Они состоят из ординала 2 и ординалов вида β = ω ^{ω γ} .

Возведение в степень

Определение возведения в степень через типы порядка проще всего объяснить, используя определение фон Неймана ординала как множества всех меньших ординалов . Затем, чтобы построить множество типа порядка α ^β, рассмотрим множество всех функций f  : β → α , таких что f ( x ) = 0 для всех, кроме конечного числа элементов x ∈ β (по сути, мы рассматриваем функции с конечным носителем ). Это множество упорядочено лексикографически, причем наименее значимая позиция идет первой: мы пишем f < g тогда и только тогда, когда существует x ∈ β с f ( x ) < g ( x ) и f ( y ) = g ( y ) для всех y ∈ β с x < y . Это хорошее упорядочение и, следовательно, дает ординальное число.

Определение возведения в степень также может быть дано с помощью трансфинитной рекурсии по показателю β . Когда показатель β = 0 , обычное возведение в степень дает α ⁰ = 1 для любого α . Для β > 0 значение α ^β является наименьшим ординалом, большим или равным α ^δ · α для всех δ < β . Записываем случаи последовательных и предельных ординалов отдельно:

• α ⁰ = 1 .
• α ^{S ( β )} знак равно ( α ^β ) · α , для порядкового номера преемника S ( β ) .
• ${\displaystyle \alpha ^{\beta }=\bigcup _{0<\delta <\beta }(\alpha ^{\delta })}$, когда β — предельный ординал.

Оба определения значительно упрощаются, если показатель степени β является конечным числом: тогда α ^β является просто произведением β копий α ; например, ω ³ = ω · ω · ω , и элементы ω ³ можно рассматривать как тройки натуральных чисел, упорядоченные лексикографически с наименее значимой позицией первой. Это согласуется с обычным возведением в степень натуральных чисел.

Но для бесконечных показателей степеней определение может быть не очевидным. Например, α ^ω можно отождествить с набором конечных последовательностей элементов α , упорядоченных надлежащим образом. Уравнение 2 ^ω = ω выражает тот факт, что конечные последовательности нулей и единиц можно отождествить с натуральными числами, используя двоичную систему счисления . Порядковый номер ω ^ω можно рассматривать как тип порядка конечных последовательностей натуральных чисел; каждый элемент ω ^ω (т. е. каждый порядковый номер, меньший ω ^ω ) можно однозначно записать в виде, где k , n ₁ , ..., n _k — натуральные числа, c ₁ , ..., c _k — ненулевые натуральные числа, и n ₁ > ... > n _k . ${\displaystyle \omega ^{n_{1}}c_{1}+\omega ^{n_{2}}c_{2}+\cdots +\omega ^{n_{k}}c_{k}}$

То же самое верно и в общем случае: каждый элемент α ^β (т. е. каждый ординал, меньший α ^β ) может быть однозначно записан в виде, где k — натуральное число, b ₁ , ..., b _k — ординалы, меньшие β, причем b ₁ > ... > b _k , а a ₁ , ..., a _k — ненулевые ординалы, меньшие α . Это выражение соответствует функции f  : β → α , которая переводит b _i в a _i для i = 1, ..., k и переводит все остальные элементы β в 0. ${\displaystyle \alpha ^{b_{1}}a_{1}+\alpha ^{b_{2}}a_{2}+\cdots +\alpha ^{b_{k}}a_{k}}$

Хотя для порядкового и кардинального возведения в степень используется одна и та же запись экспоненты , эти две операции совершенно различны и их не следует путать. Кардинальное возведение в степень A ^B определяется как кардинальное число множества всех функций B → A , в то время как порядковое возведение в степень α ^β содержит только функции β → α с конечным носителем, обычно множеством гораздо меньшей мощности. Чтобы не путать порядковое возведение в степень с кардинальным возведением в степень, можно использовать символы для порядковых чисел (например, ω ) в первом случае и символы для кардинальных чисел (например, ) во втором. ${\displaystyle \aleph _{0}}$

Характеристики

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

Якобстал показал, что единственные решения уравнения α ^β = β ^α с α ≤ β даются формулами α = β , или α = 2 и β = 4 , или α — любой предельный ординал и β = εα, где ε — ε -число, большее чем α . ^[1]

За пределами возведения в степень

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

Нормальная форма Кантора

Каждое порядковое число α может быть однозначно записано как , где k — натуральное число, — ненулевые натуральные числа, а — порядковые числа. Вырожденный случай α = 0 возникает, когда k = 0 и нет ни β s, ни c s. Это разложение α называется нормальной формой Кантора для α и может рассматриваться как позиционная система счисления с основанием ω . Наивысший показатель называется степенью и удовлетворяет условию . Равенство применяется тогда и только тогда, когда . В этом случае нормальная форма Кантора не выражает порядковый номер через меньшие числа; это может произойти, как объяснено ниже. ${\displaystyle \omega ^{\beta _{1}}c_{1}+\omega ^{\beta _{2}}c_{2}+\cdots +\omega ^{\beta _{k}}c_{k}}$ ${\displaystyle c_{1},c_{2},\ldots ,c_{k}}$ ${\displaystyle \beta _{1}>\beta _{2}>\ldots >\beta _{k}\geq 0}$ ${\displaystyle \beta _{1}}$ ${\displaystyle \alpha }$ ${\displaystyle \beta _{1}\leq \alpha }$ ${\displaystyle \beta _{1}=\alpha }$ ${\displaystyle \alpha =\omega ^{\alpha }}$

Небольшой вариант нормальной формы Кантора, с которым обычно немного проще работать, — это установить все числа c _i равными 1 и разрешить экспонентам быть равными. Другими словами, каждое порядковое число α может быть однозначно записано как , где k — натуральное число, а — порядковые числа. ${\displaystyle \omega ^{\beta _{1}}+\omega ^{\beta _{2}}+\cdots +\omega ^{\beta _{k}}}$ ${\displaystyle \beta _{1}\geq \beta _{2}\geq \ldots \geq \beta _{k}\geq 0}$

Другой разновидностью нормальной формы Кантора является «разложение по основанию δ », где ω заменяется любым порядковым числом δ > 1 , а числа c _i являются ненулевыми порядковыми числами, меньшими δ .

Нормальная форма Кантора позволяет нам однозначно выразить — и упорядочить — порядковые числа α , которые построены из натуральных чисел с помощью конечного числа арифметических операций сложения, умножения и возведения в степень с основанием - : другими словами, предполагая в нормальной форме Кантора, мы также можем выразить показатели степени в нормальной форме Кантора, и делая то же самое предположение для as для α и так далее рекурсивно, мы получаем систему обозначений для этих порядковых чисел (например, ${\displaystyle \omega }$ ${\displaystyle \beta _{1}<\alpha }$ ${\displaystyle \beta _{i}}$ ${\displaystyle \beta _{i}}$

${\displaystyle \omega ^{\omega ^{\omega ^{7}\cdot 6+\omega +42}\cdot 1729+\omega ^{9}+88}\cdot 3+\omega ^{\omega ^{\omega }}\cdot 5+65537}$

обозначает порядковый номер).

Ординал ε ₀ ( эпсилон ноль ) — это множество порядковых значений α арифметических выражений конечной длины нормальной формы Кантора, которые наследственно нетривиальны, где нетривиальность означает β ₁ < α при 0 < α . Это наименьший порядковый номер, который не имеет конечного арифметического выражения в терминах ω , и наименьший порядковый номер такой, что , т.е. в нормальной форме Кантора показатель степени не меньше самого порядкового номера. Это предел последовательности ${\displaystyle \varepsilon _{0}=\omega ^{\varepsilon _{0}}}$

${\displaystyle 0,\,1=\omega ^{0},\,\omega =\omega ^{1},\,\omega ^{\omega },\,\omega ^{\omega ^{\omega }},\,\ldots \,.}$

Порядковый номер ε ₀ важен в арифметике по разным причинам (в основном потому, что он измеряет силу доказательства теории Пеано первого порядка : то есть аксиомы Пеано могут демонстрировать трансфинитную индукцию до любого порядкового номера, меньшего ε ₀ , но не до самого ε ₀ ).

Нормальная форма Кантора также позволяет нам вычислять суммы и произведения ординалов: например, чтобы вычислить сумму, нужно просто знать (см. свойства, перечисленные в § Сложение и § Умножение), что

${\displaystyle \omega ^{\beta }c+\omega ^{\beta '}c'=\omega ^{\beta '}c'\,,}$

если (если можно применить распределительный закон слева и переписать это как , и если выражение уже находится в нормальной форме Кантора); и для вычисления произведений существенными фактами являются следующие: когда находится в нормальной форме Кантора и , то ${\displaystyle \beta '>\beta }$ ${\displaystyle \beta '=\beta }$ ${\displaystyle \omega ^{\beta }(c+c')}$ ${\displaystyle \beta '<\beta }$ ${\displaystyle 0<\alpha =\omega ^{\beta _{1}}c_{1}+\cdots +\omega ^{\beta _{k}}c_{k}}$ ${\displaystyle 0<\beta '}$

${\displaystyle \alpha \omega ^{\beta '}=\omega ^{\beta _{1}+\beta '}\,}$

и

${\displaystyle \alpha n=\omega ^{\beta _{1}}c_{1}n+\omega ^{\beta _{2}}c_{2}+\cdots +\omega ^{\beta _{k}}c_{k}\,,}$

если n — ненулевое натуральное число.

Чтобы сравнить два ординала, записанных в нормальной форме Кантора, сначала сравните , затем , затем , затем и так далее. При первом появлении неравенства ординал с большим компонентом является большим ординалом. Если они одинаковы, пока один не заканчивается раньше другого, то тот, который заканчивается первым, является меньшим. ${\displaystyle \beta _{1}}$ ${\displaystyle c_{1}}$ ${\displaystyle \beta _{2}}$ ${\displaystyle c_{2}}$

Разложение на простые множители

Эрнст Якобсталь показал, что ординалы удовлетворяют форме теоремы об уникальной факторизации: каждый ненулевой ординал может быть записан как произведение конечного числа простых ординалов. Это разложение на простые ординалы в общем случае не является уникальным, но существует «минимальное» разложение на простые числа, которое уникально с точностью до изменения порядка конечных простых множителей (Sierpiński 1958).

Простой ординал — это ординал больше 1, который не может быть записан как произведение двух меньших ординалов. Некоторые из первых простых чисел — это 2, 3, 5, ... , ω , ω + 1 , ω ² + 1 , ω ³ + 1 , ..., ω ^ω , ω ^ω + 1 , ω ^{ω + 1} + 1 , ... Существует три вида простых ординалов:

• Конечные простые числа 2, 3, 5, ...
• Ординалы вида ω ^{ω α} для любого ординала α . Это простые ординалы, которые являются пределами, и являются дельта-числами , трансфинитными ординалами, которые замкнуты относительно умножения.
• Ординалы вида ω ^α + 1 для любого ординала α > 0. Это бесконечные последующие простые числа, и они являются последующими числами гамма-чисел , аддитивно неразложимых ординалов.

Разложение на простые множители не является единственным: например, 2×3 = 3×2 , 2× ω = ω , ( ω +1)× ω = ω × ω и ω × ω ^ω = ω ^ω . Однако существует единственное разложение на простые множители, удовлетворяющее следующим дополнительным условиям:

• Каждое предельное простое число должно встречаться перед любым последующим простым числом.
• Если два последовательных простых числа разложения на простые множители являются пределами или оба конечны, то второе из них должно быть меньше или равно первому.

Эту простую факторизацию можно легко прочитать, используя нормальную форму Кантора следующим образом:

• Сначала запишем ординал в виде произведения αβ , где α — наименьшая степень ω в нормальной форме Кантора, а β — последователь.
• Если α = ω ^γ , то запись γ в нормальной форме Кантора дает разложение α как произведения предельных простых чисел.
• Теперь рассмотрим нормальную форму Кантора для β . Если β = ω ^λ m + ω ^μ n + меньшие члены, то β = ( ω ^μ n + меньшие члены)( ω ^{λ − μ} + 1) m является произведением меньшего ординала, простого и натурального чисел m . Повторение этого и разложение натуральных чисел на простые множители дает разложение β на простые множители .

Итак, факторизация ординала нормальной формы Кантора

ω ^{α ₁} n ₁ + ⋯ + ω ^{α _k} n _k (при α ₁ > ⋯ > α _k )

в минимальное произведение бесконечных простых и натуральных чисел

( ω ^{ω β ₁} ⋯ ω ^{ω β _м} ) n _k ( ω ^{α _{k −1} −α _k} + 1) n _{k −1} ⋯ ( ω ^{α ₁ − α ₂} + 1) n ₁

где каждое n _i следует заменить его разложением на невозрастающую последовательность конечных простых чисел и

α _k знак равно ω ^{β ₁} + ⋯ + ω ^{β _м} с β ₁ ≥ ⋯ ≥ β _м .

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

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

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

Естественные операции

Операции натуральной суммы и натурального произведения над ординалами были определены в 1906 году Герхардом Гессенбергом и иногда называются суммой (или произведением) Гессенберга (Sierpiński 1958). Натуральная сумма α и β часто обозначается как α ⊕ β или α # β , а натуральное произведение — как α ⊗ β или α ⨳ β .

Натуральная сумма и произведение определяются следующим образом. Пусть и находятся в нормальной форме Кантора (т.е. и ). Пусть будут показателями степеней, отсортированными в порядке невозрастания. Тогда определяется как Натуральное произведение и определяется как Например, предположим , что и . Тогда , тогда как . И , тогда как . ${\displaystyle \alpha =\omega ^{\alpha _{1}}+\cdots +\omega ^{\alpha _{k}}}$ ${\displaystyle \beta =\omega ^{\beta _{1}}+\cdots +\omega ^{\beta _{\ell }}}$ ${\displaystyle \alpha _{1}\geq \cdots \geq \alpha _{k}}$ ${\displaystyle \beta _{1}\geq \cdots \geq \beta _{\ell }}$ ${\displaystyle \gamma _{1},\ldots ,\gamma _{k+\ell }}$ ${\displaystyle \alpha _{1},\ldots ,\alpha _{k},\beta _{1},\ldots ,\beta _{\ell }}$ ${\displaystyle \alpha \oplus \beta }$ $${\displaystyle \alpha \oplus \beta =\omega ^{\gamma _{1}}+\cdots +\omega ^{\gamma _{k+\ell }}.}$$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ $${\displaystyle \alpha \otimes \beta =\bigoplus _{\begin{aligned}&1\leq i\leq k\\&1\leq j\leq \ell \end{aligned}}\omega ^{\alpha _{i}\oplus \beta _{j}}.}$$ ${\displaystyle \alpha =\omega ^{\omega ^{\omega }}+\omega }$ ${\displaystyle \beta =\omega ^{\omega }+\omega ^{5}}$ ${\displaystyle \alpha \oplus \beta =\omega ^{\omega ^{\omega }}+\omega ^{\omega }+\omega ^{5}+\omega }$ ${\displaystyle \alpha +\beta =\omega ^{\omega ^{\omega }}+\omega ^{\omega }+\omega ^{5}}$ ${\displaystyle \alpha \otimes \beta =\omega ^{\omega ^{\omega }+\omega }+\omega ^{\omega ^{\omega }+5}+\omega ^{\omega +1}+\omega ^{6}}$ ${\displaystyle \alpha \beta =\omega ^{\omega ^{\omega }+\omega }+\omega ^{\omega ^{\omega }+5}}$

Натуральная сумма и произведение коммутативны и ассоциативны, а натуральное произведение распределяется по натуральной сумме. Операции также монотонны, в том смысле, что если то ; если то ; и если и то . ${\displaystyle \alpha <\beta }$ ${\displaystyle \alpha \oplus \gamma <\beta \oplus \gamma }$ ${\displaystyle \alpha \leq \beta }$ ${\displaystyle \alpha \otimes \gamma \leq \beta \otimes \gamma }$ ${\displaystyle \alpha <\beta }$ ${\displaystyle \gamma >0}$ ${\displaystyle \alpha \otimes \gamma <\beta \otimes \gamma }$

У нас есть . ${\displaystyle \underbrace {\alpha \oplus \cdots \oplus \alpha } _{n}=\alpha \otimes n}$

У нас всегда есть и . Если и то и то . Если и то и то . ${\displaystyle \alpha +\beta \leq \alpha \oplus \beta }$ ${\displaystyle \alpha \beta \leq \alpha \otimes \beta }$ ${\displaystyle \alpha <\omega ^{\gamma }}$ ${\displaystyle \beta <\omega ^{\gamma }}$ ${\displaystyle \alpha \oplus \beta <\omega ^{\gamma }}$ ${\displaystyle \alpha <\omega ^{\omega ^{\gamma }}}$ ${\displaystyle \beta <\omega ^{\omega ^{\gamma }}}$ ${\displaystyle \alpha \otimes \beta <\omega ^{\omega ^{\gamma }}}$

Натуральная сумма и произведение не являются непрерывными в правом аргументе, так как, например , , а не ; и , а не . ${\displaystyle \lim _{n<\omega }\alpha \oplus n=\alpha +\omega }$ ${\displaystyle \alpha \oplus \omega }$ ${\displaystyle \lim _{n<\omega }\alpha \otimes n=\alpha \omega }$ ${\displaystyle \alpha \otimes \omega }$

Натуральная сумма и произведение совпадают со сложением и умножением (ограниченными порядковыми числами) в области сюрреалистических чисел Джона Конвея .

Естественные операции возникают в теории вполне частичных порядков ; если заданы два вполне частичных порядка и типов (максимальные линеаризации ) и , тип непересекающегося объединения будет , в то время как тип прямого произведения будет . ^[2] Можно взять это отношение как определение естественных операций, выбрав S и T в качестве ординалов α и β ; так что α ⊕ β является максимальным типом порядка полного порядка, расширяющего непересекающееся объединение (как частичный порядок) α и β ; в то время как α ⊗ β является максимальным типом порядка полного порядка, расширяющего прямое произведение (как частичный порядок) α и β . ^[3] Полезное применение этого — когда α и β оба являются подмножествами некоторого большего полного порядка; тогда их объединение имеет тип порядка не более α ⊕ β . Если они оба являются подмножествами некоторой упорядоченной абелевой группы , то их сумма имеет тип порядка не более α ⊗ β . ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle o(S)}$ ${\displaystyle o(T)}$ ${\displaystyle o(S)\oplus o(T)}$ ${\displaystyle o(S)\otimes o(T)}$

Мы также можем определить натуральную сумму α ⊕ β путем одновременной трансфинитной рекурсии по α и β как наименьший порядковый номер, строго больший, чем натуральная сумма α и γ для всех γ < β и γ и β для всех γ < α . ^[4] Аналогичным образом мы можем определить натуральный продукт α ⊗ β посредством одновременной трансфинитной рекурсии на α и β как наименьший ординал γ такой, что ( α ⊗ δ ) ⊕ ( ε ⊗ β ) < γ ⊕ ( ε ⊗ δ ) для все ε < α и δ < β . ^[4] Также см. статью о сюрреалистических числах для определения натурального умножения в этом контексте; Однако он использует сюрреалистическое вычитание, которое не определено для порядковых чисел.

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

При естественном сложении ординалы можно отождествить с элементами свободного коммутативного моноида , порожденного гамма-числами ω ^α . При естественном сложении и умножении ординалы можно отождествить с элементами свободного коммутативного полукольца , порожденного дельта-числами ω ^{ω α} . Ординалы не имеют однозначной факторизации на простые числа при естественном произведении. В то время как полное кольцо многочленов имеет однозначную факторизацию, подмножество многочленов с неотрицательными коэффициентами ее не имеет: например, если x — любое дельта-число, то

х ⁵ + х ⁴ + х ³ + х ² + х + 1 = ( х + 1) ( х ⁴ + х ² + 1) = ( х ² + х + 1) ( х ³ + 1)

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

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

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

Примечания

1. Эрнст Якобсталь, Vertauschbarkeit transfiniter Ordnungszahlen, Mathematische Annalen , Bd 64 (1907), 475-488. Доступно здесь
2. DHJ De Jongh и R. Parikh, Хорошо-частичные упорядочения и иерархии, Indag. Math. 39 (1977), 195–206. Доступно здесь
3. Филип В. Каррут, Арифметика ординалов с приложениями к теории упорядоченных абелевых групп, Bull. Amer. Math. Soc. 48 (1942), 262–271. См. теорему 1. Доступно здесь
4. Altman, Harry (2017-11-01). "Промежуточные арифметические операции над порядковыми числами" (PDF) . Mathematical Logic Quarterly . 63 (3–4): 228–42. arXiv : 1501.05747 . doi :10.1002/malq.201600006 . Получено 28.08.2024 .

Ссылки

• Томас Йех (21 марта 2006 г.). Теория множеств: издание третьего тысячелетия, переработанное и расширенное. Springer Science & Business Media. ISBN 978-3-540-44085-7.
• Кунен, Кеннет , 1980. Теория множеств: Введение в доказательства независимости . Elsevier. ISBN 0-444-86839-9 . 
• Серпинский, Вацлав (1958), Кардинальные и порядковые числительные , Polska Akademia Nauk Monografie Matematyczne, vol. 34, Варшава: Państwowe Wydawnictwo Naukowe, MR  0095787

Внешние ссылки

• ordCalc порядковый калькулятор