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

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

Дополнение [ править ]

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

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

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

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

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

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

После изменения метки первое выглядит как само ω, т. Е. 3 + ω = ω, а второе - нет: ω + 3 не равно ω, поскольку ω + 3 имеет наибольший элемент (а именно, 2 '), а ω не имеет (даже если ω и ω + 3 эквипотентны, они не изоморфны). Следовательно, это добавление не коммутативно . На самом деле, α + β довольно редко бывает равным β + α: это происходит тогда и только тогда, когда α = γ m , β = γ n для некоторого порядкового γ и натуральных чисел m и n . Отсюда следует, что «α коммутирует с β» - отношение эквивалентности на классе ненулевых ординалов, и все классы эквивалентности счетно бесконечны.

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

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

• α + 0 = α ,
• α + ( β + 1) = ( α + β ) + 1 (здесь «+1» обозначает последователя порядкового номера),
• и если β - предельный ординал, то α + β - предел α + δ для всех δ < β .

Используя это определение, ω + 3 можно рассматривать как порядковый номер-преемник (он является преемником ω + 2), тогда как 3 + ω является предельным ординалом , а именно пределом 3 + 0 = 3, 3 + 1 = 4, 3 + 2 = 5 и т. Д., Что и есть просто ω.

Ноль - аддитивное тождество α + 0 = 0 + α = α .

Сложение ассоциативно ( α + β ) + γ = α + ( β + γ ).

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

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

Умножение [ править ]

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

Вот ω · 2:

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

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

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

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

Дистрибутивность частично выполняется для порядковой арифметики: R ( S + T ) = RS + RT . Однако, с другой дистрибутивный закон ( Т + U ) R = ТР + UR это не правило: (1 + 1) · ω = 2 · ω = ω , а 1 · ω + 1 · ω = ω + ω , которая отличается. Поэтому порядковые номера образуют левый ближней полукольцо , но не образуют кольцо .

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

• α · 0 = 0,
• α · ( β +1) = ( α · β ) + α ,
• и если β - предельный ординал, то α · β - предел α · δ при δ < β .

Основные свойства продукта:

• α · 0 = 0 · α = 0.
• Один (1) является мультипликативным тождеством α · 1 = 1 · α = α .
• Умножение ассоциативно ( α · β ) · γ = α · ( β · γ ).
• Умножение строго возрастает и непрерывно по правому аргументу: ( α < β и γ > 0) γ · α < γ · β${\displaystyle \Rightarrow }$
• Умножение не является строго возрастающим в левом аргументе, например, 1 <2, но 1 · ω = 2 · ω = ω. Однако он (нестрого) возрастает, т.е. α ≤ β α · γ ≤ β · γ .${\displaystyle \Rightarrow }$
• Существует закон левого сокращения : если α > 0 и α · β = α · γ , то β = γ .
• Правое сокращение не работает, например 1 · ω = 2 · ω = ω, но 1 и 2 разные.
• α · β = 0, α = 0 или β = 0.${\displaystyle \Rightarrow }$
• Распределительный закон слева: α · ( β + γ ) = α · β + α · γ
• Нет закона распределения справа: например, (ω + 1) · 2 = ω + 1 + ω + 1 = ω + ω + 1 = ω · 2 + 1, что не является ω · 2 + 2.
• Левое деление с остатком : для всех α и β , если β > 0, то существуют единственные γ и δ такие, что α = β · γ + δ и δ < β . (Это, однако, не означает, что ординалы являются евклидовой областью , поскольку они даже не являются кольцом, а евклидова «норма» имеет порядковые значения.)
• Правое деление не работает: не существует α такого, что α · ω ≤ ω ^ω ≤ ( α +1) · ω.

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

Возведение в степень [ править ]

Определение порядкового возведения в степень для конечных показателей несложно. Если показатель степени является конечным числом, степень является результатом повторного умножения. Например, ω ² = ω · ω, используя операцию порядкового умножения. Обратите внимание, что ω · ω может быть определено с помощью набора функций от 2 = {0,1} до ω = {0,1,2, ...}, упорядоченных лексикографически с наименьшей значащей позицией первой:

(0,0) <(1,0) <(2,0) <(3,0) <... <(0,1) <(1,1) <(2,1) <(3,1 ) <... <(0,2) <(1,2) <(2,2) <...

Здесь для краткости мы заменили функцию {(0, k ), (1, m )} упорядоченной парой ( k , m ).

Аналогичным образом , для любого конечного показателя степени п , может быть определена с использованием набора функций от п (домен) в естественных чисел (кообласть). Эти функции могут быть сокращены как n -элементы натуральных чисел.${\displaystyle \omega ^{n}}$

Но для бесконечных показателей определение может быть неочевидным. Предельный ординал, такой как ω ^ω , является супремумом всех меньших ординалов. Может показаться естественным определить ω ^ω, используя множество всех бесконечных последовательностей натуральных чисел. Однако мы обнаруживаем, что любой абсолютно определенный порядок на этом множестве не является хорошо упорядоченным. ^{[ необходима цитата ]} Чтобы решить эту проблему, мы снова можем использовать вариант лексикографического упорядочивания. Мы ограничиваем набор последовательностями, которые не равны нулю только для конечного числа аргументов. Это естественно мотивировано как предел конечных степеней базы (аналогично концепции копроизведения в алгебре). Это также можно рассматривать как бесконечный союз ${\displaystyle \bigcup _{n<\omega }\omega ^{n}}$.

Каждая из этих последовательностей соответствует порядковому номеру меньше, чем такой как, и является верхней гранью всех этих меньших порядковых чисел.${\displaystyle \omega ^{\omega }}$${\displaystyle \omega ^{n_{1}}c_{1}+\omega ^{n_{2}}c_{2}+\cdots +\omega ^{n_{k}}c_{k}}$${\displaystyle \omega ^{\omega }}$

Лексикографический порядок в этом наборе - это хороший порядок, который напоминает порядок натуральных чисел, записанных в десятичной системе счисления, за исключением того, что позиции цифр перевернуты, и с произвольными натуральными числами вместо цифр 0–9:

(0,0,0, ...) <(1,0,0,0, ...) <(2,0,0,0, ...) <... <

(0,1,0,0,0, ...) <(1,1,0,0,0, ...) <(2,1,0,0,0, ...) <.. . <

(0,2,0,0,0, ...) <(1,2,0,0,0, ...) <(2,2,0,0,0, ...)

<... <

(0,0,1,0,0,0, ...) <(1,0,1,0,0,0, ...) <(2,0,1,0,0,0 ,. ..)

<...

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

Проще всего объяснить это, используя определение фон Неймана ординала как множества всех меньших ординалов . Затем, чтобы построить набор упорядоченного типа α ^β, рассмотрим все функции от β до α такие, что только конечное число элементов области β отображается в ненулевой элемент α (по существу, мы рассматриваем функции с конечным носителем ). Порядок лексикографический, начиная с наименее значимой позиции. Мы нашли

• 1 ^ω = 1,
• 2 ^ω = ω,
• 2 ^{ω + 1} = ω · 2 = ω + ω.

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

• α ⁰ = 1,
• α ^{β +1} = ( α ^β ) · α , и
• если β - предельный ординал, то α ^β - предел α ^δ для всех δ < β .

Свойства порядкового возведения в степень:

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

Хотя для порядкового и кардинального возведения в степень используются одни и те же обозначения , порядковое возведение в степень сильно отличается от кардинального возведения в степень. Например, с помощью порядковой экспоненциации , но для ( алефа нуля , тем мощности из ), . Здесь - мощность множества всех функций от множества всех натуральных чисел до множества с двумя элементами. (Это -мощность множества мощности множества всех натуральных чисел и равно , то мощность континуума${\displaystyle 2^{\omega }=\omega }$${\displaystyle \aleph _{0}}$${\displaystyle \omega }$${\displaystyle 2^{\aleph _{0}}>\aleph _{0}}$${\displaystyle 2^{\aleph _{0}}}$${\displaystyle {\mathfrak {c}}}$.) Чтобы не путать порядковое возведение в степень с кардинальным возведением в степень, можно использовать символы для порядковых чисел (например, ω) в первом и символы для кардинальных чисел (например ) во втором.${\displaystyle \aleph _{0}}$

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

Нормальная форма Кантора [ править ]

Каждое порядковое число α может быть однозначно записано как , где k - натуральное число, - натуральные числа и порядковые числа. Это разложение альфа называется канторовым нормальной формой из & alpha ; , а также можно считать ω-базовая позиционная система счисления . Старший показатель называется степенью и удовлетворяет . Равенство применяется тогда и только тогда, когда . В этом случае нормальная форма Кантора не выражает порядковый номер через меньшие; это может произойти, как описано ниже.${\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 ^{\left(\omega ^{\left(\omega ^{7}\cdot 6+\omega +42\right)}\cdot 1729+\omega ^{9}+88\right)}\cdot 3+\omega ^{\left(\omega ^{\omega }\right)}\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'\,,}$

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}}$

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

