Общий заказ - Total order

Бинарные отношения

	Симметричный	Антисимметричный	Connex	Обоснованный	Присоединяется	Встречается
Отношение эквивалентности	✓	✗	✗	✗	✗	✗
Предварительный заказ (Квазипорядок)	✗	✗	✗	✗	✗	✗
Частичный заказ	✗	✓	✗	✗	✗	✗
Всего предзаказ	✗	✗	✓	✗	✗	✗
Общий заказ	✗	✓	✓	✗	✗	✗
Предварительный заказ	✗	✗	✓	✓	✗	✗
Хорошо-квазиупорядоченный	✗	✗	✗	✓	✗	✗
Хороший порядок	✗	✓	✓	✓	✗	✗
Решетка	✗	✓	✗	✗	✓	✓
Соединение-полурешетка	✗	✓	✗	✗	✓	✗
Встреча-полурешетка	✗	✓	✗	✗	✗	✓

А "✓"указывает, что свойство столбца требуется в определении строки.
Например, определение отношения эквивалентности требует, чтобы оно было симметричным.
Все определения молчаливо требуют транзитивность и рефлексивность.

В математика, а общий заказ, простой заказ,^[1] линейный порядок, заказ Connex,^[2] или же полный порядок^[3] это бинарное отношение на некоторых набор ${displaystyle X}$ , который антисимметричный, переходный, а отношение Connex. Набор в паре с общим заказом называется цепь,^[4] а полностью заказанный набор,^[4] а просто заказанный набор,^[1] а линейно упорядоченный набор,^[2]^[4] или потерять.^[5]^[6]

Формально бинарное отношение ${displaystyle leq}$ это общий заказ по набору ${displaystyle X}$ если следующие утверждения верны для всех ${displaystyle a, b}$ и ${displaystyle c}$ в ${displaystyle X}$ :

Антисимметрия: Если ${displaystyle aleq b}$ и ${displaystyle bleq a}$ тогда ${displaystyle a = b}$ ;
Транзитивность: Если ${displaystyle aleq b}$ и ${displaystyle bleq c}$ тогда ${displaystyle aleq c}$ ;
Связь: ${displaystyle aleq b}$ или же ${displaystyle bleq a}$ .

Антисимметрия исключает неопределенные случаи, когда оба ${displaystyle a}$ предшествует ${displaystyle b}$ и ${displaystyle b}$ предшествует ${displaystyle a}$ .^[7]^:325 Отношение, имеющее Connex свойство означает, что любая пара элементов в наборе отношения сопоставимый по отношению. Это также означает, что набор можно представить в виде линии элементов, дав ему имя линейный.^[7]^:330 В Connex свойство также подразумевает рефлексивность, т.е. а ≤ а. Следовательно, общий порядок также является (частным случаем а) частичный заказ, поскольку для частичного порядка свойство связности заменяется свойством более слабой рефлексивности. Расширение данного частичного порядка до полного порядка называется линейное расширение этого частичного порядка.

Строгий общий порядок

Для каждого (нестрогого) общего порядка ≤ существует связанный асимметричный (следовательно иррефлексивный ) переходный Semiconnex отношение <, называемое строгий общий порядок или же строгий порядок полусложений,^[2] который можно определить двумя эквивалентными способами:

а < б если а ≤ б и а ≠ б
а < б если не б ≤ а (т.е. <- это обратный из дополнять из ≤)

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

Отношение транзитивное: а < б и б < c подразумевает а < c.
Отношение трихотомический: ровно один из а < б, б < а и а = б правда.
Отношение - это строгий слабый порядок, где ассоциированная эквивалентность - равенство.

Мы можем пойти другим путем и начать с выбора <как транзитивного трихотомического бинарного отношения; тогда общий порядок ≤ может быть определен двумя эквивалентными способами:

а ≤ б если а < б или же а = б
а ≤ б если не б < а

Еще два связанных порядка - это дополнения ≥ и>, завершающие четырехместный {<, >, ≤, ≥}.

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

Примеры

