В математической области теории множеств , порядковое арифметика описывает три обычные операции по порядковым номерам : Кроме того , умножения и возведения в степень . Каждый из них может быть определен двумя разными способами: либо путем создания явного хорошо упорядоченного набора , представляющего результат операции, либо путем использования трансфинитной рекурсии . Нормальная форма Кантора обеспечивает стандартизированный способ записи порядковых чисел. В дополнение к этим обычным порядковым операциям, есть также «естественная» арифметика порядковых чисел и операторы прохождения .
Добавление
Объединение двух непересекающихся хорошо упорядоченных множеств S и Т может быть вполне упорядочено. Заказ типа этого союза является порядковым , что результаты добавления по порядку типов S и T . Если два хорошо упорядоченные множества уже не пересекаются, то они могут быть заменены порядка изоморфны непересекающихся множеств, например , заменить S на {0} × S и T {1} × T . Таким образом, упорядоченное множество S записывается «слева» от упорядоченного множества T , что означает, что каждый определяет порядок на S Т , в котором каждый элемент из S меньше , чем каждый элемент Т . Сами наборы 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 + α = α .
Сложение ассоциативно ( α + β ) + γ = α + ( β + γ ).
В правом аргументе сложение строго возрастает и непрерывно:
но аналогичное соотношение не выполняется для левого аргумента; вместо этого у нас есть только:
Порядковое сложение является сокращающимся слева : если α + β = α + γ , то β = γ . Кроме того, можно определить левое вычитание для ординалов β ≤ α : существует единственный γ такой, что α = β + γ . С другой стороны, правильная отмена не работает:
- но
Нет и правого вычитания, даже если β ≤ α : например, не существует такого γ , что γ + 42 = ω.
Если ординалы меньше α замкнуты относительно сложения и содержат 0, то α иногда называют γ-числом (см. Аддитивно неразложимый ординал ). Это в точности ординалы формы ω β .
Умножение
Декартово произведение , S × T , из двух хорошо упорядоченных множеств S и Т может быть вполне упорядочено по варианте лексикографического порядка , что ставит наименее значимые позиции в первую очередь. Фактически, каждый элемент Т заменяется дизъюнктной копией S . Порядок-тип декартово произведение является порядковым , что результаты умножения порядка-типа S и T . Опять же, эта операция ассоциативна и обобщает умножение натуральных чисел.
Вот ω · 2:
- 0 0 <1 0 <2 0 <3 0 <... <0 1 <1 1 <2 1 <3 1 <...,
который имеет тот же тип порядка, что и ω + ω. Напротив, 2 · ω выглядит так:
- 0 0 <1 0 <0 1 <1 1 <0 2 <1 2 <0 3 <1 3 <...
и после переименования это выглядит так же, как ω. Таким образом, ω · 2 = ω + ω ≠ ω = 2 · ω, показывая, что умножение ординалов не коммутативно. В более общем смысле, натуральное число больше 1 никогда не коммутирует с любым бесконечным ординалом, а два бесконечных ординала α , β коммутируют тогда и только тогда, когда α m = β n для некоторых положительных натуральных чисел m и n . Отношение « α коммутирует с β » является отношением эквивалентности на ординалах больше 1, и все классы эквивалентности счетно бесконечны.
Дистрибутивность частично выполняется для порядковой арифметики: α ( β + γ ) = αβ + αγ . Однако, с другой дистрибутивный закон ( β + γ ) α = βα + γα это не в целом верно: (1 + 1) · ω = 2 · ω = ω , а 1 · ω + 1 · ω = ω + ω, которая отличается . Поэтому порядковые номера образуют левый ближней полукольцо , но не образуют кольцо .
Определение умножения также может быть дано индуктивно (следующая индукция по β ):
- α · 0 = 0,
- α · ( β +1) = ( α · β ) + α ,
- и если β - предельный ординал, то α · β - предел α · δ при δ < β .
Основные свойства продукта:
- α · 0 = 0 · α = 0.
- Один (1) является мультипликативным тождеством α · 1 = 1 · α = α .
- Умножение ассоциативно ( α · β ) · γ = α · ( β · γ ).
- Умножение строго возрастает и непрерывно в правом аргументе: ( α < β и γ > 0) γ · α < γ · β
- Умножение не является строго возрастающим в левом аргументе, например, 1 <2, но 1 · ω = 2 · ω = ω. Однако он (нестрого) возрастает, т.е. α ≤ β α · γ ≤ β · γ .
- Существует закон левого сокращения : если α > 0 и α · β = α · γ , то β = γ .
- Правое сокращение не работает, например 1 · ω = 2 · ω = ω, но 1 и 2 разные.
- α · β = 0 α = 0 или β = 0.
- Распределительный закон слева: α · ( β + γ ) = α · β + α · γ
- Нет закона распределения справа: например, (ω + 1) · 2 = ω + 1 + ω + 1 = ω + ω + 1 = ω · 2 + 1, что не является ω · 2 + 2.
- Левое деление с остатком : для всех α и β , если β > 0, то существуют единственные γ и δ такие, что α = β · γ + δ и δ < β . (Это, однако, не означает, что ординалы являются евклидовой областью , поскольку они даже не являются кольцом, а евклидова «норма» имеет порядковые значения.)
- Правое деление не работает: не существует α такого, что α · ω ≤ ω ω ≤ ( α +1) · ω.
Δ-число (см. Мультипликативно неразложимое ) - это порядковый номер больше 1, такой, что αβ = β, если 0 < α < β . Они состоят из ординала 2 и ординалов вида ω ω β .
Возведение в степень
Определение порядкового возведения в степень для конечных показателей несложно. Если показатель степени является конечным числом, степень является результатом повторного умножения. Например, ω 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 ,можно определить с помощью набора функций от n (область) до натуральных чисел (codomain). Эти функции могут быть сокращены как n -элементы натуральных чисел.
Но для бесконечных показателей определение может быть неочевидным. Предельный ординал, такой как ω ω , является супремумом всех меньших ординалов. Может показаться естественным определить ω ω, используя множество всех бесконечных последовательностей натуральных чисел. Однако мы обнаруживаем, что любой абсолютно определенный порядок на этом множестве не является хорошо упорядоченным. [ необходима цитата ] Чтобы решить эту проблему, мы снова можем использовать вариант лексикографического упорядочивания. Мы ограничиваем набор последовательностями, которые не равны нулю только для конечного числа аргументов. Это естественно мотивировано как предел конечных степеней базы (аналогично концепции копроизведения в алгебре). Это также можно рассматривать как бесконечный союз .
Каждая из этих последовательностей соответствует порядковому номеру меньше, чем такой как а также это верхняя грань всех этих меньших ординалов.
Лексикографический порядок в этом наборе - это хороший порядок, который напоминает порядок натуральных чисел, записанных в десятичной системе счисления, за исключением того, что позиции цифр перевернуты, и с произвольными натуральными числами вместо цифр 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 = ω + ω.
Определение возведения в степень можно также дать индуктивно (следующая индукция относится к β , показателю степени):
- α 0 = 1,
- α β +1 = ( α β ) · α , и
- если β - предельный ординал, то α β - предел α δ для всех δ < β .
Свойства порядкового возведения в степень:
- α 0 = 1.
- Если 0 < α , то 0 α = 0.
- 1 α = 1.
- α 1 = α .
- α β · α γ = α β + γ .
- ( α β ) γ = α β · γ .
- Существуют α , β и γ, для которых ( α · β ) γ ≠ α γ · β γ . Например, (ω · 2) 2 = ω · 2 · ω · 2 = ω 2 · 2 ≠ ω 2 · 4.
- Порядковое возведение в степень строго возрастает и непрерывно в правом аргументе: если γ > 1 и α < β , то γ α < γ β .
- Если α < β , то α γ ≤ β γ . Отметим, например, что 2 <3 и все же 2 ω = 3 ω = ω.
- Если α > 1 и α β = α γ , то β = γ . Если α = 1 или α = 0, это не так.
- Для всех α и β , если β > 1 и α > 0, то существуют единственные γ , δ и ρ такие, что α = β γ · δ + ρ такие, что 0 < δ < β и ρ < β γ .
Хотя для порядкового и кардинального возведения в степень используются одни и те же обозначения , порядковое возведение в степень сильно отличается от кардинального возведения в степень. Например, с порядковым возведением в степень, но для ( Алеф ноль , то количество элементов из), . Здесь,- мощность множества всех функций от множества всех натуральных чисел до множества с двумя элементами. (Это мощность набора всех натуральных чисел, равная, мощность континуума .) Чтобы не путать порядковое возведение в степень с кардинальным возведением в степень, можно использовать символы для порядковых чисел (например, ω) в первом и символы для кардинальных чисел (например,) в последнем.
Якобсталь показал, что единственными решениями α β = β α с α ≤ β являются α = β , или α = 2 и β = 4, или α - любой предельный ординал, а β = εα, где ε - ε-число, большее чем α . [1]
Нормальная форма Кантора
Каждое порядковое число α можно однозначно записать как, где k - натуральное число, положительные целые числа, и - порядковые номера. Это разложение альфа называется канторовым нормальной формой из & alpha ; , а также можно считать ω-базовая позиционная система счисления . Наивысший показатель называется степенью , и удовлетворяет . Равенство применяется тогда и только тогда, когда . В этом случае нормальная форма Кантора не выражает порядковый номер через меньшие; это может произойти, как описано ниже.
Незначительный вариант нормальной формы Кантора, с которой обычно немного легче работать, состоит в том, чтобы установить все числа c i равными 1 и позволить равным степеням. Другими словами, каждое порядковое число α можно однозначно записать как, где k - натуральное число, а - порядковые номера.
Другой вариант нормальной формы Кантора - это « расширение по основанию δ », где ω заменяется любым порядковым номером δ > 1, а числа c i являются положительными порядковыми числами меньше δ .
Нормальная форма Кантора позволяет нам однозначно выразить и упорядочить ординалы α , которые построены из натуральных чисел конечным числом арифметических операций сложения, умножения и возведения в степень.: другими словами, предполагая в нормальной форме Кантора можно также выразить показатели в нормальной форме Кантора и сделав то же предположение для что касается α и т. д. рекурсивно, мы получаем систему обозначений для этих ординалов (например,
обозначает порядковый номер).
Ординал ε 0 ( эпсилон ноль ) - это набор порядковых значений α арифметических выражений конечной длины нормальной формы Кантора, которые наследственно нетривиальны, где нетривиальность означает β 1 < α, когда 0 < α . Это наименьший ординал, не имеющий конечного арифметического выражения через ω, и наименьший ординал такой, что, т.е. в нормальной форме Кантора показатель степени не меньше самого порядкового номера. Это предел последовательности
Порядковый ε 0 важен по разным причинам в арифметическом ( в основном потому , что он измеряет доказательства теоретико-силу в первом порядке арифметик Пеано : то есть, аксиомы Пеано могут показать трансфинитную индукцию до любого порядкового меньше ε 0 , но не до ε 0 ).
Нормальная форма Кантора также позволяет нам вычислять суммы и произведения ординалов: например, для вычисления суммы нужно просто знать (см. Свойства, перечисленные в § Сложение и § Умножение ), что
если (если можно применить закон распределения слева и переписать его как , и если выражение уже в нормальной форме Кантора); а для вычисления продуктов важно то, что когда находится в нормальной форме Кантора и , тогда
а также
если n ненулевое натуральное число.
Чтобы сравнить два ординала, записанные в нормальной форме Кантора, сначала сравните , тогда , тогда , тогда и т. д. При первом различии порядковый номер, имеющий больший компонент, является большим порядковым номером. Если они одинаковы до тех пор, пока один не завершится раньше другого, то тот, который завершится первым, будет меньше.
Факторизация в простые числа
Эрнст Якобсталь показал, что ординалы удовлетворяют форме теоремы единственной факторизации: каждый ненулевой ординал может быть записан как произведение конечного числа простых ординалов. Эта факторизация в простые ординалы, как правило, не уникальна, но существует «минимальная» факторизация в простые числа, которая уникальна вплоть до изменения порядка конечных простых множителей ( Sierpiński 1958 ).
Простой порядковый номер - это порядковый номер больше 1, который не может быть записан как произведение двух меньших порядковых чисел. Некоторые из первых простых чисел: 2, 3, 5, ..., ω, ω + 1, ω 2 +1, ω 3 +1, ..., ω ω , ω ω +1, ω ω + 1 +1. , ... Есть три вида простых ординалов:
- Конечные простые числа 2, 3, 5, ...
- Ординалы вида ω ω α для любого ординала α . Это простые порядковые числа, которые являются пределами, и дельта-числа .
- Ординалы вида ω α +1 для любого ординала α > 0. Это бесконечные простые числа-последователи и последователи гамма-чисел , аддитивно неразложимых порядковых чисел .
Факторизация на простые числа не уникальна: например, 2 × 3 = 3 × 2, 2 × ω = ω, (ω + 1) × ω = ω × ω и ω × ω ω = ω ω . Однако существует уникальная факторизация на простые числа, удовлетворяющие следующим дополнительным условиям:
- Каждое предельное простое число встречается перед каждым последующим простым числом
- Если два последовательных простых числа факторизации простых чисел являются предельными или конечными, то второе число является не более чем первым.
Это разложение на простые множители можно легко прочитать с помощью нормальной формы Кантора следующим образом:
- Сначала запишите порядковый номер как произведение αβ, где α - наименьшая степень ω в нормальной форме Кантора, а β - последователь.
- Если α = ω γ, то запись γ в нормальной форме Кантора дает расширение α как произведение предельных простых чисел.
- Теперь посмотрим на нормальную форму Кантора β . Если β = ω λ m + ω μ n + меньшие члены, то β = (ω μ n + меньшие члены) (ω λ - μ + 1) m является произведением меньшего ординала, простого и целого числа m . Повторение этого и разложение целых чисел на простые дает факторизацию β на простые множители .
Итак, факторизация ординала нормальной формы Кантора
- (с участием )
в минимальное произведение бесконечных простых и целых чисел равно
где каждое n i должно быть заменено его факторизацией в невозрастающую последовательность конечных простых чисел и
- с участием .
Большие счетные порядковые числа
Как обсуждалось выше, нормальная форма Кантора порядковых чисел ниже может быть выражено в алфавите, содержащем только функциональные символы для сложения, умножения и возведения в степень, а также постоянные символы для каждого натурального числа и для . Мы можем избавиться от бесконечного числа цифр, используя только постоянный символ 0 и операцию преемника, (например, целое число 4 может быть выражено как ). Это описывает порядковую нотацию : систему именования ординалов в конечном алфавите. Эта конкретная система порядковых обозначений называется набором арифметических порядковых выражений и может выражать все указанные ниже порядковые числа., но не могу выразить . Существуют и другие порядковые обозначения, способные фиксировать порядковые номера, давно прошедшие, но поскольку в любом конечном алфавите существует только счетное количество строк, для любой данной порядковой записи будут порядковые номера ниже ( первый неисчислимый порядковый номер ), которые невозможно выразить. Такие ординалы известны как большие счетные ординалы .
Операции сложения, умножения и возведения в степень являются примерами примитивных рекурсивных порядковых функций , а более общие примитивные рекурсивные порядковые функции могут использоваться для описания более крупных порядковых чисел.
Естественные операции
В естественных сумм и натуральный продукт операции на порядковых были определены в 1906 году Gerhard хессенберговых , а иногда называют сумму Хессенберга (или продукт) ( Серпинский 1958 )
. Они такие же , как сложение и умножение (ограничивается порядковыми) от John Conway «s поля из сюрреалистических чисел . У них есть то преимущество, что они ассоциативны и коммутативны, и натуральный продукт распределяется по натуральной сумме. Цена превращения этих операций в коммутативность состоит в том, что они теряют непрерывность в правильном аргументе, что является свойством обычных суммы и произведения. Натуральная сумма α и β часто обозначается как α ⊕ β или α # β , а натуральный продукт - как α ⊗ β или α ⨳ β .Естественные операции возникают в теории хорошо частичных порядков ; даны два хорошо частичных порядков S и Т , из типов (максимум линеаризаций ) ö ( S ) и O ( T ), тип дизъюнктном союза о ( S ) ⊕ O ( Т ), в то время как тип прямого продукта o ( S ) ⊗ o ( T ). [2] Можно принять это отношение как определение естественных операций, выбрав S и T как ординалы α и β ; так что α ⊕ β - тип максимального порядка полного порядка, расширяющего несвязное объединение (как частичный порядок) α и β ; а α ⊗ β - тип максимального порядка полного порядка, расширяющий прямое произведение (как частичный порядок) α и β . [3] Полезное применение этого - когда α и β оба являются подмножествами некоторого большего общего порядка; то их объединение имеет порядковый тип не выше α ⊕ β . Если они оба являются подмножествами некоторой упорядоченной абелевой группы , то их сумма имеет порядковый тип не выше α ⊗ β .
Мы также можем определить натуральную сумму α и β индуктивно (путем одновременной индукции по α и β ) как наименьший порядковый номер, превышающий натуральную сумму α и γ для всех γ < β и γ и β для всех γ < α . Существует также индуктивное определение натурального продукта (путем взаимной индукции), но записывать его несколько утомительно, и мы не будем этого делать (см. Определение в статье о сюрреалистических числах в этом контексте, где, однако, используется сюрреалистический вычитание, что, очевидно, не может быть определено на ординалах).
Натуральная сумма ассоциативна и коммутативна. Она всегда больше или равна обычной сумме, но может быть строго больше. Например, натуральная сумма ω и 1 равна ω + 1 (обычная сумма), но это также натуральная сумма 1 и ω. Натуральный продукт ассоциативен и коммутативен и распределяется по натуральной сумме. Натуральный продукт всегда больше или равен обычному продукту, но может быть строго больше. Например, натуральное произведение ω и 2 - это ω · 2 (обычный продукт), но это также натуральное произведение 2 и ω.
Еще один способ определить натуральную сумму и произведение двух ординалов α и β - использовать нормальную форму Кантора: можно найти последовательность ординалов γ 1 >…> γ n и две последовательности ( k 1 ,…, k n ) и ( j 1 ,…, j n ) натуральных чисел (включая ноль, но удовлетворяющих k i + j i > 0 для всех i ) таких, что
и определить
При естественном сложении ординалы можно отождествить с элементами свободного коммутативного моноида, порожденного гамма-числами ω α . При естественном сложении и умножении ординалы можно отождествить с элементами свободного коммутативного полукольца, порожденного дельта-числами ω ω α . У порядковых чисел нет уникальной факторизации на простые числа под натуральным продуктом. В то время как полное кольцо многочленов действительно имеет уникальную факторизацию, подмножество многочленов с неотрицательными коэффициентами нет: например, если x - любое дельта-число, то
имеет два несовместимых выражения как натуральное произведение многочленов с неотрицательными коэффициентами, которые не могут быть разложены дальше.
Нимберская арифметика
Существуют арифметические операции с ординалами благодаря взаимно однозначному соответствию между ординалами и нимберами . Три общих операции над нимберами - это сложение ловкости, умножение ловкости и минимальное исключение (мекс) . Сложение Нимбера - это обобщение побитовой операции исключающего ИЛИ над натуральными числами. MEX из набора порядковых является наименьшим порядковым не присутствует в наборе.
Заметки
- ^ Эрнст Якобсталь, Vertauschbarkeit transfiniter Ordnungszahlen, Mathematische Annalen, Bd 64 (1907), 475-488. Доступно здесь
- ^ DHJ De Jongh и R. Parikh, Хорошо-частичные упорядочения и иерархии, Indag. Математика. 39 (1977), 195–206. Доступно здесь
- ^ Филип В. Каррут, Арифметика ординалов с приложениями к теории упорядоченных абелевых групп, Бюлл. Амер. Математика. Soc. 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, 34 , Варшава: Państwowe Wydawnictwo Naukowe, MR 0095787
Внешние ссылки
- ordCalc порядковый калькулятор