Общий заказ

Эта статья включает список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Февраль 2016 ) ( Узнайте, как и когда удалять это сообщение )

В математике полный порядок или линейный порядок — это частичный порядок , в котором любые два элемента сравнимы. То есть полный порядок — это бинарное отношение на некотором множестве , которое удовлетворяет следующим условиям для всех и в :${\displaystyle \leq}$ ${\displaystyle X}$${\displaystyle а,б}$${\displaystyle с}$${\displaystyle X}$

1. ${\displaystyle а\leq а}$( рефлексивный ).
2. Если и то ( транзитив ).${\displaystyle a\leq b}$${\displaystyle b\leq c}$${\displaystyle a\leq c}$
3. Если и то ( антисимметрично ).${\displaystyle a\leq b}$${\displaystyle b\leq a}$${\displaystyle а=б}$
4. ${\displaystyle a\leq b}$или ( сильно связанный , ранее назывался тотальным).${\displaystyle b\leq a}$

Рефлексивность (1.) уже следует из связности (4.), но тем не менее явно требуется многими авторами для указания родства с частичными порядками. ^[1] Полные порядки иногда также называют простыми , ^[2] связными , ^[3] или полными порядками . ^[4]

Множество, снабженное полным порядком, является полностью упорядоченным множеством ; ^[5] также используются термины просто упорядоченное множество , ^[2] линейно упорядоченное множество , ^{[3] [5]} toset ^[6] и loset ^{[7] [8] . Термин} chain иногда определяется как синоним полностью упорядоченного множества , ^[5] но обычно относится к полностью упорядоченному подмножеству данного частично упорядоченного множества.

Расширение данного частичного порядка до полного порядка называется линейным расширением этого частичного порядка.

Строгий полный порядок на множестве — это строгий частичный порядок на , в котором любые два различных элемента сравнимы. То есть, строгий полный порядок — это бинарное отношение на некотором множестве , которое удовлетворяет следующим условиям для всех и в :${\displaystyle X}$${\displaystyle X}$ ${\стиль_отображения <}$ ${\displaystyle X}$${\displaystyle а,б}$${\displaystyle с}$${\displaystyle X}$

1. Нет ( нерефлексивно ).${\displaystyle а<а}$
2. Если нет, то ( асимметрично ).${\displaystyle а<б}$${\displaystyle б<а}$
3. Если и то ( транзитив ).${\displaystyle а<б}$${\displaystyle б<с}$${\displaystyle а<с}$
4. Если , то или ( связано ).${\displaystyle a\neq b}$${\displaystyle а<б}$${\displaystyle б<а}$

Асимметрия следует из транзитивности и нерефлексивности; ^[9] более того, нерефлексивность следует из асимметрии. ^[10]

Для целей разграничения полный порядок, как определено выше, иногда называют нестрогим порядком. Для каждого (нестрогого) полного порядка существует связанное отношение , называемое строгим полным порядком, связанным с которым, которое может быть определено двумя эквивалентными способами:${\displaystyle \leq}$${\стиль_отображения <}$${\displaystyle \leq}$

• ${\displaystyle а<б}$если и ( рефлексивная редукция ).${\displaystyle a\leq b}$${\displaystyle a\neq b}$
• ${\displaystyle а<б}$если нет (т.е. является дополнением обратного к ) .${\displaystyle b\leq a}$${\стиль_отображения <}$${\displaystyle \leq}$

Наоборот, рефлексивное замыкание строгого тотального порядка является (нестрогим) тотальным порядком.${\стиль_отображения <}$

• Любое подмножество полностью упорядоченного множества X полностью упорядочено относительно ограничения порядка на X.
• Уникальный порядок на пустом множестве ∅ является полным порядком.
• Любой набор количественных или порядковых чисел (точнее, это порядки ).
• Если X — любое множество и fинъективная функция из X в полностью упорядоченное множество, то f индуцирует полный порядок на X , устанавливая x ₁ ≤ x ₂ тогда и только тогда, когда f ( x ₁ ) ≤ f ( x ₂ ) .
• Лексикографический порядок декартового произведения семейства полностью упорядоченных множеств, индексированных вполне упорядоченным множеством , сам по себе является полным порядком.
• Множество действительных чисел, упорядоченное обычными отношениями «меньше или равно» (≤) или «больше или равно» (≥), полностью упорядочено. Следовательно, каждое подмножество действительных чисел полностью упорядочено, например, натуральные числа , целые числа и рациональные числа . Можно показать, что каждое из них является уникальным (с точностью до изоморфизма порядка ) «начальным примером» полностью упорядоченного множества с определенным свойством (здесь полный порядок A является начальным для свойства, если всякий раз, когда B обладает этим свойством, существует изоморфизм порядка из A в подмножество B ): ^{[11] [ необходима цитата ]}
  • Натуральные числа образуют исходное непустое полностью упорядоченное множество без верхней границы .
  • Целые числа образуют исходный непустой полностью упорядоченный набор, не имеющий ни верхней, ни нижней границы .
  • Рациональные числа образуют начальный полностью упорядоченный набор, который плотен в действительных числах. Более того, рефлексивная редукция < является плотным порядком на рациональных числах.
  • Действительные числа образуют исходный неограниченный полностью упорядоченный набор, который связан в топологии порядка (определенной ниже).