Эрнст Якобсталь показал, что ординалы удовлетворяют форме теоремы единственной факторизации: каждый ненулевой ординал может быть записан как произведение конечного числа простых ординалов. Эта факторизация в простые ординалы, как правило, не уникальна, но существует «минимальная» факторизация в простые числа, которая уникальна вплоть до изменения порядка конечных простых множителей ( 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 . Повторение этого и разложение целых чисел на простые дает факторизацию β на простые множители.

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

${\displaystyle \omega ^{\alpha _{1}}n_{1}+\cdots +\omega ^{\alpha _{k}}n_{k}}$(с )${\displaystyle \alpha _{1}>\cdots >\alpha _{k}}$

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

${\displaystyle \omega ^{\omega ^{\beta _{1}}}\cdots \omega ^{\omega ^{\beta _{m}}}n_{k}(\omega ^{\alpha _{k-1}-\alpha _{k}}+1)n_{k-1}\cdots n_{2}(\omega ^{\alpha _{1}-\alpha _{2}}+1)n_{1}}$

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

${\displaystyle \alpha _{k}=\omega ^{\beta _{1}}+\cdots +\omega ^{\beta _{m}}}$с .${\displaystyle \beta _{1}\geq \cdots \geq \beta _{m}}$

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

Как обсуждалось выше, нормальная форма Кантора порядковых чисел ниже может быть выражена в алфавите, содержащем только функциональные символы для сложения, умножения и возведения в степень, а также постоянные символы для каждого натурального числа и для . Мы можем избавиться от бесконечного числа чисел, используя только постоянный символ 0 и операцию преемника (например, целое число 4 может быть выражено как ). Это описывает порядковую нотацию : систему именования ординалов в конечном алфавите. Эта конкретная система порядковых обозначений называется набором арифметических порядковых выражений и может выражать все указанные ниже порядковые числа , но не может выражать${\displaystyle \varepsilon _{0}}$${\displaystyle \omega }$${\displaystyle S}$${\displaystyle S(S(S(S(0))))}$${\displaystyle \varepsilon _{0}}$${\displaystyle \varepsilon _{0}}$. Существуют и другие порядковые обозначения, способные фиксировать порядковые номера, уже давно прошедшие , но поскольку существует только счетное количество строк в любом конечном алфавите, для любой данной порядковой записи ниже будут порядковые числа ( первый несчетный порядковый номер ), которые не могут быть выражены. Такие ординалы известны как большие счетные ординалы .${\displaystyle \varepsilon _{0}}$${\displaystyle \omega _{1}}$

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

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

В естественных суммах и натуральный продукт операция на порядковом были определены в 1906 годе Gerhard хессенбергового , а иногда называют сумму Хессенберга (или продукт) ( Серпинскую тысяча девятьсот пятьдесят восемь ) . Они такие же , как сложение и умножение (ограничивается порядковыми) от Джона Конвея поля из сюрреалистических чисел harv error: no target: CITEREFSierpinski1958 (help). У них есть то преимущество, что они ассоциативны и коммутативны, и натуральный продукт распределяется по натуральной сумме. Цена превращения этих операций в коммутативность состоит в том, что они теряют непрерывность в правильном аргументе, что является свойством обычных суммы и произведения. Натуральная сумма α и β часто обозначается α⊕β или α # β, а натуральный продукт - α⊗β или α⨳β.

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

Мы также можем определить натуральную сумму α и β индуктивно (путем одновременной индукции по α и β ) как наименьший порядковый номер, превышающий натуральную сумму α и γ для всех γ < β и γ и β для всех γ < α . Существует также индуктивное определение натурального продукта (путем взаимной индукции), но записывать его несколько утомительно, и мы не будем этого делать (см. Статью о сюрреалистических числах для определения в этом контексте, которое, однако, использует сюрреалистическое вычитание, что, очевидно, не может быть определено на ординалах).

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

Еще один способ определить натуральную сумму и произведение двух ординалов α и β - использовать нормальную форму Кантора: можно найти последовательность ординалов γ ₁ >…> γ _n и две последовательности ( k ₁ ,…, k _n ) и ( j ₁ ,…, j _n ) натуральных чисел (включая ноль, но удовлетворяющих k _i + j _i > 0 для всех i ) таких, что

${\displaystyle \alpha =\omega ^{\gamma _{1}}\cdot k_{1}+\cdots +\omega ^{\gamma _{n}}\cdot k_{n}}$

${\displaystyle \beta =\omega ^{\gamma _{1}}\cdot j_{1}+\cdots +\omega ^{\gamma _{n}}\cdot j_{n}}$

и определить

${\displaystyle \alpha \#\beta =\omega ^{\gamma _{1}}\cdot (k_{1}+j_{1})+\cdots +\omega ^{\gamma _{n}}\cdot (k_{n}+j_{n}).}$

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

${\displaystyle x^{5}+x^{4}+x^{3}+x^{2}+x+1=(x+1)(x^{4}+x^{2}+1)=(x^{2}+x+1)(x^{3}+1)}$

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

Нимбер арифметика [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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