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

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

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

Добавление

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

Определение сложения α + β также можно дать с помощью трансфинитной рекурсии по β :

• α + 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, то α иногда называют γ -числом (см . аддитивно неразложимый ординал ). Это в точности ординалы вида ω ^β .

Умножение

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

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

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

Определение умножения также можно дать индуктивно (следующая индукция проводится по β ):

• α · 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 ₀ < ₀ 1 < 1 1 _{< 0} 2 _{< 1} 2 < 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 .
• α ^{S ( β )} знак равно ( α ^β ) · α , для порядкового номера преемника S ( β ) .
• ${\displaystyle \alpha ^{\beta }=\bigcup _{0<\delta <\beta }(\alpha ^{\delta })}$, когда β является предельным порядковым номером.

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

Но для бесконечных показателей определение может быть неочевидным. Например, αω можно отождествить с набором конечных последовательностей элементов α , правильно упорядоченных ^. Уравнение 2 ^ω = ω выражает тот факт, что конечные последовательности нулей и единиц можно отождествлять с натуральными числами, используя двоичную систему счисления . Порядковый номер ω ^ω можно рассматривать как тип порядка конечных последовательностей натуральных чисел; каждый элемент ω ^ω (т.е. каждый ординал, меньший, чем ω ^ω ), можно однозначно записать в виде где k , n ₁ , ..., nk _— натуральные числа, 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}}$

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

• α ^{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 являются ненулевыми порядковыми числами, меньшими, чем δ .

Нормальная форма Кантора позволяет нам однозначно выражать и упорядочивать ординалы α , которые построены из натуральных чисел с помощью конечного числа арифметических операций сложения, умножения и возведения в степень : другими словами, полагая в нормальной форме Кантора, мы также можем выразить показатели степени в нормальной форме Кантора, и, сделав то же предположение для , что и для α и т. д. рекурсивно, мы получим систему обозначений для этих ординалов (например, ${\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 \,.}$

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

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

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

if (если можно применить распределительный закон слева и переписать это как , и если выражение уже находится в нормальной форме Кантора); и для вычисления произведений существенные факты заключаются в том, что когда находится в нормальной канторовской форме и , то ${\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}}$

Факторизация в простые числа

Эрнст Якобсталь показал, что ординалы удовлетворяют определенной форме теоремы о факторизации: каждый ненулевой ординал можно записать как произведение конечного числа простых ординалов. Эта факторизация на простые порядковые числа, как правило, не уникальна, но существует «минимальная» факторизация на простые числа, которая уникальна с точностью до изменения порядка конечных простых множителей (Серпинский 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 _{1\leq i\leq k,1\leq j\leq \ell }\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}}$

Естественные операции возникают в теории вполне частичных порядков ; учитывая два хорошо частичных порядка и , порядковых типов и , порядковый тип непересекающегося союза равен , а порядковый тип прямого произведения равен . ^[2] ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle o(S)}$ ${\displaystyle o(T)}$ ${\displaystyle o(S)\oplus o(T)}$ ${\displaystyle o(S)\otimes o(T)}$

Натуральная сумма и произведение коммутативны и ассоциативны, а натуральный продукт распределяется по натуральной сумме. Операции также монотонны в том смысле, что if then ; если тогда ; и если и то . ${\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 }$

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

Естественные операции возникают в теории вполне частичных порядков ; учитывая два вполне частичных порядка S и T типов ( максимальные линеаризации ) o ( S ) и o ( T ) , тип несвязного объединения — o ( S ) ⊕ o ( T ) , а тип прямого произведения — о ( S ) ⊗ о ( Т ) . ^[3] Это отношение можно принять как определение естественных операций, выбрав S и T в качестве ординалов α и β ; поэтому α ⊕ β — тип максимального порядка полного порядка, расширяющего дизъюнктное объединение (как частичный порядок) α и β ; а α ⊗ β — тип максимального порядка полного порядка, расширяющего прямое произведение (как частичный порядок) α и β . ^[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 Де Йонг и Р. Парих, Частичные порядки и иерархии, Indag. Математика. 39 (1977), 195–206. Доступна здесь
3. DHJ Де Йонг и Р. Парих, Частичные порядки и иерархии, Indag. Математика. 39 (1977), 195–206. Доступна здесь
4. Филип В. Каррут, Арифметика ординалов с приложениями к теории упорядоченных абелевых групп, Bull. амер. Математика. Соц. 48 (1942), 262–271. См. теорему 1. Доступно здесь.

Рекомендации

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

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

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