• Упорядоченные поля полностью упорядочены по определению. Они включают рациональные числа и действительные числа. Каждое упорядоченное поле содержит упорядоченное подполе, которое изоморфно рациональным числам. Любое дедекиндово-полное упорядоченное поле изоморфно действительным числам.
• Буквы алфавита, упорядоченные в стандартном словарном порядке , например, A < B < C и т. д., представляют собой строгий общий порядок.

Термин «цепь» иногда определяется как синоним полностью упорядоченного множества, но обычно он используется для обозначения подмножества частично упорядоченного множества , которое полностью упорядочено для индуцированного порядка. ^{[1] [12]} Обычно частично упорядоченное множество представляет собой множество подмножеств данного множества, которое упорядочено включением, и этот термин используется для указания свойств множества цепей. Такое большое количество вложенных уровней множеств объясняет полезность термина.

Распространенным примером использования цепочки для ссылки на полностью упорядоченные подмножества является лемма Цорна , которая утверждает, что если каждая цепочка в частично упорядоченном множестве X имеет верхнюю границу в X , то X содержит по крайней мере один максимальный элемент. ^[13] Лемма Цорна обычно используется для X , являющегося множеством подмножеств; в этом случае верхняя граница получается путем доказательства того, что объединение элементов цепочки в X принадлежит X. Этот способ обычно используется для доказательства того, что векторное пространство имеет базисы Гамеля , а кольцо имеет максимальные идеалы .

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

Частично упорядоченное множество имеет условие нисходящей цепи , если каждая нисходящая цепь в конечном итоге стабилизируется. ^[15] Например, порядок хорошо обоснован, если он имеет условие нисходящей цепи. Аналогично, условие восходящей цепи означает, что каждая восходящая цепь в конечном итоге стабилизируется. Например, нётерово кольцо — это кольцо, идеалы которого удовлетворяют условию восходящей цепи.

В других контекстах рассматриваются только цепи, которые являются конечными множествами . В этом случае говорят о конечной цепи , часто сокращая до цепи . В этом случае длина цепи — это число неравенств (или включений множеств) между последовательными элементами цепи; то есть число элементов в цепи минус один. ^[16] Таким образом , одноэлементное множество — это цепь длины ноль, а упорядоченная пара — это цепь длины один. Размерность пространства часто определяется или характеризуется как максимальная длина цепей подпространств. Например, размерность векторного пространства — это максимальная длина цепей линейных подпространств , а размерность Крулля коммутативного кольца — это максимальная длина цепей простых идеалов .

«Цепь» может также использоваться для некоторых полностью упорядоченных подмножеств структур , которые не являются частично упорядоченными множествами. Примером служат регулярные цепочки многочленов. Другим примером является использование «цепи» в качестве синонима для прогулки по графу .

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

${\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}}$для всех а , б .

Тогда мы пишем a ≤ b тогда и только тогда, когда . Следовательно, полностью упорядоченное множество является дистрибутивной решеткой .${\displaystyle а=а\клин б}$

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

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

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

Для любого полностью упорядоченного множества X мы можем определить открытые интервалы

• ( а , б ) = { х | а < х и х < б } ,
• (−∞, b ) = { x | x < b } ,
• ( а , ∞) = { х | а < х } , и
• (−∞, ∞) = X .

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

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

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

Полностью упорядоченное множество называется полным, если каждое непустое подмножество, имеющее верхнюю границу , имеет наименьшую верхнюю границу . Например, множество действительных чисел R является полным, а множество рациональных чисел Q — нет. Другими словами, различные концепции полноты (не путать с «полным») не переносятся на ограничения . Например, над действительными числами свойство отношения ≤ состоит в том, что каждое непустое подмножество S из R с верхней границей в R имеет наименьшую верхнюю границу (также называемую супремумом) в R. Однако для рациональных чисел этот супремум не обязательно является рациональным, поэтому то же свойство не выполняется при ограничении отношения ≤ на рациональные числа.

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