Буквы алфавита упорядочены по стандарту порядок словаря, например, $А < B < C$ и Т. Д.
Любой подмножество полностью упорядоченного набора $Икс$ полностью заказан для ограничения заказа на $Икс$ .
Уникальный порядок на пустом множестве, $\emptyset$ , это общий заказ.
Любой набор Количественные числительные или же порядковые номера (более сильно, это хорошие порядки ).
Если $Икс$ любой набор и $ж$ ан инъективная функция из $Икс$ к полностью упорядоченному набору, тогда $ж$ индуцирует тотальный порядок на $Икс$ установив $Икс 1 < Икс 2$ если и только если $ж (Икс 1) < ж (Икс 2)$ .
В лексикографический порядок на Декартово произведение семейства полностью упорядоченных множеств, индексированный по хорошо упорядоченный набор, сам по себе полный порядок.
Набор действительные числа заказывается обычным "меньше чем" (<) или "больше чем" (>) отношений полностью упорядочены, а значит, и подмножества натуральные числа, целые числа, и рациональное число. Можно показать, что каждый из них уникален (до изоморфизм порядка ) самый маленький пример полностью упорядоченного набора с определенным свойством (общий заказ А это самый маленький с определенным свойством, если всякий раз B обладает свойством, существует порядковый изоморфизм из А к подмножеству B):
- Натуральные числа составляют наименьшее непустое полностью упорядоченное множество без верхняя граница.
- Целые числа составляют наименьшее непустое полностью упорядоченное множество, не имеющее ни верхнего, ни нижняя граница.
- Рациональные числа составляют наименьшее полностью упорядоченное множество, которое плотный в реальных числах. Используемое здесь определение плотности говорит, что для каждого $а$ и $б$ в действительных числах такие, что $а < б$ , Существует $q$ в рациональных числах, таких что $а < q < б$ .
- Действительные числа составляют наименьшее неограниченное полностью упорядоченное множество, которое связаны в топология заказа (определено ниже).
Упорядоченные поля полностью упорядочены по определению. Они включают рациональные числа и действительные числа. Каждое упорядоченное поле содержит упорядоченное подполе, изоморфное рациональным числам. Любой Дедекинд-полный упорядоченное поле изоморфно действительным числам.

Цепи

Период, термин цепь является синонимом полностью упорядоченного набора, в частности, этот термин часто используется для обозначения полностью упорядоченного подмножества некоторых частично заказанный набор, например в Лемма Цорна.^[8]
An восходящая цепочка является полностью упорядоченным множеством, имеющим (уникальный) минимальный элемент, а нисходящая цепочка является полностью упорядоченным множеством, имеющим (единственный) максимальный элемент.^{[нужна цитата ]}
Учитывая набор S с частичный заказ ≤, an бесконечная нисходящая цепочка является бесконечный, строго убывающий последовательность элементов Икс₁ > х₂ > ....^[9] Например, в наборе целые числа, то цепь −1, −2, −3, ... - бесконечная убывающая цепочка, но не существует бесконечной убывающей цепи на натуральные числа, поскольку каждая цепочка натуральных чисел имеет минимальный элемент. Если частично упорядоченное множество не имеет бесконечных убывающих цепочек, говорят, что оно удовлетворяет состояние нисходящей цепочки. Если предположить аксиома выбора, условие убывающей цепи на частично упорядоченном множестве эквивалентно требованию, чтобы соответствующий строгий порядок является обоснованный. Более сильное условие, что не будет бесконечных нисходящих цепочек и бесконечных антицепи, определяет хорошие квазиупорядочения. Полностью упорядоченное множество без бесконечных убывающих цепочек называется хорошо организованный.
Смотрите также Состояние восходящей цепи для этого понятия.

В высота чугуна обозначает мощность крупнейшей сети в этом смысле.^{[нужна цитата ]}

Например, рассмотрим набор всех подмножеств целых чисел, частично заказанный к включение. Тогда множество {я_п : п натуральное число}, где я_п это набор натуральных чисел ниже п, является цепочкой в этом порядке, поскольку он полностью упорядочен по включению: Если п≤k, тогда я_п это подмножество я_k.

Дальнейшие концепции

Теория решетки

Можно определить полностью упорядоченное множество как особый вид решетка, а именно тот, в котором мы

{displaystyle {avee b, awedge b} = {a, b}}

для всех а, б.

Затем мы пишем а ≤ б если и только если ${displaystyle a = awedge b}$ . Следовательно, вполне упорядоченное множество - это распределительная решетка.

Конечная сумма заказов