• Если топология порядка на X связна, то X является полным.
• X связно в топологии порядка тогда и только тогда, когда оно полно и в X нет разрыва (разрыв — это две точки a и b в X , где a < b, такие, что ни одно c не удовлетворяет a < c < b ).
• X полно тогда и только тогда, когда каждое ограниченное множество, замкнутое в топологии порядка, компактно.

Полностью упорядоченное множество (с его топологией порядка), которое является полной решеткой, является компактным . Примерами являются замкнутые интервалы действительных чисел, например единичный интервал [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,y\in A_{1}\cup A_{2}}$${\displaystyle x\leq _{+}y}$

1. ${\displaystyle x,y\in A_{1}}$и${\displaystyle x\leq _{1}y}$
2. ${\displaystyle x,y\in A_{2}}$и${\displaystyle x\leq _{2}y}$
3. ${\displaystyle x\in A_{1}}$и${\displaystyle y\in A_{2}}$

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

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

Для справедливо , если:${\displaystyle x,y\in \bigcup _{i\in I}A_{i}}$${\displaystyle x\leq y}$

1. Либо есть некоторые с${\displaystyle i\in I}$${\displaystyle x\leq _{i}y}$
2. или есть некоторые в с , ${\displaystyle i<j}$${\displaystyle I}$${\displaystyle x\in A_{i}}$${\displaystyle y\in A_{j}}$

Теория первого порядка полных порядков разрешима , т.е. существует алгоритм для определения того, какие утверждения первого порядка справедливы для всех полных порядков. Используя интерпретируемость в S2S , монадическая теория второго порядка счетных полных порядков также разрешима. ^[17]

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

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

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

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

См. также примеры частично упорядоченных множеств .

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

Транзитивные  бинарные отношения в т е
Симметричный Антисимметричный Подключен Обоснованный Имеет соединения Имеет встречает Рефлексивный Нерефлексивный Асимметричный Всего, Полуконнекc Антирефлексивный ​ Отношение эквивалентности Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Предварительный заказ (квазизаказ) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Частичный заказ ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Всего предзаказов ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Общий заказ ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Предварительный заказ ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Хорошо-квази-упорядочение ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Хорошо упорядоченный ✗ Y Y Y ✗ ✗ Y ✗ ✗ Решетка ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-полурешетка ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Встреча-полурешетка ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Строгий частичный порядок ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Строгий слабый порядок ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Строгий общий порядок ✗ Y Y ✗ ✗ ✗ ✗ Y Y Симметричный Антисимметричный Подключен Обоснованный Имеет соединения Имеет встречает Рефлексивный Нерефлексивный Асимметричный Определения, для всех и${\displaystyle a,b}$${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
Yуказывает, что свойство столбца всегда верно для термина строки (слева), в то время как ✗ указывает, что свойство не гарантируется в общем случае (оно может выполняться, а может и не выполняться). Например, то, что каждое отношение эквивалентности симметрично, но не обязательно антисимметрично, обозначается в столбце «Симметрично» и ✗ в столбце «Антисимметрично» соответственно.Y Все определения неявно требуют, чтобы однородное отношение было транзитивным : для всех, если и то Определение термина может требовать дополнительных свойств, которые не перечислены в этой таблице.${\displaystyle R}$${\displaystyle a,b,c,}$${\displaystyle aRb}$${\displaystyle bRc}$${\displaystyle aRc.}$

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

Группа с совместимым полным порядком является полностью упорядоченной группой .

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

• Биркгофф, Гарретт (1967). Теория решеток . Colloquium Publications. Том 25. Провиденс: Am. Math. Soc.
• Дэви, Брайан А.; Пристли, Хилари Энн (1990). Введение в решетки и порядок . Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN  89009753.
• Фукс, Л. (1963). Частично упорядоченные алгебраические системы . Pergamon Press.
• Джордж Гретцер (1971). Теория решеток: первые концепции и распределительные решетки. WH Freeman and Co. ISBN 0-7167-0442-0 
• Халмош, Пол Р. (1968). Наивная теория множеств . Принстон: Nostrand.
• Джон Г. Хокинг и Гейл С. Янг (1961). Топология. Исправленное переиздание, Дувр, 1988. ISBN 0-486-65676-4 
• Розенштейн, Джозеф Г. (1982). Линейные упорядочения . Нью-Йорк: Academic Press.
• Шмидт, Гюнтер ; Штрёляйн, Томас (1993). Отношения и графы: Дискретная математика для компьютерных ученых. Берлин: Springer-Verlag. ISBN 978-3-642-77970-1.

• «Полностью упорядоченное множество», Энциклопедия математики , EMS Press , 2001 [1994]