Простой подсчет Аргумент будет проверять, что любое непустое конечное полностью упорядоченное множество (и, следовательно, любое его непустое подмножество) имеет наименьший элемент. Таким образом, каждый конечный полный порядок на самом деле хорошо порядок. Либо прямым доказательством, либо наблюдая, что каждая скважина порядок изоморфный для порядковый можно показать, что каждый конечный полный порядок порядок изоморфный для начальный сегмент натуральных чисел в порядке <. Другими словами, общий порядок набора с k элементов индуцирует биекцию с первым k натуральные числа. Следовательно, обычно индексируют конечные общие заказы или заказы скважин с помощью тип заказа ω натуральными числами, соблюдая порядок (начиная с нуля или с единицы).

Теория категорий

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

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

Топология заказа

Для любого полностью заказанного набора Икс мы можем определить открытые интервалы (а, б) = {Икс : а < Икс и Икс < б}, (−∞, б) = {Икс : Икс < б}, (а, ∞) = {Икс : а < Икс} и (−∞, ∞) = Икс. Мы можем использовать эти открытые интервалы для определения топология на любом упорядоченном наборе топология заказа.

Когда в наборе используется более одного порядка, говорят о топологии порядка, индуцированной определенным порядком. Например, если N натуральные числа, <меньше и> больше, чем мы могли бы сослаться на топологию порядка на N индуцированной <и порядковой топологией на N индуцируется> (в этом случае они идентичны, но в целом не будут).

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

Полнота

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

Есть ряд результатов, связывающих свойства порядковой топологии с полнотой X:

Если топология заказа на Икс подключен, Икс завершено.
Икс связан по порядковой топологии тогда и только тогда, когда он полон и нет зазор в Икс (разрыв составляет два балла а и б в Икс с а < б такой, что нет c удовлетворяет а < c < б.)
Икс является полным тогда и только тогда, когда каждое замкнутое в порядковой топологии ограниченное множество компактно.

Полностью упорядоченный набор (с его топологией порядка), который является полная решетка является компактный. Примеры - замкнутые интервалы действительных чисел, например то единичный интервал [0,1], а аффинно расширенная система действительных чисел (расширенная строка действительных чисел). Есть сохраняющие порядок гомеоморфизмы между этими примерами.

Суммы заказов

Для любых двух непересекающихся общих заказов ${displaystyle (A_ {1}, leq _ {1})}$ и ${displaystyle (A_ {2}, leq _ {2})}$ , есть естественный порядок ${displaystyle leq _ {+}}$ на съемочной площадке ${displaystyle A_ {1} чашка A_ {2}}$ , который называется суммой двух заказов, а иногда и просто ${displaystyle A_ {1} + A_ {2}}$ :

За

{displaystyle x, yin A_ {1} чашка A_ {2}}

,

{displaystyle xleq _ {+} y}

выполняется тогда и только тогда, когда выполняется одно из следующих условий:

${displaystyle x, инь A_ {1}}$ и ${displaystyle xleq _ {1} y}$
${displaystyle x, инь A_ {2}}$ и ${displaystyle xleq _ {2} y}$
${displaystyle xin A_ {1}}$ и ${displaystyle yin A_ {2}}$

Интуитивно это означает, что элементы второго набора добавляются поверх элементов первого набора.

В более общем смысле, если ${displaystyle (I, leq)}$ является полностью упорядоченным индексным набором, и для каждого ${displaystyle iin I}$ структура ${displaystyle (A_ {i}, leq _ {i})}$ - линейный порядок, где множества ${displaystyle A_ {i}}$ попарно не пересекаются, то естественный полный порядок на ${displaystyle igcup _ {i} A_ {i}}$ определяется

За

{displaystyle x, yin igcup _ {iin I} A_ {i}}

,

{displaystyle xleq y}

имеет место, если:

Либо есть какие-то ${displaystyle iin I}$ с ${displaystyle xleq _ {i} y}$
или есть некоторые ${displaystyle i$ в ${displaystyle I}$ с ${displaystyle xin A_ {i}}$ , ${displaystyle yin A_ {j}}$

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

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

Лексикографический порядок: (а,б) ≤ (c,d) если и только если а < c или же (а = c и б ≤ d). Это полный порядок.
(а,б) ≤ (c,d) если и только если а ≤ c и б ≤ d (в заказ продукта ). Это частичный заказ.
(а,б) ≤ (c,d) если и только если (а < c и б < d) или же (а = c и б = d) (рефлексивное замыкание прямой продукт соответствующих строгих суммарных заказов). Это тоже частичный заказ.

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

Применяется к векторное пространство р^п, каждый из них делает его упорядоченное векторное пространство.

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

Связанные структуры

Бинарное отношение, которое является антисимметричным, транзитивным и рефлексивным (но не обязательно полным), является частичный заказ.

А группа с совместимым общим заказом - это полностью упорядоченная группа.

Есть только несколько нетривиальных структур, которые являются (взаимоопределяемыми как) редуктами общего порядка. Забывание ориентации приводит к отношение промежуточности. Забыть расположение концов приводит к циклический порядок. Забывание обоих данных приводит к разделительное отношение.^[10]

Смотрите также

Артинианское кольцо
Теория порядка
В порядке
Проблема суслина
Земляк линия
Порядок префиксов - общий частичный порядок вниз

Примечания

^ ^а ^б Биркгоф 1967, п. 2.
^ ^а ^б ^c Шмидт и Стрёляйн 1993, п. 32.
^ Fuchs 1963 г., п. 2.
^ ^а ^б ^c Дэйви и Пристли 1990, п. 3.
^ Штромайер, Альфред; Гениллар, Кристиан; Вебер, Матс (1 августа 1990 г.). «Порядок символов и строк». ACM SIGAda Письма Ада (7): 84. Дои:10.1145/101120.101136.
^ Ганапати, Джаянти (1992). «Максимальные элементы и верхние границы в позетах». Пи Му Эпсилон Журнал. 9 (7): 462–464. ISSN 0031-952X. JSTOR 24340068.
^ ^а ^б Недерпелт, Роб (2004). Логическое рассуждение: первый курс. Тексты в вычислительной технике. 3 (3-е, пересмотренное изд.). Публикации Королевского колледжа. ISBN 0-9543006-7-X.
^ Пол Р. Халмос (1968). Наивная теория множеств. Принстон: Ностранд. Здесь: Глава 14
^ Яннис Н. Мощовакис (2006) Заметки по теории множеств, Тексты для бакалавриата по математике (Биркхойзер) ISBN 0-387-28723-X, п. 116
^ Макферсон, Х. Дугалд (2011), "Обзор однородных структур", Дискретная математика, 311 (15): 1599–1634, Дои:10.1016 / j.disc.2011.01.024

внешняя ссылка

«Полностью заказанный комплект», Энциклопедия математики, EMS Press, 2001 [1994]

[FOOTNOTEBirkhoff19672-1] а ^б Биркгоф 1967, п. 2.

[FOOTNOTESchmidtStröhlein199332-2] а ^б ^c Шмидт и Стрёляйн 1993, п. 32.

[FOOTNOTEFuchs19632-3] Fuchs 1963 г., п. 2.

[FOOTNOTEDaveyPriestley19903-4] а ^б ^c Дэйви и Пристли 1990, п. 3.

[5] Штромайер, Альфред; Гениллар, Кристиан; Вебер, Матс (1 августа 1990 г.). «Порядок символов и строк». ACM SIGAda Письма Ада (7): 84. Дои:10.1145/101120.101136.

[6] Ганапати, Джаянти (1992). «Максимальные элементы и верхние границы в позетах». Пи Му Эпсилон Журнал. 9 (7): 462–464. ISSN 0031-952X. JSTOR 24340068.

[Nederpelt.2004-7] а ^б Недерпелт, Роб (2004). Логическое рассуждение: первый курс. Тексты в вычислительной технике. 3 (3-е, пересмотренное изд.). Публикации Королевского колледжа. ISBN 0-9543006-7-X.

[8] Пол Р. Халмос (1968). Наивная теория множеств. Принстон: Ностранд. Здесь: Глава 14

[9] Яннис Н. Мощовакис (2006) Заметки по теории множеств, Тексты для бакалавриата по математике (Биркхойзер) ISBN 0-387-28723-X, п. 116

[10] Макферсон, Х. Дугалд (2011), "Обзор однородных структур", Дискретная математика, 311 (15): 1599–1634, Дои:10.1016 / j.disc.2011.01.024

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]